信息論與編碼理論—第三章習(xí)題解答

1、2022-4-101習(xí)題課習(xí)題課3.1 試證明長度不超過N的D元不等長碼至多有D(DN1)/(D1)個(gè)碼字。 3.1的解答長度等于k的D元碼字至多有Dk個(gè)，其中k=1N。因此長度不超過N的D元碼字至多有)1/()1(1DDDDNNkk2022-4-1023.2 以上是一個(gè)離散無記憶信源。若對其輸出的長為100的事件序列中含有兩個(gè)和更少個(gè)al的序列提供不同的碼字。(a) 在等長編碼下，求二元碼的最短碼長N。(b) 求錯(cuò)誤概率(誤組率)。3.2的解答(a) 長為L=100的事件序列中含有兩個(gè)和更少個(gè)al的序列，其個(gè)數(shù)為996.0004.021aaU。，所以最短碼長為而；10259625964951

2、001109210011000100NCCC2022-4-103習(xí)題課習(xí)題課(b) 含有兩個(gè)和更少個(gè)al的序列擁有不同的碼字，它們的譯碼不會出現(xiàn)錯(cuò)誤。因此錯(cuò)誤概率(誤組率)不會超過“含有三個(gè)以上al的序列”出現(xiàn)的概率。而“含有三個(gè)以上al的序列”出現(xiàn)的概率等于204.0201001001003100100!4.01)996.0()004.0(1)996.0()004.0(kkkkkkkkkkekCC2022-4-104習(xí)題課習(xí)題課3.2的注解 事實(shí)上，在對“含有兩個(gè)或更少個(gè)al的長為100的序列”提供不同的碼字之后,還有210-596=428個(gè)富余的碼字。這些富余的碼字如果提供給其中428 個(gè)

3、“含有恰好三個(gè)al的長為100的序列”，作為它們各自的不同碼字。則錯(cuò)誤概率不會超過00002.0!4.01)996.0()004.0(428)996.0()004.0(204.09731003100100kkkkkkekC2022-4-105習(xí)題課習(xí)題課3.4 對于有4個(gè)字母的離散無記憶源有兩個(gè)碼A和B，參看下表。試問：(a) 各碼是否滿足異字頭條件?是否為唯一可譯碼?(b) 當(dāng)收到1時(shí)得到多少關(guān)于字母a1的信息?(c) 當(dāng)收到1時(shí)得到多少關(guān)于信源的平均信息?字 母概 率碼 A碼 Ba1a2a3a4 0.40.30.20.1 1010010001 1101001000 2022-4-106習(xí)題

4、課習(xí)題課3.4的解答(a) 碼A是異字頭碼。碼B不是異字頭碼。碼A和碼B都是唯一可譯碼。碼A的譯碼規(guī)則是：1就是一個(gè)碼字的末尾。碼B的譯碼規(guī)則是：1就是一個(gè)碼字的開頭。2022-4-107習(xí)題課習(xí)題課(b) “當(dāng)收到1時(shí)得到多少關(guān)于字母a1的信息”，這是求事件a1與事件“收到1”的（非平均）互信息量。以碼A為例。P(a1)=0.4。P(收到1)=P(a1)P(收到1|a1)+P(a2)P(收到1|a2)+P(a3)P(收到1|a3)+P(a4)P(收到1|a4)=0.41+0.3(1/2)+0.2(1/3)+0.1(1/4)=0.642。P(a1，且收到1)=P(a1)P(收到1|a1)=0.

5、41=0.4。所以I(a1；收到1)=log0.4/(0.40.642)=0.64155。2022-4-108(c) “當(dāng)收到1時(shí)得到多少關(guān)于信源的平均信息”，這是求信源隨機(jī)變量U與事件“收到1”的（半平均）互信息量。以碼A為例。I(收到1；U)=)1()()1,(log)1|()1()()1,(log)1|()1()()1,(log)1|()1()()1,(log)1|(444333222111收到且收到收到收到且收到收到收到且收到收到收到且收到收到PaPaPaPPaPaPaPPaPaPaPPaPaPaP2022-4-1093.6 令離散無記憶信源如上。(a) 求對U（即U1）的最佳二元碼、

6、平均碼長和編碼效率。(b) 求對U2 （即U1U2）的最佳二元碼、平均碼長和編碼效率。(c) 求對U3 （即U1U2U3 ）的最佳二元碼、平均碼長和編碼效率。2 . 03 . 05 . 0321aaaU04. 006. 006. 009. 010. 010. 015. 015. 025. 033233222133112211121aaaaaaaaaaaaaaaaaaUU2022-4-1010（U1U2U3 ）a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.045

7、0.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.0082022-4-1011（U1U2）的第一種最佳二元碼）的第一種最佳二元碼2022-4-1012（U1U2）的第二種最佳二元碼）的第二種最佳二元碼2022-4-1013（U1U2）的最佳二元碼平均

8、碼長和編碼效）的最佳二元碼平均碼長和編碼效率：率：3)04. 0206. 009. 0(4) 210. 0215. 0(325. 02)(2Un5 .12)(2Unn因此平均碼長為48503. 12 . 01log2 . 03 . 01log3 . 05 . 01log5 . 0)(UHnnR2log編碼速率為99002.05 .148503.1)()(2RUHU因此編碼效率為2022-4-10142022-4-10152022-4-10162022-4-10172022-4-10182022-4-10192022-4-10202022-4-10212022-4-10222022-4-1023

9、2022-4-10242022-4-10252022-4-10262022-4-10272022-4-10282022-4-10292022-4-10302022-4-10312022-4-10322022-4-10332022-4-10342022-4-1035（U1U2U3）的碼字）的碼字a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a201000000001011011101000100110101011a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30010001110

10、110001100111010110111111011111001100a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a300110100111000111101111001111100101000010101001011000101112022-4-1036（U1U2U3）的最佳二元碼平均碼長：）的最佳二元碼平均碼長：487. 4)008. 03012. 0(7) 3018. 03020. 0(6)027. 06030. 0045. 0(5) 2045. 03050. 03075. 0(4125. 03)(3Un4956666.13)

