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

$H$ の第 $i$ 列を ${\mathbf{c}}_i$ とし、列ベクトルを成分を並べて書くと
$${\mathbf{c}}_1=1000,{\mathbf{c}}_2=0110,{\mathbf{c}}_3=0011,{\mathbf{c}}_4=1101,{\mathbf{c}}_5=0100,{\mathbf{c}}_6=0001,{\mathbf{c}}_7=0010,{\mathbf{c}}_8=1110$$
である。$\mathbf{x}\in {\mathbb{F}}_2^8$ の $1$ である成分の位置の集合を $S$ とすると、$H{\mathbf{x}}^T={\sum }_{i\in S}{\mathbf{c}}_i$ であるから、
$$\mathbf{x}\in C⟺\sum _{i\in S}{\mathbf{c}}_i=0$$
が成り立つ。したがって、重み $w$ の符号語は、和が $0$ になる $w$ 本の列の組と 1 対 1 に対応する。

重み 1, 2 の符号語がないこと. どの列も $0$ ではないので重み $1$ の符号語はない。また、$8$ 本の列はすべて互いに異なるので、${\mathbf{c}}_i+{\mathbf{c}}_j=0(i\ne j)$ となることはなく、重み $2$ の符号語もない。よって $d\ge 3$ である。

重み 3 の符号語の数え上げ. ${\mathbf{c}}_i+{\mathbf{c}}_j+{\mathbf{c}}_k=0$ は ${\mathbf{c}}_i+{\mathbf{c}}_j={\mathbf{c}}_k$ と同じである。$28$ 通りの 2 列の和をすべて計算すると、和がまた $H$ の列になるのは
$$\begin{array}{rl}& {\mathbf{c}}_1+{\mathbf{c}}_2={\mathbf{c}}_8,{\mathbf{c}}_1+{\mathbf{c}}_8={\mathbf{c}}_2,{\mathbf{c}}_2+{\mathbf{c}}_8={\mathbf{c}}_1,\\ & {\mathbf{c}}_2+{\mathbf{c}}_5={\mathbf{c}}_7,{\mathbf{c}}_2+{\mathbf{c}}_7={\mathbf{c}}_5,{\mathbf{c}}_5+{\mathbf{c}}_7={\mathbf{c}}_2,\\ & {\mathbf{c}}_3+{\mathbf{c}}_4={\mathbf{c}}_8,{\mathbf{c}}_3+{\mathbf{c}}_8={\mathbf{c}}_4,{\mathbf{c}}_4+{\mathbf{c}}_8={\mathbf{c}}_3,\\ & {\mathbf{c}}_3+{\mathbf{c}}_6={\mathbf{c}}_7,{\mathbf{c}}_3+{\mathbf{c}}_7={\mathbf{c}}_6,{\mathbf{c}}_6+{\mathbf{c}}_7={\mathbf{c}}_3\end{array}$$
の $12$ 通りだけである（残りの $16$ 通りの和は $1011,0101,1100,1001,1010,0111,1111$ のいずれかで、どれも $H$ の列にない。例えば ${\mathbf{c}}_1+{\mathbf{c}}_3=1011$, ${\mathbf{c}}_4+{\mathbf{c}}_7=1111$ など）。

1 つの 3 列の組 $\{i,j,k\}$ は、そのうちの 2 列の選び方 $3$ 通りで重複して数えられるので、和が $0$ になる 3 列の組は $12÷3=4$ 組で、
$$\{1,2,8\},\{2,5,7\},\{3,4,8\},\{3,6,7\}$$
である。これに対応する重み $3$ の符号語は
$$11000001,01001010,00110001,00100110$$
の $4$ 個である。

重み $3$ の符号語が存在するので $d=3$ であり、$A_3=4$ である。

（参考: $H$ の第 $1,5,7,6$ 列が単位ベクトル $e_1,e_2,e_3,e_4$ なので $\mathrm{rank}H=4$ であり、$C$ は $[8,4,3]$ 符号である。）

よって $(d,A_d)=(3,4)$ である。

$H$ の第 $1,\dots ,8$ 列を $h_1,\dots ,h_8$ とすると、各列を (第1行,第2行,第3行,第4行) の順に並べて $h_1=(1,0,0,0)$, $h_2=(0,1,1,0)$, $h_3=(0,0,1,1)$, $h_4=(1,1,0,1)$, $h_5=(0,1,0,0)$, $h_6=(0,0,0,1)$, $h_7=(0,0,1,0)$, $h_8=(1,1,1,0)$ である。重み $w$ の符号語は、$H$ の相異なる $w$ 個の列の和が $0$ になることと同値である。\n\n・重み 1: 零列がないので存在しない。\n・重み 2: $h_i=h_j$ となる $i\ne j$ がない（8 本の列はすべて相異なる）ので存在しない。\n・重み 3: $h_i+h_j=h_k$ となる組を調べる。\n $h_1+h_2=(1,1,1,0)=h_8$、$h_2+h_5=(0,0,1,0)=h_7$、$h_3+h_4=(1,1,1,0)=h_8$、$h_3+h_6=(0,0,1,0)=h_7$。\n 残りの対 $i,j$ の和は、どの列とも一致しないことを全 28 通りで確かめた（例: $h_1+h_3=(1,0,1,1)$, $h_4+h_7=(1,1,1,1)$, $h_6+h_8=(1,1,1,1)$ など）。\n よって重み 3 の符号語の台は $$\begin{gathered} 1,2,8 \\ , \\ 2,5,7 \\ , \\ 3,4,8 \\ , \\ 3,6,7 \end{gathered}$$ の 4 個である。\n\n以上より $d=3$、$A_3=4$。\n\n検算: 例えば $x=(1,1,0,0,0,0,0,1)$ について $H{x}^T$ は、各行で $x_1+x_4+x_8=1+0+1=0$、$x_2+x_4+x_5+x_8=1+0+0+1=0$、$x_2+x_3+x_7+x_8=1+0+0+1=0$、$x_3+x_4+x_6=0$ となり、確かに符号語である。