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

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成行列
$$G=\left(\begin{array}{ccccc}1& 1& 1& 1& 1\end{array}\right)$$
で定まる符号長 $5$ の線形符号 $C$ を考える。$C$ の符号語を、ビット誤り確率 $p=\frac{1}{10}$ の 2 元対称通信路で送る。各ビットの誤りは互いに独立に起こるものとする。受信側では最小距離復号（受信語にハミング距離が最も近い符号語に復号する）を行う。

送った符号語が正しく復号される確率を、既約分数で求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成行列
$$G=\left(\begin{array}{ccccc}1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1\end{array}\right)$$
で定まる符号長 $5$ の線形符号 $C$ を考える。$C$ の最小距離を $d$ とし、$t=\lfloor \frac{d-1}{2}\rfloor$ とする。

$C$ の符号語を、各ビットが互いに独立に確率 $p=\frac{1}{10}$ で反転する（$0$ と $1$ が入れ替わる）2 元対称通信路で送信し、受信語を最小距離復号する。ただし、送信語に生じた誤りの個数が $t$ 個以下のときは正しく復号され、$t+1$ 個以上のときは正しく復号されないものとする。

正しく復号される確率を求めよ。

二元体 ${\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$ の式で求めてください。

入力・出力のアルファベットがともに $\{0,1\}$ の 2 元対称通信路を考える。この通信路では、送った記号が確率 $\frac{1}{8}$ で反転し（$0$ が $1$ に、$1$ が $0$ になる）、確率 $\frac{7}{8}$ で正しく届く。各回の伝送は互いに独立とする。この通信路の通信路容量 $C$（単位はビット／通信路 1 回の使用）を求めよ。ただし、対数の底は $2$ とし、答えは ${\log }_{2}7$ を用いて表せ。