第4章无失真信源编码习题及其参考答案4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F（1）求这些码中哪些是唯一可译码；（2）求哪些码是及时码；（3）对所有唯一可译码求出其平均码长l。

4-2 设信源61261126()1()()()()iis s sXp sp s p s p sP X=⎡⎤⎡⎤==⎢⎥⎢⎥⎣⎦⎣⎦∑LL。

对此次能源进行m元唯一可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。

（提示：用kraft不等式）4-3设信源为1234567811111111()248163264128128s s s s s s s sXp X⎡⎤⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦⎢⎥⎣⎦，编成这样的码：（000，001，010，011，100，101，110，111）。

求（1）信源的符号熵；（2）这种码的编码效率；（3）相应的仙农码和费诺码。

4-4求概率分布为11122(,,,,)3551515信源的二元霍夫曼编码。

讨论此码对于概率分布为11111(,,,,)55555的信源也是最佳二元码。

4-5有两个信源X和Y如下：1234567()0.200.190.180.170.150.100.01X s s s s s s s p X ⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦123456789()0.490.140.140.070.070.040.020.020.01Y s s s s s s s s s p Y ⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦（1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X 和Y 进行编码，并计算其平均码长和编码效率；（2）从X ，Y 两种不同信源来比较三种编码方法的优缺点。

4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样 霍夫曼码的信源的所有概率分布。

4-7设信源为12345678()0.40.20.10.10.050.050.050.05X s s s s s s s s p X ⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦，求其三元霍夫曼编码。

4-8若某一信源有N 个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当N =2i 和N =2i +1（i 是正整数）时，每个码值的长度是多少？平均码长是多少？4-9现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。

表中数字为相应像素上的灰度级。

（1）不考虑图像的任何统计特性，对图像进行二元等长编码，这幅图像共需要多少个二元符号描述？（2）若考虑图像的统计特性，求这幅图像的信源熵，并对每个灰度级进行二元霍夫曼编码，问平均每个像素需用多少二元符号表示。

4-10在MPEG 中为了提高数据压缩比，采用了____方法。

A ．运动补偿与运行估计 B.减少时域冗余与空间冗余 C ．帧内图像数据与帧间图像数据压缩 D.向前预测与向后预测4-11 JPEG中使用了____熵编码方法。

A.统计编码和算术编码B.PCM编码和DPCM编码C.预测编码和变换编码D.哈夫曼编码和自适应二进制算术编码4-12 简述常用信息编码方法的两类。

4-13 简述等长编码和变长编码的特点，并举例说明。

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＝０，试对1011进行算术编码。

4-16离散无记忆信源发出A，B，C三种符号，其概率分布为5/9，1/3，1/9，应用算术编码方法对序列CABA进行编码，并对结果进行解码。

4-17给定一个零记忆信源，已知其信源符号集为A=｛a1，a2｝＝｛0，1｝，符号产生概率为P(a1)＝1/4，P(a2)＝3/4。

对二进制序列11111100，求其二进制算术编码码字。

4-18有四个符号a，b，c，d构成的简单序列S＝abdac，各符号及其对应概率如表所示。

应用算术编码方法对S进行编码，并对结果进行解码。

符号符号概率p ia 1/2b 1/4c 1/8d 1/84-19简述游程编码的思想和方法。

4-20简述JEPG算法的主要计算步骤，并详细说明每个步骤。

4-21设二元信源的字母概率为P(0)=1/4,P(1)=3/4。

若信源输出序列为10111（a）对其进行算术编码并计算编码效率。

（b）对其进行LZ编码并计算编码效率。

4-22设有二元信源符号集，输入信源符号序列为101000110110,a a a a a a a a a a a a L求其序列的字典编码。

4-23一个离散记忆信源A={a,b,c},发出的字符串为bccacbcccccccccccaccca。

试用LZ算法对序列编码，给出编码字典及发送码序列。

4-24 用LZ算法对信源A={a,b,c}编码，其发送码字序列为：2，3，3，1，3，4，5，10，11，6，10。

试据此构建译码字典并译出发送序列。

习题参考答案4-1：(1) A 、B 、C 、E 编码是唯一可译码。

(2) A 、C 、E 码是及时码。

