第7章 信源编码 - 打印版

第5章_无失真信源编码题与答案

第5章_无失真信源编 码题与答案 本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March

有一信源，它有6个可能的输出，其概率分布如题表所示，表中给出了对应的码 E D C B A ,,,, 和 F 。 (1) 求这些码中哪些是唯一可译码； (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L 。 解： (1) 唯一可译码：A ，B ，C A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。 D 是变长码，码长}4 ,4 ,4 ,3 ,2 ,1{，不是唯一可译码，因为不满足Kraft 不等式。 10625.132******** 321≥=??? ? ??+??? ??+??? ??+??? ??=∑-i l i r E 是变长码，码长}4 ,4 ,4 ,4 ,2 ,1{，满足Kraft 不等式，但是有相同的码字， 110053==W W ，不是唯一可译码。 1142121214 21≤=??? ? ??+??? ??+??? ??=∑-i l i r F 是变长码，码长}3 ,3 ,3 ,3 ,3 ,1{，不满足Kraft 不等式，不是唯一可译码。 1125.1521213 1≥=??? ? ??+??? ??=∑-i l i r (2) 非延长码：A ，C (3)

3125.1616 1 5161416131612411213 =?+?+?+?+?+?= ?===∑i i i C B A l p L L L

第5章_无失真信源编码 题与答案

有一信源，它有6个可能的输出，其概率分布如题表所示，表中给出了对应的码E D C B A ,,,, 和 F 。 (1) 求这些码中哪些是唯一可译码； * (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L 。 解： (1) 唯一可译码：A ，B ，C A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。 D 是变长码，码长}4 ,4 ,4 ,3 ,2 ,1{，不是唯一可译码，因为不满足Kraft 不等式。 10625.132******** 321≥=??? ? ??+??? ??+??? ??+??? ??=∑-i l i r ） E 是变长码，码长}4 ,4 ,4 ,4 ,2 ,1{，满足Kraft 不等式，但是有相同的码字，110053==W W ，不是唯一可译码。 1142121214 21≤=??? ? ??+??? ??+??? ??=∑-i l i r F 是变长码，码长}3 ,3 ,3 ,3 ,3 ,1{，不满足Kraft 不等式，不是唯一可译码。 1125.1521213 1≥=??? ? ??+??? ??=∑-i l i r

(2) 非延长码：A ，C (3) 3125 .16161 5161416131612411213 =?+?+?+?+?+?=?===∑i i i C B A l p L L L 设离散信源的概率空间为 % ???? ??=??????05.010.015.020.025.025.0654321 s s s s s s P S 对其采用香农编码，并求出平均码长和编码效率。 解： ()%7.897 .2423 .2)( 423.205.0log 05.0...25.0log 25.0log )(7 .2505.041.0315.032.0225.0225.0=== =?++?-=-==?+?+?+?+?+?=?=∑∑L S H bit p p S H l p L i i i i i i η 设无记忆二元信源，其概率995.0 ,005.021==p p 。信源输出100=N 的二元序列。在长为 100=N 的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。 (1) 求码字所需要的长度； (2) 考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率E p 是多少 } 解： (1)

信息论与编码第5章

第五章 信源编码（第十讲） （2课时） 主要内容：（1）编码的定义（2）无失真信源编码 重点：定长编码定理、变长编码定理、最佳变长编码。 难点：定长编码定理、哈夫曼编码方法。 作业：5。2，5。4，5。6； 说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。另外，注意，解题方法。多加一些内容丰富知识和理解。 通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。 一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。 §3.1 编码的定义 编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。 讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图 3.1是一个信源编码器，它的输入是信源符号},,,{21q s s s S =，同时存在另一符号},,,{21r x x x X =，一般来说，元素xj 是适合信道传输的，称为码符号（或者码元）。编码器的功能就是将信源符号集中的符号s i （或者长为N 的信源符号序列）变换成由x j (j=1,2,3,…r)组成的长度为l i 的一一对应的序列。 输出的码符号序列称为码字，长度l i 称为码字长度或简称码长。可见，编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。 码符号的分类： 下图是一个码分类图

信息论第五章 信源编码习题答案

5.1 设信源12 34567()0.20.190.180.170.150.10.01X x x x x x x x P X ????=???????? (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率。 解： (1) symbol bit x p x p X H i i i /609.2)01.0log 01.01.0log 1.015.0log 15.017.0log 17.018.0log 18.019.0log 19.02.0log 2.0() (log )()(22222227 1 2=?+?+?+?+?+?+?-=-=∑= 0.0 --- 0.000000 2) 0.2*2 = 0.4 0 0.4*2 = 0.8 0 0.8*2 = 1.6 1 3) 0.39 * 2 = 0.78 0 0.78 * 2 = 1.56 1 0.56 * 2 = 1.12 1 4) 0.99 * 2 = 1.98 1 0.98 * 2 = 1.96 1 0.96 * 2 = 1.92 1 0.92 * 2 = 1.84 1 0.84 * 2 = 1.68 1 0.68 * 2 = 1.36 1 0.36 * 2 = 0.72 0 (3) % 1.8314.3609.2)()(14 .301 .071.0415.0317.0318.0319.032.03)(=====?+?+?+?+?+?+?==∑K X H R X H x p k K i i i η

5.2 对信源??????=????? ?01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X 编二进制费诺码，计算编码效率。 % 2.9574.2609.2)()(74 .2=====K X H R X H i η 5.3 对信源??????=????? ?01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X 编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。 解： % 9.9572.2609.2)()(72 .2=====K X H R X H i η

第五章 信源编码习题答案

5.1 设信源? ?????=??????01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率。 解： (1) symbol bit x p x p X H i i i /609.2)01.0log 01.01.0log 1.015.0log 15.017.0log 17.018.0log 18.019.0log 19.02.0log 2.0() (log )()(22222227 1 2=?+?+?+?+?+?+?-=-=∑= %1.8314.3609 .2)()(14 .301 .071.0415.0317.0318.0319.032.03)(==== =?+?+?+?+?+?+?==∑K X H R X H x p k K i i i η 5.2 对信源? ?????=? ?????01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X 编二进制费诺码，计算编码效率。 解：

%2.9574.2609 .2)()(74 .201 .041.0415.0317.0218.0319.032.02)(==== =?+?+?+?+?+?+?==∑K X H R X H x p k K i i i η 5.3 对信源??????=??????01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X 编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。 解： %9.9572.2609 .2)()(72 .201 .041.0415.0317.0318.0319.022.02)(==== =?+?+?+?+?+?+?==∑K X H R X H x p k K i i i η 三进制哈夫曼码：

第5章_无失真信源编码 题与答案资料

5.1 有一信源，它有6个可能的输出，其概率分布如题 5.1表所示，表中给出了对应的码 E D C B A ,,,, 和 F 。 (1) 求这些码中哪些是唯一可译码； (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L 。 解： (1) 唯一可译码：A ，B ，C A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。 D 是变长码，码长}4 ,4 ,4 ,3 ,2 ,1{，不是唯一可译码，因为不满足Kraft 不等式。 10625.132******** 321≥=??? ? ??+??? ??+??? ??+??? ??=∑-i l i r E 是变长码，码长}4 ,4 ,4 ,4 ,2 ,1{，满足Kraft 不等式，但是有相同的码字，110053==W W ，不是唯一可译码。 1142121214 21≤=??? ? ??+??? ??+??? ??=∑-i l i r F 是变长码，码长}3 ,3 ,3 ,3 ,3 ,1{，不满足Kraft 不等式，不是唯一可译码。 1125.1521213 1≥=??? ? ??+??? ??=∑-i l i r (2) 非延长码：A ，C (3) 3125.1616 1 5161416131612411213 =?+?+?+?+?+?= ?===∑i i i C B A l p L L L

5.7 设离散信源的概率空间为 ???? ??=??????05.010.015.020.025.025.0654321 s s s s s s P S 对其采用香农编码，并求出平均码长和编码效率。 解： ()%7.897 .2423 .2)( 423.205.0log 05.0...25.0log 25.0log )(7 .2505.041.0315.032.0225.0225.0=== =?++?-=-==?+?+?+?+?+?=?=∑∑L S H bit p p S H l p L i i i i i i η 5.8 设无记忆二元信源，其概率995.0 ,005.021==p p 。信源输出100=N 的二元序列。在长为100=N 的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。 (1) 求码字所需要的长度； (2) 考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率E p 是多少？ 解： (1) 码字中有0个“1”，码字的个数：10 100=C 码字中有1个“1”，码字的个数：1001100=C 码字中有2个“1”，码字的个数：49502100=C 码字中有3个“1”，码字的个数：1617003 100=C 18 35.17166751log log 166751 161700495010013100210011000100===≥≥=+++=+++=i r i l l q l q r C C C C q i

第五章 信源编码-习题答案

5.1 设信源? ?????=? ?????01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X (1) 求信源熵H(X)； (2) 编二进制香农码； (3) 计算平均码长和编码效率。 解： (1) symbol bit x p x p X H i i i /609.2)01.0log 01.01.0log 1.015.0log 15.017.0log 17.018.0log 18.019.0log 19.02.0log 2.0() (log )()(22222227 1 2=?+?+?+?+?+?+?-=-=∑= %1.8314.3609 .2)()(14 .301 .071.0415.0317.0318.0319.032.03)(==== =?+?+?+?+?+?+?==∑K X H R X H x p k K i i i η 5.2 对信源? ?????=? ?????01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X 编二进制费诺码，计算编码效率。

%2.9574.2609 .2)()(74 .201 .041.0415.0317.0218.0319.032.02)(==== =?+?+?+?+?+?+?==∑K X H R X H x p k K i i i η 5.3 对信源??????=? ?????01.01.015.017.018.019.02.0)(765432 1x x x x x x x X P X 编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。 解： 二进制哈夫曼码： %9.9572.2609 .2)()(72 .201 .041.0415.0317.0318.0319.022.02)(==== =?+?+?+?+?+?+?==∑K X H R X H x p k K i i i η 三进制哈夫曼码：