信息論第五章答案

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

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

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

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

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

6、：序列序列長(zhǎng)度Li序列概率pi數(shù)字二元碼長(zhǎng)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） , 此值表示無(wú)記憶二元信源采用游程長(zhǎng)度編碼后每個(gè)二元信源需要的平均碼長(zhǎng)。，（5）4位信源符號(hào)的聯(lián)合概率、Huffman編碼及碼

7、長(zhǎng)如下表：（碼字可以不同，但碼長(zhǎng)一樣） S4P(Si)碼字Wi碼長(zhǎng)LiS4P(s)碼字Wi碼長(zhǎng)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，求它的符號(hào)熵。用三個(gè)符號(hào)合成一個(gè)來(lái)編寫(xiě)二進(jìn)制哈夫曼碼，求新符號(hào)的平均碼字長(zhǎng)度和編碼效率。解：平穩(wěn)時(shí)馬爾科夫狀態(tài)的概率：解得：一階馬氏信源的熵：S1S2S3P(S1S2S3)LiWiS1S2S3P(S1S2S3)LiWi00048/1251101121/2504001111149/250300011021/2504010000112/12530110109/25050101010012/125400101013/1255010115.7 對(duì)題5.6的信源進(jìn)行

9、游程編碼。若“0”游程長(zhǎng)度的截止值為16，“1”游程長(zhǎng)度的截止值為8，求編碼效率。解：一階馬氏信源的熵同上題，二元平穩(wěn)一階記憶序列“0”游程的長(zhǎng)度概率：二元平穩(wěn)一階記憶序列“1”游程的長(zhǎng)度概率：“1”游程長(zhǎng)度的熵：同理，“0”游程長(zhǎng)度的熵：分別對(duì)“0”和“1”游程序列進(jìn)行Huffman編碼，并分別計(jì)算出它們的編碼效率?！?”游程序列的長(zhǎng)度、對(duì)應(yīng)得概率、Huffman編碼的二元碼長(zhǎng)及碼字序列序列長(zhǎng)度Li序列概率pi數(shù)字二元碼長(zhǎng)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”游程序列的長(zhǎng)度、對(duì)應(yīng)得概率、Huffman編碼的二元碼長(zhǎng)及碼字：序列序列長(zhǎng)度Ki序列概率pi數(shù)字二元碼長(zhǎng)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可見(jiàn)滿(mǎn)足，這里的“0”游程編碼效率高，因?yàn)橛纬涕L(zhǎng)度長(zhǎng)，而“1”游程編碼效率受游程的長(zhǎng)度限制顯得比“0”游程編碼效率略低一些，因此整體的編碼效率介于兩者之間。5.8 選擇幀長(zhǎng)N = 63(1) 對(duì)00100000,00000000,00000000,00000000,01000000,00000000,00000000,0000000編L-D碼；(2) 對(duì)10000100,00101100,00000001,00100001,01001000,00000111,00000100,0000001編L-D碼再譯碼；(3) 對(duì)0000000000000000000000000000000000

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

14、出信息位的位置值是n1=3，n2=34(2) 對(duì)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；幀長(zhǎng)N=63。Q位和T位需要的二進(jìn)制自然碼位數(shù)分別是：所以，L-D編碼結(jié)果：001111，1010110,11111101,01111111,10110101,00011000,11111110 解碼：已知N=63，故前7位為Q的自然碼表示，所以Q=15；后47位為T(mén)的自然碼表示，得T= 95646769289470(a) 尋找某一值K，使 得：K=62(b)令，Q=Q-1重復(fù)步驟（a）（b）每次尋找出一個(gè)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)