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

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^3+x^2+1$$
で定まる符号長 $7$、次元 $4$ の巡回符号 $C$ を考える（$g(x)$ は $x^7-1$ を割り切る）。

語 $c=(c_0,c_1,\dots ,c_6)\in {\mathbb{F}}_2^7$ は多項式 $c(x)=c_0+c_{1}x+\cdots +c_6{x}^6$ と同一視する。情報 $m=(m_0,m_1,m_2,m_3)$ は $m(x)=m_0+m_{1}x+m_2{x}^2+m_3{x}^3$ と同一視し、次のように組織符号化する。

• $x^{3}m(x)$ を $g(x)$ で割った余りを $r(x)=r_0+r_{1}x+r_2{x}^2$ とする。
• 符号語を $c(x)=x^{3}m(x)+r(x)$ とする。すなわち $c=(r_0,r_1,r_2,m_0,m_1,m_2,m_3)$ である。

情報 $m=(1,1,0,1)$ を符号化して得られる符号語 $c=(c_0,c_1,c_2,c_3,c_4,c_5,c_6)$ を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^3+x^2+1$$
で定まる符号長 $7$、次元 $4$ の巡回符号 $C$ を考える（$x^7+1=(x+1)(x^3+x+1)(x^3+x^2+1)$ なので、$g(x)$ は $x^7-1$ を割り切る）。

情報語 $m=(m_0,m_1,m_2,m_3)=(1,0,0,1)$ を、情報多項式 $m(x)=m_0+m_{1}x+m_2{x}^2+m_3{x}^3=1+x^3$ で表す。組織符号化では、$x^{3}m(x)$ を $g(x)$ で割った余りを $r(x)$（次数 $2$ 以下）として、符号多項式を $c(x)=r(x)+x^{3}m(x)$ と定める。

このときの余り $r(x)$ を求めよ。ただし、係数の計算はすべて $2$ を法として行う。

二元体 ${\mathbb{F}}_2=\{0,1\}$（演算は $2$ を法とする）上で、検査行列
$$H=\left(\begin{array}{ccccccc}0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1\end{array}\right)$$
で定まる符号長 $7$ のハミング符号 $C=\{\mathbf{x}\in {\mathbb{F}}_2^7\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ を考える。$H$ の第 $j$ 列は、$j$ を 2 進法で表したときの各桁を上から $4$ の位・$2$ の位・$1$ の位の順に並べたものである。

ある符号語を送信したところ、ちょうど $1$ か所のビットだけが誤って
$$\mathbf{y}=(0,1,1,1,1,1,0)$$
が受信された。誤りが起きた位置（左から数えて第何成分か）を求めよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上で、符号長 $4$ の線形符号 $C$ を生成行列
$$G=\left(\begin{array}{cccc}1& 0& 2& 1\\ 0& 1& 1& 0\end{array}\right)$$
で定める。すなわち $C=\{\mathbf{u}G\mid \mathbf{u}=(a,b)\in {\mathbb{F}}_3^2\}$ とする。符号語 $\mathbf{c}$ のハミング重みを $0$ でない成分の個数とし、$C$ の最小距離 $d$ を $C$ の $0$ でない符号語の重みの最小値とする。また、重みがちょうど $d$ である符号語の個数を $A_d$ とする。$d$ と $A_d$ をこの順に組 $(d,A_d)$ で求めよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上の符号長 $4$ の線形符号 $C$ を、生成行列
$$G=\left(\begin{array}{cccc}1& 0& 2& 1\\ 0& 1& 1& 0\end{array}\right)$$
によって $C=\{\mathbf{u}G\mid \mathbf{u}\in {\mathbb{F}}_3^2\}$ と定める（$\mathbf{u}$ は行ベクトル）。ベクトルのハミング重みを $0$ でない成分の個数とし、$C$ の最小距離 $d$ を $C$ の $0$ でない符号語のハミング重みの最小値とする。また、ハミング重みがちょうど $d$ である符号語の個数を $A_d$ とする。$d$ と $A_d$ をこの順に組 $(d,A_d)$ で求めよ。