信息论及编码

1、第一章第一章 绪论绪论信息论及编码信息论及编码电子与通信工程系电子与通信工程系 余余 萍萍E-mail：well_第一章第一章 绪论绪论第一章第一章 绪论绪论1.1 信息的定义与性质信息的定义与性质 1.2 信息论的主要研究内容信息论的主要研究内容与发展途径与发展途径1.3 信道编码的研究内容与发展简史信道编码的研究内容与发展简史 1.4 信源编码的研究内容信源编码的研究内容与发展简史与发展简史 1.5 本本课程的主要内容课程的主要内容1.6 参考书参考书第一章第一章 绪论绪论1.1 信息的定义与性质信息的定义与性质一、什么是信息？一、什么是信息？消息不完全是信息；消息不完全是信息；信号不等于

2、信息信号不等于信息维纳：维纳：信息就是人和外界互相作用的过程中互相交信息就是人和外界互相作用的过程中互相交 换的内容名称。换的内容名称。香农：香农：信息是用来消除不定性的东西（即信息是熵信息是用来消除不定性的东西（即信息是熵 的减少）。的减少）。朗格：朗格：信息是事物之间的差异，而不是事物的本身。信息是事物之间的差异，而不是事物的本身。第一章第一章 绪论绪论信信 息息 的的 定定 义：义： 从纯客观的角度：从纯客观的角度：信息为事物运动的状态和方式信息为事物运动的状态和方式（事物泛指一切范畴的事物，如物质和精神）。（事物泛指一切范畴的事物，如物质和精神）。 从认识论的角度：从认识论的角度：信息

3、是关于事物运动的状态和信息是关于事物运动的状态和方式的广义知识。方式的广义知识。 信息就是事物运动的状态和方式，就是关于事物信息就是事物运动的状态和方式，就是关于事物运动的千差万别的状态和方式的知识。运动的千差万别的状态和方式的知识。第一章第一章 绪论绪论二、信息的性质二、信息的性质信息是一种资源，信息向人类提供无穷无尽的知识信息是一种资源，信息向人类提供无穷无尽的知识和智慧，是生命的资源。和智慧，是生命的资源。信息具有的特殊性质：信息具有的特殊性质：（1）信息是无形的；）信息是无形的；（2）信息资源可以）信息资源可以“无限共享无限共享”；（3）信息资源具有）信息资源具有“永不枯竭永不枯竭”的

4、性质；的性质；（4）信息具有）信息具有“开发和驾驭开发和驾驭”的能力；的能力；（5）信息是可度量的。）信息是可度量的。第一章第一章 绪论绪论三、信息的作用和价值：三、信息的作用和价值：信息是认识世界的出发点，又是改造世界的归宿，信息是认识世界的出发点，又是改造世界的归宿，它自始至终贯穿全程，并处于主导、支配和控制它自始至终贯穿全程，并处于主导、支配和控制的地位。的地位。信息的价值主要体现在信息的价值主要体现在策略、经营和交流。策略、经营和交流。四、信息技术四、信息技术 凡是可以扩展人的信息功能的技术凡是可以扩展人的信息功能的技术 均可称为为信息技术，如：均可称为为信息技术，如： 传感技术、通信

5、技术、计算机技术传感技术、通信技术、计算机技术第一章第一章 绪论绪论传感技术：是人的传感技术：是人的信息感受器官信息感受器官的功能的扩展和延的功能的扩展和延 长；包含信息识别、检测、提取、交换长；包含信息识别、检测、提取、交换 和处理。和处理。通信技术：是通信技术：是人的人的信息输送系统（神经系统）信息输送系统（神经系统）功能的功能的 扩展和延长；包含信息检测、变换、处扩展和延长；包含信息检测、变换、处 理、传递、存储及控制与调节等。理、传递、存储及控制与调节等。计算机技术：是人的计算机技术：是人的信息处理器官（大脑）信息处理器官（大脑）功能的延功能的延 长；长；包含信息存储、检索、处理、分包

6、含信息存储、检索、处理、分 析、及产生与控制等。析、及产生与控制等。 第一章第一章 绪论绪论五、信五、信 息息 的的 表表 示示设：设：X：某个事物；：某个事物； I(X)：X所具有的实在信息所具有的实在信息 R：某个观察者：某个观察者I0(X;R)：R在观察在观察X之前已经具有的关于之前已经具有的关于X 的信息，即的信息，即R关于关于X的先验信息。的先验信息。通常，通常，I0(X;R)在在0 I(X)之间之间第一章第一章 绪论绪论R在观察在观察X的过程中，实际获得的信息量为：的过程中，实际获得的信息量为： I(X;R) I(X) I0(X;R)若若I(X;R)0，并不表示事物，并不表示事物X

7、没有信息，只说没有信息，只说明观察者得实得信息量等于明观察者得实得信息量等于0。要区分要区分“实得信息为零实得信息为零”和和“实在信息为零实在信息为零”两个两个不同概念。不同概念。实在信息是最基本的概念，而实得实在信息是最基本的概念，而实得信息却是最有用得概念。信息却是最有用得概念。实得实得信息信息实在实在信息信息先验先验信息信息第一章第一章 绪论绪论1.2 信息论的主要研究内容与发展途径信息论的主要研究内容与发展途径 什么是信息论？什么是信息论？ 应用近代数理统计方法来研究应用近代数理统计方法来研究信息的传信息的传 输和处理输和处理的科学；的科学； 在在信息信息可以可以量度量度的基础上，研究

