第五章信源编码习题答案-Read

设信源

X x x x

x x x P(X) 1 2 3

4 5 6 7 70.150.1编二进制香农码；计算平均码长和编码效率。解：(1)7H(X))log)7i 2 ii12

2

2

2

0.172

2

2

0.01)symbol(2)xxp(xipa)ki码字ixix0.2030001x0.190.230012x0.30.18 301139x0.50.17 310047x0.70.15 310154xx0.80.1 4111069x0.90.01 7111111079(3)K ki ii3.14 R K

X

x2 x3 x4 x5 x6 x7 编二进制费1P(X) 1 0.19 0.180.17 0.150.1诺码，计算编码效率。解：xp(xxp(xi码编码)i字ix00.2 010x00.19 0 02101x00.18 1311x10.17 1 0402332x1x10.15 0510x10.1 1 061101x10.01 1711144K k)i ii2.74 R K X x x x x x x x 123123

P(X)

4 5

7 编 7 0.150.1二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。解：二进制哈夫曼码：xxis6s5s4s3s2x1x2x3x4x5s1x6x7p(x)i编码码字ki0.610.391010.350.26080.170.1501011011000001010223330.10.010.1101010110011144K ki

)ii2.72 R K 三进制哈夫曼码：xp(x)编码码字kisi1i3s0.5402s0.2611x0.22211x0.1900022x0.1810123x0.1720224x0.1501025x0.111126x0.0121227K ki

pxi

