第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
信源编码的基本原理及其应用 课程名称通信原理Ⅱ 专业通信工程 班级******* 学号****** 学生姓名***** 论文成绩 指导教师***** ******
信源编码的基本原理及其应用 信息论的理论定义是由当代伟大的数学家美国贝尔实验室杰出的科学家香农在他1948 年的著名论文《通信的数学理论》所定义的，它为信息论奠定了理论基础。后来其他科学家，如哈特莱、维纳、朗格等人又对信息理论作出了更加深入的探讨。使得信息论到现在形成了一套比较完整的理论体系。 信息通过信道传输到信宿的过程即为通信，通信中的基本问题是如何快速、准确地传送信息。要做到既不失真又快速地通信，需要解决两个问题：一是不失真或允许一定的失真条件下，如何提高信息传输速度（如何用尽可能少的符号来传送信源信息）；二是在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大（如何尽可能地提高信息传输的可靠性）。这样就对信源的编码有了要求，如何通过对信源的编码来实现呢？ 通常对于一个数字通信系统而言，信源编码位于从信源到信宿的整个传输链路中的第一个环节，其基本目地就是压缩信源产生的冗余信息，降低传递这些不必要的信息的开销，从而提高整个传输链路的有效性。在这个过程中，对冗余信息的界定和处理是信源编码的核心问题，那么首先需要对这些冗余信息的来源进行分析，接下来才能够根据这些冗余信息的不同特点设计和采取相应的压缩处理技术进行高效的信源编码。简言之，信息的冗余来自两个主要的方面：首先是信源的相关性和记忆性。这类降低信源相关性和记忆性编码的典型例子有预测编码、变换编码等；其次是信宿对信源失真具有一定的容忍程度。这类编码的直接应用有很大一部分是在对模拟信源的量化上，或连续信源的限失真编码。可以把信源编码看成是在有效性和传递性的信息完整性（质量）之间的一种折中有段。 信源编码的基本原理： 信息论的创始人香农将信源输出的平均信息量定义为单消息（符号）离散信源的信息熵： 香农称信源输出的一个符号所含的平均信息量为 为信源的信息熵。 通信原理中对信源研究的内容包括3个方面： (1)信源的建模 信源输出信号的数学描述已有成熟的理论——随机过程，一般的随机过程理∑=-=L i i i x p x p x H 12) (log )()()(x H
通信原理复习资料 第一章 绪论 1、模拟通信系统模型 模拟通信系统是利用模拟信号来传递信息的通信系统 2、数字通信系统模型 数字通信系统是利用数字信号来传递信息的通信系统 3、数字通信的特点 优点： （1）抗干扰能力强，且噪声不积累 （2）传输差错可控 （3）便于处理、变换、存储 （4）便于将来自不同信源的信号综合到一起传输 （5）易于集成，使通信设备微型化，重量轻 （6）易于加密处理，且保密性好 缺点： （1）需要较大的传输带宽 （2）对同步要求高 4、通信系统的分类 （1）按通信业务分类：电报通信系统、电话通信系统、数据通信系统、图像通信系统 （2）按调制方式分类：基带传输系统和带通（调制）传输系统 （3）按信号特征分类：模拟通信系统和数字通信系统 （4）按传输媒介分类：有线通信系统和无线通信系统 （5）按工作波段分类：长波通信、中波通信、短波通信 （6）按信号复用方式分类：频分复用、时分复用、码分复用 ★★5、通信系统的主要性能指标：有效性和可靠性 有效性：指传输一定信息量时所占用的信道资源（频带宽度和时间间隔）， 是“速度”问题； 模拟通信系统模型 信息源 信源编码 信道译码 信道编码信 道数字调制 加密 数字解调解密 信源译码 受信者 噪声源 数字通信系统模型
可靠性：指接收信息的准确程度，也就是传输的“质量”问题。 （1）模拟通信系统： 有效性：可用有效传输频带来度量。 可靠性：可用接收端解调器输出信噪比来度量。 （2）数字通信系统： 有效性：用传输速率和频带利用率来衡量。 可靠性：常用误码率和误信率表示。 码元传输速率R B ：定义为单位时间（每秒）传送码元的数目，单位为波特（Baud ）； 信息传输速率R b ：定义为单位时间内传递的平均信息量或比特数，单位为比特/秒。 6、通信的目的：传递消息中所包含的信息。 7、通信方式可分为：单工、半双工和全双工通信 ★8、信息量是对信息发生的概率（不确定性）的度量。一个二进制码元含1b 的信息量；一个M 进制码元含有log 2M 比特的信息量。 9、信息源的熵，即每个符号的平均信息量：)x (p log )x (p I i 2n 1 i i ∑=- = 结论：等概率发送时，信息源的熵有最大值。 第二章 信道与噪声 一 确知信号与随机过程 1、确知信号：是指其取值在任何时间都是确定的和可预知的信号，通常可以用数学公式表示它在任何时间的取值。 2、确知信号的类型 （1）按照周期性区分：周期信号和非周期信号 （2）按照能量区分：能量信号和功率信号： 特点：能量信号的功率趋于0，功率信号的能量趋于￥ 3、确知信号在频域中的性质有四种，即频谱、频谱密度、能量谱密度和功率谱密度。 4、确知信号在时域中的特性主要有自相关函数和互相关函数。 ★ 5、自相关函数反映一个信号在不同时间上取值的关联程度。能量信号的自相关函数R （0）等于信号的能量；功率信号的自相关函数R （0）等于信号的平均功率。 6、随机过程是一类随时间作随机变化的过程，它不能用确切的时间函数描述。 ★7、随机过程具有随机变量和时间函数的特点，可以从两个不同却又紧密联系的角度来描述：①随机过程是无穷多个样本函数的集合②随机过程是一族随机变量的集合。 ★8、随机过程的统计特性由其分布函数或概率密度函数描述。 9、高斯过程的概率分布服从正态分布，它的完全统计描述只需要它的数字特征。 ★★10、瑞利分布、莱斯分布、正态分布是通信中常见的三种分布：正弦载波信号加窄带高斯噪声的包络为莱斯分布；当大信噪比时，趋近于正态分布；小信噪比时近似为瑞利分布。 11、窄带随机过程：若随机过程x (t )的谱密度集中在中心频率f c 附近相对窄的频带范围Df 内，即满足Df << f c 的条件，且 f c 远离零频率，则称该x (t )为窄带随机过程。 ★★12、宽平稳随机过程的定义：P ？？. ★★13、各态历经性定义及应用：P ？？ 宽平稳与各态历经性的关系。 二、信道分类： （1）无线信道 － 电磁波（含光波）
有一信源，它有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)
第七章 信源编码 7-1已知某地天气预报状态分为六种：晴天、多云、阴天、小雨、中雨、大雨。 ① 若六种状态等概出现，求每种消息的平均信息量及等长二进制编码的码长N 。 ② 若六种状态出现的概率为：晴天—；多云—；阴天—；小雨—；中雨—；大雨—。试计算消息的平均信息量，若按Huffman 码进行最佳编码，试求各状态编码及平均码长N 。 解: ①每种状态出现的概率为 6,...,1,6 1 ==i P i 因此消息的平均信息量为 ∑=- ===6 1 22 /58.26log 1 log i i i bit P P I 消息 等长二进制编码的码长N ＝[][]316log 1log 22=+=+L 。 ②各种状态出现的概率如题所给，则消息的平均信息量为 6 2 1 2222221log 0.6log 0.60.22log 0.220.1log 0.10.06log 0.060.013log 0.0130.007log 0.0071.63/i i i I P P bit - == = ------ ≈ ∑消息 Huffman 编码树如下图所示： 由此可以得到各状态编码为：晴—0，多云—10，阴天—110，小雨—1110，中雨—11110， 大雨—11111。 平均码长为： 6 1 10.620.2230.140.0650.01350.0071.68 i i i N n P == =?+?+?+?+?+? =∑— 7-2某一离散无记忆信源（DMS ）由8个字母(1,2,,8)i X i =???组成，设每个字母出现的概率分别为：，，，，，，，。试求： ① Huffman 编码时产生的8个不等长码字； ② 平均二进制编码长度N ； ③ 信源的熵，并与N 比较。 解：①采用冒泡法画出Huffman 编码树如下图所示 可以得到按概率从大到小8个不等长码字依次为： 0100,0101,1110,1111,011,100,00,1087654321========X X X X X X X X
第五章 信源编码（第十讲） （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.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
§3.3信源编码定理 由于信源具有渐进等分割性这一很有意义的性质，这使得它在数据压缩及图像压缩中发挥了巨大作用，下面我们引入信源编码定理。 设u = {u 1,u 2,u 3…u n }是服从分布p(u)的无记忆信源产生的n 长序列，我们总是希望找到一种有效的编码方法来描述这些序列，使得编码以后码子数长尽可能少，但又要使从码字复原原序列的错误概率尽可能小。 一个行之有效的方法是将║χ║n 个序列序列分成典型序列与非典型序列两部分，对u ∈)(n W ε的每一个序列u 赋予一个编号，称每个编号为一个码字，码字集合I = ｛1，2，…，M ｝，M = ║)(n W ε║，对于那些序列u ∈)(n W ε，统一编号为字母α，这样，在从编码后的码字复制原序列时，如果收到码字是i ∈I,则可唯一的复原成某个u ∈)(n W ε，否则如果收到的 是α，则原序列无法正确复制。我们记这种编码的码率为M n log 1 (bit)，其误差概率为e P = p{u ∈)(n W ε}。 为了给出信源编码正定理，我们作以下预备。 设N 长信源序列集合为S ，典型序列集合为)(n W ε，则 1 = ∑∈s u u p )(≥ ∑ ∈ W u p n u ) ()(ε≥ ∑∈ +-W n u U H n ) (2 ] )([ε ε =║)(n W ε║.2 ] )([ε+-U H n ， 从而 ║)(n W ε║≤2] )([ε+-U H n 。 又因为 1-δ< p(u)≤║)(n W ε║.max )() (u p W n u ε ∈ ≤║) (n W ε ║.2 ] )([ε--U H n 故有 ║)(n W ε║≥()2] )([1εδ--?-U H n 这样就有 ()2] )([1εδ--?-U H n ≤║) (n W ε ║≤2] )([ε+U H n 。 于是其码率满足()ε-1log 1n +()U H -ε≤ ) (log 1n W n ε ≤()ε+U H 误差概率为 }{ εε <∈=) (n e W u P P 令0→ε，当∞→n 时，码率接近()U H 而0→e P 。 这就是我们所说的信源编码正定理。 相反的，如果我们用少于()U H 比特的码率对信源序列进行压缩编码可否？答案是否。我们可以证明，如果码率小于()δ-U H ，其中δ 0>δ不随∞→n 而改变，则当+∞→n 时，
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 η 三进制哈夫曼码：