11、(3Unn因此平均碼長為2022-4-1037（U1U2U3）的最佳二元碼編碼效率：）的最佳二元碼編碼效率：48503. 12 . 01log2 . 03 . 01log3 . 05 . 01log5 . 0)(UHnnR2log編碼速率為99289.04956666.148503.1)()(3RUHU因此編碼效率為)(99289.099002.0)(32UU2022-4-10383.9 設(shè)離散無記憶信源如上。試求其二元和三元Huffman碼。 3.9的解答 二元Huffman碼為：1 . 01 . 015. 015. 02 . 03 . 0654321aaaaaaU2022-4-1039習(xí)題

12、課習(xí)題課三元Huffman碼為：2022-4-1040習(xí)題課習(xí)題課3.10 設(shè)離散無記憶源試構(gòu)造兩組三元異字頭條件碼，其平均碼長相同，但具有不同的方差。哪一組更好些?為什么?3.10的解答 兩組不同的三元異字頭條件碼如下：1 . 01 . 01 . 01 . 01 . 015. 015. 02 . 087654321aaaaaaaaU2022-4-1041第一種三元異字頭碼（用第一種三元異字頭碼（用Huffman編碼法）編碼法）平均碼長為2 ，方差為0。2022-4-1042第二種三元異字頭碼（用第二種三元異字頭碼（用Huffman編碼法）編碼法） 平均碼長為10.2+20.6+30.2=2，

13、方差為(1-2)20.2+(2-2)20.6+(3-2)20.2=0.4。2022-4-1043習(xí)題課習(xí)題課我們認(rèn)為，第一種三元異字頭碼比第二種三元異字頭碼更好。以下是我們的理由。離散信源每隔一個(gè)定長的時(shí)間間隔就產(chǎn)生一個(gè)隨機(jī)變量。這個(gè)隨機(jī)變量共有8個(gè)可能的事件。使用第一種三元異字頭碼，則每隔一個(gè)定長的時(shí)間間隔就產(chǎn)生一個(gè)長度為2的碼字。使用第二種三元異字頭碼，則每隔一個(gè)定長的時(shí)間間隔產(chǎn)生一個(gè)長度可能為1，可能為2，也可能為3的碼字。綜上所述，第一種三元異字頭碼使得編碼器的時(shí)鐘固定，而第二種三元異字頭碼使得編碼器的時(shí)鐘隨機(jī)。因此第一種三元異字頭碼的編碼器更簡單。2022-4-10443.12 設(shè)離

14、散無記憶信源如上。若信源輸出序列為1011011110110111（a）對其進(jìn)行算術(shù)編碼并計(jì)算編碼效率。（希望編程計(jì)算）（b）對其進(jìn)行LZ編碼并計(jì)算編碼效率。3.12的解答 （a） F(0)=0， F(1)=1/4，P(0)=1/4，P(1)=3/4。 L=16，事件序列4/ 34/ 110Uu1u2u3u4u5u6u7u8u9u10u11u12u13u14u15u1610110111101101112022-4-1045編碼迭代過程最終得到的H=P(u1)P(u2)P(u16)=(1/4)4 (3/4)12=312/416 ；log2(1/H)=log2(416/312)=32-12log2

15、3=12.98057；因此n=13+1=14。G=F(u1)+P(u1)F(u2)+P(u1)P(u2)F(u3)+P(u1)P(u2)P(u15)F(u16)=(1/4) +(3/4)0 +(3/4)(1/4)(1/4) +(3/4)(1/4)(3/4)(1/4) +(3/4)(1/4)(3/4)(3/4)0 +(3/4)(1/4)(3/4)(3/4)(1/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4

16、)(3/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)0+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)0+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1

