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

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

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進行編碼,f算其平均碼長和(1)用二元霍夫曼編碼、仙農編碼以及費諾編碼對信源編碼效率；(2)從X,Y兩種不同信源來比較三種編碼方法的優(yōu)缺點。4-6設二元霍夫曼碼為(00,01,10,霍夫曼碼的信源的所有概率分布。11)和(0,10,110,111),求出可以編得這樣碼。4-7設信源為X5!p(X)10.40.2S30.1s4S50.10.05s6s7&quo

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

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

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

7、符號符號概率Ra1/2b1/4c1/8d1/84-19簡述游程編碼的思想和方法。4-20簡述JEPG算法的主要計算步驟，并詳細說明每個步驟。4-21設二元信源的字母概率為P(0)=1/4,P(1)=3/4。若信源輸出序列為10111(a) 對其進行算術編碼并計算編碼效率。(b) 對其進行LZ編碼并計算編碼效率。4-22設有二元信源符號集，輸入信源符號序列為a1a0a1a0a0a0a1a1a0a1a1a0|,求其序列的字典編碼。4-23一個離散記憶信源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。試據此構建譯碼字典并譯出發(fā)送序列。習題參考答案4-1:(1) A、B、C、E編碼是唯一可譯碼。(2) A、C、E碼是及時碼。_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)仙農編碼:信源符號Si符號概率p(Si)加概率碼長碼字Si12010S21412210S383431101

10、7S416841110S51321516511110S616431326111110S7163712864S811281271287費諾碼:信源符號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)仙農編碼：對X的仙農編碼：信源符號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的仙農編碼：信源符號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費諾編碼：對X的費諾編碼:信源符號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進行費諾編碼:信源符號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)由三種編碼的編碼效率可知：仙農編碼的編碼效率為最低，平均碼長最長；霍夫曼編碼的編碼長度最短，編碼效率最高，費諾碼居中。4-7:由三元編碼方式可知：R=D-B=Rd-i(K-2)+2由本題可知D=3,K=8,R=2,所以，首先合并最后兩個信源概率，其中一種編碼方式如下:信源符號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)碼長一進制表小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所以譯碼結果是：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算術碼的碼長l=-logp(s)=13由序列S的分布函數F(S)由二元整樹圖來計算：F(S)=1-p(11)-p(10111)-p(1011011111)-p(1011011110111)-p(1011011110110111)3234138123101331214=1一(R(G(G-(:)(G-(二)(二)一十(G444444444=0.3511403=0.0101100110011所以算術編碼為：010000110011平均碼長及編碼效率如下：-13一l=0.8125碼兀/符號16H(S)=p(1)logp(1)-p(0)l