1、第4章無失真信源編碼習(xí)題及其參考答案4-1有一信源，它有六個(gè)可能的輸出，其概率分布如下表所示，表中給出了對應(yīng)的碼A、B、C、D、E和F(1)求這些碼中哪些是唯一可譯碼；(2)求哪些碼是及時(shí)碼；(3)對所有唯一可譯碼求出其平均碼長。消息概率ABCDEFS11/200000000S21/400101101010100S31/160100111101101100101S41/160110111111011101101110S51/16100011111111010111110111S61/1610101111111111011011111011Xsss64-2設(shè)信源|Zp(s)=1。對此次能源進(jìn)行m

2、兀唯一>(x)j1p(s)p(s2)rnpg)一i可譯編碼，其對應(yīng)的碼長為di,l2,-J)=(1,1,2,3,2,3),求m值的最好下限。(提示：用kraft不等式)4-3設(shè)信源為bX)s214S318s4s5s6s71111163264128SI1128,編成這樣的碼:(000,001,010,011,100,101,110,111)。求(1)信源的符號嫡；(2)這種碼的編碼效率；(3)相應(yīng)的仙農(nóng)碼和費(fèi)諾碼。，、八一11124-4求概率分布為(一，一，一,3551515)言源的二元霍夫曼編碼。討論此碼對于概率分布為(1,1,1,1,1)的信源也是最佳二元碼。555554-5有兩個(gè)信源

