第五章信源編碼習(xí)題答案-Read

設(shè)信源

X x x x

x x x P(X) 1 2 3

4 5 6 7 70.150.1編二進(jìn)制香農(nóng)碼；計(jì)算平均碼長和編碼效率。解：(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 編二進(jìn)制費(fèi)1P(X) 1 0.19 0.180.17 0.150.1諾碼，計(jì)算編碼效率。解：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二進(jìn)制和三進(jìn)制哈夫曼碼，計(jì)算各自的平均碼長和編碼效率。解：二進(jìn)制哈夫曼碼：xxis6s5s4s3s2x1x2x3x4x5s1x6x7p(x)i編碼碼字ki0.610.391010.350.26080.170.1501011011000001010223330.10.010.1101010110011144K ki

)ii2.72 R K 三進(jìn)制哈夫曼碼：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)；編二進(jìn)制香農(nóng)碼和二進(jìn)制費(fèi)諾碼；計(jì)算二進(jìn)制香農(nóng)碼和二進(jìn)制費(fèi)諾碼的平均碼長和編碼效率；編三進(jìn)制費(fèi)諾碼；計(jì)算三進(jìn)制費(fèi)諾碼的平均碼長和編碼效率；解：(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)二進(jìn)制香農(nóng)碼：xxp(x)ip(xa iki碼字ix0.50101x0.250.52102x0.1250.7531103x0.0620.8754111045x0.03111110.9375 55250x0.01511110.96875 6662510x0.0070.98437711117781255110x0.0070.99218111178812575111二進(jìn)制費(fèi)諾碼：xip(x)i編碼碼字kix0.5001x0.250102x0.12501103x0.0625011104x0.031250111105x6x7x80.0156250.00781250.0078125111110101111110111111011111116771212345香農(nóng)編碼效率：K

p(x)1112131415161717ii1.984

i 2 4 8 16 32 64 128 128 H(X R K 費(fèi)諾編碼效率：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，請給出聯(lián)合隨機(jī)變量（X

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

1 2 3Huffman編碼，并求其平均碼長。解：根據(jù)已知條件可以得到聯(lián)合隨機(jī)變量1 2 3

）的概率分布，如表所示。xxxxx1 2 3p(xxx)1 2 30001/40011/120101/80111/241001/41011/121101/81111/24然后根據(jù)Huffman編碼算法得到編碼結(jié)果為：xxxxx1 2 3碼字00010001110001011101101101000010111011100101110111L

12663334221

2.755號集合為{x，y，z}4個(gè)碼都是二進(jìn)制碼。{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不等式？⑵此碼是否是即時(shí)碼？如果不是，請給出反例。解：碼字集合一：{xx，xz，y，zz，xyz}⑴此碼的碼長分布滿足Kraft-McMillan不等式：1

111

339

31

19132

32

272727272727⑵根據(jù)碼樹圖可知此碼是即時(shí)碼。⑶由于此碼是即時(shí)碼，所以也是唯一可譯碼。碼字集合二：{000，10，00，11}⑴此碼的碼長分布滿足Kraft-McMillan不等式：1 1 1 1 12227123

22 22 22

888

8⑵此碼不是即時(shí)碼，因?yàn)榇a字00是碼字000的前綴。00000000，00000，000。碼字集合三：{100，101，0，11}⑴此碼的碼長分布滿足Kraft-McMillan不等式：1 1 1 1 11428123

23 22

888

8⑵根據(jù)碼樹圖可知此碼是即時(shí)碼。⑶由于此碼是即時(shí)碼，所以也是唯一可譯碼。碼字集合四：{01，100，011，00，111，1010，1011，1101}⑴此碼的碼長分布不滿足Kraft-McMillan不等式：1122

1123 22

111123 24 24 24

17116⑵因?yàn)椴粷M足Kraft-McMillan不等式，所以此碼不是即時(shí)碼。Kraft-McMillan不等式，所以此碼不是唯一可譯碼。碼字集合五：{01，111，011，00，010，110}⑴此碼的碼長分布滿足Kraft-McMillan不等式：1122

1123 22

1123

818⑵此碼不是即時(shí)碼，因?yàn)榇a字01是碼字011的前綴。⑶此碼是唯一可譯碼。一離散信源的符號表為{a，b，c，d，e}x=daadcadbea信源的觀察序列。假設(shè)此信源為具體分布未知的獨(dú)立同分布隨機(jī)過程，估計(jì)求信源的熵。Huffmanx編碼所需的比特?cái)?shù)與平均碼長的關(guān)系。解：⑴此時(shí)信源概率分布的估計(jì)為{0.4，0.1，0.1，0.3，0.1}，相應(yīng)的熵為H0.4log30.1log0.10.3log2.0464比特符號2 2 2Huffman表所示。符號估計(jì)概率分布碼字碼長a0.411b0.10013c0.100004d0.3012e0.100014

0.410.320.1320.142.1x=daadcadbea特?cái)?shù)為：2+1+1+2+4+1+2+3+4+1=21d a a d c a d b e a而此序列的自信息為10H=20.464bit。一個(gè)離散無記憶信源，其樣本空間為{W，B}W0.99，B0.01。⑴對此信源的二次擴(kuò)展，求出信源符號序列的概率分布，找出相應(yīng)的Huffman編碼并求平均碼長。⑵對此信源的三次擴(kuò)展重復(fù)上一問。解：⑴二次擴(kuò)展信源的符號序列、概率分布及碼字如表所示。符號序列符號序列概率碼字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⑵三次擴(kuò)展信源的符號序列、概率分布及碼字如表所示：符號序列概率碼字WWW0.9702990WWB0.009801100WBW0.009801101BWW0.009801110WBB0.00009911100BWB0.00009911101BBW0.00009911110BBB0.00000111111平均碼長為：L0.970299130.000099553⑶信源的單符號熵為H0.99log2

10.99

0.01log2

10.01

0.080179比特/符號二次擴(kuò)展信源和三次擴(kuò)展信源的單符號平均碼長分別為：L L20.51495，2 3

0.35333都遠(yuǎn)大于信源的單符號熵。已知離散無記憶信源如下：S s sP 1 2

s s s s s 3 4 5 6 7 00.01試求：⑴信源符號熵（S；⑵相應(yīng)的二元Huffman編碼及其編碼效率；⑶相應(yīng)的三元Huffman編碼及其編碼效率；⑷若要求p≤10-3，采用定長二元碼要求達(dá)到第⑵問中的編碼效率，E至少需要多少信源符號一起編碼才能實(shí)現(xiàn)？解：⑴信源符號熵為S2log2

2

2

2

2

0.152

2

0.01）/符號⑵二元Huffman編碼如表所示：信源符號s1s2s3s4s5s6s7概率00.01碼字10110000