8、的基础上，研究最有最有 效、最可靠地传输和处理信息效、最可靠地传输和处理信息的理论。的理论。根据通信系统模型，可归纳下列主要研究内容：根据通信系统模型，可归纳下列主要研究内容：第一章第一章 绪论绪论一、信息论的主要研究内容一、信息论的主要研究内容1、通信的统计理论的研究通信的统计理论的研究主要研究利用统计数学工具分析信息和信息传主要研究利用统计数学工具分析信息和信息传输的统计规律，内容包含：输的统计规律，内容包含：（1）信息的度量；（）信息的度量；（2）信息速率与熵；）信息速率与熵；研究信源所包含的信息量（熵），单位时间研究信源所包含的信息量（熵），单位时间内信源发出的信息量（时间熵）内信源发

9、出的信息量（时间熵）（3）信道传输能力（信道容量）；）信道传输能力（信道容量）；第一章第一章 绪论绪论2、信源的统计特性、信源的统计特性包括包括：（：（1）文字、字母统计特性；）文字、字母统计特性； （2）语音的参数分析和统计特性；）语音的参数分析和统计特性； （3）图片及活动图像的统计特性；）图片及活动图像的统计特性； （4）其它信源的统计特性。）其它信源的统计特性。3、收信者接收器官的研究、收信者接收器官的研究包括：（包括：（1）人的听觉和视觉器官的特性；）人的听觉和视觉器官的特性； （2）人的大脑感受和记忆能力的模拟。）人的大脑感受和记忆能力的模拟。研究无扰和有扰信道上信宿能收到的信息量

10、的多少研究无扰和有扰信道上信宿能收到的信息量的多少第一章第一章 绪论绪论4、编码理论与技术的研究、编码理论与技术的研究包括：（包括：（1）有效性编码）有效性编码针对信源的统计特性进行编码，以提高信息传输效率针对信源的统计特性进行编码，以提高信息传输效率（信源编码）（信源编码） （2）抗干扰编码）抗干扰编码针对信道统计特性进行编码，以提高信息传输的可靠针对信道统计特性进行编码，以提高信息传输的可靠性（信道编码）性（信道编码）5、提高信息传输效率的研究、提高信息传输效率的研究包括：功率的节约、频带的压缩、传输时间的缩包括：功率的节约、频带的压缩、传输时间的缩 短（即快速传输问题）短（即快速传输问题

11、）第一章第一章 绪论绪论6、抗干扰理论与技术的研究、抗干扰理论与技术的研究包括：各种调制制度的抗干扰性、理想接收机的实现包括：各种调制制度的抗干扰性、理想接收机的实现7、噪声中信号检测理论与技术的研究、噪声中信号检测理论与技术的研究包括：信息检测的最佳准则、信号最佳检测的实现包括：信息检测的最佳准则、信号最佳检测的实现（检测与估值理论）（检测与估值理论）第一章第一章 绪论绪论二、二、 信息论的发展途径信息论的发展途径1、一般信息论（微弱信号检测理论或维纳理论）、一般信息论（微弱信号检测理论或维纳理论）维纳认为：信息只有当它受到噪声干扰时，才需要进维纳认为：信息只有当它受到噪声干扰时，才需要进行

12、处理。行处理。维纳着重研究自动控制过程中的信号预测问题，维纳着重研究自动控制过程中的信号预测问题，即干扰作用下信号的最佳接收问题，是通信、雷即干扰作用下信号的最佳接收问题，是通信、雷达、导航、遥测、遥控及电子对抗等技术的理论达、导航、遥测、遥控及电子对抗等技术的理论基础。基础。第一章第一章 绪论绪论2、侠义信息论（香农信息论）、侠义信息论（香农信息论）香农认为信号在通过噪声信道的前后都需要进香农认为信号在通过噪声信道的前后都需要进行处理。行处理。香农研究信源和信道的统计特性及其编码方法，以香农研究信源和信道的统计特性及其编码方法，以提高信息传输的效率和可靠性，它是通信理论的基提高信息传输的效率

13、和可靠性，它是通信理论的基础。础。维纳和香农探讨的数学模型有很大不同，但两种模维纳和香农探讨的数学模型有很大不同，但两种模型的最终目的都是在接收端逼真地重现原信号。型的最终目的都是在接收端逼真地重现原信号。第一章第一章 绪论绪论1. 3 信道编码的研究内容与发展简史信道编码的研究内容与发展简史信道编码是信道编码是20世纪世纪40年代末提出年代末提出60年代开始发展的年代开始发展的提高数据传输可靠性的理论与技术。提高数据传输可靠性的理论与技术。1948年，香农给出了信道编码定理，给定了系统可年，香农给出了信道编码定理，给定了系统可靠传输的精确上界（信道容量），这是存在性定理，靠传输的精确上界（信

14、道容量），这是存在性定理，没有给出编码方案。没有给出编码方案。1950年以后，年以后，Hamming和和Golay开发了第一个可实现开发了第一个可实现的差错控制方案。创造了汉明码，在每个数据块中的差错控制方案。创造了汉明码，在每个数据块中可纠正一个错误；而可纠正一个错误；而Golay码可以纠正码可以纠正3个比特错误。个比特错误。这类码的共同特点是信息比特之后插入校验比特组这类码的共同特点是信息比特之后插入校验比特组成码字，即分组码。成码字，即分组码。第一章第一章 绪论绪论1957年，年，Prange提出了循环码概念，可利用码字的循环特提出了循环码概念，可利用码字的循环特性降低编译码器的复杂度性

15、降低编译码器的复杂度。1959年，发现了循环码的一个重要子类，即年，发现了循环码的一个重要子类，即BCH码，码，Reed和和Solomon在多进制上构造出的在多进制上构造出的BCH码码, ,称为称为RS码，码，可以纠正突发错误，但直到可以纠正突发错误，但直到1967年年Berlekamp提出一个有提出一个有效译码算法后效译码算法后RS码才广泛应用。码才广泛应用。以上分组码在信噪比较低时，性能相当差。以上分组码在信噪比较低时，性能相当差。1955年，年，Elias提出了卷积码概念，克服了分组码的缺点，提出了卷积码概念，克服了分组码的缺点，1961年年Wozencraft和和Reiffen提出序列