12(0.19i H H 2.609 91.4%R K/log L m

1.8/log23 X

x x

x x x x x x 3 4 5 6 788

1 1 1 1 1 1 1P(X) 2 4 8 16 32 64 128 128H(X)；编二进制香农码和二进制费诺码；计算二进制香农码和二进制费诺码的平均码长和编码效率；编三进制费诺码；计算三进制费诺码的平均码长和编码效率；解：(1)H(X)8p(x)logp(x)i 2 ii11log

21log

41log

81

log

1log

1log

1log1

log2 2

2 8 2

2 32

64

128

128bit/symbol(2)二进制香农码：xxp(x)ip(xa iki码字ix0.50101x0.250.52102x0.1250.7531103x0.0620.8754111045x0.03111110.9375 55250x0.01511110.96875 6662510x0.0070.98437711117781255110x0.0070.99218111178812575111二进制费诺码：xip(x)i编码码字kix0.5001x0.250102x0.12501103x0.0625011104x0.031250111105x6x7x80.0156250.00781250.0078125111110101111110111111011111116771212345香农编码效率：K

p(x)1112131415161717ii1.984

i 2 4 8 16 32 64 128 128 H(X R K 费诺编码效率：K

p(x)1112131415161717ii1.984

i 2 4 8 16 32 64 128 128 H(X R K (4)xix

p(x)i

码编码 k字 i0.5 0 0 11x0.25 1 1 12x0.125

0 20 23x 0.062154x 0.0310255 2x 0.015

21 2220 36x7x8(5)

6250.00781250.0078125

1 221 322220 4022221 41K k)1112

1213131414i i1.328

2 4 8 16 32 64 128 128 H(X) 94.3% R K/logm

2 23X，X，X1 2

Pr 1

1，2P

1，P

1，请给出联合随机变量（X

，X，X）的r 2 3 r 3 4

1 2 3Huffman编码，并求其平均码长。解：根据已知条件可以得到联合随机变量1 2 3

）的概率分布，如表所示。xxxxx1 2 3p(xxx)1 2 30001/40011/120101/80111/241001/41011/121101/81111/24然后根据Huffman编码算法得到编码结果为：xxxxx1 2 3码字00010001110001011101101101000010111011100101110111L

12663334221

2.755号集合为{x，y，z}4个码都是二进制码。{xx，xz，y，zz，xyz}{000，10，00，11}{100，101，0，11}{01，100，011，00，111，1010，1011，1101}{01，111，011，00，010，110}对于上面列出的5种编码，分别回答下述问题：⑴此码的码长分布是否满足Kraft-McMillan不等式？⑵此码是否是即时码？如果不是，请给出反例。解：码字集合一：{xx，xz，y，zz，xyz}⑴此码的码长分布满足Kraft-McMillan不等式：1

111

339

31

19132

32

272727272727⑵根据码树图可知此码是即时码。⑶由于此码是即时码，所以也是唯一可译码。码字集合二：{000，10，00，11}⑴此码的码长分布满足Kraft-McMillan不等式：1 1 1 1 12227123

22 22 22

888

8⑵此码不是即时码，因为码字00是码字000的前缀。00000000，00000，000。码字集合三：{100，101，0，11}⑴此码的码长分布满足Kraft-McMillan不等式：1 1 1 1 11428123

23 22

888

8⑵根据码树图可知此码是即时码。⑶由于此码是即时码，所以也是唯一可译码。码字集合四：{01，100，011，00，111，1010，1011，1101}⑴此码的码长分布不满足Kraft-McMillan不等式：1122

1123 22

111123 24 24 24

17116⑵因为不满足Kraft-McMillan不等式，所以此码不是即时码。Kraft-McMillan不等式，所以此码不是唯一可译码。码字集合五：{01，111，011，00，010，110}⑴此码的码长分布满足Kraft-McMillan不等式：1122

1123 22

1123

818⑵此码不是即时码，因为码字01是码字011的前缀。⑶此码是唯一可译码。一离散信源的符号表为{a，b，c，d，e}x=daadcadbea信源的观察序列。假设此信源为具体分布未知的独立同分布随机过程，估计求信源的熵。Huffmanx编码所需的比特数与平均码长的关系。解：⑴此时信源概率分布的估计为{0.4，0.1，0.1，0.3，0.1}，相应的熵为H0.4log30.1log0.10.3log2.0464比特符号2 2 2Huffman表所示。符号估计概率分布码字码长a0.411b0.10013c0.100004d0.3012e0.100014

0.410.320.1320.142.1x=daadcadbea特数为：2+1+1+2+4+1+2+3+4+1=21d a a d c a d b e a而此序列的自信息为10H=20.464bit。一个离散无记忆信源，其样本空间为{W，B}W0.99，B0.01。⑴对此信源的二次扩展，求出信源符号序列的概率分布，找出相应的Huffman编码并求平均码长。⑵对此信源的三次扩展重复上一问。解：⑴二次扩展信源的符号序列、概率分布及码字如表所示。符号序列符号序列概率码字WW0.99×0.99=0.98010WB0.99×0.01=0.009911BW0.01×0.99=0.0099100BB0.01×0.01=0.0001101平均码长为：L 0.980110.009920.009930.000131.02992⑵三次扩展信源的符号序列、概率分布及码字如表所示：符号序列概率码字WWW0.9702990WWB0.009801100WBW0.009801101BWW0.009801110WBB0.00009911100BWB0.00009911101BBW0.00009911110BBB0.00000111111平均码长为：L0.970299130.000099553⑶信源的单符号熵为H0.99log2

10.99

0.01log2

10.01

0.080179比特/符号二次扩展信源和三次扩展信源的单符号平均码长分别为：L L20.51495，2 3

0.35333都远大于信源的单符号熵。已知离散无记忆信源如下：S s sP 1 2

s s s s s 3 4 5 6 7 00.01试求：⑴信源符号熵（S；⑵相应的二元Huffman编码及其编码效率；⑶相应的三元Huffman编码及其编码效率；⑷若要求p≤10-3，采用定长二元码要求达到第⑵问中的编码效率，E至少需要多少信源符号一起编码才能实现？解：⑴信源符号熵为S2log2

2

2

2

2

0.152

2

0.01）/符号⑵二元Huffman编码如表所示：信源符号s1s2s3s4s5s6s7概率00.01码字10110000