17、/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(1/4)+(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4)2022-4-1046習(xí)題課習(xí)題課=(0.01011001111001000010100111001111)2碼字為碼字為0101100111100181129. 034log434log41)(UH99851. 013)(16)(UHnUHL序列的編碼效率，為編碼效率

18、指的是該事件2022-4-1047習(xí)題課習(xí)題課（b）“分段分段”：(1011011110110111)(1，0，11，01，111，011，0111)；“事件編號事件編號”依次為 00， 11；“段編號段編號”依次為段1011011110110111段號0010100111001011101112022-4-1048習(xí)題課習(xí)題課“按段進(jìn)行編碼按段進(jìn)行編碼”：101101111011011100010000001101010111100111012022-4-1049習(xí)題課習(xí)題課譯碼時(shí)，比特串“0001000000110101011110011101”按照碼字長度為3+1=4來分割碼字：0000

19、，0001，0011，0101，0111，1001，1101碼字碼字0001000000110101011110011101段號段號001010011100101110111段值段值10110111101101112022-4-1050習(xí)題課習(xí)題課編碼效率怎樣計(jì)算?該事件序列的碼字總長度為N=每段的碼字長度段數(shù)=47=28。因此46359. 028)(16)(UHNUHL序列的編碼效率，為編碼效率指的是該事件2022-4-10513.13 設(shè)DMS為如上的概率分布。各ai相應(yīng)編成碼字0，10，110和111。試證明對足夠長的信源輸出序列，相應(yīng)的碼序列中0和1出現(xiàn)的概率相等。 3.13的證明 設(shè)

20、有一個(gè)足夠長的信源輸出序列，因而相應(yīng)的碼序列也足夠長。在碼序列中隨機(jī)地取一個(gè)符號X，以下只需要證明P(X=0)=1/2。記Aj=“X是aj的碼字中的符號”，j=14。根據(jù)全概率公式，8/18/14/12/14321aaaaU41)|0()()0(jjjAXPAPXP2022-4-1052習(xí)題課習(xí)題課72381381241121121)(1AP72381381241121241)(2AP143381381241121381)(3AP143381381241121381)(4AP2022-4-1053習(xí)題課習(xí)題課P(X=0|A1)=1；P(X=0|A2)=1/2；P(X=0|A3)=1/3；P(X=0|A4)=0。所以210143311432172172)0(XP2022-4-10543.14 設(shè)有一DMS如上。采用下述串長編碼法進(jìn)行編碼： 1 . 09 . 010U信源輸出序列 0串長度（或中間數(shù)字）