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

手順 1：次元 $k$ を求める。
$H$ の第 $4,5,6$ 列は単位行列 $I_3$ をなすので、$H$ の 3 つの行は一次独立で $\mathrm{rank}H=3$ である。よって
$$k=n-\mathrm{rank}H=6-3=3.$$

手順 2：$H$ の列を調べて最小距離 $d$ を求める。
$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}1\\ 0\\ 1\end{array}\right),{\mathbf{h}}_3=\left(\begin{array}{c}0\\ 1\\ 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).$$
$\mathbf{x}\in C$ であることは、$\mathbf{x}$ の $1$ である位置の列の和が $0$ になることと同じである。
- どの列も $0$ でないので、重み $1$ の符号語はない（どの 1 列も一次独立）。
- 6 つの列はすべて異なるので、${\mathbf{h}}_i+{\mathbf{h}}_j=0(i\ne j)$ となることはなく、重み $2$ の符号語もない（どの 2 列も一次独立）。
- 一方 ${\mathbf{h}}_1+{\mathbf{h}}_4+{\mathbf{h}}_5=0$ のように和が $0$ になる 3 列がある（一次従属な 3 列がある）。

よって $d=3$ である。

手順 3：$A_3$ を数える。
和が $0$ になる 3 列の組を探す。${\mathbb{F}}_2$ 上では ${\mathbf{h}}_a+{\mathbf{h}}_b+{\mathbf{h}}_c=0$ は ${\mathbf{h}}_c={\mathbf{h}}_a+{\mathbf{h}}_b$ と同じなので、2 列を選んで和が残りの列に現れるかを調べればよい。$H$ の列には $(1,1,1{)}^{\mathsf{T}}$ が現れないことに注意して調べると、
$${\mathbf{h}}_1+{\mathbf{h}}_4+{\mathbf{h}}_5=0,{\mathbf{h}}_2+{\mathbf{h}}_4+{\mathbf{h}}_6=0,{\mathbf{h}}_3+{\mathbf{h}}_5+{\mathbf{h}}_6=0,{\mathbf{h}}_1+{\mathbf{h}}_2+{\mathbf{h}}_3=0$$
の 4 組である（たとえば ${\mathbf{h}}_4+{\mathbf{h}}_3=(1,1,1{)}^{\mathsf{T}}$ のように和が $(1,1,1{)}^{\mathsf{T}}$ になる組は列の中に相手がない）。対応する符号語は
$$100110,010101,001011,111000$$
で、$A_3=4$ である。

（確認：$C$ の $8$ 個の符号語は上の 4 つと $000000,110011,101101,011110$ で、0 でない符号語の重みは $3,3,3,3,4,4,4$ となり、$d=3,A_3=4$ と一致する。）

したがって $(k,d,A_d)=(3,3,4)$。

$H$ の第 4〜6 列は単位行列なので $\mathrm{rank}H=3$ である。よって $k=6-3=3$ で、符号語は $2^3=8$ 個ある。

$H$ の列を $h_1=(1,1,0{)}^{\mathsf{T}}$, $h_2=(1,0,1{)}^{\mathsf{T}}$, $h_3=(0,1,1{)}^{\mathsf{T}}$, $h_4=(1,0,0{)}^{\mathsf{T}}$, $h_5=(0,1,0{)}^{\mathsf{T}}$, $h_6=(0,0,1{)}^{\mathsf{T}}$ とおく。重み $w$ の符号語は、和が $0$ になる $w$ 個の列の選び方と一対一に対応する。

• 零列はなく、6 つの列は互いに異なる。したがって重み 1, 2 の符号語はなく、$d\ge 3$ である。
• 重み 3 の符号語は、$h_a+h_b+h_c=0$ となる 3 列の組に対応する。調べると次の 4 組がある。
• $h_1+h_2+h_3=0$
• $h_1+h_4+h_5=0$
• $h_2+h_4+h_6=0$
• $h_3+h_5+h_6=0$
• 列は ${\mathbb{F}}_2^3$ の非零ベクトル 7 個のうち $(1,1,1{)}^{\mathsf{T}}$ を除く 6 個である。和が 0 になる 3 列の組はファノ平面の直線（7 本）に対応する。そのうち $(1,1,1{)}^{\mathsf{T}}$ を通る 3 本は、この列を含むので使えない。よって $7-3=4$ 組で、上の数え上げと一致する。

ゆえに $d=3$、$A_3=4$ である。

検算として、符号語は $x_4,x_5,x_6$ が $x_1,x_2,x_3$ から決まるので 8 個である。生成行列の行は、$x_1=1$ の語 $(1,0,0,1,1,0)$、$x_2=1$ の語 $(0,1,0,1,0,1)$、$x_3=1$ の語 $(0,0,1,0,1,1)$ で、重みはすべて 3 である。残りは次のとおり。
- $x_1=x_2=1$ の語は $(1,1,0,0,1,1)$ で重み 4。
- $x_1=x_3=1$ の語は $(1,0,1,1,0,1)$ で重み 4。
- $x_2=x_3=1$ の語は $(0,1,1,1,1,0)$ で重み 4。
- $x_1=x_2=x_3=1$ の語は $(1,1,1,0,0,0)$ で重み 3。

重み 3 の語は 4 個で、重み 4 の語が 3 個、零語が 1 個であり、合計 8 個になる。

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