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

${\mathbb{F}}_2^4$ の基本ベクトルを ${\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3,{\mathbf{e}}_4$、すべての成分が $1$ のベクトルを $\mathbf{j}=(1,1,1,1{)}^{\mathsf{T}}$ とする。重みが奇数のベクトルは、重み $1$ の ${\mathbf{e}}_i$ （$4$ 個）と、重み $3$ の ${\mathbf{f}}_i=\mathbf{j}+{\mathbf{e}}_i$ （${\mathbf{e}}_i$ の $0$ と $1$ を入れかえたもの、$4$ 個）の計 $8$ 個である。列の並べ方を変えても、符号語の座標が同じように並べかわるだけなので、$k,d,A_d$ は並べ方によらない。

次元 $k$　$H$ の列に ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_4$ が含まれるので $\mathrm{rank}H=4$。$C$ は $H$ の核なので、次元定理より
$$k=8-\mathrm{rank}H=8-4=4.$$

最小距離 $d$　線形符号の最小距離は $0$ でない符号語の重みの最小値であり、重み $w$ の符号語があることと、$H$ の $w$ 本の列で和が $0$ になるものがあることは同値である。
- $H$ に零列はないので、重み $1$ の符号語はない。
- $H$ の列はすべて異なるので、$2$ 本の列の和は $0$ にならず、重み $2$ の符号語もない。
- ベクトルの成分の和（重みの偶奇）を $\epsilon (\mathbf{v})\in {\mathbb{F}}_2$ とすると $\epsilon$ は線形である。$H$ の列はどれも $\epsilon =1$ なので、$3$ 本の列の和 $\mathbf{s}$ は $\epsilon (\mathbf{s})=1+1+1=1$ となり $\mathbf{s}\ne 0$。よって重み $3$ の符号語もない。
- 一方 ${\mathbf{e}}_1+{\mathbf{e}}_2+{\mathbf{e}}_3+{\mathbf{f}}_4={\mathbf{e}}_1+{\mathbf{e}}_2+{\mathbf{e}}_3+({\mathbf{e}}_1+{\mathbf{e}}_2+{\mathbf{e}}_3)=0$ なので重み $4$ の符号語がある。

したがって $d=4$。

$A_4$ の計算　和が $0$ になる $4$ 本の列の選び方を数える。${\mathbf{e}}_i$ を $i\in S$ について、${\mathbf{f}}_i$ を $i\in T$ について選ぶとし（$S,T\subset \{1,2,3,4\}$, $|S|+|T|=4$）、$|S|=a$ とおく。${\mathbf{e}}_A={\sum }_{i\in A}{\mathbf{e}}_i$ と書くと、和は
$${\mathbf{e}}_S+\sum _{i\in T}(\mathbf{j}+{\mathbf{e}}_i)=(4-a)\mathbf{j}+{\mathbf{e}}_S+{\mathbf{e}}_T=(4-a)\mathbf{j}+{\mathbf{e}}_{S△T}$$
である（$S△T$ は対称差）。
- $a$ が偶数のとき：和は ${\mathbf{e}}_{S△T}$ で、これが $0$ となるのは $S=T$ のとき。$|S|=|T|$ から $a=2$ で、$S$ の選び方は $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 通り。（$a=0,4$ は $S\ne T$ なので不適。）
- $a$ が奇数のとき：和は $\mathbf{j}+{\mathbf{e}}_{S△T}$ で、これが $0$ となるのは $S△T=\{1,2,3,4\}$、すなわち $S$ と $T$ が互いに補集合のとき。$a=1$ なら $S$ の選び方 $4$ 通り、$a=3$ なら $4$ 通り。

よって $A_4=6+4+4=14$。

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

（参考：この $C$ は拡大ハミング符号 $[8,4,4]$ と同値な符号で、重み分布は $1+14x^4+x^8$ である。）

$H$ の列は、${\mathbb{F}}_2^4$ の奇数重みのベクトル 8 個を 1 回ずつ並べたものである。列の順序を入れ替えても、符号語の成分が同じ置換で入れ替わるだけなので、$k,d,A_d$ は順序によらない。

次元 $k$: 列に単位ベクトル $e_1,e_2,e_3,e_4$（重み 1）が含まれるので $\mathrm{rank}H=4$。よって $k=8-4=4$。

最小距離 $d$: 線形符号の最小距離は、$H$ の線形従属な列の最小個数に等しい。
- 1 列: どの列も零ベクトルでない。
- 2 列: 列はすべて異なるので、2 列の和は $0$ にならない。
- 3 列: 奇数重みのベクトル 3 個の和は、重みの偶奇が（奇+奇+奇）で奇数になる（$\mathrm{wt}(u+v)\equiv \mathrm{wt}(u)+\mathrm{wt}(v)(\mathrm{mod}2)$）ので $0$ にならない。
- 4 列: 例えば $1000+0100+0010+1110=0000$ となる 4 列が存在する。

よって $d=4$。

$A_4$: 和が $0$ になる 4 列の組（重み 4 の符号語と 1 対 1 に対応）を数える。相異なる 3 列 $a,b,c$ を選ぶと $d=a+b+c$ は奇数重みで、$d=a$ なら $b=c$ となって矛盾するので $d$ は $a,b,c$ のいずれとも異なる。したがって、相異なる順序つき 3 列 $8\cdot 7\cdot 6=336$ 通りのそれぞれから、和が $0$ になる 4 列の組がちょうど 1 つ決まる。1 つの 4 列の組は、そこから 3 列を順序つきで選ぶ $4\cdot 3\cdot 2=24$ 通りから得られるので、組の個数は $336/24=14$。

検算: この符号は拡大ハミング符号 $[8,4,4]$ と同値で、重み分布は $1+14x^4+x^8$。合計 $1+14+1=16=2^4$ で $k=4$ と整合する。

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