信息論與編碼理論-第4章無失真信源編碼-知識(shí)題解答-2007120

第4章無失真信源編碼習(xí)題及其參考答案4-1有一信源，它有六個(gè)可能的輸出，其概率分布如下表所示，表中給出了對應(yīng)的碼A、B、C、D、E和F（1）求這些碼中哪些是唯一可譯碼；（2）求哪些碼是及時(shí)碼；4-2設(shè)信源XP(X4-2設(shè)信源XP(X)s1

p(s)1s2

p(s)2s6p(s)6￡p（s）=1。對此次能源進(jìn)行m元唯一ii=1（3）對所有唯一可譯碼求出其平均碼長T。消息概率ABCDEFS11/200000000S21/400101101010100S31/160100111101101100101S41/160110111111011101101110S51/16100011111111010111110111S61/1610101111111111011011111011可譯編碼，其對應(yīng)的碼長為（lj2,..（）二（1,12323）,求m值的最好下限。（提示：用kraft不等式）4-3設(shè)信源為ss4-3設(shè)信源為ssssssss1234567811111111248163264128128Xp(X)，編成這樣的碼：（000，001，010，011，100，101，110，111）。求（1）信源的符號(hào)熵；（2）這種碼的編碼效率；（3）相應(yīng)的仙農(nóng)碼和費(fèi)諾碼。111224-4求概率分布為（1,1,1，巳,±）信源的二元霍夫曼編碼。討論此碼對于概率分布為3551515（1,1,1,1,1）的信源也是最佳二元碼。555554-5有兩個(gè)信源X和Y如下：Y

p(Y)X

p(X)sY

p(Y)X

p(X)s1

0.49s1

0.20s2

0.19ss340.180.17sss5670.150.100.01sssss567890.070.040.020.020.01sss2340.140.140.07（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，10，110，111），求出可以編得這樣霍夫曼碼的信源的所有概率分布。4-7設(shè)信源為X

p(X)4-7設(shè)信源為X

p(X)s1

0.4s20.20.10.10.050.050.050.05，求其三元霍夫曼編碼。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ì)特性，對圖像進(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-11JPEG中使用了―熵編碼方法。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=及二0.25唱=0.25飛=0.2爪4=0.15陽=0.10線=0.05]試對其進(jìn)行Huffman編碼。4-15已知信源X=[x1=1/4,x2=3/4],若x1=1,x2=0,試對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,a2}={0,1},符號(hào)產(chǎn)生概率為P(a1)=1/4,P(a2)=3/4。對二進(jìn)制序列I」11111100，求其二進(jìn)制算術(shù)編碼碼字。4-18有四個(gè)符號(hào)a,b,c,d構(gòu)成的簡單序列S=abdac,各符號(hào)及其對應(yīng)概率如表所示。應(yīng)用算術(shù)編碼方法對S進(jìn)行編碼，并對結(jié)果進(jìn)行解碼。符號(hào) 符號(hào)概率piTOC\o"1-5"\h\za 1/2b 1/4c 1/8d 1/84-19簡述游程編碼的思想和方法。4-20簡述JEPG算法的主要計(jì)算步驟，并詳細(xì)說明每個(gè)步驟。4-21設(shè)二元信源的字母概率為P(0)=1/4,P(1)=3/4。若信源輸出序列為1011011110110111(a)對其進(jìn)行算術(shù)編碼并計(jì)算編碼效率。(b)對其進(jìn)行LZ編碼并計(jì)算編碼效率。4-22設(shè)有二元信源符號(hào)集，輸入信源符號(hào)序列為aaaaaaaaaaaa ，求其序列的字典編碼。1010001101104-23一個(gè)離散記憶信源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ù)此構(gòu)建譯碼字典并譯出發(fā)送序列。習(xí)題參考答案4-1：A、B、C、E編碼是唯一可譯碼。A、C、E碼是及時(shí)碼。唯一可譯碼的平均碼長如下：-V 111111l=乙p(s)1=3義(一+—+一+—+一+一)=3碼兀/信源符號(hào)aJj2416161616i=1TOC\o"1-5"\h\z-V 1 1 1 1 1 11=乙p(s)1=—義1+—義2+一義3+一義4+一義5+一義6=2.125碼兀/信源符號(hào)b-2 4 16 16 16 16j=1-V 1 1 1 1 1 11=2Lp(s)1=—義1+—義2+一義3+一義4+一義5+一義6=2.125碼兀/信源符號(hào)c-2 4 16 16 16 16j=1-V 1 1 11111=2p(s)1=—義1+—義2+(一+一+一+一)義4=2碼兀/信源符號(hào)eii2 4 16161616j=14-3：z—bit/符平均碼長：

-V 1111111 1l=乙p(s)l=3義(一+—+—+―+—+一+——+——)=3碼兀/信源符號(hào)― 248163264128128i=1所以編碼效率："=HX)=0.6615l(3)仙農(nóng)編碼：信源符號(hào)S符號(hào)概率p(S.)加概率碼長碼字S12010S24;210S3833110S4116741110S5321516511110S66431326111110S7128636471111110S812812712871111111費(fèi)諾碼：信源符號(hào)S符號(hào)概率p(S)編碼碼字碼長S12001S2410102S38101103S4A1011104S53210111105S6614101111106