(3) 唯一可译码的平均码长如下：61111111()3()32416161616A i i i l p s l ===⨯+++++=∑ 码元/信源符号61111111()123456 2.1252416161616B i i i l p s l ===⨯+⨯+⨯+⨯+⨯+⨯=∑码元/信源符号61111111()123456 2.1252416161616C i i i l p s l ===⨯+⨯+⨯+⨯+⨯+⨯=∑码元/信源符号61111111()12()422416161616E i i i l p s l ===⨯+⨯++++⨯=∑码元/信源符号4-3：(1)/bit ∑8i i i=1H(X)=-p(x )logp(x )1111111111=-log -log -log -log -log 22448816163232111111 -log -log -log646412812812812863=164符 (2) 平均码长：6111111111()3()3248163264128128i i i l p s l ===⨯+++++++=∑码元/信源符号所以编码效率：()0.6615H X lη==4-5：(1)霍夫曼编码：l=⨯+⨯+⨯+⨯+⨯+⨯+⨯=码元/信源符号0.220.1920.1830.1730.1530.140.014 2.7271()log 2.61i i i H X p p ===∑ 码元/符号() 2.610.95962.72H X lη===平均码长：0.4910.14320.07420.0440.0250.0260.016 2.23l =⨯+⨯⨯+⨯⨯+⨯+⨯+⨯+⨯=码元/信源符 91()log 2.31i i i H Y p p ===∑码元/符号编码效率：() 2.310.99142.33H Y lη=== (2) 仙农编码：平均码长：0.230.1930.1830.1730.1530.140.017 3.14l =⨯+⨯+⨯+⨯+⨯+⨯+⨯=码元/信源符() 2.610.83123.14H X lη===平均编码长度：0.4920.1420.07420.0450.02620.0260.017 2.89l =⨯+⨯+⨯⨯+⨯+⨯⨯+⨯+⨯=码元/信源符编码效率：() 2.310.79932.89H Y lη=== (3) 费诺编码：对X 的费诺编码：0.220.1930.1830.1720.1530.140.014 2.74l =⨯+⨯+⨯+⨯+⨯+⨯+⨯=码元/信源符号 编码效率：() 2.610.95262.74H X lη=== 对Y 进行费诺编码：0.4910.14230.07420.0440.0250.0260.016 2.33l=⨯+⨯⨯+⨯⨯+⨯+⨯+⨯+⨯=码元/信源符号编码效率：() 2.310.99142.33H Ylη===(4)由三种编码的编码效率可知：仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。

4-7：由三元编码方式可知：R=D－B=R D-1(K－2)+2由本题可知D=3，K=8，R=2，所以，首先合并最后两个信源概率，其中一种编码方式如下：译码：46738()0.9292,172996738572990.36280,89190.36280580.6530,5991950.6530590.36280,85999F u ⎡⎫==∈⎪⎢⎣⎭∴-⎡⎫=∈⎪⎢⎣⎭-∴-⎡⎫=∈⎪⎢⎣⎭-∴-⎡⎫=∈⎪⎢⎣⎭-∴第一字符是:C 第二字符是:A 第二字符是:B第二字符是:A所以译码结果是：CABA4-21： 1011 0111 1011 0111124124()31(1)(0)()()0.0001237441011 0111 1011 0111p s p p ====算术码的码长log ()13l p s =-=由序列S 的分布函数F （S ）由二元整树图来计算：2482103124()1(11)(10111)(1011011111)(1011011110111)(1011011110110111)3313131311()()()()()()()()()4444444440.35114030.0101100110011F S p p p p p =-----=-----== 所以算术编码为：0100 0011 0011 平均码长及编码效率如下：130.812516l ==码元/符号 ()(1)log (1)(0)log (0)0.8113H S p p p p =--= bit/符号 ()0.9985H S lη== (2)由于信源符号集中共有2个元素，因此只需要⎡⎤12log =位二进制数就可以表示其编码，该符号集的编码表如下：按照分段规则，分段为：1 0 11 01 111 011 0111 短语数为7，可用⎡⎤37log ==n 位来表示段号；每个信源符号编码长度为1，所以短语长度为：3+1=4，具体编码过程如下：平均编码长度： 1.7516l ==码元/符号编码效率为：4636.075.18113.0)(===lS H η。