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

記号 $0,1$ を使う 2 元符号を考える。長さ $2$ の符号語が $2$ 個、長さ $3$ の符号語が $1$ 個、長さ $4$ の符号語が $k$ 個からなる語頭符号（瞬時符号）を作りたい。ただし、どの 2 つの符号語も互いに異なるものとする。このような語頭符号が存在する 0 以上の整数 $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\}$、出力アルファベット $\{0,1,2\}$ の離散無記憶通信路を考える。入力 $X$ に対して、$X$ と独立な雑音 $Z$ が $P(Z=0)=P(Z=1)=\frac{1}{2}$ で生じ、出力は通常の整数の和
$$Y=X+Z$$
で与えられる。入力分布を $P(X=1)=q$ $(0\le q\le 1)$ とする。この通信路の通信路容量 $C={\max }_{P_X}I(X;Y)$ を求めよ。ただし、対数の底は $2$ とし、単位はビットとする。

情報源 $X$ は 4 個の記号 $a_1,a_2,a_3,a_4$ を、それぞれ次の確率で出力する。$$P(a_1)=\frac{2}{5},P(a_2)=\frac{3}{10},P(a_3)=\frac{1}{5},P(a_4)=\frac{1}{10}$$符号記号を $\{0,1,2\}$ とする 3 元語頭符号で $X$ の各記号を符号化するとき、1 記号あたりの平均符号長 $\bar{L}={\sum }_{i=1}^{4}P(a_i)l_i$（$l_i$ は $a_i$ の符号語の長さ）の最小値を求めよ。

符号長 $5$ の 2 元符号
$$C=\{00000,11100,00111,11011\}$$
を考える。$C$ の符号語を、ビット誤り確率 $p=\frac{1}{10}$ の 2 元対称通信路で送る。各ビットは互いに独立に確率 $p$ で反転する。

受信側では次のように復号する。$C$ の最小距離を $d$ とし、$t=\lfloor \frac{d-1}{2}\rfloor$ とおく。受信語とのハミング距離が $t$ 以下の符号語があれば、その符号語に復号する。そのような符号語がなければ、復号失敗とする。

送った符号語が正しく復号される確率を求めよ。