3、X和Y如下：X_S1s2s3s4p(X)1(0.200.190.180.17s5s6s70.150.100.01；Y1_；5s2s3s4與%(丫)_卜.490.140.140.070.07s6s70.040.02s840.020.01X和Y進(jìn)行編碼,f算其平均碼長和(1)用二元霍夫曼編碼、仙農(nóng)編碼以及費(fèi)諾編碼對信源編碼效率；(2)從X,Y兩種不同信源來比較三種編碼方法的優(yōu)缺點(diǎn)。4-6設(shè)二元霍夫曼碼為(00,01,10,霍夫曼碼的信源的所有概率分布。11)和(0,10,110,111),求出可以編得這樣碼。4-7設(shè)信源為X5!p(X)10.40.2S30.1s4S50.10.05s6s7&quo

4、t;,求其三元霍夫曼編0.050.050.054-8若某一信源有N個(gè)符號，并且每個(gè)符號等概率出現(xiàn)，對這個(gè)信源進(jìn)行二元霍夫曼編碼，問當(dāng)N=2i和N=2i+1(i是正整數(shù))時(shí)，每個(gè)碼值的長度是多少？平均碼長是多少？8級，如下表所示。表中數(shù)字為相應(yīng)像素4-9現(xiàn)有一幅已離散量化后的圖像，圖像的灰度量化分成上的灰度級。1111111111111111111111111111111111111111222222222222222223333333333444444444455555556666667777788888(1)不考慮圖像的任何統(tǒng)計(jì)特性，對圖像進(jìn)行二元等長編碼，這幅圖像共需要多少個(gè)二元符號描述？

5、(2)若考慮圖像的統(tǒng)計(jì)特性，求這幅圖像的信源嫡，并對每個(gè)灰度級進(jìn)行二元霍夫曼編碼，問平均每個(gè)像素需用多少二元符號表示。4-10在MPEG中為了提高數(shù)據(jù)壓縮比，采用了方法。A.運(yùn)動補(bǔ)償和運(yùn)行估計(jì)B.減少時(shí)域冗余和空間冗余C.幀內(nèi)圖像數(shù)據(jù)和幀間圖像數(shù)據(jù)壓縮D.向前預(yù)測和向后預(yù)測4-11JPEG中使用了嫡編碼方法。4-124-13A.統(tǒng)計(jì)編碼和算術(shù)編碼C.預(yù)測編碼和變換編碼簡述常用信息編碼方法的兩類。簡述等長編碼和變長編碼的特點(diǎn)，并舉例說明。B.PCM編碼和DPCM編碼D.哈夫曼編碼和自適應(yīng)二進(jìn)制算術(shù)編碼4-14已知信源X=X1=0.25,X2=0.25,X3=0.2,X4=0.15,X5=0.10

6、,X6=0.05,試對其進(jìn)行Huffman編碼。4-15已知信源X=x1=1/4,x2=3/4,若x1=1,x2=0,試對1011進(jìn)行算術(shù)編碼。4-16離散無記憶信源發(fā)出A,B,C三種符號，其概率分布為5/9,1/3,1/9,使用算術(shù)編碼方法對序列CABA進(jìn)行編碼，并對結(jié)果進(jìn)行解碼。4-17給定一個(gè)零記憶信源，已知其信源符號集為A=a1,32=0,1,符號產(chǎn)生概率為P(a1)=1/4,P(a2)=3/4。對二進(jìn)制序列11111100,求其二進(jìn)制算術(shù)編碼碼字。4-18有四個(gè)符號a,b,c,d構(gòu)成的簡單序列S=abdac,各符號及其對應(yīng)概率如表所示。使用算術(shù)編碼方法對S進(jìn)行編碼，并對結(jié)果進(jìn)行解碼。

7、符號符號概率Ra1/2b1/4c1/8d1/84-19簡述游程編碼的思想和方法。4-20簡述JEPG算法的主要計(jì)算步驟，并詳細(xì)說明每個(gè)步驟。4-21設(shè)二元信源的字母概率為P(0)=1/4,P(1)=3/4。若信源輸出序列為10111(a) 對其進(jìn)行算術(shù)編碼并計(jì)算編碼效率。(b) 對其進(jìn)行LZ編碼并計(jì)算編碼效率。4-22設(shè)有二元信源符號集，輸入信源符號序列為a1a0a1a0a0a0a1a1a0a1a1a0|,求其序列的字典編碼。4-23一個(gè)離散記憶信源A=a,b,c,發(fā)出的字符串為bccacbcccccccccccaccca。試用LZ算法對序列編碼,給出編碼字典及發(fā)送碼序列。4-24用LZ算法對

8、信源A=a,b,c編碼，其發(fā)送碼字序列為：2,3,3,1,3,4,5,10,11,6,10。試據(jù)此構(gòu)建譯碼字典并譯出發(fā)送序列。習(xí)題參考答案4-1:(1) A、B、C、E編碼是唯一可譯碼。(2) A、C、E碼是及時(shí)碼。_61a='p(s)lii1(3)唯一可譯碼的平均碼長如下：)=3碼元/信源符號:3(1.1.±.±.±.±24161616166二p(s)lii1=1123451616161+x62.125碼兀/信源將節(jié)1661C=ZP(si)lii1111111二一父1+父2+*3+乂4+x5+x6=2.125碼兀/信源付節(jié)2416161616_

9、617=Ep(s)ii4111111=_父1+_父2+(+)x4=2碼兀/信源符號24161616164-3:8H(X)=-p(xj10gp(xi)i=11111111111=-log-log-log-log一一一log22448816163232111111-log-log-log6464128128128128.634=1bit/符64平均碼長：l=Ep(si)li=3父(一十一十一十十十十+)=3碼兀/信源符號y248163264128128所以編碼效率：=旦3=0.6615l(2)仙農(nóng)編碼:信源符號Si符號概率p(Si)加概率碼長碼字Si12010S21412210S383431101

10、7S416841110S51321516511110S616431326111110S7163712864S811281271287費(fèi)諾碼:信源符號Si符號概率p(Si)編碼碼字碼長Si12001S21410102S318101103S41161011104S513210111105S6164101111106S71128107S81128174-5:霍夫曼編碼：對X的霍夫曼編碼如下:信源符號Si符號概率P(S)編碼過程碼長碼字Si0.20.2r0.260.350.390.61.0102S20.190.190.20.2600.35_0/尸0.391112S30.180.180.190.20/0

11、.2610003S40.170.170.18I100.1910013S50.150.1500.17110103S60.1010.11101104S70.0101114l=0.2父2+0.19父2+0.18父3+0.17父3+0.15父3+0.1父4+0.01父4=2.72碼元/信源符號7H(X)=£Pi10gpi=2.61碼元/符號i1=3=型=0.95962.72Y的二元霍夫曼編碼:信源符號Si符號概率P(Si)編碼過程碼字碼長S10.4940.490.49/0.4920.49/0.49/0.4900.51011S20.140.140.140.140.1400.230.280.49

12、10003S30.140.140.140.140.140.14,/00.2310013S40.070.070.07.0.09,0.1400.14101004S50.070.070.0700.07,分0.09101014S60.040.040.0500.07101114S70.02<0.030.041011015S80.02/0.0210110006S90.0110110016平均碼長：l=0.49父1+0.14父3父2+0.07x4x2+0,04x4+0,02x5+0,02x6+0.01父6=2.23碼元/信源符9H(Y)=£plogPi=2.31碼元/符號i44H(Y)2.3

13、1編碼效率：=M=0.9914l2.33(2)仙農(nóng)編碼：對X的仙農(nóng)編碼：信源符號S符號概率p(S)和概率碼長碼字S10.203000S20.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.997平均碼長：1=0,230,1930.1830.1730.1530.140,017=3.14碼元/信源符H(X)2.61=0.831213.14對Y的仙農(nóng)編碼：信源符號S符號概率p(S)和概率碼長碼字S10.490200S20.140.493011S30.140.633101S40.070.7741100S5

14、0.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.997平均編碼長度:=0.49m2+0.14=<2+0,07x4x2+0,04x5+0.02父6黑2+0.02黑6+0.01x7=2.89碼元/信源符H(Y)2.31編碼效率：n=07993l2.89費(fèi)諾編碼：對X的費(fèi)諾編碼:信源符號S符號概率p(Si)編碼碼字碼長S10.200002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.01111114平均編碼長度:1=0,2

15、20,1930.1830.1720.1530.140,014=2.74碼元/信源符號"力斗多H(X)2.61編碼效率："=0.9526l2.74對Y進(jìn)行費(fèi)諾編碼:信源符號Si符號概率p(S)編碼碼字碼長S10.49001S20.141001003S30.1411013S40.0710011004S50.07111014S60.041011104S70.0210111105S80.02101111106S90.0111111116平均碼長:l=0,49父1+0,14父2父3+0,07父4父2+0,04父4+0,02父5+0,02父6+0.01父6=2.33碼元/信源符編碼效率

16、：H(Y)2.31=0.99142.33(4)由三種編碼的編碼效率可知：仙農(nóng)編碼的編碼效率為最低，平均碼長最長；霍夫曼編碼的編碼長度最短，編碼效率最高，費(fèi)諾碼居中。4-7:由三元編碼方式可知：R=D-B=Rd-i(K-2)+2由本題可知D=3,K=8,R=2,所以，首先合并最后兩個(gè)信源概率，其中一種編碼方式如下:信源符號S符號概率p(S)編碼碼字碼長Si0.40.40.40.4001S20.20.20.200.4121S30.10.110.20.22112S40.10.10.11122S50.0540.1/0.121013S60.05i0.0511023S70.0500.05210004S80

17、.051100144-16:符號uiP(ui)F(ui)碼長一進(jìn)制表小CC198940.1110ACA5818950.11100Bcab524367372960.111011Acaba5218767372990.111011000符號分布概率:符號概率分布區(qū)間A5910，9；b13b,9C19對譯碼:F(u4)6737290.92928,1_9二第一字符是：C6738729。9=0.36280,518.99二第二字符是:A0.3628-0一581=0.6530wI-,一5119,9；9二第二字符是:Bcccc50.653059=0.36280,58_5一999.第二字符是：A所以譯碼結(jié)果是：C

18、ABA4-21:符號概率分布區(qū)間00.250,0.25)10.7510.25,1)由題目可知信源符號為:1011011110110111p(s=1011011110110111)12431214=p(1)p(0)4=()12()4-0.000123744算術(shù)碼的碼長l=-logp(s)=13由序列S的分布函數(shù)F(S)由二元整樹圖來計(jì)算：F(S)=1-p(11)-p(10111)-p(1011011111)-p(1011011110111)-p(1011011110110111)3234138123101331214=1一(R(G(G-(:)(G-(二)(二)一十(G444444444=0.3511403=0.0101100110011所以算術(shù)編碼為：010000110011平均碼長及編碼效率如下：-13一l=0.8125碼兀/符號16H(S)=p(1)logp(1)-p(0)l