信息論與編碼理論第4章無失真信源編碼習(xí)題解答20071202

1、信息論與編碼理論 # 信息論與編碼理論 #第4章無失真信源編碼習(xí)題及其參考答案4-1有一信源，它有六個可能的輸出，其概率分布如下表所示，表中給出了對應(yīng)的碼A、B、C、D、E和F（1）求這些碼中哪些是唯一可譯碼；（2）求哪些碼是及時碼；消息概率ABCDEFS1/200000000S21/400101101010100S31/160100111101101100101S1/160110111111011101101110S51/16100011111111010111110111S61/1610101111111111011011111011（3）對所有唯一可譯碼求出其平均碼長l。_X，P(X)_

2、4-2設(shè)信源ss12p(s)p(s)12s6p(s)6可譯編碼，其對應(yīng)的碼長為（人）=（1，1，2,3,2,3），求_X，p(X)_4-3設(shè)信源為sss123111248sss64561113264藝p（s）1。對此次能源進行m元唯一ii=1m值的最好下限。（提示：用kraft不等式），編成這樣的碼：（000,001,010，011，100，101，110，111）。求（1）信源的符號熵；（2）這種碼的編碼效率；（3）相應(yīng)的仙農(nóng)碼和費諾碼。4-4求概率分布為（3,|,1,15，1|）信源的二元霍夫曼編碼。討論此碼對于概率分布為（5,5,5,5,5）的信源也是最佳二元碼。4-5有兩個信源X和Y如

3、下:信息論與編碼理論 # 信息論與編碼理論 # #p(Y)Xsssssss,1234567p(X)0.200.190.180.170.150.100.01sssssssss,1234567890.490.140.140.070.070.040.020.020.01信息論與編碼理論 #（1）用二元霍夫曼編碼、仙農(nóng)編碼以及費諾編碼對信源X和Y進行編碼，并計算其平均碼長和編碼效率；（2）從X,Y兩種不同信源來比較三種編碼方法的優(yōu)缺點。4-6設(shè)二元霍夫曼碼為（00，01，10，11)和（0，10，110，111)，求出可以編得這樣霍夫曼碼的信源的所有概率分布。x1ssssssss4-7設(shè)信源為,123

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

5、進行二元等長編碼，這幅圖像共需要多少個二元符號描述？（2）若考慮圖像的統(tǒng)計特性，求這幅圖像的信源熵，并對每個灰度級進行二元霍夫曼編碼，問平均每個像素需用多少二元符號表示。4-10在MPEG中為了提高數(shù)據(jù)壓縮比，采用了方法。運動補償與運行估計減少時域冗余與空間冗余信息論與編碼理論 # #信息論與編碼理論 # #幀內(nèi)圖像數(shù)據(jù)與幀間圖像數(shù)據(jù)壓縮D.向前預(yù)測與向后預(yù)測信息論與編碼理論 4-11JPEG中使用了熵編碼方法。A.統(tǒng)計編碼和算術(shù)編碼B.PCM編碼和DPCM編碼C.預(yù)測編碼和變換編碼D.哈夫曼編碼和自適應(yīng)二進制算術(shù)編碼4-12簡述常用信息編碼方法的兩類。4-13簡述等長編碼和變長編碼的特點，并