16、译码算法，提出序列译码算法，Fano和和Jelinek对其进行了改进；但直到对其进行了改进；但直到1967年引入了年引入了Viterbi算法算法后，最佳译码方案才可实际操作。后，最佳译码方案才可实际操作。第一章第一章 绪论绪论卷积码抗突发错误能力较差卷积码抗突发错误能力较差，但可以通过交织器来减轻。，但可以通过交织器来减轻。1993年，在通信国际会议（年，在通信国际会议（ICC）上，讨论了一种新的）上，讨论了一种新的编码方式和相关译码技术，作者编码方式和相关译码技术，作者Berrou、Glavieux和和Thitimajshima将其称为将其称为Turbo码，其编码系统与香农理码，其编码系统与

17、香农理论极限更接近了。论极限更接近了。1960年，年，Gallager提出了提出了LDPC码，即低密度奇偶校验码，即低密度奇偶校验码，其性能接近香农极限，误码率小，抗干扰性强，但码，其性能接近香农极限，误码率小，抗干扰性强，但运算复杂度较大。但随着技术进步，可使其复杂度更低，运算复杂度较大。但随着技术进步，可使其复杂度更低，现在又对其重新研究，现在又对其重新研究，LDPC码取代码取代Turbo码的趋势明码的趋势明显，应用前景良好。显，应用前景良好。第一章第一章 绪论绪论1. 4 信源编码的研究内容与发展简史信源编码的研究内容与发展简史将信源输出地消息序列转换成通信系统要求的码字将信源输出地消息

18、序列转换成通信系统要求的码字的过程称为信源编码。的过程称为信源编码。信源编码的主要目的是选出一组适当的码字，使表示信源编码的主要目的是选出一组适当的码字，使表示信源输出消息序列的码率最低。信源输出消息序列的码率最低。而以压缩数码率、提而以压缩数码率、提高系统有效性为目的的技术称为数据压缩。高系统有效性为目的的技术称为数据压缩。一、数据压缩的必要性一、数据压缩的必要性数字通信系统抗干扰能力强，宜于再生与存储、误码数字通信系统抗干扰能力强，宜于再生与存储、误码保护与加密、多路复用、分组与组合，并利于现代保护与加密、多路复用、分组与组合，并利于现代计算技术进行信息处理，但数字信号数据量大、占用计算技

19、术进行信息处理，但数字信号数据量大、占用频带宽，所以通过信源编码进行数据压缩处理是关键频带宽，所以通过信源编码进行数据压缩处理是关键技术课题之一。技术课题之一。第一章第一章 绪论绪论二、数据压缩的可能性和基本方法二、数据压缩的可能性和基本方法依据香农理论，信源编码定理包括无失真和限失真依据香农理论，信源编码定理包括无失真和限失真信源编码两种类型，相应的数据压缩应用技术也分信源编码两种类型，相应的数据压缩应用技术也分为无失真数据压缩（如传真系统）和限失真数据压缩为无失真数据压缩（如传真系统）和限失真数据压缩（如图像、语音系统）（如图像、语音系统）数据压缩研究的重点是在信息率失真理论指导下的限失数

20、据压缩研究的重点是在信息率失真理论指导下的限失真编码方法。真编码方法。三、信源编码研究的发展与现状三、信源编码研究的发展与现状早期，电报系统中的早期，电报系统中的莫尔斯码莫尔斯码提高了电报通信的速度；提高了电报通信的速度；图像编码图像编码用于伦敦与纽约间的海底电缆传输，使一幅新用于伦敦与纽约间的海底电缆传输，使一幅新闻图片传输时间由一星期缩短为小于三小时；闻图片传输时间由一星期缩短为小于三小时；声码器声码器使使数字语音能在窄带电话信道内传输。数字语音能在窄带电话信道内传输。第一章第一章 绪论绪论从从20世纪世纪40年代末开始，以香农信息论为理论指导、以计年代末开始，以香农信息论为理论指导、以计

21、算机为处理工具的信源编码理论与技术得到系统研究和应算机为处理工具的信源编码理论与技术得到系统研究和应用。用。上世纪上世纪60至至70年代，预测编码和正交变换编码快速发展，年代，预测编码和正交变换编码快速发展，1969年，年，Milliard等人等人研制出带宽约研制出带宽约1MHz的电视电话的电视电话DPCM编译码机。编译码机。1983年，提出年，提出32kb/s长途电话质量语音长途电话质量语音DPCM标准的编码标准的编码系统；设计出系统；设计出ADM和和LPC语言压缩器，运用于轻便电话语言压缩器，运用于轻便电话和移动通信系统；和移动通信系统；1988年以后，确定电视电话年以后，确定电视电话/会

22、议电视会议电视H.261建议和静止图建议和静止图像压缩的像压缩的JPEG建议；提出活动图像的建议；提出活动图像的MPEG-2、MPEG-4标准；标准；现代，子带编码、塔形编码、小波变换编码、分形法和神现代，子带编码、塔形编码、小波变换编码、分形法和神经网络编码等，显著改进压缩比及信号质量。经网络编码等，显著改进压缩比及信号质量。第一章第一章 绪论绪论1. 5 本课程研究内容本课程研究内容仙农信息论及编码仙农信息论及编码第一章第一章 绪论绪论1.6 参考书参考书教材：教材：平西建，童莉等平西建，童莉等. 信息论与编码，信息论与编码， 西安电子科技大学出版社，西安电子科技大学出版社，2009年年参

