1、信息論與編碼理論-第4章無失真信源編碼-習題解答-20071202 信息論與編碼理論 第4章 無失真信源編碼 習題及其參考答案 4-1 有一信源，它有六個可能的輸出，其概率分布如下表所示，表中給出了對應的碼A、B、C、D、E和F （1）求這些碼中哪些是唯一可譯碼； （2）求哪些碼是及時碼； （3）對所有唯一可譯碼求出其平均碼長。 ?X?s1 4-2 設信源?p(s)P(X)?1s6? p(s2)?p(s6)? ? s2 ?p(s)?1。對此次能源進行m元唯一 i i?1 6 可譯編碼，其對應的碼長為（l1,l2,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式）

2、 ?s ?X?1 4-3設信源為?1? ?p(X)?2? （1）信源的符號熵； （2）這種碼的編碼效率； s2 14s3s411816s5132s6s7s8? ，編成這樣的碼：（000，001，111?64128128? 010，011，100，101，110，111）。求 （3）相應的仙農碼和費諾碼。 4-4求概率分布為(, 11122 信)源的二元霍夫曼編碼。討論此碼對于概率分布為3551515 11111 (,)的信源也是最佳二元碼。 55555 4-5有兩個信源X和Y如下： 1 信息論與編碼理論 s2s3s4s5s6s7?X?s1 ?p(X)?0.200.190.180.170.150

3、.100.01? ?s2s3s4s5s6s7s8s9?Y?s1?p(Y)?0.490.140.140.070.070.040.020.020.01? ? （1）用二元霍夫曼編碼、仙農編碼以及費諾編碼對信源X和Y進行編碼，并計算其平均碼長和編碼效率； （2）從X，Y兩種不同信源來比較三種編碼方法的優(yōu)缺點。 4-6設二元霍夫曼碼為（00，01，10，11）和（0，10，110，111），求出可以編得這樣 霍夫曼碼的信源的所有概率分布。 4-7設信源為?碼。 4-8若某一信源有N個符號，并且每個符號等概率出現(xiàn)，對這個信源進行二元霍夫曼編碼，問當N=2i和N=2i+1（i是正整數(shù)）時，每個碼值的長度是

4、多少？平均碼長是多少？ 4-9現(xiàn)有一幅已離散量化后的圖像，圖像的灰度量化分成8級，如下表所示。表中數(shù)字為相應像素上的灰度級。 （1）不考慮圖像的任何統(tǒng)計特性，對圖像進行二元等長編碼，這幅圖像共需要多少個二元符號描述？ （2）若考慮圖像的統(tǒng)計特性，求這幅圖像的信源熵，并對每個灰度級進行二元霍夫曼編碼，問平均每個像素需用多少二元符號表示。 4-10在MPEG中為了提高數(shù)據(jù)壓縮比，采用了_方法。 A運動補償與運行估計 B.減少時域冗余與空間冗余 C幀內圖像數(shù)據(jù)與幀間圖像數(shù)據(jù)壓縮 D.向前預測與向后預測 2 s2s3s4s5s6s7s8?X?s1 ?0.40.20.10.10.050.050.050.

5、05?，求其三元霍夫曼編 p(X)? 信息論與編碼理論 4-11 JPEG中使用了_熵編碼方法。 A.統(tǒng)計編碼和算術編碼 B.PCM編碼和DPCM編碼 C.預測編碼和變換編碼 D.哈夫曼編碼和自適應二進制算術編碼 4-12 簡述常用信息編碼方法的兩類。 4-13 簡述等長編碼和變長編碼的特點，并舉例說明。 4-14已知信源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/

6、9，1/3，1/9，應用算術編碼方法對序列CABA進行編碼，并對結果進行解碼。 4-17給定一個零記憶信源，已知其信源符號集為A=a1，a20，1，符號產生概率為P(a1)1/4，P(a2)3/4。對二進制序列11111100，求其二進制算術編碼碼字。 4-18有四個符號a，b，c，d構成的簡單序列Sabdac，各符號及其對應概率如表所示。應用算術編碼方法對S進行編碼，并對結果進行解碼。 符號 a b c d 4-19簡述游程編碼的思想和方法。 4-20簡述JEPG算法的主要計算步驟，并詳細說明每個步驟。 4-21設二元信源的字母概率為P(0)=1/4,P(1)=3/4。若信源輸出序列為101

