信息論與編碼理論第4章無失真信源編碼習題解答(共10頁)

1、精選優(yōu)質文檔-傾情為你奉上第4章 無失真信源編碼習題及其參考答案4-1 有一信源，它有六個可能的輸出，其概率分布如下表所示，表中給出了對應的碼A、B、C、D、E和F（1）求這些碼中哪些是唯一可譯碼；（2）求哪些碼是及時碼；（3）對所有唯一可譯碼求出其平均碼長。消息概率ABCDEFS11/200000000S21/400101101010100S31/160100111101101100101S41/160110111111011101101110S51/16100011111111010111110111S61/1610111011111011 4-2 設信源。對此次能源進行m元唯一可譯編碼，

2、其對應的碼長為（l1,l2,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式） 4-3設信源為，編成這樣的碼：（000，001，010，011，100，101，110，111）。求（1）信源的符號熵；（2）這種碼的編碼效率；（3）相應的仙農(nóng)碼和費諾碼。4-4求概率分布為信源的二元霍夫曼編碼。討論此碼對于概率分布為的信源也是最佳二元碼。4-5有兩個信源X和Y如下：（1）用二元霍夫曼編碼、仙農(nóng)編碼以及費諾編碼對信源X和Y進行編碼，并計算其平均碼長和編碼效率；（2）從X，Y兩種不同信源來比較三種編碼方法的優(yōu)缺點。4-6設二元霍夫曼碼為（00，01，10，11）和（0，

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

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

5、Xx1=0.25,x2=0.25,x3=0.2,x4=0.15,x5=0.10,x6=0.05，試對其進行Huffman編碼。4-15已知信源Xx11/4，x23/4，若x11,x2，試對1011進行算術編碼。4-16離散無記憶信源發(fā)出A，B，C三種符號，其概率分布為5/9，1/3，1/9，應用算術編碼方法對序列CABA進行編碼，并對結果進行解碼。4-17給定一個零記憶信源，已知其信源符號集為A=a1，a20，1，符號產(chǎn)生概率為P(a1)1/4，P(a2)3/4。對二進制序列，求其二進制算術編碼碼字。4-18有四個符號a，b，c，d構成的簡單序列Sabdac，各符號及其對應概率如表所示。應用算

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

7、=a,b,c編碼，其發(fā)送碼字序列為：2，3，3，1，3，4，5，10，11，6，10。試據(jù)此構建譯碼字典并譯出發(fā)送序列。習題參考答案4-1：(1) A、B、C、E編碼是唯一可譯碼。(2) A、C、E碼是及時碼。(3) 唯一可譯碼的平均碼長如下： 碼元/信源符號碼元/信源符號碼元/信源符號碼元/信源符號4-3：(1)(2) 平均碼長：碼元/信源符號所以編碼效率：(3) 仙農(nóng)編碼：信源符號符號概率加概率碼長碼字S1010S2210S33110S441110S5511110S66S77S87費諾碼：信源符號符號概率編碼碼字碼長S1001S210102S3101103S41011104S5101111

8、05S6106S7107S8174-5：(1) 霍夫曼編碼：對X的霍夫曼編碼如下：信源符號符號概率編碼過程碼長碼字S10.20.20.260.350.390.610102S20.190.190.20.260.3500.391112S30.180.180.190.200.2610003S40.170.170.1800.1910013S50.150.1500.1710103S60.10010.11101104S70.0101114碼元/信源符號 碼元/符號Y的二元霍夫曼編碼：信源符號符號概率編碼過程碼字碼長S10.490.490.490.490.490.490.490.51011S20.140.1

9、40.140.140.140.230.2800.4910003S30.140.140.140.140.140.1400.2310013S40.070.070.070.090.1400.14101004S50.070.070.070.0700.09101014S60.040.040.0500.07101114S70.020.0300.041011015S80.0200.0216S90.0116平均碼長：碼元/信源符碼元/符號編碼效率：(2) 仙農(nóng)編碼：對X的仙農(nóng)編碼：信源符號符號概率和概率碼長碼字S10.203000S20.190.23001S30180.393011S40.170.573100

10、S50.150.743101S60.100.8941110S70.010.997平均碼長：碼元/信源符對Y的仙農(nóng)編碼：信源符號符號概率和概率碼長碼字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956S80.020.976S90.010.997平均編碼長度：碼元/信源符編碼效率：(3) 費諾編碼：對X的費諾編碼：信源符號符號概率編碼碼字碼長S10.200002S20.19100103S30.1810113S40.1710102S50.15101103S60.

11、101011104S70.01111114平均編碼長度：碼元/信源符號編碼效率：對Y進行費諾編碼：信源符號符號概率編碼碼字碼長S10.49001S20.141001003S30.1411013S40.0710011004S50.07111014S60.041011104S70.0210111105S80.02106S90.0116平均碼長：碼元/信源符號編碼效率：(4) 由三種編碼的編碼效率可知：仙農(nóng)編碼的編碼效率為最低，平均碼長最長；霍夫曼編碼的編碼長度最短，編碼效率最高，費諾碼居中。4-7： 由三元編碼方式可知：R=DB=RD-1(K2)+2由本題可知D=3，K=8，R=2，所以，首先合并

12、最后兩個信源概率，其中一種編碼方式如下：信源符號符號概率編碼碼字碼長S10.40.40.40.4001S20.20.20.20.4121S30.10.10.200.22112S40.10.10.11122S50.050.100.121013S60.050.0511023S70.0500.05210004S80.051100144-16：符號uiP(ui)F(ui)碼長二進制表示CC40.1110ACA50.11100BCAB60.ACABA90.符號分布概率：符號概率分布區(qū)間ABC譯碼：所以譯碼結果是：CABA4-21：(1)符號概率分布區(qū)間00.2510.75由題目可知信源符號為：1011 0111 1011 0111算術碼的碼長由序列S的分布函數(shù)F（S）由二元整樹圖來計算： 所以算術編碼為：0100 0011 0011平均碼長及編碼效率如下：碼元/符號 bit/符號(2)由于信源符號集中共有2個元素，因此只需要位二進制數(shù)