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

検出されない誤りの言い換え

$C$ は線形符号なので、$r=c+e\in C$ と $e\in C$ は同値である。よって、検出されない誤りパターンは、$0$ でない符号語そのものである。求める個数は、重み $1,2,3,4$ の符号語の個数 $A_1,A_2,A_3,A_4$ の和である。

符号語の特徴づけ

$g(x)$ は既約で $\alpha$ を根にもつので、$g(x)$ は $\alpha$ の最小多項式である。したがって $\mathrm{deg}c(x)\le 14$ の多項式 $c(x)$ について
$$g(x)\mid c(x)⟺c(\alpha )=0$$
が成り立つ。重み $w$ の語 $c$ の $1$ の位置を $i_1,\dots ,i_w$ とすると $c(\alpha )={\alpha }^{i_1}+\cdots +{\alpha }^{i_w}$ である。${\alpha }^0,\dots ,{\alpha }^{14}$ は ${\mathbb{F}}_{16}^{\times }$（${\mathbb{F}}_{16}$ の $0$ でない $15$ 個の元）をちょうど $1$ 回ずつ動くから、

> 重み $w$ の符号語 $⟷$ 和が $0$ になる ${\mathbb{F}}_{16}^{\times }$ の $w$ 元部分集合

という $1$ 対 $1$ 対応がある。以下、${\mathbb{F}}_{16}$ の加法では $a+a=0$ であることを使う。

$A_1,A_2$

$0$ でない元 $a$ について $a\ne 0$ なので $A_1=0$。異なる $a,b$ について $a+b=0$ なら $a=b$ となり矛盾するので $A_2=0$。（最小距離が $3$ 以上で、$1$ 個・$2$ 個の誤りは必ず検出できる。）

$A_3$

異なる $a,b\in {\mathbb{F}}_{16}^{\times }$ に対し $c=a+b$ とおくと、$c\ne 0$ であり、$c=a$ なら $b=0$、$c=b$ なら $a=0$ となるので $c\ne a,b$。よって $a+b+c=0$ となる $c$ は $\{a,b\}$ から一意に決まり、$\{a,b,c\}$ は $3$ 元部分集合になる。$2$ 元部分集合 $\{a,b\}$ は $\left(\genfrac{}{}{0ex}{}{15}{2}\right)=105$ 個あり、和が $0$ の $3$ 元部分集合 $\{a,b,c\}$ はその中の $2$ 元部分集合 $3$ 個から重複して数えられるので
$$A_3=\frac{105}{3}=35.$$

$A_4$

異なる $4$ 元 $a,b,c,d$ で $a+b+c+d=0$ となるのは $a+b=c+d$ のときである。

まず $0$ でない $s\in {\mathbb{F}}_{16}$ を固定し、$x+y=s$ となる ${\mathbb{F}}_{16}^{\times }$ の $2$ 元部分集合 $\{x,y\}$ を数える。$x$ は $0,s$ 以外の $14$ 通りで、$y=x+s$ は $0$ でも $x$ でもない。$(x,y)$ と $(y,x)$ が同じ組を与えるので、$\{x,y\}$ は $14/2=7$ 個ある。これらの $7$ 個の組は互いに共通の元をもたない（$x$ を決めると相手 $y=x+s$ が決まるため）。

$\{a,b\}\ne \{c,d\}$ をこの $7$ 個から選ぶと $\{a,b,c,d\}$ は和が $0$ の $4$ 元部分集合になり、その選び方は $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$ 通り。$s$ は $15$ 通りなので、のべ $15\times 21=315$ 個。

逆に、和が $0$ の $4$ 元部分集合 $\{a,b,c,d\}$ を $2$ 元ずつに分ける方法は
$$\{a,b\}\cup \{c,d\},\{a,c\}\cup \{b,d\},\{a,d\}\cup \{b,c\}$$
の $3$ 通りで、どの分け方でも $s=a+b$ などは $0$ でない（元が異なるため）。よって各部分集合は $3$ 回ずつ数えられており
$$A_4=\frac{315}{3}=105.$$

結論

検出されない誤りパターンの個数は
$$A_1+A_2+A_3+A_4=0+0+35+105=140.$$

$g(x)=x^4+x+1$ の倍数全体である $C$ は、検査行列の列が ${\mathbb{F}}_{16}^{\times }$ の元 $1,\alpha ,\dots ,{\alpha }^{14}$ である符号、すなわち $c\in C⟺{\sum }_i{c}_i{\alpha }^i=0$ と同値である（$g$ は $\alpha$ の最小多項式なので、$c(x)$ が $g$ で割り切れることと $c(\alpha )=0$ は同値）。これは $[15,11]$ ハミング符号である。\n\n誤りパターン $e\ne 0$ が検出されない $⟺r=c+e\in C⟺e\in C$。よって求める個数は、重み $1$ 以上 $4$ 以下の非零符号語の個数 $A_1+A_2+A_3+A_4$ である。\n\n$e$ の台を $S$ とすると $e\in C⟺{\sum }_{i\in S}{\alpha }^i=0$。\n\n- 重み $1$: ${\alpha }^i\ne 0$ なので $A_1=0$。\n- 重み $2$: ${\alpha }^i+{\alpha }^j=0$ は ${\alpha }^i={\alpha }^j$ を意味し、元がすべて異なるので不可。$A_2=0$。\n- 重み $3$: 相異なる $i,j$ に対し ${\alpha }^i+{\alpha }^j\ne 0$ であり、これは ${\mathbb{F}}_{16}^{\times }$ の元 ${\alpha }^k$ に等しい。$k\ne i,j$ である（${\alpha }^k={\alpha }^i$ なら ${\alpha }^j=0$ となり矛盾）。したがって順序なしの対 $\{i,j\}$ ごとに第 3 の点 $k$ がただ 1 つ定まり、$\{i,j,k\}$ は和が $0$ の 3 点集合である。対は $\left(\genfrac{}{}{0ex}{}{15}{2}\right)=105$ 個で、各 3 点集合は 3 つの対から得られるので $A_3=105/3=35$。\n- 重み $4$: 相異なる $i,j,k,l$ で ${\alpha }^i+{\alpha }^j+{\alpha }^k+{\alpha }^l=0$ となる集合を数える。相異なる 3 点の組 $\{i,j,k\}$ は $\left(\genfrac{}{}{0ex}{}{15}{3}\right)=455$ 個あり、${\alpha }^l={\alpha }^i+{\alpha }^j+{\alpha }^k$ とおく。この ${\alpha }^l$ が $0$ になるのは $\{i,j,k\}$ が和 $0$ の 3 点集合のとき（$35$ 個）。また ${\alpha }^l={\alpha }^i$ なら ${\alpha }^j+{\alpha }^k=0$ となり不可能なので、$l$ は $i,j,k$ と異なる。よって和が $0$ でない 3 点集合 $455-35=420$ 個のそれぞれにつき、ちょうど 1 つの $l$ が定まる。各 4 点集合は 4 つの 3 点部分集合から得られるので $A_4=420/4=105$。\n\n検算: ハミング符号 $[15,11]$ の重み分布は $A_0=1,A_3=35,A_4=105,A_5=168,A_6=280,A_7=435,A_8=435,A_9=280,A_{10}=168,A_{11}=105,A_{12}=35,A_{15}=1$ で、総和は $2048=2^{11}$ となり一致する。\n\nよって求める個数は $0+0+35+105=140$。