京都大学 情報学研究科 知能情報学専攻 2020年8月実施 専門科目 S-4
Author
祭音Myyura
Description
記号の集合 \(\{a,b,c,d\}\) をアルファベットとする記憶のない定常情報源 \(A\) を考える。
\(A\) における各記号の生起確率 \(p\) は
\[
p(a) = 3/8, \ p(b) = 1/4, \ p(c) = 1/4, \ p(d) = 1/8
\]
とする。
設問1 情報源 \(A\) のエントロピー \(H(A)\) を求めよ。
設問2 \(A\) の各記号を下表の符号 \(C_1\) により \(\{0,1\}\) に２元符号化することを考える。符号 \(C_1\) は一意に復号可能か、理由とともに示せ。
| \(C_1\) |
|
| \(a\) |
\(0\) |
| \(b\) |
\(01\) |
| \(c\) |
\(011\) |
| \(d\) |
\(111\) |
設問3 情報源 \(A\) から得られる十分長い記号列を符号 \(C_1\) で２元符号化した系列を考える。この２進系列から任意に 1 bit を取り出すとき、取り出した記号が１である確率を求めよ。
設問4 下の通信線路図によって与えられる非対称の２元通信路を考える。\(X\) の生起確率が設問3のように与えられるとき、相互情報量 \(I(X;Y)\) を求めよ。
設問5 情報源 \(A\) から得られる記号を下表の符号 \(C_2\) で２元符号化し、設問4の通信路で伝送して \(C_2\) で復号することを考える。復号された記号を事象 \(B\) とするとき、相互情報量 \(I(A;B)\) を求めよ。
| \(C_2\) |
|
| \(a\) |
\(00\) |
| \(b\) |
\(01\) |
| \(c\) |
\(10\) |
| \(d\) |
\(11\) |
設問6 情報源 \(A\) が生成する記号列を設問4の通信路で伝送する際の 2 bit の固定長２進符号として、符号 \(C_2\) が最適かどうかについて論じよ。
Kai
設問1
\[
\begin{aligned}
H(A) &= \sum_{x\in A} p(x)\log_2\frac{1}{p(x)}\\
&= \frac{3}{8}\log_2 \frac{3}{8} + \frac{1}{4} \log_2 \frac{1}{4} + \frac{1}{4} \log_2 \frac{1}{4} + \frac{1}{8} \log_2 \frac{1}{8}\\
&= \frac{5}{2} - \frac{3}{8}\log_2 3
\end{aligned}
\]
設問2
符号 \(C_1\) の反転した符号 \(C'_1\) を考える。
| \(C'_1\) |
|
| \(a\) |
\(0\) |
| \(b\) |
\(10\) |
| \(c\) |
\(110\) |
| \(d\) |
\(111\) |
符号 \(C'_1\) のいずれの符号語も他の符号語の接頭になっていないため、符号 \(C'_1\) は瞬時符号である。
よって、符号 \(C'_1\) は一意に復号可能である。
したがって、情報源 \(A\) から得られる記号を反転して符号 \(C'_1\) に基づいて符号化し、復号するときは、反転して符号 \(C'_1\) に基づく復号を利用することで，一意に復号することができる。
設問3
\[
\frac{\frac{3}{8}n\cdot 0 + \frac{1}{4}n \cdot 1 + \frac{1}{4}n \cdot 2 + \frac{1}{8}n \cdot 3}{\frac{3}{8}n\cdot 1 + \frac{1}{4}n\cdot 2 + \frac{1}{4}n\cdot 2 + \frac{1}{8}n\cdot 3} = \frac{9}{16}
\]
設問4
設問3の結果より、
\[
\begin{aligned}
p(X{=}0) = \frac{7}{16},\ p(X{=}1) = \frac{9}{16},\ p(Y{=}0) = \frac{7}{18},\ p(Y{=}1) = \frac{11}{18}
\end{aligned}
\]
与えられた２元通信路より、
\[
\begin{aligned}
p(Y{=}0|X{=}0) = \frac{8}{9},\ p(Y{=}1|X{=}0) = \frac{1}{9},\ p(Y{=}0|X{=}1) = 0,\ p(Y{=}1|X{=}1) = 1
\end{aligned}
\]
\(P(X,Y)=P(Y|X)P(X)\) より、
\[
\begin{aligned}
p(Y{=}0,X{=}0) = \frac{7}{18},\ p(Y{=}1,X{=}0) = \frac{7}{144},\ p(Y{=}0,X{=}1) = 0,\ p(Y{=}1,X{=}1) = \frac{9}{16}
\end{aligned}
\]
従って、
\[
\begin{aligned}
I(X ; Y)
&= \sum_{x \in X, y \in Y} P(x, y) \log \frac{P(x, y)}{P(x) P(y)} \\
&= \frac{7}{18} \log \frac{7/18}{7/16 \cdot 7/18}+ \frac{7}{144} \log \frac{7/144}{7/16 \cdot 11/18}+0+ \frac{9}{16} \log \frac{9/16}{9/16 \cdot 11/18} \\
&=\frac{13}{6} + \frac{9}{8}\log 3 - \frac{7}{18}\log 7 - \frac{11}{18}\log 11
\end{aligned}
\]
設問5
定常情報源 \(A\) における各記号の生起確率より、
\[
p(A{=}a)=\frac{3}{8},\ p(A{=}b)=\frac{1}{4},\ p(A{=}c)=\frac{1}{4},\ p(A{=}d)=\frac{1}{8}
\]
定常情報源 \(A\) において \(a\) が生起するとき、\(C_2\) の符号化方法を考えすると、
\[
p(B{=}a|A{=}a)=\frac{64}{81},\ p(B{=}b|A{=}a)=\frac{8}{81},\ p(B{=}c|A{=}a)=\frac{8}{81},\ p(B{=}d|A{=}a)=\frac{1}{81}
\]
同様に、
\[
p(B{=}a|A{=}b)=0,\ p(B{=}b|A{=}b)=\frac{8}{9},\ p(B{=}c|A{=}b)=0,\ p(B{=}d|A{=}b)=\frac{1}{9}
\]
\[
p(B{=}a|A{=}c)=0,\ p(B{=}b|A{=}c)=0,\ p(B{=}c|A{=}c)=\frac{8}{9},\ p(B{=}d|A{=}c)=\frac{1}{9}
\]
\[
p(B{=}a|A{=}d)=0,\ p(B{=}b|A{=}d)=0,\ p(B{=}c|A{=}d)=0,\ p(B{=}d|A{=}d)=1
\]
よって、
\[
P(B=a) = \frac{8}{27},\ P(B=b) = \frac{7}{27},\ P(B=c) = \frac{7}{27},\ P(B=d) = \frac{5}{27}
\]
が得られる。従って、
\[
\begin{aligned}
I(A ; B)
&= \sum_{a \in A, b \in B} P(A=a, B=b) \log \frac{P(A=a, B=b)}{P(A=a) P(B=b)} \\
&= \frac{22}{9}+\frac{1}{2}\log 3-\frac{5}{27}\log 5-\frac{14}{27}\log 7
\end{aligned}
\]
設問6
設問4の通信路は、入力が \(1\) の場合は誤りがないため、平均符号長が最大の記号に極力多くの \(1\) を割り当てるべきである。
2 bit の固定長2進符号の場合の平均符号長 \(L\) を計算すると、
\[
L(a)=\frac{6}{8},\ L(b)=\frac{1}{2},\ L(c)=\frac{1}{2},\ L(d)=\frac{1}{4}
\]
がわかる。よって、\(a\) に \(11\) を割り当てるべきである。故に、\(C_2\) は最適ではない。