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

符号アルファベットを $\{0,1,2\}$ とする 3 元符号を考える。符号長 $1$ の符号語が $2$ 個、符号長 $2$ の符号語が $2$ 個、符号長 $3$ の符号語が $k$ 個からなる語頭符号（瞬時符号）が存在するような正の整数 $k$ の最大値を求めよ。

5 個の情報源記号 $a_1,a_2,a_3,a_4,a_5$ に、符号アルファベット $\{0,1\}$ の 2 元語頭符号（瞬時符号）を割り当てる。各符号語の長さを
$$l_1=1,l_2=3,l_3=3,l_4=3,l_5=l$$
とするとき、このような 2 元語頭符号が存在するような正の整数 $l$ のうち、最小のものを求めよ。

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

情報源の記号 $a_1,a_2,a_3,a_4,a_5$ が、それぞれ確率
$$\frac{7}{20},\frac{1}{4},\frac{1}{5},\frac{1}{10},\frac{1}{10}$$
で独立に出力される無記憶情報源を考える。この情報源に対して 2 元（記号 $0,1$）のハフマン符号を構成するとき、1 記号あたりの平均符号長 $\bar{L}={\sum }_i{p}_i{l}_i$ を求めよ。ただし $p_i$ は $a_i$ の確率、$l_i$ は $a_i$ に割り当てられた符号語の長さとする。

二元体 ${\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$ 個以上のときは正しく復号されないものとする。

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