ハミング符号とシンドローム復号

二元体 ${\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)$$
が受信された。誤りが起きた位置（左から数えて第何成分か）を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、$3\times 7$ 行列
$$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=1,2,\dots ,7)$ は、上から順に $j$ を 2 進数で表したときの $2^2,2^1,2^0$ の位の数字を並べたものである。

ある符号語 $\mathbf{c}=(c_1,c_2,\dots ,c_7)\in C$ を送信したところ、通信路で高々 $1$ か所の成分が反転し、受信語
$$\mathbf{y}=(1,0,1,1,0,0,0)$$
を受け取った。シンドローム $H{\mathbf{y}}^{\mathsf{T}}$ を用いて誤りを訂正し、送信された符号語 $\mathbf{c}$ を $(c_1,c_2,\dots ,c_7)$ の形で求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、検査行列
$$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=1,2,\dots ,7)$ は、上から読むと $j$ を 2 進法で表した 3 桁の数になっている。

ある符号語を送信したところ、ちょうど 1 か所のビットが反転して
$$\mathbf{y}=(1,1,0,1,1,0,1)$$
を受信した。シンドローム $H{\mathbf{y}}^{\mathsf{T}}$ を計算して、誤りが生じた位置（左から何番目の成分か）を求めよ。

二元体 ${\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+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$ の式で求めよ。

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\}$ 上で、生成多項式
$$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)$ と異なる語を出力してしまうものの個数を求めよ。