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

方針. $C^{\perp }=\{x\in {\mathbb{F}}_2^8\mid G{x}^T=0\}$ なので、$G$ は $C^{\perp }$ の検査行列である。線形符号の最小距離は 0 でない符号語の最小重みに等しく、重み $w$ の符号語 $x$ があることは、$x$ の台（1 の位置）に対応する $G$ の $w$ 本の列の和が $0$ であることと同値である。

列ベクトル. $G$ の第 $i$ 列を $g_i$ とし、上から成分を並べて書くと
$$g_1=1000,g_2=1100,g_3=0010,g_4=0011,g_5=0100,g_6=0001,g_7=0101,g_8=1010.$$
$g_1,g_5,g_3,g_6$ が標準基底なので $\mathrm{rank}G=4$、よって $\dim C=4$、$\dim C^{\perp }=8-4=4$ である。

$d\ge 3$. どの列も $0$ でないので重み 1 の符号語はない。また 8 本の列はすべて異なるので $g_i+g_j\ne 0(i\ne j)$ となり、重み 2 の符号語もない。よって $d\ge 3$。

重み 3 の符号語. $g_i+g_j+g_k=0$、すなわち $g_i+g_j=g_k$ となる 3 列の組を探す。28 通りの対 $\{i,j\}$ の和を調べると、和が再び $G$ の列になるのは
$$g_1+g_2=g_5,g_1+g_3=g_8,g_3+g_4=g_6,g_5+g_6=g_7$$
とそれらの入れかえ（例えば $g_1+g_5=g_2$）だけである（例: $g_1+g_4=1011$, $g_2+g_8=0110$, $g_7+g_8=1111$ などはどの列とも一致しない）。したがって和が $0$ になる 3 列の組は
$$\{1,2,5\},\{1,3,8\},\{3,4,6\},\{5,6,7\}$$
の 4 組で、それぞれ重み 3 の符号語 $11001000,10100001,00110100,00001110$ を与える。よって $d=3$、$A=4$。

検算（直接求める）. $G{x}^T=0$ は
$$x_1+x_2+x_8=0,x_2+x_5+x_7=0,x_3+x_4+x_8=0,x_4+x_6+x_7=0$$
で、$x_5,x_6,x_7,x_8$ を自由に選ぶと
$$x_1=x_5+x_7+x_8,x_2=x_5+x_7,x_3=x_6+x_7+x_8,x_4=x_6+x_7.$$
16 通りを調べると重み分布は、重み 0 が 1 個、重み 3 が 4 個（$(x_5,x_6,x_7,x_8)=1000,0100,0001,1110$）、重み 4 が 5 個、重み 5 が 4 個、重み 6 が 2 個となり、上の結果と一致する。

以上より $(d,A)=(3,4)$。

$C^{\perp }$ は $G$ を検査行列とする符号である。$G$ の階数は 4 なので $\dim C^{\perp }=4$ となる。$C^{\perp }$ の最小距離は、$G$ の列ベクトルのうち、一次従属になる最小の個数に等しい。

$G$ の列を、行の基底 $a,b,c,d$ に対応する ${\mathbb{F}}_2^4$ のベクトルで表す。
$c_1=a,c_2=a+b,c_3=c,c_4=c+d,c_5=b,c_6=d,c_7=b+d,c_8=a+c$。

1. どの列も 0 でない。したがって重み 1 の符号語はない。
2. 8 本の列はすべて異なる。したがって重み 2 の符号語はない。よって $d\ge 3$ である。
3. 和が 0 になる 3 列の組を調べる。2 列の和がちょうど第 3 の列になる組を、すべての 2 列の組について確かめる。見つかったのは次の 4 組である。
- $c_1+c_2=c_5$
- $c_1+c_3=c_8$
- $c_3+c_4=c_6$
- $c_5+c_6=c_7$

他の 2 列の組の和は、どの列にも一致しない。
4. したがって、重み 3 の符号語は台が $\{1,2,5\},\{1,3,8\},\{3,4,6\},\{5,6,7\}$ の 4 個である。

検算として、$x=(1,1,0,0,1,0,0,0)$ は $G{x}^T=(1+1,1+1,0,0)=0$ となり、$C^{\perp }$ に属する。

よって $d=3$、$A=4$ である。