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

習(xí)題課3.1試證明長度不超過N的D元不等長碼至多有D(DN－1)/(D－1)個(gè)碼字。[3.1的解答]長度等于k的D元碼字至多有Dk個(gè)，其中k=1~N。因此長度不超過N的D元碼字至多有6/27/201913.2以上是一個(gè)離散無記憶信源。若對(duì)其輸出的長為100的事件序列中含有兩個(gè)和更少個(gè)al的序列提供不同的碼字。(a)在等長編碼下,求二元碼的最短碼長N。(b)求錯(cuò)誤概率(誤組率)。[3.2的解答](a)長為L=100的事件序列中含有兩個(gè)和更少個(gè)al的序列,其個(gè)數(shù)為6/27/20192習(xí)題課(b)含有兩個(gè)和更少個(gè)al的序列擁有不同的碼字,它們的譯碼不會(huì)出現(xiàn)錯(cuò)誤。因此錯(cuò)誤概率(誤組率)不會(huì)超過“含有三個(gè)以上al的序列”出現(xiàn)的概率。而“含有三個(gè)以上al的序列”出現(xiàn)的概率等于6/27/20193習(xí)題課[3.2的注解]事實(shí)上,在對(duì)“含有兩個(gè)或更少個(gè)al的長為100的序列”提供不同的碼字之后,還有210-596=428個(gè)富余的碼字。這些富余的碼字如果提供給其中428個(gè)“含有恰好三個(gè)al的長為100的序列”,作為它們各自的不同碼字。則錯(cuò)誤概率不會(huì)超過6/27/20194習(xí)題課3.4對(duì)于有4個(gè)字母的離散無記憶源有兩個(gè)碼A和B，參看下表。試問:各碼是否滿足異字頭條件?是否為唯一可譯碼?當(dāng)收到1時(shí)得到多少關(guān)于字母a1的信息?當(dāng)收到1時(shí)得到多少關(guān)于信源的平均信息?字母概率碼A碼Ba10.411a20.30110a30.20011006/27/20195a0.100011000習(xí)題課6/27/20196[3.4的解答](a)碼A是異字頭碼。碼B不是異字頭碼。碼A和碼B都是唯一可譯碼。碼A的譯碼規(guī)則是:1就是一個(gè)碼字的末尾。碼B的譯碼規(guī)則是:1就是一個(gè)碼字的開頭。習(xí)題課6/27/20197(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.4×1+0.3×(1/2)+0.2×(1/3)+0.1×(1/4)=0.642。P(a1,且收到1)=P(a1)×P(收到1|a1)=0.4×1=0.4。所以I(a1；收到1)=log{0.4/(0.4×0.642)}=0.64155。(c)“當(dāng)收到1時(shí)得到多少關(guān)于信源的平均信息”,這是求信源隨機(jī)變量U與事件“收到1”的（半平均）互信息量。以碼A為例。I(收到1；U)=6/27/201983.6令離散無記憶信源如上。求對(duì)U（即U1）的最佳二元碼、平均碼長和編碼效率。求對(duì)U2

（即U1U2）的最佳二元碼、平均碼長和編碼效率。求對(duì)U3

（即U1U2U3

）的最佳二元碼、平均碼長和編碼效率。6/27/20199（U1U2U3

）~6/27/201910a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.0450.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.008（U1U2）的第一種最佳二元碼6/27/201911（U1U2）的第二種最佳二元碼6/27/201912（U1U2）的最佳二元碼平均碼長和編碼效率:6/27/2019136/27/2019146/27/2019156/27/2019166/27/2019176/27/2019186/27/2019196/27/2019206/27/2019216/27/2019226/27/2019236/27/2019246/27/2019256/27/2019266/27/2019276/27/2019286/27/2019296/27/2019306/27/2019316/27/2019326/27/2019336/27/201934（U1U2U3）的碼字6/27/201935a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a201000000001011011101000100110101011a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30010001110110001100111010110111111011111001100a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30011010011100011110111100111110010100001010100101100010111（U1U2U3）的最佳二元碼平均碼長:6/27/201936（U1U2U3）的最佳二元碼編碼效率:6/27/2019373.9設(shè)離散無記憶信源如上。試求其二元和三元Huffman碼。[3.9的解答]二元Huffman碼為:6/27/201938習(xí)題課三元Huffman碼為:6/27/201939習(xí)題課3.10設(shè)離散無記憶源試構(gòu)造兩組三元異字頭條件碼，其平均碼長相同，但具有不同的方差。哪一組更好些?為什么?[3.10的解答]兩組不同的三元異字頭條件碼如下:6/27/201940第一種三元異字頭碼（用Huffman編碼法）平均碼長為2,方差為0。6/27/201941第二種三元異字頭碼（用Huffman編碼法）平均碼長為1×0.2+2×0.6+3×0.2=2,方差為(1-2)2×0.2+(2-2)2×0.6+(3-2)2×0.2=0.4。6/27/201942習(xí)題課6/27/201943我們認(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ī)。因此第一種三元異字頭碼的編碼器更簡單。3.12設(shè)離散無記憶信源如上。若信源輸出序列為1011011110110111對(duì)其進(jìn)行算術(shù)編碼并計(jì)算編碼效率。（希望編程計(jì)算）對(duì)其進(jìn)行LZ編碼并計(jì)算編碼效率。[3.12的解答]（a）F(0)=0,F(1)=1/4,P(0)=1/4,P(1)=3/4。L=16,事件序u1u2u3u4u5u6u7u8u9u10u11u12u13u14u15u1610110111101101116/27/201944編碼迭代過程最終得到的H=P(u1)P(u2)…P(u16)=(1/4)4

(3/4)12=312/416

；log2(1/H)=log2(416/312)=32-12×log23=12.98057；因此n=13+1=1G=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)×(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/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)×(3/4)×(1/4)×(3/4)×(3/4)×(3/4)×(3/4)×(1/4)×(3/4)×(3/4)×(1/4)×(1/4)6/27/201945習(xí)題課=(0.01011001111001000010100111001111)2碼字為010110011110016/27/201946習(xí)題課6/27/201947（b）“分段”:(1011011110110111)→(1，0，11，01，111，011，0111)；“事件編號(hào)”依次為{0~0，1~1}；“段編號(hào)”依次為段1011011110110111段號(hào)001010011100101110111習(xí)題課6/27/201948“按段進(jìn)行編碼”:10110111101101110001000000110101011110011101習(xí)題課譯碼時(shí)，比特串“0001000000110101011110011101”按照碼字長度為3+1=4來分割碼字:0000，0001，0011，0101，0111，1001，1101碼字0001000000110101011110011101段號(hào)001010011100101110111段值10110111101101116/27/201949習(xí)題課編碼效率怎樣計(jì)算?該事件序列的碼字總長度為N=每段的碼字長度×段數(shù)=4×7=28。因此6/27/2019503.13設(shè)DMS為如上的概率分布。各ai相應(yīng)編成碼字0,10,110和111。試證明對(duì)足夠長的信源輸出序列,相應(yīng)的碼序列中0和1出現(xiàn)的概率相等。[3.13的證明]設(shè)有一個(gè)足夠長的信源輸出序列,因而相應(yīng)的碼序列也足夠長。在碼序列中隨機(jī)地取一個(gè)符號(hào)X,以下只需要證明P(X=0)=1/2。記Aj=“X是aj的碼字中的符號(hào)”,j=1~4。根據(jù)全概率公式,6/27/201951習(xí)題課6/27/201952習(xí)題課P(X=0|A1)=1；P(X=0|A2)=1