Homework 02

约 905 个字 12 张图片 预计阅读时间 5 分钟

3.1

长度为 \(i\) 的码字最多有 \(D^i\) 个，所以长度不大于 \(N\) 的 \(D\) 元不等长码字数最多有：

\[ \sum_{i=1}^N D^i = \frac{D(D^N-1)}{D-1} \]

---

3.3

（a）\(\{0,10,11\}\) 是前缀码，所以唯一可译

（b）后缀分解集为：

\(S_0\)	\(S_1\)	\(S_2\)
0	1	1
01
11

没有一个后缀分解集包含码字，所以是唯一可译的

（c）后缀分解集为：

\(S_0\)	\(S_1\)	\(S_2\)
0	1	0
01
10

其中后缀分解集 \(S_2\) 包含码字，所以不是唯一可译的

例如 “010”，可以被译为 “0” 和 “10”，或者 “01”和“0”，所以不是唯一可译的

（d）后缀分解集为：

\(S_0\)	\(S_1\)	\(S_2\)
0	1	\(\phi\)
01

没有一个后缀分解集包含码字，所以是唯一可译的

（e）\(\{00,01,10,11\}\) 是前缀码，所以唯一可译

（f）后缀分解集为：

\(S_0\)	\(S_1\)	\(S_2\)
110	0	\(\phi\)
11
10

没有一个后缀分解集包含码字，所以是唯一可译的

（g）后缀分解集为：

\(S_0\)	\(S_1\)	\(S_2\)
110	0	0
100
00
10

没有一个后缀分解集包含码字，所以是唯一可译的

---

3.4

（a）后缀分解集为：

\(S_0\)	\(S_1\)	\(S_2\)	\(S_3\)	\(S_4\)	\(S_5\)	\(S_6\)
010	1	100	11	00	01	0
0001		1110		110	011	10
0110		01011			110	001
1100					0	110
00011						0011
00110						0110
11110
101011

其中 \(S_6\) 包含码字 0110，所以不是唯一可译的，例如 "000110101111000110" 可以译为 \(x_5x_1x_7x_6\)，也可以译为 \(x_2x_8x_4x_3\)

（b）后缀分解集为：

\(S_0\)	\(S_1\)	\(S_2\)	\(S_3\)	\(S_4\)	\(S_5\)	\(S_6\)	\(S_7\)
abc	d	ba	ce	ac	c	eac	ac
abcd	abd			ab	cd	eab	ab
e							d
dba
bace
ceac
ceab
eabd

因为 \(S_7\) 所有的元素都被包含在前面了，所以后面也不会出现 \(S_1-S_7\) 中的元素，且 \(S_1-S_7\) 都不包含码字，所以是唯一可译的

---

3.6

（a）

\(\overline{n}=\sum\limits_{i=1}^{10}n_i\times p_i=3.26\)

\(H(U)=\sum\limits_{i=1}^{10}-p_i\log p_i=3.234\text{ bit}\Rightarrow\eta = \frac{H(U)}{\overline{n}\log D}=99.2\%\)

（b）

\(\overline{n}=\sum\limits_{i=1}^{10}n_i\times p_i=2.11\)

\(\eta=\frac{H(U)}{\overline{n}\log D}=96.7\%\)

---

3.10

（a）\(x_1\)：0，\(x_2\)：11，\(x_3\)：101，\(x_4\)：100

（b）也可以使用编码 \(x_1\)：11，\(x_2\)：10，\(x_3\)：01，\(x_4\)：00

（c）例如，概率分布为 0.49, 0.25, 0.25, 0.01，此时对应编码为 0, 10, 110, 111，对于第三个符号来说，香农编码码长为 2，但是最佳码字长度为 3

---

3.11

（a）

\(\overline{n}=\sum\limits_{i=1}^{10}n_i\times p_i=3.419\)

\(H(U)=\sum\limits_{i=1}^{10}-p_i\log p_i=2.325\text{ bit}\Rightarrow \eta=\frac{H(U)}{\overline{n}\log D}=68.0\%\)

（b）

\(\overline{n}=\sum\limits_{i=1}^{10}n_i\times p_i=2.2\)

\(\eta=\frac{H(U)}{\overline{n}\log D}=96.2\%\)

---

3.16

（a）我们有如下方程：

\[ \begin{cases} q(1)=q(3)\\ q(2)=\frac{3}{4}q(1)+\frac{1}{2}q(2)\\ q(3)=\frac{1}{4}q(1)+\frac{1}{2}q(2)\\ q(1)+q(2)+q(3)=1 \end{cases} \]

解得 \(q(1)=q(3)=\frac{2}{7},q(2)=\frac{3}{7}\)

\[ \begin{aligned} p(a_1)&=q(1)\cdot p(a_1|s_1)+q(3)\cdot p(a_1|s_3)=\frac{3}{7}\\ p(a_2)&=q(1)\cdot p(a_2|s_1)+q(2)\cdot p(a_2|s_2)=\frac{2}{7}\\ p(a_3)&=q(1)\cdot p(a_3|s_1)+q(2)\cdot p(a_3|s_2)=\frac{2}{7}\\ \end{aligned} \]

（b）\(H(U|s_1)=1.5\text{ bit},H(U|s_2)=1\text{ bit},H(U|s_3)=0\text{ bit}\)

（c）\(H_{\infty}(U)=q(1)\cdot H(U|s_1)+q(2)\cdot H(U|s_2)+q(3)\cdot H(U|s_3)=\frac{6}{7}\text{ bit}\)

（d）对 \(s_1\) 来说 \(a_1,a_2,a_3\) 分别为 1, 01, 00，对 \(s_2\) 来说 \(a_2,a_3\) 分别为 1, 0，对 \(s_3\) 来说无需编码

（e）\(\overline{n}=\overline{n_1}\cdot q(1)+\overline{n_2}\cdot q(2)=\frac{6}{7}\)

评论