信息论第五章答案 本文关键词：信息论，第五章，答案
信息论第五章答案 本文简介：5.1设信源(1)求信源熵H(X)；(2)编二进制香农码；(3)计算平均码长和编码效率。解：(1)(2)xip(xi)pa(xi)ki码字x10.203000x20.190.23001x30.180.393011x40.170.573100x50.150.743101x60.10.8941110x7
信息论第五章答案 本文内容：
5.1
设信源
(1)
求信源熵H(X)；
(2)
编二进制香农码；
(3)
计算平均码长和编码效率。
解：
(1)
(2)
xi
p(xi)
pa(xi)
ki
码字
x1
0.2
0
3
000
x2
0.19
0.2
3
001
x3
0.18
0.39
3
011
x4
0.17
0.57
3
100
x5
0.15
0.74
3
101
x6
0.1
0.89
4
1110
x7
0.01
0.99
7
1111110
(3)
5.2
对信源编二进制费诺码，计算编码效率。
解：
xi
p(xi)
编码
码字
ki
x1
0.2
0
0
00
2
x2
0.19
1
0
010
3
x3
0.18
1
011
3
x4
0.17
1
0
10
2
x5
0.15
1
0
110
3
x6
0.1
1
0
1110
4
x7
0.01
1
1111
4
5.3
对信源编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。
解：
二进制哈夫曼码：
xi
p(xi)
编码
码字
ki
s6
1
s5
0.61
0
s4
0.39
1
s3
0.35
0
s2
0.26
1
x1
0.2
0
10
2
x2
0.19
1
11
2
x3
0.18
0
000
3
x4
0.17
1
001
3
x5
0.15
0
010
3
s1
0.11
1
x6
0.1
0
0110
4
x7
0.01
1
0111
4
三进制哈夫曼码：
xi
p(xi)
编码
码字
ki
s3
1
s2
0.54
0
s1
0.26
1
x1
0.2
2
2
1
x2
0.19
0
00
2
x3
0.18
1
01
2
x4
0.17
2
02
2
x5
0.15
0
10
2
x6
0.1
1
11
2
x7
0.01
2
12
2
5.4
设信源
(1)
求信源熵H(X)；
(2)
编二进制香农码和二进制费诺码；
(3)
计算二进制香农码和二进制费诺码的平均码长和编码效率；
(4)
编三进制费诺码；
(5)
计算三进制费诺码的平均码长和编码效率；
解：
(1)
=127/64
bit/symbol
(2)
二进制香农码：
xi
p(xi)
pa(xi)
ki
码字
x1
0.5
0
1
0
x2
0.25
0.5
2
10
x3
0.125
0.75
3
110
x4
0.0625
0.875
4
1110
x5
0.03125
0.9375
5
11110
x6
0.015625
0.96875
6
111110
x7
0.0078125
0.984375
7
1111110
x8
0.0078125
0.9921875
7
1111111
二进制费诺码：
xi
p(xi)
编码
码字
ki
x1
0.5
0
0
1
x2
0.25
1
0
10
2
x3
0.125
1
0
110
3
x4
0.0625
1
0
1110
4
x5
0.03125
1
0
11110
5
x6
0.015625
1
0
111110
6
x7
0.0078125
1
0
1111110
7
x8
0.0078125
1
1111111
7
(3)
香农编码效率：
费诺编码效率：
(4)
xi
p(xi)
编码
码字
ki
x1
0.5
0
0
1
x2
0.25
1
1
1
x3
0.125
2
0
20
2
x4
0.0625
1
21
2
x5
0.03125
2
0
220
3
x6
0.015625
1
221
3
x7
0.0078125
2
0
2220
4
x8
0.0078125
1
2221
4
(5)
5.5
设无记忆二进制信源
先把信源序列编成数字0，1，2，……，8，再替换成二进制变长码字，如下表所示。
(1)
验证码字的可分离性；
(2)
求对应于一个数字的信源序列的平均长度；
(3)
求对应于一个码字的信源序列的平均长度；
(4)
计算，并计算编码效率；
(5)
若用4位信源符号合起来编成二进制哈夫曼码，求它的平均码长，并计算编码效率。
序列
数字
二元码字
1
0
1000
01
1
1001
001
3
1010
0001
3
1011
00001
4
1100
000001
5
1101
0000001
6
1110
00000001
7
1111
00000000
8
0
解：（1）满足Kcraft不等式：；由码树图可见，没有一个码字是其它码字的前缀，码字均在树的终结点。所以码字可分离。
（2）序列长度、序列概率及二元码长如下表所示：
序列
序列长度Li
序列概率pi
数字
二元码长L’i
二元码字
1
1
0.1
0
4
1000
01
2
0.1×0.9
1
4
1001
001
3
0.1×0.92
3
4
1010
0001
4
0.1×0.93
3
4
1011
00001
5
0.1×0.94
4
4
1100
000001
6
0.1×0.95
5
4
1101
0000001
7
0.1×0.96
6
4
1110
00000001
8
0.1×0.97
7
4
1111
00000000
8
0.98
8
1
0
（3）
（4）,此值表示无记忆二元信源采用游程长度编码后每个二元信源需要的平均码长。，
（5）4位信源符号的联合概率、Huffman编码及码长如下表：（码字可以不同，但码长一样）
S4
P(Si)
码字Wi
码长Li
S4
P(s)
码字Wi
码长Li
0000
0.6561
0
1
1001
0.0081
1111010
7
0001
0.0729
110
3
1010
0.0081
1111011
7
0010
0.0729
100
3
1100
0.0081
1111110
7
0100
0.0729
101
3
0111
0.0009
111111100
9
1000
0.0729
1110
4
1011
0.0009
111111101
9
0011
0.0081
111110
6
1101
0.0009
111111110
9
0101
0.0081
1111000
7
1110
0.0001
1111111110
10
0110
0.0081
1111001
7
1111
0.0001
1111111111
10
5.6
有二元平稳马氏链，已知p(0/0)
=
0.8，p(1/1)
=
0.7，求它的符号熵。用三个符号合成一个来编写二进制哈夫曼码，求新符号的平均码字长度和编码效率。
解：平稳时马尔科夫状态的概率：
解得：
一阶马氏信源的熵：
S1S2S3
P(S1S2S3)
Li
Wi
S1S2S3
P(S1S2S3)
Li
Wi
000
48/125
1
1
011
21/250
4
0011
111
49/250
3
000
110
21/250
4
0100
001
12/125
3
011
010
9/250
5
01010
100
12/125
4
0010
101
3/125
5
01011
5.7
对题5.6的信源进行游程编码。若“0”游程长度的截止值为16，“1”游程长度的截止值为8，求编码效率。
解：一阶马氏信源的熵同上题，
二元平稳一阶记忆序列“0”游程的长度概率：
二元平稳一阶记忆序列“1”游程的长度概率：
“1”游程长度的熵：
同理，“0”游程长度的熵：
分别对“0”和“1”游程序列进行Huffman编码，并分别计算出它们的编码效率。
“0”游程序列的长度、对应得概率、Huffman编码的二元码长及码字
序列
序列长度Li
序列概率pi
数字
二元码长L’i
二元码字
0
1
P1/0
0
2
11
00
2
P0/0
P
1/0
1
3
001
000
3
P0/02
P
1/0
2
3
011
0000
4
P0/03
P
1/0
3
3
101
0000,0
5
P0/04
P
1/0
4
4
0001
0000,00
6
P0/05
P
1/0
5
4
0101
0000,000
7
P0/06
P
1/0
6
4
1001
0000,0000
8
P0/07
P
1/0
7
5
00000
0000,0000,0
9
P0/08
P
1/0
8
5
01001
0000,0000,00
10
P0/09
P
1/0
9
5
10001
0000,0000,000
11
P0/010
P
1/0
A
6
000010
0000,0000,0000
12
P0/011
P
1/0
B
6
100000
0000,0000,0000,0
13
P0/012
P
1/0
C
6
100001
0000,0000,0000,00
14
P0/013
P
1/0
D
7
0000110
0000,0000,0000,000
15
P0/014
P
1/0
E
7
0000111
0000,0000,0000,0000
16
P0/015
F
5
01000
“1”游程序列的长度、对应得概率、Huffman编码的二元码长及码字：
序列
序列长度Ki
序列概率pi
数字
二元码长K’i
二元码字
1
1
P0/1
0
2
01
11
2
P0/1
P
1/1
1
2
10
111
3
P0/1
P
1/12
3
3
001
1111
4
P0/1
P
1/13
3
3
110
1111,1
5
P0/1
P
1/14
4
4
0001
1111,11
6
P0/1
P
1/15
5
4
1110
1111,111
7
P0/1
P
1/16
6
4
1111
1111,1111
8
P
1/17
7
4
0000
可见满足，这里的“0”游程编码效率高，因为游程长度长，而“1”游程编码效率受游程的长度限制显得比“0”游程编码效率略低一些，因此整体的编码效率介于两者之间。
5.8
选择帧长N
=
63
(1)
对00100000,00000000,00000000,00000000,01000000,00000000,00000000,0000000编L-D码；
(2)
对10000100,00101100,00000001,00100001,01001000,00000111,00000100,0000001编L-D码
再译码；
(3)
对0000000000000000000000000000000000000000000000000000000000000000编L-D码；
(4)
对10100011010111000110001110100110000111101100101000110101011010010编L-D码；
(5)
对上述结果进行讨论。
解：（1）本帧内信息位数Q=2；各信息位位置值n1=3，n2=34；帧长N=63。
Q位和T位需要的二进制自然码位数分别是：
所以，L-D编码结果：000010,01000010010
解码：已知N=63，故前6位为Q的自然码表示，所以Q=2；后11位为T的自然码表示，得T=530
寻找某一值K，使
得：K=33
再令，
再次寻找某一值L，使
得：L=2
所以解码出信息位的位置值是n1=3，n2=34
(2)
对10000100,00101100,00000001,00100001,01001000,00000111,00000100,00000010编L-D码
本帧内信息位数Q=15；各信息位位置值n1=1，n2=6，n3=11，n4=13，n5=14，n6=24，n7=27，n8=32，n9=34，n10=37，n11=46，n12=47，n13=48，n14=54，n15=63；帧长N=63。
Q位和T位需要的二进制自然码位数分别是：
所以，L-D编码结果：001111，1010110,11111101,01111111,10110101,00011000,11111110
解码：已知N=63，故前7位为Q的自然码表示，所以Q=15；后47位为T的自然码表示，得
T=
95646769289470
(a)
寻找某一值K，使
得：K=62
(b)令，Q=Q-1
重复步骤（a）（b）每次寻找出一个K值，得：
解出的各信息位位置值：
n1=1，n2=6，n3=11，n4=13，n5=14，n6=24，n7=27，n8=32，n9=34，n10=37，n11=46，n12=47，n13=48，n14=54，n15=63；
(3)
本帧内信息位数Q=0；帧长N=64
Q位和T位需要的二进制自然码位数分别是：
所以，L-D编码结果：0000000
解码：已知N=64，故前7位为Q的自然码表示，所以Q=0。表示64位全零。
（4）“0”、“1”数几乎相等，用一般的能表示15位十进制整数的数学软件已无法表示其T值，可以肯定的是，其编出的码要比64bit二进制还要长。
（5）L-D编码的结论是，全0、全1、或少量的0、1可以编出短码，当冗余位和信息为相当时，反而使其码长增加，此时不宜使用L-D编码。