東大 情報理工学系研究科 知能機械情報学専攻 知能機械情報学 2020年度 院試 過去問 解答例・解説（全3問）

問1：2の補数

8ビット2の補数で $-50$ を表す。まず $$50=(00110010)_2$$ である。ビット反転して $$11001101$$ となり、1を足すと $$-50=(11001110)_2$$ である。

8ビット符号付き整数の範囲は $$-2^7\le x\le 2^7-1$$ なので $$-128\le x\le 127$$ である。

また $$32-50=-18.$$ $$18=(00010010)_2$$ より、2の補数で $$-18=(11101110)_2$$ となる。

問2：線形符号

生成行列を $$G=[P\ I_4],\qquad P= \begin{bmatrix} 1&0&1\\ 1&1&1\\ 1&1&0\\ 0&1&1 \end{bmatrix}$$ とする。加算はすべてGF(2)で行う。入力 $$u=[1\ 0\ 1\ 1]$$ に対して $$uP=[0\ 0\ 0]$$ なので $$w=uG=[0\ 0\ 0\ 1\ 0\ 1\ 1].$$

検査行列を $$H=[I_3\ A]$$ と書く。任意の符号語で $Hw^\top=0$ が成り立つには $$HG^\top=[I_3\ A] \begin{bmatrix} P^\top\\ I_4 \end{bmatrix} = P^\top+A=0$$ であればよい。GF(2)では $A=-P^\top=P^\top$ だから $$A=P^\top = \begin{bmatrix} 1&1&1&0\\ 0&1&1&1\\ 1&1&0&1 \end{bmatrix}.$$

受信語を $$r=[0\ 1\ 1\ 1\ 0\ 1\ 1]$$ とすると、シンドロームは $$s=Hr^\top = \begin{bmatrix} 0\\1\\1 \end{bmatrix}.$$ これは $H$ の第7列と一致するので、誤りは第7ビットである。訂正後の符号語は $$[0\ 1\ 1\ 1\ 0\ 1\ 0]$$ であり、後半4ビットが元の入力なので $$u=[1\ 0\ 1\ 0]$$ である。

問3：情報量とエントロピー

10進数1桁は10通りを区別するので、情報量は $$\log_2 10 = \frac{1}{\log_{10}2} \simeq \frac{1}{0.30} \simeq 3.33\ \mathrm{bit}$$ である。

確率分布 $P=(p_1,\ldots,p_n)$、$Q=(q_1,\ldots,q_n)$ について、ギブスの不等式を示す。 $\log x\le x-1$ を $x=q_k/p_k$ に適用すると $$\log\frac{q_k}{p_k}\le \frac{q_k}{p_k}-1.$$ 両辺に $p_k$ を掛けて和を取ると $$\sum_{k=1}^n p_k\log\frac{q_k}{p_k} \le \sum_{k=1}^n(q_k-p_k)=0.$$ 従って $$\sum_{k=1}^n p_k\log\frac{p_k}{q_k}\ge0$$ である。等号はすべての $k$ で $q_k/p_k=1$、すなわち $P=Q$ のときに限る。

エントロピーを $$\mathcal{H}(P)=-\sum_{k=1}^n p_k\log_2 p_k$$ とする。各 $p_k$ は $0<p_k\le1$ なので $$\mathcal{H}(P)\ge0$$ である。上限は、ギブスの不等式で一様分布 $Q=(1/n,\ldots,1/n)$ を取ればよい。 $$\sum_{k=1}^n p_k\log_2\frac{p_k}{1/n}\ge0$$ より $$\sum_{k=1}^n p_k\log_2p_k+\log_2 n\ge0.$$ したがって $$\mathcal{H}(P)\le\log_2 n.$$ 等号は $P$ が一様分布、すなわち $$p_1=\cdots=p_n=\frac{1}{n}$$ のときに限る。