S71281011111107S81281111111174-5：(1)霍夫曼編碼：對X的霍夫曼編碼如下:信源符號(hào)符號(hào)概率P(5)編碼過程碼長碼S10.20.20.2610.35(10.39因610102S20.190.190.20.260.3500.391112S30.180.180.190.200.2610003S40.170.170.1800.1910013S50.150.1500.1710103S60.100.11101104S70.0101114l=0.2X2+0.19X2+0.18x3+0.17x3+0.15x3+0.1x4+0.01x4=2.72碼元/信源符號(hào)H(X)=Xplogp=2.61碼元/符號(hào)iii=1n=HX=261=0.9596l2.72Y的二元霍夫曼編碼:

信源符符號(hào)概率P(5)編碼過程碼字碼長S10.490.4/0.4/0.4/0.4/0.4/0.4'0.5011S20.140.1*40.10.10.10.20.200.410003S30.140.10.10.10.10.100.210013S40.070.00.000.0，0.100.1101004S50.070.00.00.000.0101014S60.040.00.000.0101114S70.020.000.01011015S80.0200.01011006S90.011011006

1平均碼長：l=0.49x1+0.14x3x2+0.07x4x2+0.04x4+0.02x5+0.02x6+0.01x6=2.23碼元/信源符H(Y)=Xplogp=2.31碼元/符號(hào)iii=1編碼效率：n=絲Y)=231=0.9914l2.33仙農(nóng)編碼：對X的仙農(nóng)編碼：信源符號(hào)S符號(hào)概率p(S)和概率碼長碼字S10.203000S20.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.9971111110平均碼長：l=0.2x3+0.19x3+0.18x3+0.17x3+0.15x3+0.1x4+0.01x7=3.14碼元/信源符

=0.8312H(X) =0.8312n=—=—=—l3.14對Y的仙農(nóng)編碼:信源符號(hào)S符號(hào)概率p(sp和概率碼長碼字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.9971111110平均編碼長度：l=0.49x2+0.14x2+0.07x4x2+0.04x5+0.02x6x2+0.02x6+0.01x7=2.89碼元/信源符編碼效率：n=H(Y)=N31=0.7993l2.89費(fèi)諾編碼：對X的費(fèi)諾編碼：信源符號(hào)S符號(hào)概率p(S)編碼碼字碼長S10.200002S20.19100103S30.1810113

S40.1710102S50.15101103S60.101011104S70.01111114平均編碼長度：l=0.2x2+0.19x3+0.18x3+0.17x2+0.15x3+0.1x4+0.01x4=2.74碼元/信源符號(hào)編碼效率：^=H(X)=至1=0.9526l2.74對Y進(jìn)行費(fèi)諾編碼：信源符號(hào)S符號(hào)概率p(S)編碼碼字碼長S10.49001S20.141001003S30.1411013S40.0710011004S50.07111014S60.041011104S70.0210111105S80.02101111106S90.0111111116平均碼長：l=0.49x1+0.14x2x3+0.07x4x2+0.04x4+0.02x5+0.02x6+0.01x6=2.33碼元/信源符號(hào)

H(Y)2.31編碼效率：n=—=—= =0.9914l2.33由三種編碼的編碼效率可知：仙農(nóng)編碼的編碼效率為最低，平均碼長最長；霍夫曼編碼的編碼長度最短，編碼效率最高，費(fèi)諾碼居中。4-7:由三元編碼方式可知：R=D-B=RD-1(K-2)+2由本題可知D=3,K=8,R=2,所以，首先合并最后兩個(gè)信源概率，其中一種編碼方式如下:信源符號(hào)S符號(hào)概率p(sp編碼碼字碼長S10.4/0.4/0.40.4*001S20.20.2?0.20.4121S30.100.10.200.22112S40.10.10.11122S50.050.100.121013S60.050.0511023S70.0500.05210004S80.051100144-16:符號(hào)UiP(Ui)F(Ui)碼長二進(jìn)制表示CC9840.1110ACA81850.11100BCAB24367372960.111011

ACABA5218767372990.111011000符號(hào)分布概率:符號(hào)概率分布區(qū)間5「八51A0,-9[9J1「58)Bl-,-3L99J1「8八Cl-,19L9J譯碼：673 「81F(u4)=一=0.9292el-,1729 L9)??.第一字符是:C673877^一二22989=0.3628e0,51 8 91——9?.第二字符是:A0.3628—0八二。八「58)=0.6530el-,-5—i L99)9?.第二字符是B0.6530—5 「5、=必628e[0,g,9—9?.第二字符是A所以譯碼結(jié)果是：CABA4-21:⑴符號(hào)概率分布區(qū)間

00.251.0,0,25)10.75【0.25,1)由題目可知信源符號(hào)為：1011011110110111p(s=101101