信息論第五章答案

1、5.1 設(shè)信源(1) 求信源熵H(X)；(2) 編二進制香農(nóng)碼；(3) 計算平均碼長和編碼效率。解：(1)(2)xip(xi)pa(xi)ki碼字x10.203000x20.190.23001x30.180.393011x40.170.573100x50.150.743101x60.10.8941110x70.010.9971111110(3)5.2 對信源編二進制費諾碼，計算編碼效率。解：xip(xi)編碼碼字kix10.200002x20.19100103x30.1810113x40.1710102x50.15101103x60.11011104x70.011111145.3 對信源編二進

2、制和三進制哈夫曼碼，計算各自的平均碼長和編碼效率。解：二進制哈夫曼碼：xip(xi)編碼碼字kis61s50.610s40.391s30.350s20.261x10.20102x20.191112x30.1800003x40.1710013x50.1500103s10.111x60.1001104x70.01101114三進制哈夫曼碼：xip(xi)編碼碼字kis31s20.540s10.261x10.2221x20.190002x30.181012x40.172022x50.150102x60.11112x70.0121225.4 設(shè)信源(1) 求信源熵H(X)；(2) 編二進制香農(nóng)碼和二進

3、制費諾碼；(3) 計算二進制香農(nóng)碼和二進制費諾碼的平均碼長和編碼效率；(4) 編三進制費諾碼；(5) 計算三進制費諾碼的平均碼長和編碼效率；解：(1)=127/64 bit/symbol (2)二進制香農(nóng)碼：xip(xi)pa(xi)ki碼字x10.5010x20.250.5210x30.1250.753110x40.06250.87541110x50.031250.9375511110x60.0156250.968756111110x70.00781250.98437571111110x80.00781250.992187571111111二進制費諾碼：xip(xi)編碼碼字kix10.50

4、01x20.2510102x30.125101103x40.06251011104x50.0312510111105x60.015625101111106x70.00781251011111107x80.0078125111111117(3)香農(nóng)編碼效率：費諾編碼效率：(4)xip(xi)編碼碼字kix10.5001x20.25111x30.12520202x40.06251212x50.03125202203x60.01562512213x70.00781252022204x80.0078125122214(5)5.5 設(shè)無記憶二進制信源先把信源序列編成數(shù)字0，1，2，8，再替換成二進制變長

5、碼字，如下表所示。(1) 驗證碼字的可分離性；(2) 求對應(yīng)于一個數(shù)字的信源序列的平均長度；(3) 求對應(yīng)于一個碼字的信源序列的平均長度；(4) 計算，并計算編碼效率；(5) 若用4位信源符號合起來編成二進制哈夫曼碼，求它的平均碼長，并計算編碼效率。序列數(shù)字二元碼字10100001110010013101000013101100001411000000015110100000016111000000001711110000000080解：（1）滿足Kcraft不等式：；由碼樹圖可見，沒有一個碼字是其它碼字的前綴，碼字均在樹的終結(jié)點。所以碼字可分離。 （2）序列長度、序列概率及二元碼長如下表所示

6、：序列序列長度Li序列概率pi數(shù)字二元碼長Li二元碼字110.10410000120.1×0.914100100130.1×0.92341010000140.1×0.933410110000150.1×0.9444110000000160.1×0.95541101000000170.1×0.966411100000000180.1×0.977411110000000080.98810 （3） （4） , 此值表示無記憶二元信源采用游程長度編碼后每個二元信源需要的平均碼長。，（5）4位信源符號的聯(lián)合概率、Huffman編碼及碼

7、長如下表：（碼字可以不同，但碼長一樣） S4P(Si)碼字Wi碼長LiS4P(s)碼字Wi碼長Li00000.65610110010.00811111010700010.0729110310100.00811111011700100.0729100311000.00811111110701000.0729101301110.0009111111100910000.07291110410110.0009111111101900110.0081111110611010.0009111111110901010.00811111000711100.000111111111101001100.00811

8、111001711110.00011111111111105.6 有二元平穩(wěn)馬氏鏈，已知p(0/0) = 0.8，p(1/1) = 0.7，求它的符號熵。用三個符號合成一個來編寫二進制哈夫曼碼，求新符號的平均碼字長度和編碼效率。解：平穩(wěn)時馬爾科夫狀態(tài)的概率：解得：一階馬氏信源的熵：S1S2S3P(S1S2S3)LiWiS1S2S3P(S1S2S3)LiWi00048/1251101121/2504001111149/250300011021/2504010000112/12530110109/25050101010012/125400101013/1255010115.7 對題5.6的信源進行

9、游程編碼。若“0”游程長度的截止值為16，“1”游程長度的截止值為8，求編碼效率。解：一階馬氏信源的熵同上題，二元平穩(wěn)一階記憶序列“0”游程的長度概率：二元平穩(wěn)一階記憶序列“1”游程的長度概率：“1”游程長度的熵：同理，“0”游程長度的熵：分別對“0”和“1”游程序列進行Huffman編碼，并分別計算出它們的編碼效率?！?”游程序列的長度、對應(yīng)得概率、Huffman編碼的二元碼長及碼字序列序列長度Li序列概率pi數(shù)字二元碼長Li二元碼字01P1/00211002P0/0 P 1/0130010003P0/02 P 1/02301100004P0/03 P 1/0331010000,05P0/0

10、4 P 1/04400010000,006P0/05 P 1/05401010000,0007P0/06 P 1/06410010000,00008P0/07 P 1/075000000000,0000,09P0/08 P 1/085010010000,0000,0010P0/09 P 1/095100010000,0000,00011P0/010 P 1/0A60000100000,0000,000012P0/011 P 1/0B61000000000,0000,0000,013P0/012 P 1/0C61000010000,0000,0000,0014P0/013 P 1/0D70000

11、1100000,0000,0000,00015P0/014 P 1/0E700001110000,0000,0000,000016P0/015F501000“1”游程序列的長度、對應(yīng)得概率、Huffman編碼的二元碼長及碼字：序列序列長度Ki序列概率pi數(shù)字二元碼長Ki二元碼字11P0/10201112P0/1 P 1/112101113P0/1 P 1/123300111114P0/1 P 115P0/1 P 1/144400011111,116P0/1 P 1/155411101111,1117P0/1 P 1/166411111111,11118P 1/1774

12、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) 對0000000000000000000000000000000000

13、000000000000000000000000000000編L-D碼；(4) 對10100011010111000110001110100110000111101100101000110101011010010編L-D碼；(5) 對上述結(jié)果進行討論。解：（1）本幀內(nèi)信息位數(shù)Q=2；各信息位位置值n1=3，n2=34；幀長N=63。Q位和T位需要的二進制自然碼位數(shù)分別是：所以，L-D編碼結(jié)果：000010,01000010010解碼：已知N=63，故前6位為Q的自然碼表示，所以Q=2；后11位為T的自然碼表示，得T=530尋找某一值K，使得：K=33再令，再次尋找某一值L，使得：L=2所以解碼

14、出信息位的位置值是n1=3，n2=34(2) 對10000100,00101100,00000001,00100001,01001000,00000111,00000100,00000010編L-D碼本幀內(nèi)信息位數(shù)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位需要的二進制自然碼位數(shù)分別是：所以，L-D編碼結(jié)果：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重復(fù)步驟（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)