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

手順 1：検査行列を求める。
$G=(I_3\mid P)$ において
$$P=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& 1\end{array}\right),P^{\mathsf{T}}=\left(\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& 1\end{array}\right)$$
です。${\mathbb{F}}_2$ では $-1=1$ なので $-P^{\mathsf{T}}=P^{\mathsf{T}}$ となり、
$$H=(P^{\mathsf{T}}\mid I_3)=\left(\begin{array}{cccccc}1& 0& 1& 1& 0& 0\\ 1& 1& 0& 0& 1& 0\\ 0& 1& 1& 0& 0& 1\end{array}\right)$$
です。（確認：$G{H}^{\mathsf{T}}=P+P=O$ となります。）

手順 2：$H$ の列を調べる。
$H$ の列を左から ${\mathbf{h}}_1,\dots ,{\mathbf{h}}_6$ とすると
$${\mathbf{h}}_1=\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right),{\mathbf{h}}_2=\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right),{\mathbf{h}}_3=\left(\begin{array}{c}1\\ 0\\ 1\end{array}\right),{\mathbf{h}}_4=\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right),{\mathbf{h}}_5=\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right),{\mathbf{h}}_6=\left(\begin{array}{c}0\\ 0\\ 1\end{array}\right)$$
です。
- どの列も $0$ でないので、1 列だけで一次従属になることはありません。
- 6 本の列はすべて異なるので、${\mathbb{F}}_2$ 上で ${\mathbf{h}}_i+{\mathbf{h}}_j=0$（$i\ne j$）となることはありません。よって、どの 2 列も一次独立です。
- 一方、${\mathbf{h}}_1+{\mathbf{h}}_4+{\mathbf{h}}_5=0$ のように一次従属な 3 列があります。

したがって、どの $2$ 列も一次独立で一次従属な $3$ 列があるので、$d=3$ です。

手順 3：$A_3$ を求める。
重み 3 の符号語は、和が $0$ になる 3 列の組と 1 対 1 に対応します。${\mathbb{F}}_2$ 上で 3 列が一次従属であることは、その 3 列の和が $0$ であること、つまりある列が残り 2 列の和に等しいことと同じです。
- ${\mathbf{h}}_1={\mathbf{h}}_4+{\mathbf{h}}_5$ より $\{1,4,5\}$
- ${\mathbf{h}}_2={\mathbf{h}}_5+{\mathbf{h}}_6$ より $\{2,5,6\}$
- ${\mathbf{h}}_3={\mathbf{h}}_4+{\mathbf{h}}_6$ より $\{3,4,6\}$
- ${\mathbf{h}}_1+{\mathbf{h}}_2+{\mathbf{h}}_3=0$ より $\{1,2,3\}$

漏れがないことは次のように確かめられます。和が $0$ になる 3 列のうち 2 列を選ぶと、残りの 1 列はその 2 列の和として決まります。2 列の選び方 ${}_6{\mathrm{C}}_2=15$ 通りのうち、和が $\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)$（$H$ の列にない）になるのは $\{{\mathbf{h}}_1,{\mathbf{h}}_6\},\{{\mathbf{h}}_2,{\mathbf{h}}_4\},\{{\mathbf{h}}_3,{\mathbf{h}}_5\}$ の 3 通りです。残りの 12 通りでは和が $H$ の列になり、1 つの 3 列の組がその中の 2 列の選び方 3 通りずつで数えられるので、$12÷3=4$ 組です。

よって $A_3=4$ です。

（検算：符号語は $100110,010011,001101,110101,101011,011110,111000$ と $0$ で、重み 3 のものは $100110,010011,001101,111000$ の 4 個です。これは上の 4 組 $\{1,4,5\},\{2,5,6\},\{3,4,6\},\{1,2,3\}$ に対応しています。）

答え：$(d,A_d)=(3,4)$

${\mathbb{F}}_2$ 上なので $-P^{\mathsf{T}}=P^{\mathsf{T}}$ である。$P=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& 1\end{array}\right)$ より $P^{\mathsf{T}}=\left(\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& 1\end{array}\right)$。よって
$$H=\left(\begin{array}{cccccc}1& 0& 1& 1& 0& 0\\ 1& 1& 0& 0& 1& 0\\ 0& 1& 1& 0& 0& 1\end{array}\right)$$
列は $h_1=(1,1,0{)}^T,h_2=(0,1,1{)}^T,h_3=(1,0,1{)}^T,h_4=(1,0,0{)}^T,h_5=(0,1,0{)}^T,h_6=(0,0,1{)}^T$ である。

最小距離 $d$ は、H の一次従属な列の最小個数に等しい。
- どの列も零ベクトルでないので、1 個の列は一次従属にならない。
- 6 個の列はすべて異なるので、2 個の列も一次従属にならない。したがって $d\ge 3$。
- $h_1+h_2+h_3=(1+0+1,1+1+0,0+1+1)=(0,0,0)$ なので、3 個の列が一次従属になる。したがって $d=3$。

重み 3 の符号語の個数 $A_3$ は、和が 0 になる 3 列の組の個数に等しい。そこで全符号語を列挙する。メッセージ $(a,b,c)$ に対する符号語は $(a,b,c,a+c,a+b,b+c)$ である。
- 100 → 100110 (重み3)
- 010 → 010011 (重み3)
- 001 → 001101 (重み3)
- 110 → 110101 (重み4)
- 101 → 101011 (重み4)
- 011 → 011110 (重み4)
- 111 → 111000 (重み3)

重み 3 の符号語は 4 個ある。検算として、和が 0 になる 3 列の組は {1,2,3}, {1,4,5}, {2,5,6}, {3,4,6} の 4 組で、これも 4 個で一致する。

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