第四章信源编码习题解答
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 )
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 η=
==码码
与费诺编码相比，哈夫曼编码的编码效率要高于费诺编码。
一般情况下哈夫曼编码效率较高，但费诺编码如果每次划分概率很接近，则效率也很高。 3、离散无记忆信源X 的概率空间为：1
2345678()0.220.200.180.10.150.020.050.08X x x x x x x x x p X ????=?????
??? 1）对其进行费诺编码；
2）对其进行哈夫曼编码。 解：1）费诺编码：
410
x
8
101
110
4
x
7
101
1110
5
x
6
11
1111
5
2）哈夫曼编码：
4、离散无记忆信源S描述为：123456
()0.370.250.10.180.030.07
S s s s s s s
p S
??
??
=??
??
??
??
1）计算信源熵及其冗余度；
2）对其进行费诺编码；
3）对其进行哈夫曼编码；
4*）对其进行香农-费诺-埃利阿斯编码；
5*）对其进行香农编码；
6）计算哈夫曼码的平均码长、编码效率和码冗余度；
7）把哈夫曼编码器的输出看成一个新信源X，计算其概率分布p(x1) 和p(x2)；
8）H[p(x1), p(x2)] 是否等于H码（即平均码元熵）为什么
解：1）信源熵：
()0.37lb0.370.25lb0.250.18lb0.180.1lb0.10.07lb0.070.03lb0.03 2.229
H S=------=比特/消息
冗余度：
max
() 2.23
1113.788%
()lb6
H S
E
H S
=-=-=
2）费诺编码：
信p(S编码过程码字码
源S)长
s
1
00002
s
2
1012
s
4
10102
s
3
101103
s
6
1011104
s
5
111114 3）哈夫曼编码：
4）香农-费诺-埃利阿斯编码：
信源S
p(
S)
F(
s)
()
F s()
F s的二进
制数
码
长
码字
s
1
..3001 s
2
..3011 s
4
..41011 s
3
..511011 s
6
..511101
5
6）分析哈夫曼码，
其平均码长：6
1()2(0.370.250.18)30.14(0.07+0.03=2.3i i i L p s l ===?+++?+?∑） 码元/消息
平均码元熵：() 2.229
0.968962.3H S H L
===码 比特/码元 编码效率：max 0.97096.896%lb2
H H η=
==码码
码冗余度：max 0.96896
11 3.104%lb2
H E H η==-
=-=码码码1-
7）把哈夫曼编码器的输出看成一个新信源X ，计算其概率分布p (x 1) 和 p (x 2)：
11211
()(0)0.370.250.10.03+0.07=0.60422342p x p ==+?+?+??
21131
()(1)0.250.10.180.030.070.39582342
p x p ==?+?++?+?=
8
）
计
算
12[(),()](0.6042,0.3958)0.6042lb0.60420.3958lb0.39580.9685 /H p x p x H ==--=比特码元
相比平均码元熵：12() 2.229
0.96896[(),()]2.3H S H H p x p x L
=
==≈码 比特/码元
可见，两者很相近，但理论上不相同。因为平均码元熵计算的是算术平均值，而12[(),()]H p x p x 作的是统计平均。
5. 设有6个消息，其出现概率分别为
A B C D E F 1/16 1/16 2/16 3/16 4/16 5/16
将它们分别进行费诺编码和霍夫曼编码，并比较编码效率。是否在任何情况下费诺编码比霍夫曼编码效率都低
解：信源：112345()161616161616A B C D E F X p X ??
????
=???????
???
费诺编码：
平均码长：543211234 2.375161616161616L ????
=++?+?++?=
? ?????
码元/符号
信源熵：111111331155
()lb lb lb lb lb lb 2.35216161616881616441616
H X =-
-----=比特/符号 编码后平均码元熵：() 2.352
0.992.375H X H L
=
==码比特/码元 二元信源最大码元熵为1比特/码元，故编码效率：max 0.99
99%1
H H η=
==码码
哈夫曼编码：
由于平均码长与费诺编码一样，故编码效率也为99%。一般情况下哈夫曼编码效率较高，但费诺编码如果每次划分概率很接近，则效率也很高。
6. 有一冗余位序列，N =15，码字为00，试将其编成L-D 码，并将L-D 码译回原序列。 解：00 N=15 编码：
[]()21122121
11111312152,3,11
45247105 lb105 6.77 lb 151 4
n n Q n n T C C C C C ----====+=+=+====+=????已知：计算： 24477Q T ==将转变成位二进制数，转变成位二进制数，于是得L-D 码： 0010 0101111
译码：
2
2
1011215,
2,47
454755
10111
N Q T C C n ====≤<==+=
修正：
21101123147452223
213
T T C C C n =-=-==≤<==+=
故译码恢复出原序列：00
作业：1、2、4
第四章信源编码 习题解答 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中有相同的码字。