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

通信路

入力 $X\in\{0,1\}$、出力 $Y\in\{0,1,2\}$ の通信路で、遷移行列は $$W=\begin{pmatrix} 1-p-q&p&q\\ p&1-p-q&q \end{pmatrix}$$ である。入力分布を $P_X(0)=\omega,\ P_X(1)=1-\omega$ とすると $$P_Y(0)=p+\omega(1-2p-q),\quad P_Y(1)=1-p-q-\omega(1-2p-q),\quad P_Y(2)=q.$$ まず $$P(X\ne Y)=p+q$$ である。$Y$ のエントロピーは、固定された $q$ の下で $P_Y(0)=P_Y(1)$ のとき最大となる。よって $$\omega=\frac{(1-q)/2-p}{1-2p-q}=\frac12$$ である。ただし $1-2p-q=0$ の退化場合は、任意の $\omega$ で $P_Y(0)=P_Y(1)$ となる。

通信路容量は $$C=\max_{\omega} I(X;Y)=\max_{\omega}\{H(Y)-H(Y\mid X)\}.$$ $H(Y\mid X)$ は入力に依らず $$H(1-p-q,p,q)$$ であり、最大の $H(Y)$ は $((1-q)/2,(1-q)/2,q)$ で達成される。したがって $$C=H\!\left(\frac{1-q}{2},\frac{1-q}{2},q\right)-H(1-p-q,p,q).$$

エントロピーの分解

$B$ が $X$ と独立で、$B=1$ のときだけ新しい記号 $M+1$ を出す。したがって $$P_Y(i)=(1-q)P_X(i)\quad(1\le i\le M),\qquad P_Y(M+1)=q.$$ よって自然対数単位で $$H(Y)=h(q)+(1-q)H(X),$$ ただし $$h(q)=-q\log q-(1-q)\log(1-q)$$ である。固定された $p_X$ の下で微分すると $$\frac{dH(Y)}{dq}=\log\frac{1-q}{q}-H(X).$$ したがって最大値を与える $$q=\frac{1}{1+e^{H(X)}}.$$