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

$H$ の列を左から ${\mathbf{h}}_1,\dots ,{\mathbf{h}}_6$ とおくと（列ベクトルを横に書く）
$${\mathbf{h}}_1=(1,0,0),{\mathbf{h}}_2=(1,1,0),{\mathbf{h}}_3=(0,1,0),{\mathbf{h}}_4=(1,0,1),{\mathbf{h}}_5=(0,1,1),{\mathbf{h}}_6=(0,0,1)$$
である。

次元 $k$. ${\mathbf{h}}_1,{\mathbf{h}}_3,{\mathbf{h}}_6$ は ${\mathbb{F}}_2^3$ の基本ベクトルなので $\mathrm{rank}H=3$。よって $k=n-\mathrm{rank}H=6-3=3$。

最小距離 $d$. $\mathbf{x}=(x_1,\dots ,x_6)$ が符号語であることは $x_1{\mathbf{h}}_1+\cdots +x_6{\mathbf{h}}_6=0$ と同じである。したがって重み $w$ の符号語があることと、和が $0$ になる $w$ 本の列があることは同じである。
- どの列も $0$ でないので、重み $1$ の符号語はない。
- 6 本の列はすべて異なるので、${\mathbb{F}}_2$ 上で ${\mathbf{h}}_i+{\mathbf{h}}_j=0(i\ne j)$ となることはない。よって重み $2$ の符号語はない。つまりどの $2$ 列も一次独立である。
- ${\mathbf{h}}_1+{\mathbf{h}}_2+{\mathbf{h}}_3=(1,0,0)+(1,1,0)+(0,1,0)=(0,0,0)$ なので、一次従属な $3$ 列がある。

よって $d=3$。

$A_3$. 和が $0$ になる $3$ 列の組、すなわち ${\mathbf{h}}_i+{\mathbf{h}}_j$ がほかの列 ${\mathbf{h}}_l$ に等しくなる組 $\{i,j,l\}$ を数える。$15$ 通りの組 $\{i,j\}$ について和を計算すると
- ${\mathbf{h}}_1+{\mathbf{h}}_2={\mathbf{h}}_3,{\mathbf{h}}_1+{\mathbf{h}}_3={\mathbf{h}}_2,{\mathbf{h}}_2+{\mathbf{h}}_3={\mathbf{h}}_1$
- ${\mathbf{h}}_1+{\mathbf{h}}_4={\mathbf{h}}_6,{\mathbf{h}}_1+{\mathbf{h}}_6={\mathbf{h}}_4,{\mathbf{h}}_4+{\mathbf{h}}_6={\mathbf{h}}_1$
- ${\mathbf{h}}_3+{\mathbf{h}}_5={\mathbf{h}}_6,{\mathbf{h}}_3+{\mathbf{h}}_6={\mathbf{h}}_5,{\mathbf{h}}_5+{\mathbf{h}}_6={\mathbf{h}}_3$
- ${\mathbf{h}}_2+{\mathbf{h}}_4={\mathbf{h}}_5,{\mathbf{h}}_2+{\mathbf{h}}_5={\mathbf{h}}_4,{\mathbf{h}}_4+{\mathbf{h}}_5={\mathbf{h}}_2$
- 残りの ${\mathbf{h}}_1+{\mathbf{h}}_5,{\mathbf{h}}_2+{\mathbf{h}}_6,{\mathbf{h}}_3+{\mathbf{h}}_4$ はすべて $(1,1,1)$ で、これはどの列とも一致しない。

したがって和が $0$ になる $3$ 列の組は $\{1,2,3\},\{1,4,6\},\{3,5,6\},\{2,4,5\}$ の $4$ 組である。これらに対応する重み $3$ の符号語は
$$(1,1,1,0,0,0),(1,0,0,1,0,1),(0,0,1,0,1,1),(0,1,0,1,1,0)$$
の $4$ 個である。よって $A_3=4$。

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

$H$ の列は $c_1=(1,0,0{)}^T,c_2=(1,1,0{)}^T,c_3=(0,1,0{)}^T,c_4=(1,0,1{)}^T,c_5=(0,1,1{)}^T,c_6=(0,0,1{)}^T$ である。

1. 次元: $c_1,c_3,c_6$ は一次独立なので $\mathrm{rank}H=3$。よって $k=6-3=3$ で、符号語は $2^3=8$ 個である。

2. 最小距離: $H$ のどの列も $0$ でなく、どの 2 列も相異なる。したがって重み 1, 2 の符号語はなく、$d\ge 3$ である。一方 $c_1+c_3=c_2$ なので、$\{1,2,3\}$ の位置に 1 を持つ重み 3 の符号語が存在する。よって $d=3$。

3. $A_3$: 重み 3 の符号語は、和が $0$ になる 3 列の組に対応する。列の 2 つの和を調べると次のとおり。
- $c_1+c_3=c_2$ より $\{1,2,3\}$
- $c_1+c_4=c_6$ より $\{1,4,6\}$
- $c_2+c_4=c_5$ より $\{2,4,5\}$
- $c_3+c_5=c_6$ より $\{3,5,6\}$

他の組では和が $(1,1,1{)}^T$ になるなどして条件を満たさない。6 列は ${\mathbb{F}}_2^3$ の $(1,1,1{)}^T$ 以外の非零ベクトル 6 個なので、和が 0 になる 3 つ組は、ファノ平面の 7 本の直線のうち $(1,1,1{)}^T$ を通らない 4 本に対応する。この対応でも 4 個で、上の列挙と一致する。よって $A_3=4$。

検算: 残り 3 個の符号語の重みは、重み 3 の語どうしの和をとると 4 になる（例: $111000+100101=011101$ は重み 4）。重み 1, 2 の語はなく、$d=3$ と矛盾しない。

答え: $(k,d,A_d)=(3,3,4)$