设信源 } X P(X) (1) 求信源熵 H(X);(2) 编二进制香农码;(3) 计算平均码长和编码效率。
设信源 $\begin{bmatrix} X \\ P(X) \end{bmatrix} = \begin{cases} x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 \\ 0.2 & 0.19 & 0.18 & 0.17 & 0.15 & 0.1 & 0.01 \end{cases}$
(1) 求信源熵 $H(X)$;
(2) 编二进制香农码;
(3) 计算平均码长和编码效率。
题目解答
答案
解析
本题主要考查信源熵、二进制香农码的编码、平均码长和编码效率的计算。解题思路如下:
- 计算信源熵 $H(X)$:根据信源熵的定义公式 $H(X)=-\sum_{i = 1}^{n}p(x_i)\log_2p(x_i)$,其中 $n$ 是信源符号的个数,$p(x_i)$ 是第 $i$ 个信源符号的概率。
- 编二进制香农码:
- 首先将信源符号按概率从大到小排序。
- 计算累加概率 $P_{i}=\sum_{j = 1}^{i - 1}p(x_j)$。
- 对累加概率进行二进制小数表示,取小数点后足够的位数作为香农码。
- 计算平均码长 $\overline{K}$:根据平均码长的定义公式 $\overline{K}=\sum_{i = 1}^{n}p(x_i)k_i$,其中 $k_i$ 是第 $i$ 个信源符号的码长。
- 计算编码效率 $\eta$:根据编码效率的定义公式 $\eta=\frac{H(X)}{\overline{K}}\times100\%$。
(1)求信源熵 $H(X)$
已知信源 $\begin{bmatrix} X \\ P(X) \end{bmatrix} = \begin{cases} x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 \\ 0.2 & 0.19 & 0.18 & 0.17 & 0.15 & 0.1 & 0.01 \end{cases}$,根据信源熵公式 $H(X)=-\sum_{i = 1}^{7}p(x_i)\log_2p(x_i)$ 可得:
$\begin{align*}H(X)&=-0.2\log_20.2 - 0.19\log_20.19 - 0.18\log_20.18 - 0.17\log_20.17 - 0.15\log_20.15 - 0.1\log_20.1 - 0.01\log_20.01\\&\approx -0.2\times(-2.32) - 0.19\times(-2.47) - 0.18\times(-2.59) - 0.17\times(-2.74) - 0.15\times(-2.74) - 0.1\times(-3.32) - 0.01\times(-6.64)\\&=0.464 + 0.4693 + 0.4662 + 0.4658 + 0.411 + 0.332 + 0.0664\\&\approx 2.61 \text{ bit/symbol}\end{align*}$
(2)编二进制香农码
- 排序:信源符号已按概率从大到小排序。
- 计算累加概率:
- $P_1 = 0$
- $P_2 = 0.2$
- $P_3 = 0.2 + 0.19 = 0.39$
- $P_4 = 0.2 + 0.19 + 0.18 = 0.57$
- $P_5 = 0.2 + 0.19 + 0.18 + 0.17 = 0.74$
- $P_6 = 0.2 + 0.19 + 0.18 + 0.17 + 0.15 = 0.89$
- $P_7 = 0.2 + 0.19 + 0.18 + 0.17 + 0.15 + 0.1 = 0.99$
- 二进制表示累加概率并取码:
- $x_1$:$P_1 = 0$,二进制表示为 $0.000\cdots$,取前三位 $000$。
- $x_2$:$P_2 = 0.2$,二进制表示为 $0.00110011\cdots$,取前三位 $001$。
- $x_3$:$P_3 = 0.39$,二进制表示为 $0.0110011\cdots$,取前三位 $011$。
- $x_4$:$P_4 = 0.57$,二进制表示为 $0.1000111\cdots$,取前三位 $100$。
- $x_5$:$P_5 = 0.74$,二进制表示为 $0.1011101\cdots$,取前三位 $101$。
- $x_6$:$P_6 = 0.89$,二进制表示为 $0.1110011\cdots$,取前四位 $1110$。
- $x_7$:$P_7 = 0.99$,二进制表示为 $0.1111010\cdots$,取前六位 $1111110$。
所以二进制香农码为:
$\begin{array}{ccccccc}x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 \\000 & 001 & 011 & 100 & 101 & 1110 & 1111110 \\\end{array}$
(3)计算平均码长和编码效率
- 计算平均码长 $\overline{K}$:
已知各符号码长 $k_1 = 3$,$k_2 = 3$,$k_3 = 3$,$k_4 = 3$,$k_5 = 3$,$k_6 = 4$,$k_7 = 6$,根据平均码长公式 $\overline{K}=\sum_{i = 1}^{7}p(x_i)k_i$ 可得:
$\begin{align*}\overline{K}&=0.2\times3 + 0.19\times3 + 0.18\times3 + 0.17\times3 + 0.15\times3 + 0.1\times4 + 0.01\times6\\&=(0.2 + 0.19 + 0.18 + 0.17 + 0.15)\times3 + 0.1\times4 + 0.01\times6\\&=0.89\times3 + 0.4 + 0.06\\&=2.67 + 0.4 + 0.06\\&= 3.14 \text{ bit/symbol}\end{align*}$ - 计算编码效率 $\eta$:
根据编码效率公式 $\eta=\frac{H(X)}{\overline{K}}\times100\%$,将 $H(X)\approx 2.61$ bit/symbol,$\overline{K} = 3.14$ bit/symbol 代入可得:
$\eta=\frac{2.61}{3.14}\times100\%\approx 83.1\%$