九大 システム情報科学府 情報理工学専攻 専門科目（情報系4分野） 2022年度 院試 過去問 解答例・解説（全4問）

1. 通信路容量

入力と出力を $\mathbb{F}_2^k$ 上のベクトルとみなす。この通信路は $$Y=X\oplus Z$$ と書ける。ただし雑音 $Z$ はハミング重み $1$ の $k$ 個のベクトルのうち一つを等確率 $1/k$ でとる。したがって $$H(Y\mid X)=H(Z)=\log_2 k$$ である。

任意の入力分布に対して $$I(X;Y)=H(Y)-H(Y\mid X)\leq k-\log_2 k$$ である。一方、$X$ を $\mathbb{F}_2^k$ 上の一様分布にすると、加法雑音との和 $Y=X\oplus Z$ も一様分布になり $H(Y)=k$ となる。よって上限が達成される。

$$C=k-\log_2 k \quad \text{bits/use}$$ である。

2. マルコフ情報源

遷移確率行列を $$P= \begin{pmatrix} 1/2&1/2&0&0\\ 0&1/2&0&1/2\\ 1/2&1/2&0&0\\ 0&0&y&1-y \end{pmatrix}$$ とおく。

(1) 状態遷移は、非零確率だけを並べれば $$\begin{array}{c|c} \text{状態} & \text{遷移先と確率}\\ \hline 1 & 1(1/2),\ 2(1/2)\\ 2 & 2(1/2),\ 4(1/2)\\ 3 & 1(1/2),\ 2(1/2)\\ 4 & 3(y),\ 4(1-y) \end{array}$$ である。

(2) 定常分布を $\pi=(1/8,1/4,1/8,1/2)$ とする。第3成分について $$\pi_3=(\pi P)_3=\pi_4 y=\frac12 y$$ であるから $$y=\frac14$$ を得る。

(3) エントロピーレートは定常分布で平均した条件付きエントロピー $$H_{\infty}=\sum_i \pi_i H(P_{i,\cdot})$$ である。第1,2,3行の分岐は二分岐等確率なので各 $1$ bit、第4行は $(1/4,3/4)$ なので $h_2(1/4)$ bit である。従って $$H_{\infty} =\frac18+\frac14+\frac18+\frac12 h_2\!\left(\frac14\right) =\frac12+\frac12 h_2\!\left(\frac14\right)$$ である。数値では $$h_2(1/4)\simeq 0.8113,\qquad H_{\infty}\simeq 0.9056\ \text{bits/symbol}.$$

(4) 定常状態から始めたときの $(X_1,X_2)$ の非零確率は $$\begin{array}{c|c} (X_1,X_2) & \Pr(X_1,X_2)\\ \hline (1,1),(1,2),(3,1),(3,2) & 1/16\\ (2,2),(2,4),(4,3) & 1/8\\ (4,4) & 3/8 \end{array}$$ である。ハフマン符号の一例は次である。 $$\begin{array}{c|c} (X_1,X_2) & \text{符号語}\\ \hline (4,4) & 11\\ (4,3) & 100\\ (2,2) & 010\\ (2,4) & 011\\ (3,1) & 000\\ (3,2) & 001\\ (1,1) & 1010\\ (1,2) & 1011 \end{array}$$ この符号は接頭語条件を満たす。平均符号長は $$\frac38\cdot 2 +3\cdot \frac18\cdot 3 +2\cdot\frac1{16}\cdot 3 +2\cdot\frac1{16}\cdot 4 =\frac{11}{4}$$ である。