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

$m\ge 3$ を整数とし、$n=2^m-1$ とおく。$p(x)\in {\mathbb{F}}_2[x]$ を次数 $m$ の原始多項式とする。すなわち $p(x)$ は ${\mathbb{F}}_2$ 上既約であり、有限体 ${\mathbb{F}}_{2^m}$ における $p(x)$ の根 $\alpha$ の乗法的位数はちょうど $n$ である。

$g(x)=(x+1)p(x)$ とし、
$$C=\{c(x)\in {\mathbb{F}}_2[x]\mid c(x)=0\text{ または }\mathrm{deg}c(x)<n,\text{かつ }g(x)\mid c(x)\}$$
とおく。$c(x)=c_0+c_{1}x+\cdots +c_{n-1}{x}^{n-1}$ を語 $(c_0,c_1,\dots ,c_{n-1})\in {\mathbb{F}}_2^n$ と同一視し、語の重みを $0$ でない成分の個数、$C$ の最小距離 $d$ を $C$ の $0$ でない語の重みの最小値と定める（$C$ は線形符号である）。

このとき、$C$ の最小距離が $d=4$ であることを証明せよ。

なお、有限体 ${\mathbb{F}}_{2^m}$ の基本的な性質（$\alpha$ を根にもつ ${\mathbb{F}}_2[x]$ の多項式はすべて $p(x)$ で割り切れること、${\mathbb{F}}_{2^m}$ の $0$ でない元はすべて ${\alpha }^k$ $(0\le k\le n-1)$ の形に書けること、$1,\alpha ,\dots ,{\alpha }^{m-1}$ が ${\mathbb{F}}_2$ 上 1 次独立であること）は用いてよい。

$n\ge 2$ を整数とし、情報源記号 $a_1,a_2,\dots ,a_n$ がそれぞれ確率 $p_1,p_2,\dots ,p_n$ で現れるとする。ただし $p_i>0$ $(i=1,\dots ,n)$, ${\sum }_{i=1}^n{p}_i=1$ とする。

各 $a_i$ に $\{0,1\}$ 上の語 $w_i$ を割り当て、$i\ne j$ ならば $w_i$ が $w_j$ の接頭語（$w_j$ の先頭部分。$w_j$ 自身も含む）でないものを 2 元の語頭符号とよぶ。$w_i$ の長さを $l_i$（$0$ 以上の整数）とし、平均符号長を $\bar{L}={\sum }_{i=1}^n{p}_i{l}_i$ とする。

2 元の語頭符号のうち平均符号長が最小のもの（最適符号）の 1 つを $C$ とし、$C$ の符号長を $l_1,\dots ,l_n$、その最大値を $L={\max }_i{l}_i$ とする。このとき、$C$ において長さが $L$ の符号語の個数は偶数である（特に $2$ 以上である）ことを証明せよ。

なお、次のクラフトの不等式とその逆は用いてよい: $0$ 以上の整数 $m_1,\dots ,m_n$ に対し、符号長が $m_1,\dots ,m_n$ の 2 元の語頭符号が存在するための必要十分条件は ${\sum }_{i=1}^n{2}^{-m_i}\le 1$ である。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上で考える。${\mathbb{F}}_3^3$ の $0$ でないベクトル（列ベクトル）のうち、上から見て最初に現れる $0$ でない成分が $1$ であるものは全部で $13$ 個ある。これら $13$ 個のベクトルをすべて、ある順序で列として並べた $3\times 13$ 行列を $G$ とする。

$G$ を生成行列とする符号長 $13$ の線形符号を
$$C=\{\mathbf{u}G\mid \mathbf{u}\in {\mathbb{F}}_3^3(\text{行ベクトル})\}$$
とし、その双対符号を
$$C^{\perp }=\{\mathbf{y}\in {\mathbb{F}}_3^{13}\mid \mathbf{y}\cdot \mathbf{c}=0\text{がすべての}\mathbf{c}\in C\text{について成り立つ}\}$$
とする（$\mathbf{y}\cdot \mathbf{c}$ は成分ごとの積の和を $3$ を法として計算したもの）。ハミング重みは $0$ でない成分の個数、線形符号の最小距離は $0$ でない符号語のハミング重みの最小値とする。

$C^{\perp }$ の次元 $k^{\perp }$、$C$ の最小距離 $d$、$C^{\perp }$ の最小距離 $d^{\perp }$ を求め、組 $(k^{\perp },d,d^{\perp })$ の形で答えよ。なお、答えは $G$ の列の並べ方によらない。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $8$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccccccc}1& 0& 0& 1& 0& 0& 0& 1\\ 0& 1& 0& 1& 1& 0& 0& 1\\ 0& 1& 1& 0& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 1& 0& 0\end{array}\right)$$
を用いて $C=\{\mathbf{x}\in {\mathbb{F}}_2^8\mid H{\mathbf{x}}^T=0\}$ で定める。ただし、符号語の重みとは $0$ でない成分の個数であり、$C$ の最小距離 $d$ とは $C$ の $0$ でない符号語の重みの最小値である。$C$ の最小距離 $d$ と、$C$ に含まれる重み $d$ の符号語の個数 $A_d$ を、この順に組 $(d,A_d)$ で求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、次の $4\times 10$ 行列 $H$ を考える。
$$H=\left(\begin{array}{cccccccccc}1& 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 1& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 1& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 0& 1& 1\end{array}\right)$$
$H$ の列は、${\mathbb{F}}_2^4$ のベクトルのうちハミング重み（$1$ である成分の個数）が $1$ または $2$ であるもの全部（$10$ 個）を $1$ 回ずつ並べたものである。$H$ を検査行列とする符号長 $10$ の二元線形符号
$$C=\{x\in {\mathbb{F}}_2^{10}:H{x}^T=0\}$$
について、$C$ の最小距離を $d$ とし、$C$ に含まれるハミング重み $k$ の符号語の個数を $A_k$ とする。$d,A_d,A_{d+1}$ をこの順に組で求めよ。