23、考书：参考书：1、傅祖芸、傅祖芸. 信息论信息论基础理论与应用，基础理论与应用， 电子工业出版社，电子工业出版社，2007年年2、曲炜等、曲炜等. 信息论基础及应用，信息论基础及应用， 清华大学出版社，清华大学出版社，2005年年3、曹雪虹等、曹雪虹等. 信息论与编码，信息论与编码， 清华大学出版社，清华大学出版社，2004年年4、曹雪虹曹雪虹. 信息论基础，信息论基础， 清华大学出版社，清华大学出版社，2009年年第二章第二章 信源和信息熵信源和信息熵第二章第二章 信源和信息熵信源和信息熵 2.1 信源的数学模型及分类信源的数学模型及分类 2.2 离散信源的信息熵离散信源的信息熵2.3 离散

24、平稳信源的熵离散平稳信源的熵2.4 连续信源的熵连续信源的熵第二章第二章 信源和信息熵信源和信息熵2.1 信源的数学模型及分类信源的数学模型及分类通信系统模型及信息传输模型：通信系统模型及信息传输模型： 第二章第二章 信源和信息熵信源和信息熵 一、离散无记忆信源一、离散无记忆信源例：例：扔一颗质地均匀的正方体骰子，研究其下落后，扔一颗质地均匀的正方体骰子，研究其下落后，朝上一面的点数。每次试验结果必然是朝上一面的点数。每次试验结果必然是1点、点、2点、点、3点、点、4点、点、5点、点、6点中的某一个面朝上。每次试验只点中的某一个面朝上。每次试验只随机出现其中一种消息，不可能出现这个集合以外的随

25、机出现其中一种消息，不可能出现这个集合以外的消息，考察此事件信源的数学模型。消息，考察此事件信源的数学模型。解：数学模型为：解：数学模型为： 且满足：且满足：第二章第二章 信源和信息熵信源和信息熵离散信源：信源输出是单一符号的消息，其符号集离散信源：信源输出是单一符号的消息，其符号集 的取值是有限的或可数的。的取值是有限的或可数的。无记忆：不同的信源输出消息之间相互独立。无记忆：不同的信源输出消息之间相互独立。一维离散信源数学模型就是离散型的概率空间：一维离散信源数学模型就是离散型的概率空间：且满足：且满足：第二章第二章 信源和信息熵信源和信息熵连续信源：信源输出数据取值是连续的，但又是随连续

26、信源：信源输出数据取值是连续的，但又是随机机 的，即可能出现的消息数是不可数的无的，即可能出现的消息数是不可数的无限限 值。值。数学模型是连续型的概率空间：数学模型是连续型的概率空间：且满足：且满足：X X的概率的概率密度函数密度函数实数集（实数集（，）第二章第二章 信源和信息熵信源和信息熵随机矢量：信源输出的消息是按一定概率选取的符号随机矢量：信源输出的消息是按一定概率选取的符号 序列。用序列。用N维随机矢量维随机矢量X描述：描述： X（x1，x2， xN） 其中：其中：N维随机矢量维随机矢量X也称为随机序列（过程）。也称为随机序列（过程）。平稳随机序列：序列的统计性质与时间的推移无关。平稳

27、随机序列：序列的统计性质与时间的推移无关。二、信源分类二、信源分类（1）根据随机序列）根据随机序列X中每个随机变量中每个随机变量xi的取值不同：的取值不同： 离散平稳信源：如语言文字、离散化平面图像离散平稳信源：如语言文字、离散化平面图像 连续平稳信源：如语音信号、热噪声信号等连续平稳信源：如语音信号、热噪声信号等第二章第二章 信源和信息熵信源和信息熵（2）信源发出的符号间彼此是否独立：）信源发出的符号间彼此是否独立： 无记忆信源：随机矢量的各分量相互独立无记忆信源：随机矢量的各分量相互独立 有记忆信源：随机矢量的各分量不相互独立有记忆信源：随机矢量的各分量不相互独立表述有记忆信源比无记忆信源

28、困难的多，实际中，信表述有记忆信源比无记忆信源困难的多，实际中，信源发出的符号往往只与前若干符号的依赖关系强，与源发出的符号往往只与前若干符号的依赖关系强，与更前面的符号依赖关系弱，这类信源可用马尔可夫信更前面的符号依赖关系弱，这类信源可用马尔可夫信源表示。源表示。不同统计特性的信源可用随机变量、随机矢量以及随不同统计特性的信源可用随机变量、随机矢量以及随机过程描述其输出的消息。机过程描述其输出的消息。第二章第二章 信源和信息熵信源和信息熵2.2 离散信源的信息熵离散信源的信息熵一、信息量和熵一、信息量和熵信息的度量应符合实际情况：信息的度量应符合实际情况：出现概率小的随机事件，不确定性大，信

29、息量大；出现概率小的随机事件，不确定性大，信息量大；出现概率大的随机事件，不确定性小，信息量小；出现概率大的随机事件，不确定性小，信息量小；概率为概率为1的确定事件，信息量为的确定事件，信息量为0。香农定义的自信息量香农定义的自信息量I(x)：任意随机事件出现概率的对：任意随机事件出现概率的对数的负值表示数的负值表示自信息量自信息量。 第二章第二章 信源和信息熵信源和信息熵设随机事件设随机事件x xi i的出现概率为的出现概率为p pi i，则自信息为：，则自信息为： I(xI(xi i) )logplogpi ilog(1/plog(1/pi i) )例：一个输出两种消息的离散无记忆信源，计

30、算消息例：一个输出两种消息的离散无记忆信源，计算消息x x1 1、x x2 2的自信息量，其概率空间为：的自信息量，其概率空间为：解：解：I I（x x1 1)=-log0.99=0.014)=-log0.99=0.014比特比特 I（x2)=-log0.01=6.644-log0.01=6.644比特比特自信息的两种含义：信源输出消息自信息的两种含义：信源输出消息x x1 1之前，自信息之前，自信息I(xI(x1 1) )是关于是关于x x1 1发生地不确定性的度量；而在信源输出发生地不确定性的度量；而在信源输出消息消息x x1 1后，自信息后，自信息I(xI(x1 1) )表示表示x x1