6、舉例說明。4-14已知信源X=x1=0.25,x2=0.25,x3=0.2,x4=0.15,x5=0.10,x6=0.05，試對其進行Huffman編碼。4-15已知信源X=x1=1/4,x2=3/4,若x1=1,x2=0,試對1011進行算術(shù)編碼。4-16離散無記憶信源發(fā)出A,B,C三種符號，其概率分布為5/9,1/3,1/9，應(yīng)用算術(shù)編碼方法對序列CABA進行編碼,并對結(jié)果進行解碼。4-17給定一個零記憶信源，已知其信源符號集為A=a1,a2=0,1,符號產(chǎn)生概率為P(aJ=1/4,P(a2)=3/4。對二進制序列11111100,求其二進制算術(shù)編碼碼字。4-18有四個符號a,b,c,d構(gòu)

7、成的簡單序列S=abdac，各符號及其對應(yīng)概率如表所示。應(yīng)用算術(shù)編碼方法對S進行編碼，并對結(jié)果進行解碼。符號符號概率Pia1/2b1/4c1/8d1/84-19簡述游程編碼的思想和方法。4-20簡述JEPG算法的主要計算步驟，并詳細說明每個步驟。4-21設(shè)二元信源的字母概率為P(0)=1/4,P(1)=3/4。若信源輸出序列為1011011110110111對其進行算術(shù)編碼并計算編碼效率。對其進行LZ編碼并計算編碼效率。4-22設(shè)有二元信源符號集，輸入信源符號序列為aaaaaaaaaaaa,求其序列的字典編碼。1010001101104-23一個離散記憶信源A=a,b,c,發(fā)出的字符串為bcc

8、acbcccccccccccaccca。試用LZ算法對序列編碼,給出編碼字典及發(fā)送碼序列。4-24用LZ算法對信源A=a,b,c編碼，其發(fā)送碼字序列為：2,3,3,1,3,4,5,10,11,6,10。試據(jù)此構(gòu)建譯碼字典并譯出發(fā)送序列。習(xí)題參考答案4-1：A、B、C、E編碼是唯一可譯碼。A、C、E碼是及時碼。唯一可譯碼的平均碼長如下：Aiii1廠p(s)l3X(2，4，22，11-，召3碼元/信源符號241616161661111111P(s)lX1X2+X3+X4+X5+X62125碼元/信源符號Bii2416161616i161111111p(s)1X1+X2+X3+X4+X5+X62.1

9、25碼元/信源符號Cii2416161616i161V1c/1111、/C一，亠、左1乙p(s)1X1+tx2+(+)X42碼兀/信源符號Eii2416161616i14-3：(1)工一bit/符(2)平均碼長：611111111、一亠、1p(S)13X(,，,，)3碼元/信源符號ii248163264128128i1所以編碼效率：H(X)0.66151(3)仙農(nóng)編碼：信源符號S符號概率P(S)加概率碼長碼字S12010S242210S333110S416741110S513215岳511110S616431藥6111110S71128636471111110S8112812712871111

10、111費諾碼：4-5：(1)霍夫曼編碼對X的霍夫曼編碼如下:信源符號Si符號概率p(S)i編碼過程碼長碼字S10.20.20.260.350.390.610102S20.190.190.20.260.350/F0.391112S30.180.180.190.20/0.26z10003S40.170.170.1800.1910013S50.150.1500.1710103S60.10吹10.11101104S70.0101114l0.2x2,0.19x2,0.18x3,0.17x3,0.15x3,0.1x4,0.01x4=2.72碼元/信源符號H(X)工plogp2.61碼元/符號iii1H(X

11、)l2.720-9596信息論與編碼理論 # #信息論與編碼理論 Y的二元霍夫曼編碼：信源符號Si符號概率p(S)i編碼過程碼字碼長S10.490.490.490.490.490.490.490.51011S20.140.140.140.140.14f0.23/0.2800.4910003S30.140.140.140.140.140.14/00.2310013S40.070.070.070.09r0.1400.14101004S50.070.070.07/0.07.0.09101014S60.040.04/0.0500.07101114S70.020.03X0.041011015S80.02

12、/0.0210110006S90.0110110016平均碼長：l0.49x10.14x3x20.07x4x20.04x40.02x50.02x60.01x6=2.23碼元/信源符H(Y)Xplogp2.31碼元/符號iii1編碼效率：,H(Y)l2.31一_0.99142.33(2)仙農(nóng)編碼：對X的仙農(nóng)編碼:信源符號Si符號概率p(S)i和概率碼長碼字S10.203000S20.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.9971111110平均碼長：l0.2x3,0.19x3,0.18x3

13、,0.17x3,0.15x3,0.1x4,0.01x7=3.14碼元/信源符-H(X)2618312對Y的仙農(nóng)編碼:信源符號Si符號概率p(S)i和概率碼長碼字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.9971111110平均編碼長度：/0.49x2,0.14x2,0.07x4x2,0.04x5,0.02x6x2,0.02x6,0.01x7=2.89碼元/信源符編碼效率：n=H(Y)l2

14、.31=0.79932.89信息論與編碼理論 # #信息論與編碼理論 # #(3)費諾編碼：對X的費諾編碼：信源符號Si符號概率p(S)i編碼碼字碼長S10.200002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.01111114平均編碼長度：l=0.2x2+0.19x3+0.18x3+0.17x2+0.15x3+0.1x4+0.01x4=2.74碼元/信源符號編碼效率：n=H:)lIS9526信息論與編碼理論 # #信息論與編碼理論 # #對Y進行費諾編碼：信息論與編碼理論 信源符號Si符號概率p(S)i編碼碼

15、字碼長S10.49001S20.14001003S30.1411013S40.070011004S50.071111014S60.041011104S70.0210111105S80.021101111106S90.0111111116平均碼長：l0.49x1,0.14x2x3,0.07x4x2,0.04x4,0.02x5,0.02x6,0.01x6=2.33碼元/信源符編碼效率：=日J=0.9914l由三種編碼的編碼效率可知：仙農(nóng)編碼的編碼效率為最低，平均碼長最長；霍夫曼編碼的編碼長度最短，編碼效率最高，費諾碼居中。4-7：由三元編碼方式可知：R=DB=RD-1(K2)+2由本題可知D=3,

16、K=8,R=2，所以，首先合并最后兩個信源概率，其中一種編碼方式如下:信源符號Si符號概率p(S)i編碼碼字碼長S10.40.40.40.4001S20.20.20.2*0.4121S30.10.10.20.22112S40.10.10.11122S50.05/0.10.121013S60.050.0511023S70.050.05210004S80.051100144-16：符號UiP(Ui)F(ui)碼長一進制表示CC198940.1110ACA5818950.11100BCAB524367372960.111011ACABA567390.1110110002187729信息論與編碼理論

17、#信息論與編碼理論 # 符號分布概率：F(u4)=673729673-8729-9L9第二字符是A=0.36280,59丿0.3628-0“58,=0.6530el5-1L99丿9第二字符是B0.6530-5959=0.3628e所以譯碼結(jié)果是：CABA0,5符號概率分布區(qū)間00.25【0,0.25)10.75【0.25,1)4-21：(1)由題目可知信源符號為1011011110110111P(s=)=p(1)12p(0)4=(1)12(1)4=0.0001237信息論與編碼理論 #算術(shù)碼的碼長l-logp(s)13由序列S的分布函數(shù)F(S)由二元整樹圖來計算：F(S)=1-p(11)p(10111)p(1011011111)p(1011011110111)p(1011011110110111)=1(4)22-A434信息論與編碼理論 # #0.35114030.0101100110011所以算術(shù)編碼為：010000110011平均碼長及編碼效率如下：-13l0.8125碼元/符號16H(S)plogp(1)p(0)