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

符号の構造. $\alpha$ の位数が $15$ なので $x^4+x+1$ は $\alpha$ の最小多項式であり、$g(x)$ は $x^{15}-1$ を割り切る。次数 $14$ 以下の多項式 $c(x)$ について
$$c(x)\in C⟺c(1)=0\text{かつ}c(\alpha )=0$$
である。$c(\alpha )=0$ となる語全体をハミング符号 $\mathcal{H}$（$[15,11,3]$ 符号、パリティ検査行列の列が ${\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{14}$、すなわち ${\mathbb{F}}_{16}$ の $0$ でない元 $15$ 個すべて）とすると、$c(1)=0$ は重みが偶数であることと同値なので、$C$ は $\mathcal{H}$ の偶数重みの語全体である。

$r=c+e$ で $c(1)=c(\alpha )=0$ だから $s_0=e(1)$（$e$ の重みの偶奇）、$s_1=e(\alpha )$ であり、復号器の動作は $e$ だけで決まる。$\mathcal{H}$ の重み $w$ の語の個数を $A_w$ とする。

$A_3,A_4,A_5$ の計算. ${\alpha }^i$ $(0\le i\le 14)$ はすべて異なる。
- $A_3$：異なる $i,j$ を選ぶと ${\alpha }^i+{\alpha }^j={\alpha }^k$ となる $k$ が $i,j$ と異なる値としてただ $1$ つ定まり、$\{i,j,k\}$ が重み $3$ の符号語の台になる。各符号語は $3$ 通りの組 $\{i,j\}$ から数えられるので $A_3=\left(\genfrac{}{}{0ex}{}{15}{2}\right)/3=35$。
- $A_4$：異なる $3$ 個 $i,j,k$ について ${\alpha }^i+{\alpha }^j+{\alpha }^k$ は、$\{i,j,k\}$ が重み $3$ の符号語の台のとき $0$、そうでないとき $i,j,k$ と異なるある ${\alpha }^l$ に等しい。後者の $3$ 個組は $\left(\genfrac{}{}{0ex}{}{15}{3}\right)-35=455-35=420$ 個あり、各重み $4$ の符号語は $4$ 回数えられるので $A_4=420/4=105$。
- $A_5$：重み $4$ の語 $v$（$\left(\genfrac{}{}{0ex}{}{15}{4}\right)=1365$ 個）を分類する。$v(\alpha )=0$ なら $v$ は符号語（$105$ 個）。$v(\alpha )={\alpha }^m$ で $m\in \mathrm{supp}v$ なら $v+x^m$ は重み $3$ の符号語であり、このような $v$ は重み $3$ の符号語に外の $1$ ビットを加えたもので $35\times 12=420$ 個。$m\notin \mathrm{supp}v$ なら $v+x^m$ は重み $5$ の符号語であり、各重み $5$ の符号語から $5$ 個の $v$ が得られる。よって
$$1365=105+420+5A_5\text{より}{A}_5=168.$$

重みごとの復号結果.
- 重み $1$（$e=x^j$）：$s_0=1$、$s_1={\alpha }^j\ne 0$ なので $x^j$ を反転し、正しく訂正される。誤出力 $0$ 個。
- 重み $2$：$s_0=0$、$s_1={\alpha }^i+{\alpha }^j\ne 0$ なので必ず検出される。誤出力 $0$ 個。
- 重み $3$：$s_0=1$。$s_1=0$（$e\in \mathcal{H}$、$35$ 個）なら検出。それ以外は $s_1={\alpha }^m$ で、$m\in \mathrm{supp}e$ とすると残り $2$ 項の和が $0$ になって矛盾するので $m\notin \mathrm{supp}e$。出力は $c+(e+x^m)$ で、$e+x^m$ は重み $4$ の $C$ の符号語だから誤った符号語を出力する。誤出力 $\left(\genfrac{}{}{0ex}{}{15}{3}\right)-35=455-35=420$ 個。
- 重み $4$：$s_0=0$。$s_1=0$ なら $e$ は $0$ でない符号語で、$r$ がそのまま出力され誤る（$A_4=105$ 個）。$s_1\ne 0$ なら検出。誤出力 $105$ 個。
- 重み $5$：$s_0=1$。$s_1=0$（$A_5=168$ 個）なら検出。それ以外は $s_1={\alpha }^m$ で、$e+x^m$ は $s_0=s_1=0$ を満たし重み $4$ または $6$ の $0$ でない $C$ の符号語なので誤出力。誤出力 $\left(\genfrac{}{}{0ex}{}{15}{5}\right)-168=3003-168=2835$ 個。

合計.
$$0+0+420+105+2835=3360.$$

$C$ は $(x+1)$ と $x^4+x+1$ の両方で割り切れる語の集合で、$[15,11]$ ハミング符号の偶数重み部分符号である。$e$ のシンドロームを $s_0=e(1)$、$s_1=e(\alpha )$ とすると、$r=c+e$ より $(s_0,s_1)$ は $e$ だけで決まる。

(1) $s_0=s_1=0$ の場合：$e$ は非零の符号語である。出力は $c+e\ne c$ なので誤りになる。$C$ の語はすべて偶数重みで、最小距離は 4 である。重み 2 の語はなく、重み 4 の語は $[15,11]$ ハミング符号の重み 4 の語数と一致して $105$ 個ある。重み 4 の語数はハミング符号の重み分布（$A_3=35,A_4=105,A_5=168,\dots$）による。この分布は $1+35+105+168+280+435=1024$ を 2 倍して $2^{11}$ になることで確かめた。

(2) $s_0=1$ かつ $s_1\ne 0$ の場合：$e$ の重みは奇数で 1, 3, 5 のいずれかである。出力は $c+e+x^m$ となり、$e=x^m$ のときだけ $c$ に一致する。
- 重み 1 では $e=x^i$、$s_1={\alpha }^i$ なので $m=i$ となり、正しく復号される。
- 重み 3 では、$s_1=0$ となる $e$ はハミング符号の重み 3 の語で $35$ 個である。$s_1\ne 0$ のものは $\left(\genfrac{}{}{0ex}{}{15}{3}\right)-35=455-35=420$ 個で、これらは誤復号になる。
- 重み 5 では、$s_1=0$ となる $e$ はハミング符号の重み 5 の語で $168$ 個である。$s_1\ne 0$ のものは $\left(\genfrac{}{}{0ex}{}{15}{5}\right)-168=3003-168=2835$ 個で、これらは誤復号になる。

(3) $s_0=1,s_1=0$ の場合は誤りを検出して何も出力しないので、数えない。偶数重みで $s_0=0,s_1\ne 0$ の場合も検出になる。

合計は $105+420+2835=3360$。