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

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

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

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

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

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

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

7、序列為：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í)碼。(3) 唯一可譯碼的平均碼長如下： 碼元/信源符號(hào)碼元/信源符號(hào)碼元/信源符號(hào)碼元/信源符號(hào)4-3：(1)(2) 平均碼長：碼元/信源符號(hào)所以編碼效率：(3) 仙農(nóng)編碼：信源符號(hào)符號(hào)概率加概率碼長碼字S1010S2210S33110S441110S5511110S66111110S771111110S871111111費(fèi)諾碼：信源符號(hào)符號(hào)概率編碼碼字碼長S1001S210102S3101103S41011104S5

8、10111105S6101111106S71011111107S81111111174-5：(1) 霍夫曼編碼：對X的霍夫曼編碼如下：信源符號(hào)符號(hào)概率編碼過程碼長碼字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碼元/信源符號(hào) 碼元/符號(hào)Y的二元霍夫曼編碼：信源符號(hào)符號(hào)概率編碼過程碼字碼長S10.490.490.490.490.

9、490.490.490.51011S20.140.140.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.0210110006S90.0110110016平均碼長：碼元/信源符碼元/符號(hào)編碼效率：(2) 仙農(nóng)編碼：對X的仙農(nóng)編碼：信源符號(hào)符號(hào)概率和概率碼長碼字S10.203000S2

10、0.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.9971111110平均碼長：碼元/信源符對Y的仙農(nóng)編碼：信源符號(hào)符號(hào)概率和概率碼長碼字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.9971111110平均編碼長度：碼元/信源符編碼效率：(3) 費(fèi)諾編碼：對X的費(fèi)諾編碼：信源符號(hào)符號(hào)概率編碼

11、碼字碼長S10.200002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.01111114平均編碼長度：碼元/信源符號(hào)編碼效率：對Y進(jìn)行費(fèi)諾編碼：信源符號(hào)符號(hào)概率編碼碼字碼長S10.49001S20.141001003S30.1411013S40.0710011004S50.07111014S60.041011104S70.0210111105S80.02101111106S90.0111111116平均碼長：碼元/信源符號(hào)編碼效率：(4) 由三種編碼的編碼效率可知：仙農(nóng)編碼的編碼效率為最低，平均碼長最長；霍夫曼編

12、碼的編碼長度最短，編碼效率最高，費(fèi)諾碼居中。4-7： 由三元編碼方式可知：R=DB=RD-1(K2)+2由本題可知D=3，K=8，R=2，所以，首先合并最后兩個(gè)信源概率，其中一種編碼方式如下：信源符號(hào)符號(hào)概率編碼碼字碼長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：符號(hào)uiP(ui)F(ui)碼長二進(jìn)制表示CC40.1110ACA50.11100BCAB60.111011ACABA90.111011000符號(hào)分布概率：符號(hào)概率分布區(qū)間ABC譯碼：所以譯碼結(jié)果是：CABA4-21：(1)符號(hào)概率分布區(qū)間00.2510.75由題目可知信源符號(hào)為：1011 0111 1011 0111算術(shù)碼的碼長由序列S的分布函數(shù)F（S）由二元整樹圖來計(jì)算： 所以算術(shù)編碼為：0100 0011 0011平均碼長及編碼效率如下：碼元/符號(hào) bit/符號(hào)(2)由于信源符號(hào)集中共有2個(gè)元