京都大学 情報学研究科 知能情報学専攻 2020年8月実施 専門科目 S-4

标签：

• Kyoto-University
• Source-Coding
• Channel-Coding

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$ が最適かどうかについて論じよ。

题目描述

考虑字母表 $\{a,b,c,d\}$ 上的平稳无记忆信源 $A$，概率为

$$p(a)=\frac38,\quad p(b)=\frac14,\quad p(c)=\frac14,\quad p(d)=\frac18.$$

1. 求信源熵 $H(A)$。

2. 用下列二元码 $C_1$ 编码，判断是否唯一可译并说明理由。

   符号	$C_1$
   $a$	0
   $b$	01
   $c$	011
   $d$	111

3. 将信源产生的足够长序列用 $C_1$ 编码，从所得比特流中均匀抽取 1 bit，求抽到 1 的概率。

4. 考虑题图给出的非对称二元信道。当输入 $X$ 的概率由第 3 问确定时，求互信息 $I(X;Y)$。

   

5. 改用固定长码 $C_2$ 编码信源符号，经第 4 问信道传输后再按 $C_2$ 译码，令译码符号为随机变量 $B$，求 $I(A;B)$。

   符号	$C_2$
   $a$	00
   $b$	01
   $c$	10
   $d$	11

6. 讨论在通过第 4 问信道传输信源 $A$ 的 2 bit 固定长二元码中，$C_2$ 是否最优。

考点

• 信源熵与唯一可译码：计算离散熵，并用 Sardinas–Patterson 思想或构造歧义判断非前缀码是否唯一可译。
• 变长码输出比特分布：按码字长度加权统计长比特流中的 1 比例。
• 非对称信道互信息：根据题图转移概率和非均匀输入计算 $I(X;Y)$。
• 固定长信道编码设计：把两次独立二元信道使用诱导为符号级信道，计算 $I(A;B)$ 并比较不同码字分配。

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$ は最適ではない。