第4章无失真信源编码
习题及其参考答案
4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F
（1）求这些码中哪些是唯一可译码；
（2）求哪些码是及时码；
（3）对所有唯一可译码求出其平均码长l。
4-2 设信源
6
126
1
126
()1
()()()
()i
i
s s s
X
p s
p s p s p s
P X
=
??
??
==
??
??
????
∑
L
L
。对此次能源进行m元唯一
可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式）
4-3设信源为
12345678
11111111
()
248163264128128
s s s s s s s s
X
p X
??
????
=
????
????
??
，编成这样的码：（000，001，
010，011，100，101，110，111）。求（1）信源的符号熵；
（2）这种码的编码效率；
（3）相应的仙农码和费诺码。
4-4求概率分布为
11122
(,,,,)
3551515
信源的二元霍夫曼编码。讨论此码对于概率分布为
11111
(,,,,)
55555
的信源也是最佳二元码。
4-5有两个信源X和Y如下：
1
234567()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设信源为1234
5678()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 i
a 1/2
b 1/4
c 1/8
d 1/8
4-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) 唯一可译码的平均码长如下：
6
1
111111
()3()32416161616A i i i l p s l ===?+++++=∑ 码元/信源符号
6
1111111
()123456 2.1252416161616B i i i l p s l ===?+?+?+?+?+?=∑码元/信源符号
61111111
()123456 2.1252416161616C i i i l p s l ===?+?+?+?+?+?=∑码元/信源符号
61
111111
()12()422416161616E i i i l p s l ===?+?++++?=∑码元/信源符号
4-3：
(1)
/bit ∑8
i i i=1
H(X)=-p(x )logp(x )
1111111111=-log -log -log -log -log 22448816163232111111 -log -log -log
646412812812812863
=164
符 (2) 平均码长：
6
1
11111111
()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.72
7
1
()log 2.61i i i H X p p ===∑ 码元/符号
() 2.61
0.95962.72H X l
η=
==
平均码长：
0.4910.14320.07420.0440.0250.0260.016 2.23l =?+??+??+?+?+?+?=码元/信源符 9
1()log 2.31i i i H Y p p ===∑码元/符号
编码效率：() 2.31
0.99142.33H Y l
η=
== (2) 仙农编码：
平均码长：
0.230.1930.1830.1730.1530.140.017 3.14l =?+?+?+?+?+?+?=
码元/信源符
() 2.61
0.83123.14H X l
η=
==
平均编码长度：
0.4920.1420.07420.0450.02620.0260.017 2.89l =?+?+??+?+??+?+?=码元/信源符
编码效率：() 2.31
0.79932.89H Y l
η=
== (3) 费诺编码：
对X 的费诺编码：
0.220.1930.1830.1720.1530.140.014 2.74l =?+?+?+?+?+?+?=
码元/信源符号 编码效率：() 2.61
0.95262.74H X l
η=
== 对Y 进行费诺编码：
0.4910.14230.07420.0440.0250.0260.016 2.33
l=?+??+??+?+?+?+?=码元/信源符号
编码效率：
() 2.31
0.9914
2.33
H Y
l
η===
(4)由三种编码的编码效率可知：
仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。
4-7：由三元编码方式可知：R=D－B=R D-1(K－2)+2
由本题可知D=3，K=8，R=2，所以，首先合并最后两个信源概率，其中一种编码方式如下：
译码：
46738()0.9292,172996738
572990.36280,8919
0.36280580.6530,59919
5
0.6530590.36280,85999
F u ??
=
=∈????
∴-
?
?
=∈????-
∴-??
=∈?
???-∴-
??
=∈????-
∴第一字符是:C 第二字符是:A 第二字符是:B
第二字符是:A
所以译码结果是：CABA
4-21： 1011 0111 1011 0111
12
4
124
()
31(1)(0)()()0.0001237
44
1011 0111 1011 0111p s p p ====
算术码的码长log ()13l p s =-=
由序列S 的分布函数F （S ）由二元整树图来计算：
2482103124()1(11)(10111)(1011011111)(1011011110111)(1011011110110111)
3313131311()()()()()()()()()4444444440.35114030.0101100110011
F S p p p p p =-----=-----== 所以算术编码为：0100 0011 0011 平均码长及编码效率如下：
13
0.812516
l =
=码元/符号 ()(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.7516
l =
=码元/符号
编码效率为：4636.075.18113
.0)(===
l
S H η
第四章信源编码 习题解答 1、一个信源由 1） 哪些是非奇异码？哪些是唯一可译码？哪些是即时码？ 2） 分别计算每个唯一可译码的平均码长和编码效率。 解：1）A 、B 、C 、D 、E 、F 是非奇异码。A 、B 、C 、F 是唯一可译码（E 不满足克拉夫特不等式）。A 、C 、F 是即时码（B 是续长码）。 3） 编码A ： 平均码长：3A L = 码元/消息 信源熵：111111 ()lb lb 4lb 222441616 H X =---?=比特/消息 编码效率：max ()/2/3 66.7%lb21 A H H X L H η====码码 编码B 和C ： 平均码长：111111 23456 2.1252416161616 B C L L ==+?+?+?+?+?= 码元/消息 编码效率：max ()/2/2.125 94.1%lb21 B C H H X L H ηη=====码码 编码F ： 平均码长：11 1234 2.524 16F L ??=? +?+?= ??? 码元/消息 编码效率：max ()/2/2.5 80%lb21 F H H X L H η====码码 2、离散无记忆信源X 的概率空间为：1 234567()0.200.190.180.170.150.100.01X x x x x x x x p X ????=???????? 1）对其进行费诺编码，并计算其编码效率； 2）对其进行哈夫曼编码，并将其编码效率与费诺编码相比较。
解：1）费诺编码： 平均码长：()()()0.20.1720.190.180.1530.10.014 2.74L =+?+++?++?=码元/符号 信源熵： ()0.20lb0.200.19lb0.190.18lb0.180.17lb0.170.15lb0.150.1lb0.10.01lb0.01 2.60/874H X =-------= 比特符号 编码后平均码元熵：() 2.60874 0.95212.74H X H L ===码比特/码元 编码效率：max 0.9521 95.21%lb2 H H η= ==码码 2）哈夫曼编码： 码长 码字 信源X p (X ) 2 10 x 1 2 11 x 2 3 000 x 3 3 001 x 4 3 010 x 5 4 0110 x 6 4 0111 x 7 平均码长：()()()0.20.1920.180.170.1530.10.014 2.72L =+?+++?++?=码元/符号 编码后平均码元熵：() 2.60874 0.95912.72H X H L ===码比特/码元 编码效率：max 0.9591 95.91%lb2 H H η= ==码码 与费诺编码相比，哈夫曼编码的编码效率要高于费诺编码。 一般情况下哈夫曼编码效率较高，但费诺编码如果每次划分概率很接近，则效率也很高。
第四章信源编码习题解答 1、一个信源由: 1） 2）分别计算每个唯一可译码得平均码长与编码效率。 解:1)A、B、C、D、E、F就是非奇异码。A、B、C、F就是唯一可译码(E不满足克拉夫特不等式)。A、C、F就是即时码(B就是续长码)。 3）编码A: 平均码长: 信源熵:比特/消息 编码效率: 编码B与C: 平均码长: 111111 23456 2.125 2416161616 B C L L ==+?+?+?+?+?=码元/消息 编码效率: 编码F: 平均码长: 编码效率: 2、离散无记忆信源X得概率空间为: 1)对其进行费诺编码,并计算其编码效率; 2)对其进行哈夫曼编码,并将其编码效率与费诺编码相比较。解:1)费诺编码:
平均码长:()()()0.20.1720.190.180.1530.10.014 2.74L =+?+++?++?=码元/符号 信源熵: ()0.20lb0.200.19lb0.190.18lb0.180.17lb0.170.15lb0.150.1lb0.10.01lb0.01 2.60/874H X =-------= 比特符号 编码后平均码元熵:比特/码元 编码效率: 2)哈夫曼编码: 码长 码字 信源X p (X ) 2 10 x 1 0、20 2 11 x 2 0、19 3 000 x 3 0、18 3 001 x 4 0、17 3 010 x 5 0、15 4 0110 x 6 0、10 4 0111 x 7 0、01 平均码长:()()()0.20.1920.180.170.1530.10.014 2.72L =+?+++?++?=码元/符号 编码后平均码元熵:比特/码元 编码效率: 与费诺编码相比,哈夫曼编码得编码效率要高于费诺编码。 一般情况下哈夫曼编码效率较高,但费诺编码如果每次划分概率很接近,则效率也很高。 3、离散无记忆信源X 得概率空间为: 1)对其进行费诺编码; 2)对其进行哈夫曼编码。 解:1)费诺编码:
第四章信源编码习 题解答
第四章信源编码 习题解答 1、一个信源由6个消息组成，其概率分布已知，对其进行信源编码得如下表所示6种编码方法： 1） 哪些是非奇异码？哪些是唯一可译码？哪些是即时码？ 2） 分别计算每个唯一可译码的平均码长和编码效率。 解：1）A 、B 、C 、D 、E 、F 是非奇异码。A 、B 、C 、F 是唯一可译码（E 不满足克拉夫特不等式）。A 、C 、F 是即时码（B 是续长码）。 3） 编码A ： 平均码长：3A L = 码元/消息 信源熵：111111 ()lb lb 4lb 222441616H X =---?=比特/消息 编码效率：max ()/2/3 66.7%lb21 A H H X L H η====码码 编码 B 和 C ： 平均码长：1 11111 23456 2.1252416161616 B C L L ==+?+?+?+?+?= 码元/消息 编码效率：max ()/2/2.12594.1%lb21 B C H H X L H ηη=====码码 编码F ： 平均码长：111234 2.52 4 16F L ?? =?+?+? = ??? 码元/消息
编码效率：max ()/2/2.5 80%lb21 F H H X L H η====码码 2、离散无记忆信源X 的概率空间为：1 234567()0.200.190.180.170.150.100.01X x x x x x x x p X ????=??? ?? ??? 1）对其进行费诺编码，并计算其编码效率； 2）对其进行哈夫曼编码，并将其编码效率与费诺编码相比较。 解：1）费诺编码： 平均码长：()()()0.20.1720.190.180.1530.10.014 2.74L =+?+++?++?=码元/符号 信源熵： ()0.20lb0.200.19lb0.190.18lb0.180.17lb0.170.15lb0.150.1lb0.10.01lb0.01 2.60/874H X =-------= 比特符号 编码后平均码元熵：() 2.60874 0.95212.74H X H L = ==码比特/码元 编码效率：max 0.9521 95.21%lb2 H H η= ==码码 2）哈夫曼编码： 码长 码字 信源X p (X ) 2 10 x 1 2 11 x 2
第四章信源编码习题解答 1 种编码方法： 1）哪些是非奇异码哪些是唯一可译码哪些是即时码 2）分别计算每个唯一可译码的平均码长和编码效率。 解：1）A、B、C、D、E、F是非奇异码。A、B、C、F是唯一可译码（E不满足克拉夫特不等式）。A、C、F是即时码（B是续长码）。 3）编码A： 平均码长：3 A L=码元/消息 信源熵： 111111 ()lb lb4lb2 22441616 H X=---?=比特/消息 编码效率： max ()/2/3 66.7% lb21 A H H X L H η==== 码 码 编码B和C： 平均码长： 111111 23456 2.125 2416161616 B C L L ==+?+?+?+?+?=码元/消息 编码效率： max ()/2/2.125 94.1% lb21 B C H H X L H ηη ===== 码 码 编码F： 平均码长： 111 234 2.5 2416 F L?? =?+?+?= ? ?? 码元/消息
编码效率：max ()/2/2.5 80%lb21 F H H X L H η====码码 2、离散无记忆信源X 的概率空间为：1 234567()0.200.190.180.170.150.100.01X x x x x x x x p X ????=????? ??? 1）对其进行费诺编码，并计算其编码效率； 2）对其进行哈夫曼编码，并将其编码效率与费诺编码相比较。 解：1平均码长：()()()0.20.1720.190.180.1530.10.014 2.74L =+?+++?++?=码元/符号 信源熵： ()0.20lb0.200.19lb0.190.18lb0.180.17lb0.170.15lb0.150.1lb0.10.01lb0.01 2.60/874H X =-------= 比特符号 编码后平均码元熵：() 2.60874 0.95212.74H X H L = ==码比特/码元 编码效率：max 0.9521 95.21%lb2 H H η= ==码码 2）哈夫曼编码： 码 长 码字 信源X (X )
第4章无失真信源编码 习题及其参考答案 4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长l。 4-2 设信源 6 126 1 126 ()1 ()()() ()i i s s s X p s p s p s p s P X = ?? ?? == ?? ?? ???? ∑。对此次能源进行m元唯一 可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式）
4-3设信源为1 234567 811111111()2 4 8 16 3264128128s s s s s s s s X p X ?? ????=???? ??? ??? ，编成这样的码：（000，001，010，011，100，101，110，111）。求 （1）信源的符号熵； （2）这种码的编码效率； （3）相应的仙农码和费诺码。 4-4求概率分布为11122 (,,, ,)3551515 信源的二元霍夫曼编码。讨论此码对于概率分布为 11111 (,,,,)55555 的信源也是最佳二元码。 4-5有两个信源X 和Y 如下： 1 234567()0.200.190.180.170.150.100.01X s s s s s s s p X ????=???????? 1 23456789()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设信源为1234 5678()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级，如下表所示。表中数字为相应像
第4章 无失真信源编码 习题及其参考答案 4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A 、B 、C 、D 、E 和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长l 。 4-2 设信源6 1 261 126()1() () ()()i i s s s X p s p s p s p s P X =????==???? ???? ∑。对此次能源进行m 元唯一 可译编码，其对应的码长为（l 1,l 2,…,l 6）=(1,1,2,3,2,3)，求m 值的最好下限。（提示：用kraft 不等式） 4-3设信源为1 234567 811111111()2 4 8 16 3264128128s s s s s s s s X p X ?? ????=???? ??? ??? ，编成这样的码：（000，001，010，011，100，101，110，111）。求 （1）信源的符号熵； （2）这种码的编码效率； （3）相应的仙农码和费诺码。 4-4求概率分布为11122 (, ,,,)3551515 信源的二元霍夫曼编码。讨论此码对于概率分布为11111 (,,,,)55555 的信源也是最佳二元码。 4-5有两个信源X 和Y 如下： 1 234567()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 ????=????????
00001 001 0000001 0000000 01 0000000 0001 000001 0001 0000001 5 3 7 7 2 7 4 6 4 7 1 01 001 0001 00001 000001 0000001 0000000 S1 s2 s3 s4 s5 s6 s7 s8 000 001 010 011 100 101 110 111
第四章无失真信源编码 将信源产生的全部信息无损地发送给信宿，这种信源编码称无失真信源编码。编码过程由编码器实现。 §4.1 编码器 r 编码器数学模型
1、编码器构成： 输入： 信源符号集S =(s 1,s 2, …s q )，由q 个符号组成码符号集X =(x 1,x 2…x r )，由r 个符号组成输出： 代码组C =(w 1, w 2,…w q )，由q 个码字组成 其中，称为码字，l i 称为码字长度)...(21i l i i i i x x x w =2、编码器的作用： 将信源符号集S 中的符号s i ，i=1,2…,q → 变换成由码符号集X 中的码元x j ，j=1,2…,r 组成的长度为l i 的一一对应的码字 码字的集合称为代码组C 。 )...(21i l i i i i x x x w =
3、码分类：根据代码组C 中码字的长度 固定长度码：（定长码）代码组C 中所有码字的长度相同。可变长度码：（变长码）代码组C 中码字的长度不相同。 10 晴阴雨雪 0.40.30.20.1 1*0.4+2*0.3+3*0.2+3*0.1=1.9
4、码奇异性： 非奇异码：代码组C中所有码字都不相同。奇异码：代码组C中有相同的码字。