巡回符号と生成多項式

三元体 ${\mathbb{F}}_3=\{0,1,2\}$（$3$ を法とする演算）上で考える。$x^4-1=(x^2+1)(x^2-1)$ より $g(x)=x^2+1$ は $x^4-1$ を割り切るので、$g(x)$ を生成多項式とする符号長 $4$、次元 $2$ の巡回符号 $C$ が定まる。ここで語 $(c_0,c_1,c_2,c_3)$ を多項式 $c(x)=c_0+c_{1}x+c_2{x}^2+c_3{x}^3$ と同一視する。

情報 $(m_0,m_1)$ を $m(x)=m_0+m_{1}x$ で表し、次の組織符号化を行う：$x^{2}m(x)$ を $g(x)$ で割った余りを $r(x)$ として、符号語を
$$c(x)=x^{2}m(x)-r(x)$$
とする。

情報 $(m_0,m_1)=(1,2)$ を符号化したときの符号語 $(c_0,c_1,c_2,c_3)$ を求めよ。各成分は $0,1,2$ のいずれかで答えること。

二元体 ${\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\}$ 上で、生成多項式
$$g(x)=x^3+x+1$$
で定まる符号長 $7$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $6$ 以下の多項式のうち $g(x)$ で割り切れるものの係数ベクトル全体である。

$C$ の符号語を $1$ つ選び、各ビットが互いに独立に確率 $p=\frac{1}{10}$ で反転する二元対称通信路で送る。受信側は、受信語とのハミング距離が最小となる符号語に復号する。復号結果が送信した符号語に一致する確率を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^4+x^3+x^2+1$$
で定まる符号長 $7$ の巡回符号 $C$ を考えます。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $2$ 以下の多項式 $a(x)$ を用いて $a(x)g(x)$ と表される多項式全体です。多項式 $c_0+c_{1}x+\cdots +c_6{x}^6$ を語 $(c_0,c_1,\dots ,c_6)\in {\mathbb{F}}_2^7$ と同一視します。

$C$ の符号語を、ビット誤り確率 $p$ $\left(0<p<\frac{1}{2}\right)$ の二元対称通信路で送ります。各ビットは互いに独立に確率 $p$ で反転します。受信語 $r$ に対して、受信側は次のように復号します。

• $r$ とのハミング距離が $1$ 以下である符号語が存在すれば、その符号語を出力する。
• 存在しなければ、誤りを検出したと判断して何も出力しない。

（この復号法で、ハミング距離 $1$ 以下の符号語は存在すれば $1$ つに定まることも確かめてください。）

送信した符号語とは異なる符号語が出力される確率を、$p$ の式で求めてください。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^4+x+1$$
で定まる符号長 $15$ の巡回符号 $C$ を考える。すなわち、符号語 $c=(c_0,c_1,\dots ,c_{14})\in {\mathbb{F}}_2^{15}$ を多項式 $c(x)=c_0+c_{1}x+\cdots +c_{14}{x}^{14}$ と同一視し、$C=\{c(x)\mid \mathrm{deg}c(x)\le 14,g(x)\text{ が }c(x)\text{ を割り切る}\}$ とする。なお、$g(x)$ は ${\mathbb{F}}_2$ 上の原始多項式である（既約であり、その根 $\alpha$ は $15$ 個の元 ${\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{14}$ がすべて異なる、${\mathbb{F}}_{16}$ の $0$ でない元すべてとなる）。

この符号を誤り検出のためだけに用いる。送信した符号語 $c$ に誤りパターン $e\in {\mathbb{F}}_2^{15}$ が加わって $r=c+e$ が受信されたとき、$r\in C$ ならば「誤りなし」と判定し、$r\notin C$ ならば「誤りあり」と判定する。$e\ne 0$ で $r\in C$ となるとき、誤りは検出されない。

ハミング重み（$1$ である成分の個数）が $1$ 以上 $4$ 以下の誤りパターン $e$ のうち、検出されないものの個数を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式 $$g(x)=x^4+x+1$$ で定まる符号長 $15$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $14$ 以下の多項式のうち $g(x)$ で割り切れるもの全体（係数の列を長さ $15$ のベクトルとみなす）である。なお、$g(x)$ は ${\mathbb{F}}_2$ 上の原始多項式であり、$x^{15}-1$ を割り切る。

$C$ の符号語を、ビット反転確率が $p$ $\left(0<p<\frac{1}{2}\right)$ の 2 元対称通信路で送る。各ビットの反転は互いに独立に起こるものとする。受信語は、シンドロームを計算し、そのシンドロームをもつベクトルのうちハミング重みが最小のもの（コセットリーダー）を誤りとみなして訂正する方法で復号する。

復号した符号語が送信した符号語と一致する確率を $p$ の式で求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、
$$g(x)=(x^4+x+1)(x^4+x^3+x^2+x+1)$$
を生成多項式とする符号長 $15$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $14$ 以下の多項式のうち $g(x)$ で割り切れるもの全体であり、多項式 $c_0+c_{1}x+\cdots +c_{14}{x}^{14}$ を語 $(c_0,c_1,\dots ,c_{14})\in {\mathbb{F}}_2^{15}$ と同一視する（$g(x)$ は $x^{15}-1$ を割り切る）。

$C$ の最小ハミング距離を $d$ とする。また、${\mathbb{F}}_2^{15}$ を $C$ による剰余類（$v+C$ の形の集合）に分けたとき、ハミング重みが $2$ 以下の語を $1$ つも含まない剰余類の個数を $N$ とする。$(d,N)$ をこの順に組で求めよ。

$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 次独立であること）は用いてよい。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=(x+1)(x^4+x+1)=x^5+x^4+x^2+1$$
で定まる符号長 $15$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $14$ 以下の多項式のうち $g(x)$ で割り切れるもの全体であり、多項式 $c_0+c_{1}x+\cdots +c_{14}{x}^{14}$ を語 $(c_0,c_1,\dots ,c_{14})\in {\mathbb{F}}_2^{15}$ と同一視する。また、$\alpha$ を ${\mathbb{F}}_{16}$ における $x^4+x+1$ の根とする（$\alpha$ の位数は $15$ である）。

符号語 $c(x)\in C$ を送信し、誤りパターン $e(x)$（次数 $14$ 以下）が加わって $r(x)=c(x)+e(x)$ を受信したとする。復号器は $s_0=r(1)\in {\mathbb{F}}_2$、$s_1=r(\alpha )\in {\mathbb{F}}_{16}$ を計算し、次の規則で動作する。

• $(1)$ $s_0=0$ かつ $s_1=0$ のとき：$r(x)$ をそのまま出力する。
• $(2)$ $s_0=1$ かつ $s_1\ne 0$ のとき：$s_1={\alpha }^m$ $(0\le m\le 14)$ となる $m$ をとり、$r(x)+x^m$ を出力する。
• $(3)$ それ以外のとき：誤りを検出したと宣言し、何も出力しない。

ハミング重み（$0$ でない係数の個数）が $1$ 以上 $5$ 以下の誤りパターン $e(x)$ のうち、復号器が送信した符号語 $c(x)$ と異なる語を出力してしまうものの個数を求めよ。