情報理論・符号理論の問題

$C$ の大きさと最小距離　$g(x)$ は次数 $3$ なので、$C$ の次元は $k=7-3=4$ で、符号語は $2^4=16$ 個ある。

符号語 $c(x)$ は $g(x)$ で割り切れることと同値なので、$\alpha$ を $g(\alpha )=0$ をみたす元（${\mathbb{F}}_2[x]/(g(x))$ における $x$）とすると、$c(x)\in C⟺c(\alpha )=0$。${\alpha }^i$（$0\le i\le 6$）を $x^i\mathrm{mod}g(x)$ として計算すると（$x^3\equiv x+1$ を使う）
$$\begin{array}{rl}& x^0\equiv 1,x^1\equiv x,x^2\equiv x^2,x^3\equiv x+1,\\ & x^4\equiv x^2+x,x^5\equiv x^2+x+1,x^6\equiv x^2+1\end{array}$$
となり、$7$ 個はすべて $0$ でなく互いに異なる。これらを列とする $3\times 7$ 行列が $C$ の検査行列になるので、$C$ には重み $1$ の符号語（$x^i\equiv 0$ が必要）も重み $2$ の符号語（$x^i\equiv x^j$, $i\ne j$ が必要）もない。一方 $g(x)$ 自身が重み $3$ の符号語である。よって最小距離は $d=3$ で、$C$ は $[7,4,3]$ ハミング符号である。

完全符号であること　$d=3$ より、各符号語を中心とする半径 $1$ のハミング球（中心とそこから $1$ ビットだけ違う語、$1+7=8$ 個）は互いに交わらない。その合計は
$$16\times 8=128=2^7$$
で ${\mathbb{F}}_2^7$ 全体と一致する。したがって、どの受信語もただ $1$ つの符号語から距離 $1$ 以下にあり、ハミング距離が最小となる符号語はつねにただ $1$ つに決まる。

正しく復号される条件　送信語を $\mathbf{c}$、誤りの個数を $t$ とする。
- $t\le 1$ のとき、受信語は $\mathbf{c}$ の半径 $1$ の球に入るので $\mathbf{c}$ に復号される。
- $t\ge 2$ のとき、受信語は $\mathbf{c}$ の球に入らないが、完全符号なので別の符号語の半径 $1$ の球に入り、その符号語に誤って復号される。

よって求める確率は、$7$ ビット中の誤りが $0$ 個または $1$ 個である確率で、
$$(1-p{)}^7+7p(1-p{)}^6=(1-p{)}^6(1+6p).$$
$p=\frac{1}{10}$ を代入すると
$${\left(\frac{9}{10}\right)}^6\cdot \frac{16}{10}=\frac{531441}{1000000}\cdot \frac{8}{5}=\frac{531441\cdot 8}{5000000}=\frac{531441}{625000}.$$
（小数では $0.8503056$。）

$g(x)=x^3+x+1$ は ${\mathbb{F}}_2$ 上の既約多項式で、$x^7-1=(x+1)(x^3+x+1)(x^3+x^2+1)$ の因数である。したがって $C$ は符号長 $7$、次元 $7-3=4$ の巡回符号で、$(7,4)$ ハミング符号と（巡回同値な形で）一致し、最小距離は $3$ である。

実際、$g$ の根 $\alpha$ は ${\mathbb{F}}_8^{\times }$ の位数 $7$ の元で、検査行列の列は $1,\alpha ,\dots ,{\alpha }^6$（${\mathbb{F}}_8$ の相異なる非零元すべて）となる。よって $C$ は完全符号であり、符号語を中心とする半径 $1$ のハミング球 $2^4\cdot (1+7)=128=2^7$ が全空間を過不足なく敷き詰める。

最近傍復号（最小ハミング距離復号）では、誤りビット数が $0$ または $1$ のときだけ正しく復号され、$2$ 個以上では（完全符号なので別の符号語の半径 1 の球に入り）必ず誤復号される。球が全空間を敷き詰めるので距離が同順位になる場合（復号の曖昧さ）も生じない。

成功確率は
$$(1-p{)}^7+7p(1-p{)}^6=(1-p{)}^6(1+6p)={\left(\frac{9}{10}\right)}^6\cdot \frac{16}{10}=\frac{531441}{10^6}\cdot \frac{8}{5}=\frac{531441}{625000}.$$

検算: $0.9^6=0.531441$、$0.531441\times 1.6=0.8503056$。$531441/625000=0.8503056$ で一致する。また、$7$ ビットの誤りパターンは $2^7=128$ 通りの綜合ベクトル（シンドローム $8$ 通り $\times$ 符号語 $16$）に対応し、訂正可能な誤りパターンは重み $0$ の 1 個と重み $1$ の 7 個の計 8 個であることとも整合する。