31、 1所含有的信息量。所含有的信息量。 01. 099. 0,21xxPX第二章第二章 信源和信息熵信源和信息熵注意：信息单位比特（表示以注意：信息单位比特（表示以2 2为底的对数）为底的对数）与计算机术语中的比特（表示二进制数的位）与计算机术语中的比特（表示二进制数的位）的意义是不同的。的意义是不同的。收到某消息获得的信息量收到此消息前关收到某消息获得的信息量收到此消息前关于某事件发生的不确定性收到此消息后关于于某事件发生的不确定性收到此消息后关于某事件发生的不确定性某事件发生的不确定性即：收信者所获得的信息量应等于信息传输前即：收信者所获得的信息量应等于信息传输前后不确定性的减少的量。后不确

32、定性的减少的量。例：设一条电线上串联例：设一条电线上串联8 8个灯泡，且损坏的可个灯泡，且损坏的可能性为等概，若仅有一个坏灯泡，须获知多少能性为等概，若仅有一个坏灯泡，须获知多少信息量才可确认？信息量才可确认？第二章第二章 信源和信息熵信源和信息熵例解：例解：测量前，测量前，P P1 1(x)(x)1/81/8，存在不确定性：，存在不确定性： I(PI(P1 1(x)(x)log8log83bit3bit第一次测量获得信息量：第一次测量获得信息量：第二次测量获得信息量：第二次测量获得信息量：第三次测量获得信息量：第三次测量获得信息量：每次测量获得每次测量获得1bit1bit信息量，需三次测量可

33、确定坏灯泡信息量，需三次测量可确定坏灯泡第二章第二章 信源和信息熵信源和信息熵自信息自信息I I是一个随机变量，不能作为信源总体的信息量。是一个随机变量，不能作为信源总体的信息量。定义：自信息量的数学期望为信源的平均信息量，即信定义：自信息量的数学期望为信源的平均信息量，即信源的信息熵，数学表示为：源的信息熵，数学表示为：信息熵的单位取决于对数选取的底，信息熵的单位取决于对数选取的底，r r进制信息熵：进制信息熵：r r进制信息熵与二进制信息熵的关系：进制信息熵与二进制信息熵的关系：第二章第二章 信源和信息熵信源和信息熵例如，有两个信源：例如，有两个信源：则：则：H（X）=0.08比特比特/符

34、号符号 H（Y）=1比特比特/符号符号显然，信源显然，信源X输出消息输出消息x1的可能性是的可能性是99%，所以对，所以对X的平均不确定性较小；而信源的平均不确定性较小；而信源Y输出输出y1、y2的可能性的可能性均为均为0.5，则我们对，则我们对Y输出哪一个消息的平均不确定输出哪一个消息的平均不确定性性较大。较大。01. 099. 0,21xxPX5 . 05 . 0,21yyPY第二章第二章 信源和信息熵信源和信息熵熵的物理含义：熵的物理含义：信息熵信息熵H(x)H(x)是表示信源输出后，每个消息是表示信源输出后，每个消息( (或符号或符号) )所提所提供的平均信息量；信息熵供的平均信息量；

35、信息熵H(x)H(x)是表示信源输出前，信源是表示信源输出前，信源的平均不确定性；用信息熵的平均不确定性；用信息熵H(x)H(x)来表征变量来表征变量X X的随机的随机性。性。注意：注意：信息熵是信源的平均不确定的描述。一般情况信息熵是信源的平均不确定的描述。一般情况下，它并不等于平均获得的信息量，获得的信息量是两下，它并不等于平均获得的信息量，获得的信息量是两熵之差，并不是信息熵本身。熵之差，并不是信息熵本身。 第二章第二章 信源和信息熵信源和信息熵二、信息熵的基本性质二、信息熵的基本性质1 1、对称性：、对称性：此性质说明：熵的总体性。它只与随机变量的总体结此性质说明：熵的总体性。它只与随

36、机变量的总体结构有关，而不在于个别值的概率，甚至也不因随机变构有关，而不在于个别值的概率，甚至也不因随机变量取值的不同而异。量取值的不同而异。2 2、非负性：、非负性：第二章第二章 信源和信息熵信源和信息熵3 3、扩展性：、扩展性：说明：说明：概率很小的值的出现，给予接收者以较大的信概率很小的值的出现，给予接收者以较大的信息，但在熵的计算中占的比重很小，这是熵的总体平息，但在熵的计算中占的比重很小，这是熵的总体平均性的一种体现。均性的一种体现。4、确定性：、确定性： H（1,0）H（0,1）H（1,0,0, ）0说明：从熵的不确定概念来说，确知信源的不确定度说明：从熵的不确定概念来说，确知信源

37、的不确定度应该为应该为0。第二章第二章 信源和信息熵信源和信息熵5、可加性：、可加性：二个随机变量二个随机变量X和和Y不独立时：不独立时：H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y)二个随机变量二个随机变量X和和Y独立时：独立时： H(XY)=H(X)+H(Y)6、极值性：、极值性：H(p1,p2, ,pq) pilogqi，当，当qi1/q时，时，可见：所有概率分布可见：所有概率分布pi所构成的熵，以等概时为最大，所构成的熵，以等概时为最大，称为最大离散熵定理。称为最大离散熵定理。第二章第二章 信源和信息熵信源和信息熵7 7、上凸性：、上凸性：熵函数具有严格的上凸性，它的极值必

38、为最大值。熵函数具有严格的上凸性，它的极值必为最大值。8、递增性：、递增性：其中：其中：此性质说明：熵增加了一项由于划分而产生的不确定性此性质说明：熵增加了一项由于划分而产生的不确定性 量。量。第二章第二章 信源和信息熵信源和信息熵例：运用熵函数的递增性，计算熵函数例：运用熵函数的递增性，计算熵函数 H（1/3,1/3,1/6,1/6）的数值。）的数值。可见：熵函数的递增性也可称为递推性，表示可见：熵函数的递增性也可称为递推性，表示n个元素的信源熵可以递推成（个元素的信源熵可以递推成（n1）个二元信）个二元信源的熵函数的加权和。可使多元信源的熵函数源的熵函数的加权和。可使多元信源的熵函数计算简

39、化成计算若干个二元信源的熵函数。计算简化成计算若干个二元信源的熵函数。第二章第二章 信源和信息熵信源和信息熵2.3 离散平稳信源的熵离散平稳信源的熵离散平稳信源：离散平稳信源：各维联合概率分布均与时间起点无关各维联合概率分布均与时间起点无关 的完全平稳信源称为离散平稳信源。的完全平稳信源称为离散平稳信源。一、联合事件的熵和互信息一、联合事件的熵和互信息设两个随机变量设两个随机变量X1和和X2，单个符号数学模型为：，单个符号数学模型为：联合事件的概率空间：联合事件的概率空间：第二章第二章 信源和信息熵信源和信息熵条件概率分布：条件概率分布：二个符号的数学模型：二个符号的数学模型：联合熵：联合熵：

40、第二章第二章 信源和信息熵信源和信息熵联合熵（共熵）：是联合空间联合熵（共熵）：是联合空间X1X2上的每个元素对上的每个元素对X1X2的自信息量的概率加权平均值。共熵表示信源输的自信息量的概率加权平均值。共熵表示信源输出长度为出长度为2的序列的平均不确定性，或所含的信息量。的序列的平均不确定性，或所含的信息量。条件熵：联合空间条件熵：联合空间X1X2上的条件自信息量的概率加权上的条件自信息量的概率加权 平均值：平均值：联合熵、信息熵及条件熵的关系为：联合熵、信息熵及条件熵的关系为： H（X2）H（X1/X2）第二章第二章 信源和信息熵信源和信息熵根据熵的极值性可得：根据熵的极值性可得：表明某一

41、变量的条件熵必小于或等于它的无条件熵。表明某一变量的条件熵必小于或等于它的无条件熵。还可得：还可得：且且X1、X2独立时，上式等号成立。独立时，上式等号成立。定义无条件熵和条件熵之差为互信息：定义无条件熵和条件熵之差为互信息： I(X1;X2)H(X1)H(X1/X2) 0 H(X1)H(X2)H(X1X2) 且：且：I(X1;X2)I(X2;X1)第二章第二章 信源和信息熵信源和信息熵注意：注意：任何无源处理总是丢失信息的，至多保持原来任何无源处理总是丢失信息的，至多保持原来的信息，这是信息不可增性的一种表现。的信息，这是信息不可增性的一种表现。二、离散平稳信源的极限熵二、离散平稳信源的极限

42、熵设信源输出一系列符号序列设信源输出一系列符号序列X1,X2, XN概率分布：概率分布：联合熵：联合熵：定义定义序列的平均符号熵总和序列的平均符号熵总和/序列长度，序列长度，即：即：第二章第二章 信源和信息熵信源和信息熵 平均符号熵就是信源符号序列中平均每个信平均符号熵就是信源符号序列中平均每个信源符号所携带的信息量。源符号所携带的信息量。 条件熵条件熵无条件熵；条件较多的熵无条件熵；条件较多的熵条件较少条件较少的熵，所以：的熵，所以：第二章第二章 信源和信息熵信源和信息熵离离 散散 平平 稳稳 信信 源源 性性 质（质（H1(X)H(S)，这种编码一，这种编码一定可以做到几乎无失真；定可以做

43、到几乎无失真；反之，当反之，当Rk0），该码段的），该码段的n0k0个校验元不仅与个校验元不仅与本组的信息元有关，而且也与其前本组的信息元有关，而且也与其前m段的信息元段的信息元有关。有关。3 3、按校验元与信息之间的关系：线性码，非线性码、按校验元与信息之间的关系：线性码，非线性码4 4、按纠正错误的类型：纠随机错误码，纠突发错误、按纠正错误的类型：纠随机错误码，纠突发错误 码，纠同步错误码，既纠码，纠同步错误码，既纠 随机错误又纠突发错误码随机错误又纠突发错误码第二章第二章 信源和信息熵信源和信息熵5 5、按码字中的信息位是否发生变化：、按码字中的信息位是否发生变化： 系统码，非系统码系统

44、码，非系统码6 6、按每个码元取值：二进制码，、按每个码元取值：二进制码，q q进制码进制码7 7、按对每个信息元保护能力是否相等：、按对每个信息元保护能力是否相等： 等保护纠错码，不等保护纠错码等保护纠错码，不等保护纠错码第二章第二章 信源和信息熵信源和信息熵纠错码分类第二章第二章 信源和信息熵信源和信息熵6.4 线性分组码线性分组码一、线性分组码的生成一、线性分组码的生成例：任给一个由例：任给一个由k3位信息组成的信息组：位信息组成的信息组：m（m2，m1，m0），所生成的（），所生成的（6，3）线性）线性分组码的码字由下列关系确定：分组码的码字由下列关系确定：ci3mi，i0，1，2c2

45、m2+m1，c1m2m0，c0m1m0显然，可生成显然，可生成8个码字，前个码字，前k3位是原信息组，位是原信息组，后后nk3位是由关系式确定的校验元，也称位是由关系式确定的校验元，也称系系统码统码（也称可分码）（也称可分码）第二章第二章 信源和信息熵信源和信息熵定义：定义：信息组以不变的形式，在码字的任意信息组以不变的形式，在码字的任意k位中出现的码称位中出现的码称为为系统码系统码，否则称为，否则称为非系统码非系统码。如：。如：将码字生成的关系式用向量与矩阵乘积表示：将码字生成的关系式用向量与矩阵乘积表示： C（m2,m1,m0） （m2,m1,m0）G这里这里G称为该（称为该（6，3）码的

46、生成矩阵，有了生成矩阵）码的生成矩阵，有了生成矩阵就很容易把就很容易把8个信息组变换成（个信息组变换成（6，3）码的）码的8个码字个码字1 0 0 1 1 00 1 0 1 0 10 0 1 0 1 1第二章第二章 信源和信息熵信源和信息熵对任意给定的信息组，由对任意给定的信息组，由m生成的码字：生成的码字：CmG其中：其中：m（mn-1，mn-2， mn-k）n，k分组码的分组码的2k个码字组成了一个个码字组成了一个k维子空间，码维子空间，码字可由字可由k个独立矢量所组成的基底生成，个独立矢量所组成的基底生成，设基底为：设基底为： 写成矩阵形式：写成矩阵形式：第二章第二章 信源和信息熵信源和

47、信息熵n，k码中的任何码字，都可由基底的线性组合生成码中的任何码字，都可由基底的线性组合生成即：即：若若n，k码为系统码，且前码为系统码，且前k位是原来的信息组，则位是原来的信息组，则G矩矩阵左边阵左边k列必组成一个列必组成一个kk阶单位方阵阶单位方阵Ik，因此系统码，因此系统码的生成矩阵通常为：的生成矩阵通常为：式中，式中，P是是k(nk)阶矩阵阶矩阵 ，G的的k行是线性无关行是线性无关的，的，这是标准型生成矩阵，这是标准型生成矩阵，只有只有G是标准型，才生成系统码。是标准型，才生成系统码。第二章第二章 信源和信息熵信源和信息熵结论结论码的生成矩阵码的生成矩阵G为为kn阶矩阵，可阶矩阵，可以

48、不止一种形式，但都生成相同以不止一种形式，但都生成相同的矢量空间，即生成同一个的矢量空间，即生成同一个n，k码，码，G中的每一行及其线性组合中的每一行及其线性组合均为均为n，k码的一个码字。码的一个码字。第二章第二章 信源和信息熵信源和信息熵二、分组码的几个参数二、分组码的几个参数1、码率：、码率：R=k/n表示（表示（n,k）分组码中，信息位在码字）分组码中，信息位在码字中所占的比重。中所占的比重。2、汉明距离：用、汉明距离：用d(a,b)表示表示a与与b相应分量不相等的个相应分量不相等的个数，则数，则 d为向量为向量a与与b的汉明距离，简称距离。的汉明距离，简称距离。3、码长为、码长为n的

49、码字的码字c中不为中不为0的码元个数称为该码字的的码元个数称为该码字的重量，记为重量，记为W（c）。）。4、最小汉明距离、最小汉明距离dmin：任两个码字之间距离的最小值。：任两个码字之间距离的最小值。纠错码的基本任务就是构造出纠错码的基本任务就是构造出R一定、一定、dmin尽可能大的尽可能大的码字，或码字，或dmin一定、一定、R尽可能高地码字。尽可能高地码字。第二章第二章 信源和信息熵信源和信息熵三、最小距离译码三、最小距离译码将译码器的输入将译码器的输入R与与C的码字逐个进行比较，与哪个码字的码字逐个进行比较，与哪个码字差别最小，就将其译成哪个码字，称为最小距离译码。差别最小，就将其译成

50、哪个码字，称为最小距离译码。四、分组码的检、纠错能力四、分组码的检、纠错能力1、检测、检测e个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离 dmine+12、纠正、纠正t个随机错误，则要求个随机错误，则要求dmin2t+13、纠正、纠正t个随机错误，同时检测个随机错误，同时检测e(t)个错误，则要求个错误，则要求 dmint+e+1第二章第二章 信源和信息熵信源和信息熵例：发生例：发生t个错误的概率远大于发生个错误的概率远大于发生t+1个错误的概率：个错误的概率：一个数字通信系统的误码率为一个数字通信系统的误码率为P104，因而收到一个，因而收到一个7位码位码元的码字有一位码元发

51、生错误的概率为：元的码字有一位码元发生错误的概率为： P(1)C17 104（1104）67104 其中其中C17表示表示7中取中取1的组合，同理：的组合，同理： P(2)C27 P2（1P）52.1107 P(3)C37 P3（1P）43.51011 P(4)C47 P4（1P）33.51015 P(5)C57 P5（1P）22.11019 P(6)C67 P6（1P）71024 P(7)C77 P71028第二章第二章 信源和信息熵信源和信息熵不发生错误，其概率为不发生错误，其概率为P(0)(1P)70.9993 以上结果归纳：以上结果归纳： P(0) P(1)P(2)P(7)结论：发生结

52、论：发生t个错误的概率远大于发生个错误的概率远大于发生t+1个错误个错误 的概率。的概率。因此：当收到一个因此：当收到一个R，若它不属于码集，若它不属于码集C，可将，可将R 与与C中中qk个码字作比较，当个码字作比较，当R与与Cj的距离的距离 最小时，则发送最小时，则发送Cj收到收到R的条件概率最的条件概率最 大，由此可将大，由此可将R判决为判决为Cj第二章第二章 信源和信息熵信源和信息熵实现最小距离译码的直观方法，就是将收到的实现最小距离译码的直观方法，就是将收到的码字与码集合中所有可能的码字进行比较，取码字与码集合中所有可能的码字进行比较，取距离最小的码字为译码结果。但当码长较长距离最小的

53、码字为译码结果。但当码长较长时，计算量太大，无法实现。时，计算量太大，无法实现。其他还有陪集译码和伴随式译码方式。但陪集其他还有陪集译码和伴随式译码方式。但陪集译码器的复杂性随译码器的复杂性随n指数增长，很不实用。指数增长，很不实用。第二章第二章 信源和信息熵信源和信息熵四、伴随式纠错码四、伴随式纠错码伴随式纠错码是用校验矩阵纠错的译码方法：伴随式纠错码是用校验矩阵纠错的译码方法：设发送设发送C时，收端收到时，收端收到R，错误图样：，错误图样：ERC（en1，en2，e1，e0）译码时，从译码时，从R中得出中得出C的估值的估值 ，或解出错误图样，或解出错误图样从而得到从而得到 ，并使译码错误概

54、率最小，或使，并使译码错误概率最小，或使 尽可能是尽可能是C，每个码字都满足校验方程，每个码字都满足校验方程HCT=0或或CHT=0因此可用校验方程检验因此可用校验方程检验R：RHT（CE）HTCHTEHTEHT若若E0，则，则RHT0，收到的，收到的R就是就是C第二章第二章 信源和信息熵信源和信息熵若若E0，则，则RHT0，故它仅与错误图样有关，与发送，故它仅与错误图样有关，与发送的码字无关。的码字无关。令令SRHTEHT 或或 STHRTHET称称S为为R的伴随式（或校正子）的伴随式（或校正子）伴随式完全由伴随式完全由E决定，它充分地反映了信道干扰情况，决定，它充分地反映了信道干扰情况，译

55、码器的主要任务就是如何从译码器的主要任务就是如何从S求得求得E，从而译出发送，从而译出发送的码字的码字C，所以：，所以：收到收到R时，首先计算伴随式时，首先计算伴随式SRHT 若若S0，则接收的，则接收的R无错无错 S0 ，则接收的则接收的R一定有错一定有错第二章第二章 信源和信息熵信源和信息熵例例：（：（7，3）码，发送码字）码，发送码字C（1110100），），R（0010100），）， E（1100000）时：）时：所得伴随式所得伴随式S是是H矩阵第一列与第二列之和矩阵第一列与第二列之和第二章第二章 信源和信息熵信源和信息熵E（0010000）时：）时：S是是H矩阵的第三列（矩阵的第三列

56、（1个错）个错）第二章第二章 信源和信息熵信源和信息熵E（0010100），则：），则：S是是H矩阵第三列与第五列之和（矩阵第三列与第五列之和（2个错）个错）第二章第二章 信源和信息熵信源和信息熵结结 论论1）如果）如果ST0，则判，则判R无错，此时无错，此时CR；2）如果）如果ST0，且，且ST与与H矩阵的第矩阵的第i列相同，就判列相同，就判 R的第的第i位有错；位有错；3）如果）如果ST0，且，且ST与与H矩阵的哪列都不相同，矩阵的哪列都不相同， 则只判则只判R有错，但不指出究竟是哪些位有有错，但不指出究竟是哪些位有 错，即只发现错误而不纠错。错，即只发现错误而不纠错。第二章第二章 信源和

57、信息熵信源和信息熵6.5 循环码循环码一、基本概念一、基本概念定义：定义：设设C是一个（是一个（n，k）线性分组码，如果）线性分组码，如果C中任意一个码字每次循环移位后得到的中任意一个码字每次循环移位后得到的n维向量维向量仍是仍是C中的一个码字，那么就称中的一个码字，那么就称C为循环码。为循环码。第二章第二章 信源和信息熵信源和信息熵例：例： 7，4汉明码的汉明码的H阵为：阵为：交换交换H阵各列，并不影响码的纠错能力，交换各列后的阵各列，并不影响码的纠错能力，交换各列后的 H阵：阵：显然，第二行是第一行循环右移一位得到，第三行是第显然，第二行是第一行循环右移一位得到，第三行是第二行循环右移一位

58、。由此二行循环右移一位。由此 编出的编出的16个码字为：个码字为：1000110，0100011，1010001，1101000，0110100，0011010，0001101，1001011，1100101，1110010，0111001，1011100，0101110，0010111，1111111，0000000。第二章第二章 信源和信息熵信源和信息熵二、循环码的多项式描述二、循环码的多项式描述在（在（n，k）循环码中，任一个码字）循环码中，任一个码字C1（cn-1,cn-2, c0）可用多项式表示为：）可用多项式表示为： f1(x)cn-1xn-1cn-2xn-2c0C1循环移位一次得

59、到循环移位一次得到C2（cn-2,cn-3, c0,cn-1）C2对应的多项式：对应的多项式： f2(x)cn-2xn-1 c0 xcn-1同理：再循环得到同理：再循环得到C3对应的码多项式：对应的码多项式： f3(x)cn-3xn-1 c0 x2cn-1xcn-2第二章第二章 信源和信息熵信源和信息熵比较以上各多项式可知：比较以上各多项式可知：用用x乘以乘以f1(x)再取模（再取模（xn1）得到）得到 f2(x)，用用x乘以乘以f2(x)，或用，或用x2乘以乘以f1(x)再取模（再取模（xn1）得到）得到 f3(x)，推广到一般情况：，推广到一般情况：任何一个码字任何一个码字C1循环移位循环

60、移位i次得到次得到Ci1，对应多项式：，对应多项式： fi+1(x)cn-1-ixn-1 cn-2-ixn-2 cn-i这相当于用这相当于用xi乘以乘以f1(x)，然后取模，然后取模xn1即：即：xif1(x) fi+1(x)mod(xn1)上式表示：上式表示：fi+1(x)是是xn1除多项式除多项式 xif1(x)的余式的余式 第二章第二章 信源和信息熵信源和信息熵 三、循环码的纠突发错误能力三、循环码的纠突发错误能力 突发错误与随机错误的区别：突发错误与随机错误的区别： E1（0.010.010.），）， E2 （0.01110110.） 错误图样错误图样E1对应的传输错误为对应的传输错误