7、1011110110111 （a） 對其進行算術編碼并計算編碼效率。 （b） 對其進行LZ編碼并計算編碼效率。 4-22設有二元信源符號集，輸入信源符號序列為a1a0a1a0a0a0a1a1a0a1a1a0?,求其序列的字典編碼。 4-23一個離散記憶信源A=a,b,c,發(fā)出的字符串為bccacbcccccccccccaccca。試用LZ算法對序列編碼，給出編碼字典及發(fā)送碼序列。 4-24 用LZ算法對信源A=a,b,c編碼，其發(fā)送碼字序列為：2，3，3，1，3，4，5，10，11，6，10。試據(jù)此構建譯碼字典并譯出發(fā)送序列。 符號概率pi 1/2 1/4 1/8 1/8 習題參考答案 3 信

8、息論與編碼理論 4-1： (1) A、B、C、E編碼是唯一可譯碼。 (2) A、C、E碼是及時碼。 (3) 唯一可譯碼的平均碼長如下： 111111 lA?p(si)li?3?(?)?3 碼元/信源符號 2416161616i?1 111111 lB?p(si)li?1?2?3?4?5?6?2.125碼元/信源符號 2416161616i?1111111 lC?p(si)li?1?2?3?4?5?6?2.125碼元/信源符號 2416161616i?1111111 lE?p(si)li?1?2?(?)?4?2碼元/信源符號 2416161616i?1 4-3： (1) 666 6 H(X)=-

9、?p(xi)logp(xi) i=1 8 1111111111=-log-log-log-log-log22448816163232 111111 -log-log-log 646412812812812863 =1bit/符64 (2) 平均碼長： 11111111 l?p(si)li?3?(?)?3碼元/信源符號 248163264128128i?1 所以編碼效率：?4 6 H(X) ?0.6615 l 信息論與編碼理論 4-5： (1) 霍夫曼編碼： l?0.2?2?0.19?2?0.18?3?0.17?3?0.15?3?0.1?4?0.01?4?2.72碼元/信源符號 5 信息論與編碼

10、理論 7 H(X)?pilogpi?2.61 碼元/符號 i?1 ? H(X)2.61 ?0.9596 2.72l 平均碼長： l?0.49?1?0.14?3?2?0.07?4?2?0.04?4?0.02?5?0.02?6?0.01?6?2.23碼元/信源符 H(Y)?pilogpi?2.31碼元/符號 i?19 編碼效率：? H(Y)2.31 ?0.9914 2.33l (2) 仙農編碼： 6 信息論與編碼理論 平均碼長： l?0.2?3?0.19?3?0.18?3?0.17?3?0.15?3?0.1?4?0.01?7?3.14 碼元/信源符 ? H(X)2.61 ?0.8312 3.14l

11、 平均編碼長度： l?0.49?2?0.14?2?0.07?4?2?0.04?5?0.02?6?2?0.02?6?0.01?7?2.89碼元/信源符 編碼效率：? H(Y)2.31 ?0.7993 2.89l (3) 費諾編碼： 對X的費諾編碼： l?0.2?2?0.19?3?0.18?3?0.17?2?0.15?3?0.1?4?0.01?4?2.74 碼元/信源符號 編碼效率：? H(X)2.61 ?0.9526 2.74l 對Y進行費諾編碼： 7 信息論與編碼理論 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碼元/信

12、源符 號 編碼效率：? H(Y)2.31 ?0.9914 2.33l (4) 由三種編碼的編碼效率可知： 仙農編碼的編碼效率為最低，平均碼長最長；霍夫曼編碼的編碼長度最短，編碼效率最高，費諾碼居中。 4-7： 由三元編碼方式可知：R=DB=RD-1(K2)+2 由本題可知D=3，K=8，R=2，所以，首先合并最后兩個信源概率，其中一種編碼方式如下： 8 信息論與編碼理論 譯碼： 673?8?0.9292?,1?729?9? ?第一字符是:CF(u4)? 6738?0.3628? 0,5?89?1?9 ?第二字符是:A 0.3628?0?58?0.6530?,?5?99?19 ?第二字符是:B

13、5 ?0.3628?0,5?9?99 ?第二字符是:A0.6530? 所以譯碼結果是：CABA 4-21： 1011 0111 1011 0111 p(s?1011 0111 1011 0111) 31214124?p(1)p(0)?()()?0.000123744 9 信息論與編碼理論 算術碼的碼長l?logp(s)?13 由序列S的分布函數(shù)F（S）由二元整樹圖來計算： F(S)?1?p(11)?p(10111)?p(1011011111)?p(1011011110111)?p(1011011110110111)331313131?1?()2?()4()?()8()2?()10()3?()12()4 444444444?0.3511403?0.0101100110011 所以算術編碼為：0100 0011 0011 平均碼長及編碼效率如下： l? 13 ?0.8125碼元/符號 16 H(S)?p(1)logp(1)?p(0)logp(0)?0.8113 bit/符號 ? (2) H(S) ?0