教学课件·编码理论(第二版).ppt

1、第第1章章 绪绪 论论1.1信息传输系统信息传输系统 1.2信息编码的发展信息编码的发展 1.1 1.1信息传输系统信息传输系统1.1.11.1.1信息传输的目标信息传输的目标研究通信系统的目的就是要找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，从而达到信息传输系统最优化。所谓可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地、不失真地再现在接收端。所谓有效性高，就是经济效果好，即用尽可能短的时间和尽可能少的设备来传送一定数量的信息。提高可靠性和提高有效性常常会发生矛盾，需要统筹兼顾。例如为了兼顾有效性(考虑经济效果)，有时就不一定要求绝对准确地在接收

2、端再现原来的消息，可以允许有一定的误差或一定的失真，或者说允许近似地再现原来的消息。所谓保密性，就是隐蔽和保护通信系统中传送的消息，使它只能被授权接收者获取，而不能被未授权者接收和理解。所谓认证性，是指接收者能正确判断所接收的消息的正确性，验证消息的完整性，确认消息不是伪造的和被篡改的。有效性、可靠性、保密性、认证性和经济性构成了现代通信系统对信息传输的全面要求，其中前四项正是本书要研究的主要内容。1.1.21.1.2信息传输系统模型信息传输系统模型各种现代数字通信系统如电报、电话、无线电、电视、广播、因特网、遥测、遥控、雷达和导航等，虽然它们的形式和用途各不相同，但本质是相同的，都是信息的传

3、输系统。为了便于研究信息传输和处理的共同规律，将各种通信系统中具有共同特性的部分抽取出来，概括成一个统一的理论模型，如图11所示。通常称它为信息传输系统模型。图11所示的模型也适用于其他的信息流通系统，如生物有机体的遗传系统，人体、动物的神经网络系统和视觉系统等，甚至人类社会的管理系统都可概括成这个模型。人们通过系统中消息的传输和处理来研究信息传输和处理的共同规律。信息传输或通信的目的，是要把收方不知道的信息及时、可靠、完整、安全而又经济地传送给指定的收方。该模型按功能可分为信源、编码器、信道、译码器、信宿五部分。图11信息传输系统模型 1 1信源信源信源是产生消息和消息序列的源，它可以是人、

4、生物、机器或其他事物，它是事物各种运动状态或存在状态的集合。信源发出的消息有语音、图像、文字等，人的大脑思维活动也是一种信源。信源的输出是消息，消息是具体的，但它不是信息本身。另外，信源输出的消息是随机的、不确定的，但又有一定的规律性。信源输出的消息有多种形式，可以是离散的或连续的、平稳的或非平稳的、无记忆的或有记忆的。2 2编码器编码器编码器可分为信源编码器、信道编码器和保密编码器三种。信源编码对信源输出的消息进行适当的变换和处理，把信息变换成信号，目的是为了提高信息传输的效率，使传输更为经济、有效，还要去掉一些与被传信息无关的多余度；信道编码是为了提高信息传输的可靠性而对消息进行的变换和处

5、理；保密编码保证了信息的安全性。由于传输信息的媒质如电波、电缆等总是存在有各种人为或天然的干扰和噪声，因此，为了提高整个通信系统传输信息的可靠性，就需要对加密器输出的信息进行一次纠错编码，人为地增加一些多余信息，使信息传输系统具有自动检错或纠错功能。当然对于各种实际的通信系统，编码器还应包括换能、调制、发射等各种变换处理功能。3.3.信道信道信道是信息传输和存储的媒介，是通信系统把载荷消息的信号从甲地传输到乙地的媒介。在狭义的通信系统中，实际信道有明线、电缆、波导、光纤、无线电波传播空间等，这些都属于传输电磁波能量的信道。当然，对广义的通信系统来说，信道还可以是其他的传输媒介。信道除了传送信号

6、以外，还有存储信号的作用，在信道中还存在噪声和干扰，为了分析方便起见，把在系统其他部分产生的干扰和噪声都等效地折合成信道干扰，看成是由一个噪声源产生的，它将作用于所传输的信号上。这样，信道输出的是已叠加了干扰的信号。由于干扰或噪声往往具有随机性，因此信道的特性也可以用概率空间来描述。4.4.译码器译码器译码是编码的反变换。一般认为这种变换是可逆的。译码器也可分成信源译码器、信道译码器和保密译码器三种。5 5信宿信宿信宿是消息传送的对象，即接收消息的人或机器。5 5信宿信宿信宿是消息传送的对象，即接收消息的人或机器。图11给出的模型只适用于收、发两端单向通信的情况。它只有一个信源和一个信宿，信息

7、传输也是单向的。更一般的情况是：信源和信宿各有若干个，即信道有多个输入和多个输出。另外，信息传输也可以双向进行。例如，广播通信是一个输入、多个输出的单向传输通信，因特网是多个输入、多个输出的多向传输通信，卫星通信网也是多个输入、多个输出的多向传输通信。1.2信息编码的发展信息编码的发展1.2.11.2.1信源压缩编码的发展信源压缩编码的发展1948年,香农在通信的数学理论一文中，用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论。香农理论的核心是：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。从数学观点

8、看，这些定理是最优编码的存在定理。但从工程观点看，这些定理不是结构性的，不能从定理的结果直接得出实现最优编码的具体途径。然而，它们给出了编码的性能极限，在理论上阐明了通信系统中各种因素的相互关系，为人们寻找最佳通信系统提供了重要的理论依据。当已知信源符号的概率特性时，可计算它的信息熵，用它表示每个信源符号所载有的信息量。编码定理不但证明了必存在一种编码方法，使代码的平均长度可任意接近但不能低于信息熵，而且还阐明达到这一目标的途径，就是使概率与码长匹配。信源编码定理出现后，编码方法就趋向于合理化。从无失真信源编码定理出发，1948年，香农在论文中提出并给出了简单的编码方法(香农编码)；1952年

9、，费诺(Fano)提出了一种费诺码；同年，霍夫曼(D.A.Huffman)构造了一种霍夫曼编码方法，并证明了它是最佳码。霍夫曼码是有限长度的块码中最好的码，亦即它是代码总长度最短的码。1949年，克拉夫特(L.G.Kraft)提出了Kraft不等式，指出了即时码的码长必须满足的条件。后来，麦克米伦（B.McMillan）在1956年证明惟一可译码也满足此不等式。到1961年，卡拉什（J.Karush）简化了麦克米伦的证明方法。霍夫曼码在实际中已有所应用，但它仍存在一些块码及变长码所具有的缺点。例如,概率特性必须精确地测定，它若略有变化，就需更换码表；对于二元信源，常需多个符号合起来编码，才能取

10、得好的效果等。因此，霍夫曼码在实用中常需作一些改进，同时也就有研究非块码的必要性。算术码就是一种非块码，它是从整个序列的概率匹配的角度来进行编码的。其实，此概念也是香农首先提出的，后经许多学者改进，已逐渐进入实用阶段。1968年前后，埃利斯(P.Elias)发展了香农费诺码，提出了算术编码的初步思路。而里斯桑内(JRissanen)在1976年给出和发展了算术编码；1982年，他和兰登(G.G.Langdon)一起将算术编码系统化，并省去了乘法运算，使其更为简化,易于实现。若对概率特性未知或不确知的信源进行有效的编码，上述方法已无能为力。对有些信源，要确知信源的统计特性相当困难，尤其是高阶条件

11、概率；何况有时信源的概率特性根本无法测定，或是否存在也不知道。例如,地震波信号就是如此，因为无法取得大量实验数据。当信源序列是非平稳时，其概率特性随时间而变更，要测定这种信源的概率特性也近乎不可能。人们总希望能有一种编码方法通用于各类概率特性的信源，通用编码就是在信源统计特性未知时对信源进行编码，且使编码效率很高的一种码。1977年，以色列学者兰佩尔（A.Lempel)和奇费（J.Ziv)提出了一种语法解析码，习惯上称之为LZ码。到1978年，他们又对这种基于字典的方法提出了改进算法，分别称为LZ77和LZ78。1984年,韦尔奇（T.A.Welch)以LZ编码中的LZ78算法为基础修改成一种

12、实用的算法，后定名为LZW算法。LZW算法保留了LZ78算法的自适应性能，压缩效果也大致相同；但LZW算法的显著特点是逻辑性强，易于硬件实现，且价格低廉，运算速度快。LZW算法已经作为一种通用压缩方法，广泛应用于二元数据的压缩。前面介绍的无失真信源编码只适用于离散信源或数字信号，不适用于连续信源或模拟信号，如语音、图像等信号的数字处理。因为连续信源的每个样值所能载荷的信息量是无限的，而数字信号的值则是有限的，所以对连续信源不引入失真是不可能的。并且连续信号所对应的信宿一般是人，当失真在某一限度以下时是不易被人感觉到的。同时，信宿不论是人还是机器都存在一定的灵敏度和分辨力，超过信宿的灵敏度和分辨

13、力所传送的信息是毫无意义的，也是完全没有必要的。比如语音信源，当分层量化超过28256级时，人耳就很难分辨，所以没有必要在量化时超过256级。对图像信源亦是如此，人们看电影时可以充分利用人眼的视觉暂留效应，当放映机放速达25张每秒以上时，人眼就能将离散的照片在人脑内反映成连续画面。若放速大大超过25张每秒，则对普通画面是毫无意义的。限失真信源编码的研究较信道编码和无失真信源编码落后十年左右。1948年，香农在其论文中已体现出了关于率失真函数的思想，在1959年,他发表的保真度准则下的离散信源编码定理首先提出了率失真函数及率失真信源编码定理。1971年，伯格尔的信息率失真理论是一本较全面地论述有

14、关率失真理论的专著。率失真信源编码理论是信源编码的核心问题，是频带压缩、数据压缩的理论基础，直到今天它仍是信息论研究的课题。连续信源编成代码后就无法无失真地恢复成原来的连续值，此时只能根据率失真理论进行限失真编码。限失真编码实际上就是最佳量化问题。最佳标量量化常不能达到率失真函数所规定的R(D)值。后来人们又提出了矢量量化的概念，即将多个信源符号合成一个矢量并对它进行编码。从理论上讲，在某些条件下，用矢量量化来编码可以达到上述的R(D)值，但在实现上还是非常困难的，有待进一步的研究成果来改进。1955年，埃利斯提出了预测编码方法,经过改进,现已经成为美国军用通信语言压缩的标准算法。预测编码利用

15、前几个符号来预测后一个符号的值，预测值与实际值之差亦即预测误差作为待编码的符号，这些符号间的相关性就大为减弱，这样可提高压缩比。变换编码是指样值空间的变换，例如从时域变到频域。在某些情况下，变换编码可减弱符号间的相关性，取得良好的压缩比。预测编码和变换编码已在实际中有所应用。从理论上说，怎样才能把有记忆信源转换成无记忆序列，目前尚无理想的方法，更没有不十分复杂而能实际应用的方法。现在，编码理论与技术不仅在通信、计算机以及自动控制等电子学领域中得到直接的应用，而且还广泛地渗透到生物学、医学、生理学、语言学、社会学和经济学等领域。在编码理论与自动控制、系统工程、人工智能、仿生学、电子计算机等学科互

16、相渗透、互相结合的基础上，形成了一些综合性的新兴学科。尤其是随着数学理论，如小波变换、分形几何理论、数学形态学等，以及相关学科，如模式识别、人工智能、神经网络、感知生理心理学等的深入发展，世界范围内的有关专家一直在追求、寻找现有压缩编码的快速算法，同时，又在不断探索新的科学技术在压缩编码中的应用，因此，新颖、高效的现代压缩方法相继产生。1.2.21.2.2信道纠错编码的发展信道纠错编码的发展在一部分科学家研究信源编码的同时，另外一部分科学家从事有关信道编码(纠错码)的研究工作。这一工作已取得了很大的进展，并已经形成一门独立的分支纠错码理论。1950年,汉明(R.W.Hamming)发表的论文检

17、错码与纠错码是开拓编码理论研究的第一篇论文。这篇论文主要考虑在大型计算机中如何纠正所出现的单个错误。1952年,费诺(RM.Fano)给出并证明了费诺不等式，并给出了关于香农信道编码逆定理的证明；1957年，沃尔夫维兹采用类似典型序列方法证明了信道编码强逆定理；1961年，费诺又描述了分组码中码率、码长和错误概率的关系，并提供了香农信道编码定理的充要性证明；1965年，格拉格尔(R.G.Gallager)发展了费诺的证明结论并提供了一种简明的证明方法；1972年,阿莫托(S.Arimoto)和布莱哈特(R.Blahut)分别发展了信道容量的迭代算法。1948年，香农首先分析并研究了高斯信道问题

18、；1964年，霍尔辛格(JL.Holsinger)发展了有色高斯噪声信道容量的研究；1969年，平斯克尔(M.S.Pinsker)提出了具有反馈的非白噪声高斯信道容量问题；1989年,科弗尔(T.M.Cover)对平斯克尔的结论给出了简洁的证明。从能够纠正单个错误的汉明码过渡到能够纠正多个错误的所谓BCH码，整整经历了10年的时间。因此，可以说20世纪60年代是代数编码理论发展的鼎盛时期。20世纪70年代出现了高帕码(GoppaCode)，从而又把编码理论推向了一个新的高峰，到了80年代，茨伐斯曼(Tsfasman)等人运用代数几何的方法推广了高帕码的思想，指出存在GF(m)上的一列码。这一令

19、人吃惊的结果给编码理论的进一步发展带来了新的希望。汉明码出现后，人们把代数方法引入到纠错码的研究中，形成了代数编码理论。由此找到了大量可纠正多个错误的好码，而且提出了可实现的编译码方法。但代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果，因此，有些人于1960年左右提出了卷积码的概率译码，并逐步形成了一系列概率译码理论。尤其以维特比(Viterbi)译码为代表的译码方法被美国卫星通信系统所采用，使得香农理论成为真正具有实用意义的科学理论。香农在1961年发表的论文双路通信信道开拓了网络信息论的研究。1970年以来，随着卫星通信、计算机通信网的迅速发展，网络信息理论的研究异常活跃，成

20、为当前信息论的中心研究课题之一。一方面，艾斯惠特(RAhlswede)(1971年)和廖(HLiao)(1972年)找出了多元接入信道的信道容量区，在1973年，沃尔夫(JKWolf)和斯莱平(DSlepian)将它推广到具有公共信息的多元接入信道中，科弗尔(TMCover)和艾斯惠特也于1983年分别发表文章讨论相关信源在多元接入信道中的传输问题。另一方面，在1972年,科弗尔提出了广播信道的研究，伯格曼斯(PBergmans)(1973年)、格拉格尔(1974年)、科弗尔(1975年)、马登(K.Marton)(1979年)、伊盖马尔(A.ElGamal)(1979年)和范德缪伦(E.C.

21、VanderMeulen)(1979年)等人也先后分别研究了广播信道的容量区问题。近20多年来，对这一领域的活跃研究使得网络信息论的存在理论日趋完善。1.2.31.2.3密码编码学的发展密码编码学的发展香农在1949年发表的保密通信的信息理论论文中，首先用信息论的观点对信息保密问题作了全面的论述。由于保密问题的特殊性，直至1976年Diffe和Hellman发表的密码学的新方向一文提出了公开密钥密码体制后，保密通信问题才得到广泛研究。尤其在当今，信息的安全和保密问题更加突出和重要。人们把线性代数、初等数论、矩阵等知识引入保密问题的研究，已形成了独树一帜的一个分支密码学理论。密码是一个古老的话题

22、。早在4000多年前，古埃及人就开始使用密码来保密传递的消息。作为保密信息的手段，密码技术本身也处于秘密状态，基本上局限于军事目的，只为少数人所掌握和控制，所以，它的发展受到了极大的限制。20世纪70年代是密码学发展的重要时期。美国国家标准局(NBS，即现在的国家标准与技术研究所NIST)开始数据加密标准(DataEncryptionStandard)的征集工作。1975年3月17日，NBS在FederalRegister上公布了一个候选算法；1976年11月23日，该算法被正式确认为联邦标准DES，并授权在政府通信中使用。此后，DES被多个部门和标准化机构采纳，甚至成为事实上的国际标准，直到

23、1998年该标准才正式退役。1976年11月，Diffie与Hellman的革命性论文密码学新方向(NewDirectionsinCrypotography)发表，开辟了公开密钥密码学的新领域，成为现代密码学的一个里程碑。1978年，R.L.Rivest、A.Shamir和L.Adleman实现了RSA公钥密码体制，并成为了公钥密码的杰出代表和事实标准。1969年,哥伦比亚大学的StephenWiesner首次提出“共轭编码(ConjugateCoding)”的概念。1984年，BennettCharles等人在Wiesner的思想启发下，首次提出了基于量子理论的(现称为)BB84协议，从此量

24、子密码理论宣告诞生。量子密码不同于以前的密码技术，是一种可以发现窃听行为、安全性基于量子定律的密码技术，可以抗击具有无限计算能力的攻击。有人甚至认为，在量子计算机诞生之后，量子密码技术可能成为惟一的真正安全的密码技术。1985年，N.Koblitz和V.Miller把椭圆曲线理论应用到公钥密码技术中，使公钥密码技术取得了重大进展，成为公钥密码技术研究的新方向。密码技术的另一个重要方向流密码(也称序列密码)理论同样也取得了重要的进展。1989年,R.Mathews、D.Wheeler、L.M.Pecora和Carroll等人把混沌理论引入到流密码及保密通信理论中，为序列密码理论开辟了一条新的途径

25、。1997年9月12日，美国国家标准与技术研究所NIST开始征集新一代数据加密标准来接任即将退役的DES;2000年10月2日，由比利时密码学家JoanDaemen和VincentRijmen提交的Rijndael算法被确定为AES算法。2000年1月，欧盟启动了新欧洲数据加密、数字签名、数据完整性计划NESSIE，旨在提出一套强壮的包括分组密码、流密码、散列函数、消息认证码(MAC)、数字签名和公钥加密的密码标准，使欧洲工业界保持密码学研究领域的领先地位，到2002年底最终确定各类标准算法。经典的密码学是关于加密和解密的理论，主要用于通信保密。在今天，密码学已得到了更加深入、广泛的发展。其内

26、容已不再是单一的加、解密技术，已被有效、系统地用于电子数据的保密性、完整性、真实性和不可否认性等各个方面。其中，数据的保密性就是对数据进行加密，使非法用户无法读懂数据信息以及读取信息；完整性是对数据完整性的鉴别，以确定数据是否被非法篡改;真实性是指数据来源和数据本身真实性的鉴别，保证合法用户可以应用密钥得到正确的信息不被欺骗；不可否认性是真实性的另一个方面，有时，不但要确定数据来自何方，而且还要求数据源不可否认发送的数据。现代密码技术的应用已深入到信息安全的各个环节和对象。主要技术有：数据加密、密码分析、数字签名、信息鉴别、零知识认证、秘密共享，等等。密码学的数学工具也更加丰富，如概率统计、数

27、论、组合、代数、混沌、椭圆曲线等，现代数学的许多领域都有密码学的足迹。另一个值得一提的是近年来发展迅速的信息隐藏技术。这是一种将需要保密的信息隐藏在公开信息中来保密、传输的技术，所以可以称为秘密的信息嵌入技术，它主要基于不在意信息传输的思想。相对而言，密码技术是一种公开的信息嵌入、刻意传输技术。如果把密钥视为秘密隐藏信息的秘密，那么广义上，密码技术也是一种信息隐藏技术，这种信息隐藏的秘密由密钥控制；狭义上隐藏信息的秘密由算法控制，如果算法暴露或公开，那么信息也就无法隐藏了，所以信息隐藏技术的另一个重要环节是不在意传输。将信息隐藏在平凡、经常性的公开信息(如广播、电视、图片等)中进行传输，使窃密

28、者无从下手，以此达到逃避信息窥测的目的。数字水印、数字指纹等技术是信息隐藏技术的典型方法，已被广泛地应用于数字产品的产权保护上。第2章无失真信源编码原理 2.1离散信源及其信息测度离散信源及其信息测度 2.2信源编码的基本概念信源编码的基本概念 2.3惟一可译码惟一可译码 2.4信源变长编码信源变长编码 2.5统计匹配码统计匹配码 2.12.1离散信源及其信息测度离散信源及其信息测度 2.1.12.1.1信源概述信源概述 1 1消息、信号和信息消息、信号和信息信源的输出被称做消息(message)，消息一般不能被直接传输，需要经过发送器的变换才能转换成适于信道传输的信号(signal)。消息和

29、信号的这种区别对信息传输系统来讲是有一定意义的。在一般情况下，消息和信号既是相互区别的，又是相互联系的。一方面，消息和信号的定义与含义不同。当信源的输出连同语义学上的意义一并加以理解时则称为消息。例如，播音员播送的一段新闻，记者拍摄的一段录像，歌手演唱的一首歌曲等，都应该说是消息。而当信源的输出只被看做是随时间变化的某一物理量f（t）或随时间、空间位置变化的某一物理量f（x，y，t）时，则称为信号。另一方面，信源的输出在收到、看到、听到之前都是随机的、不确定的，属于随机现象。因此，从信息论的观点来看，信源的输出无论是被看做消息，还是被看做信号，它均含有信息。消息、信号和信息这三者都可以说是信源

30、的输出，或者说它们是信源输出的三个方面。由于信息论关心的是信源输出的信息，因此可将信源称为信息源。通常，统计信息论是不研究消息、信号和信息三个方面在语义学上的意义的，它只考虑信源输出的后两个方面，即信号和信息。应该说，信号是信息的载体和具体表达形式，信息必须借助信号才能得以表现，信息不能离开信号而单独存在。所以，研究信源就是要研究信号和信息的关系，特别是信号如何才能有效地携带信息。2 2信源的分类信源的分类按信号取值的集合和信号取值时刻的集合是离散的或连续的进行分类，信源可分为数字信源(DigitalSource)或离散信源(DiscreteSource)、模拟信源(AnalogSource)

31、或波形信源(WaveformSource)、连续信源(ContinuousSource)。信源输出的信息从数学角度来看就是一种随机过程。有些信源输出的是单个符号(或代码)的消息，它们符号集的取值是有限的或可数的，即可用一维离散型随机变量来描述这些信源的输出，这样的信源称为离散信源。在实际情况中，存在着很多这样的信源。例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。当我们掷一个六面质地均匀的骰子时，每次出现朝上一面的点数都是随机的，如把出现朝上一面的点数作为这个随机试验的结果，并把试验的结果看做信源的输出消息，无可置疑，这个随机试验可看做是一个信源。这个信源输出有限种离散数字，其

32、组成的集合为A=1，2，3，4，5，6，而且每一个数字代表一个完整的消息，所以，这个信源是单符号离散信源。有的信源输出的虽是单个符号(或代码)的消息，但其可能出现的消息数是不可数的或无限的，即输出消息的符号集的取值是连续的，或取值范围是实数集(-，+)。例如，语音信号、热噪声信号等某时间的连续取值数据，以及遥控系统中有关电压、温度、压力等测得的连续数据。这些数据取值虽是连续的，但又是随机的，可用一维的连续型随机变量来描述这些消息，所以这种信源可称为连续信源。若信源只输出一个消息(符号)，则用一维随机变量来描述。然而，很多实际信源输出的消息往往是由一系列符号序列所组成的。例如，将中文自然语言文字

33、作为信源，这时中文信源的样本空间是所有汉字与标点符号的集合。由这些汉字和标点符号组成的序列即构成中文句子和文章。因此，从时间上看，中文信源输出的消息是时间上离散的符号序列，其中每个符号的出现是不确定的、随机的，由此构成了不同的中文消息。又例如，对离散化的平面灰度图像信源来说，从XY平面空间上来看每幅画面是一系列空间离散的灰度值符号，而空间每一点的符号（灰度值）又都是随机的，由此形成了不同的图像消息。这类信源输出的消息是按一定概率选取的符号序列,所以可以把这种信源输出的消息看做时间上或空间上离散的一系列随机变量，即随机矢量。这样，信源的输出可用N维随机矢量来描述，这N维随机矢量有时也称为随机序列

34、，其中，N可为有限正整数或可数的无限值。若在信源输出的随机序列XX1X2XN中，每个随机变量Xi(i=1,2,N)都是取值离散的离散型随机变量，即每个随机变量Xi的可能取值是有限的或可数的,而且随机变量X的各维概率分布都与时间起点无关，也就是在任意两个不同时刻，随机变量的各维概率分布都相同，这样的信源称为离散平稳信源。前面所述的中文自然语言文字与离散化平面灰度图像都是这种离散型平稳信源。若信源输出的消息可用N维随机序列XX1X2XN来描述，其中每个随机分量Xi(i=1,2,N)都是取值为连续的连续型随机变量(即Xi的可能取值是不可数或无限的)，并且满足随机变量X的各维概率密度函数与时间起点无关

35、，也就是在任意两个不同时刻随机变量X的各维概率密度函数都相同，这样的信源称为连续平稳信源。例如，语音信号与热噪声信号，它们在时间上取样离散化后的信源输出矢量在时间上是离散的，但输出矢量中的随机变量的取值都是连续的，所以它们是连续型平稳信源。某些简单的离散平稳信源先后发出的一个个符号是统计独立的。也就是说，在信源输出的随机序列XX1X2XN中，各随机变量Xi(i=1,2,N)之间是无依赖的、统计独立的，这样的信源称为离散无记忆信源。该信源在不同时刻发出的各符号之间也是无依赖的、统计独立的。离散无记忆信源输出的随机变量X所描述的信源称为离散无记忆信源的N次扩展信源。可见，N次扩展信源是由离散无记忆

36、信源输出N长的随机序列构成的信源。一般情况下，信源在不同时刻发出的各符号之间是相互依赖的，也就是在信源输出的平稳随机序列XX1X2XN中,各随机变量Xi之间是相互依赖的。例如，在汉字组成的序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的，其他如英文、德文等自然语言都是如此，将这种信源称为有记忆信源。对这类信源需要在N维随机矢量的联合概率分布中引入条件概率分布来说明它们之间的关联。表述有记忆信源要比表述无记忆信源困难得多。实际上，信源发出的符号往往只与前若干个符号的依赖关系

37、强，而与其更前面的符号依赖关系弱，为此，可以限制随机序列的记忆长度。当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关。假设m阶马尔可夫信源输出的随机序列为XX1X2Xi-1XiXi+1XN。在这序列中某i时刻的随机变量Xi取什么符号只与前m个随机变量Xi-1Xi-2Xi-m取什么符号有关，而与其更前面的随机变量以及后面的随机变量取什么符号都无关。这样，就可用马尔可夫链来描述此信源。如果描述随机序列中各随机变量之间依赖关系的条件概率都与时间起点i无关，即信源输出的符号序列可看成时齐马尔可夫链，则此信源称为时齐马尔可夫信源。一

38、般来说，实际信源输出的消息常常是时间和取值都是连续的，如语音信号、热噪声信号和电视图像信号等时间连续函数。同时，在某一固定时间，它们的可能取值又是连续的和随机的。这种信源输出的消息可用随机过程来描述，所以称其为随机波形信源。分析一般随机波形信源的过程比较复杂和困难。常见的随机波形信源输出的消息是时间上或频率上为有限的随机过程。根据取样定理，只要是时间上或频率上受限的随机过程，都可以把随机过程用一系列时间(或频率)域上离散的取样值来表示，而每个取样值都是连续型随机变量。这样，就可把随机过程转换成时间(或频率)上离散的随机序列来处理。甚至在某种条件下可以转换成随机变量间统计独立的随机序列。如果随机

39、过程是平稳的随机过程，时间离散化后可转换成平稳的随机序列。这样，随机波信源可以转换成连续平稳信源来处理。若再对每个取样值(连续型的)经过分层(量化)，就可将连续的取值转换成有限的或可数的离散值。也就可把连续信源转换成离散信源来处理。2.1.22.1.2信源的数学模型信源的数学模型根据信源输出信息所对应的不同的随机过程可以导出不同的信源模型。例如，根据随机过程具有的随机变量前后独立与否可分为独立随机信源(或称无记忆信源)和不独立随机信源(或称有记忆信源)；根据随机过程平稳与否可分为平稳(稳恒)信源和非平稳(非稳恒)信源。与特殊的随机过程相对应又有特殊的信源模型，例如，与高斯过程相对应的高斯信源，

40、与马尔可夫过程相对应的马尔可夫信源等,其中，马尔可夫信源是有记忆信源中最简单且最具代表性的一种。信源的类型不同其对应的模型也不同，限于篇幅，这里只介绍基本离散信源的数学模型及其无记忆扩展信源的数学模型。在信息传输系统中收信者在未收到消息以前，对信源发出什么消息是不确定的和随机的，所以可用随机变量、随机矢量或随机过程来描述信源输出的消息。或者说,用一个样本空间及其概率测度，也就是概率空间来描述信源。一个基本离散信源的数学模型)()()()(2121nnupupupuuuUPU（2-1）式中：ui 信源输出消息；p（ui）ui发生的先验概率，且0p（ui）1，i，n，riiup)(1。【例21】随

41、机掷一个六面质地均匀的骰子，每次出现朝上一面的点数与其概率分布为 616161616161654321)(UPU式（21）描述了信源基本特征，即一个信源符号就代表一个完整的消息,这样的信源也叫单符号离散信源。但实际信源发出的消息往往不止一个符号，而是由多个符号的时间(或空间)序列组成的。由多个符号组成的时间(或空间)序列称为多符号离散信源。设序列由N个符号组成,且先后发出的符号间彼此统计独立,这样的多符号离散信源可看做离散无记忆信源的N次扩展信源，其数学模型为N维概率空间。由信源U的信源空间可得信源U的N次扩展信源的信源空间为)()()(2121NNnnNNpppUPU）（2-2）式中：UN信

42、源 U 的 N 次扩展信源；i扩展信源输出符号，且iNiiiuuu.21；niNiiuuuuuu,.,.2121，i=1,2,nN；i1,i2,.,iN=1,2,.,n；P（i）扩展信源符号出现的先验概率，1)(1Nniip N 维离散无记忆扩展信源)().()().()(2121iNiiiNiiiupupupuuupp，1)(1Nniip 例2-2 已知二元信源 3.07.0)(baUPU分别计算信源U的2次扩展信源及3次扩展信源模型。解解由式（22）可得信源U的2次扩展信源的模型为 09.021.021.049.0)(22bbbaabaaUPU同理，由式（22）可得信源的3次扩展信源的模型

43、为 027.0063.0063.0063.0147.0147.0147.0343.0)(33bbbbbabababbbaaabaaabaaaUPU2.1.32.1.3自信息量自信息量信息论不研究信源的内部结构，不研究信源为什么产生和怎样产生各种不同的、可能的消息，而只研究信源的各种可能的输出，以及输出各种可能消息的不确定性。由于信源发出的消息是不确定的，只有当信源发出的消息通过信道传输给信宿后，才能消除不确定性并获得信息。事件发生的不确定性与事件发生的概率有关。事件发生的概率越小，猜测它有没有发生的困难程度就越大，不确定性也就越大；而事件发生的概率越大，猜测这事件发生的可能性就越大，不确定性也

44、就越小。对于发生概率等于1的必然事件，就不存在不确定性。1.1.自信息量自信息量自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息。如果事件ui已发生，则信息ui包含的自信息量为 I(ui)logap（）（2-3）ui发生所含信息量 I（ui），自信息量的单位与所用对数底有关。在信息论中常用的对数底是 2，信息量的单位是比特（bit），即：I(ui)lbp（ui）（比特）；若取自然对数 e 为底，则信息量的单位为奈特（nat），即：I(ui)lnp（ui）（奈特）；若以 10 为对数底，则信息量的单位为笛特（det），即：I(ui)lgp（ui）（笛特）。这三个信

45、息量单位之间的转换关系如下：1bit0.693nat0.301det 如果 p（ui）0.5,则由式（2-3）得 I（ui）1bit。所以 1比特信息量就是两个互不相容的等可能事件之一发生时所提供的信息量。在这里比特是指抽象的信息量单位，与计算机术语中“比特”的含义有所不同。当事件ui发生前，其自信息量I(ui)表示事件发生的不确定性；当事件 ui发生后，其自信息量 I(ui)表示事件所能提供的信息量。例 2-3在一个盒子中放有 n 个阻值各为n,21，的 电 阻，将 从 盒 子 中 取 出 阻 值 为i的 电 阻 记 为 事 件),2,1(nixi，则ix发生的概率为nxpi1)(（等概分布

46、），这一事件发生所获得的信息量为nnxIaailog1log)(2.联合自信息量联合自信息量式（2-3）的自信息量是针对一维空间的，可把它推广到二维空间,设概率空间X为：)()()()(2121nnxpxpxpxxxXPX（24）式中：p（xi）xi 出现概率，i,n 且 p（xi）0，iixp)(1。设概率空间Y为)()()()(2121mmypypypyyyYPY（25）式中：p（yi）yi出现概率，j,m 且 p（yj）0，mjjyp)(1。在联合集 XY 上，每对元素 xiyi 同时出现的联合概率 p（xiyj）0，i,n，j,m 满足 nimjiiyxp111)(（2-6）在二维空间

47、XY，p（xiyi），p（xiyi）是元素 xiyi在 二维空间上的联合概率密度，二维联合集 XY 上元素 xiyi的联合自信息量 I（xiyi）的定义 I（xiyi）=-loga p（xiyi）（2-7）3 3条件自信息量条件自信息量 在联合集XY上，在已知事件jy条件下，随机事件ix发生的概率为条件概率)(jiyxp，条件自信息量)(jiyxI定义为)(log)(jiajiyxpyxI (2-8)与事件ix的自信息量类似，随机事件的条件自信息量类似也可以理解为这是在事件jy给定的条件下关于事件ix是否发生的平均不确定性。若条件概率)(jiyxp小，则给定jy时关于ix的是否发生有着较大的不

48、确定性，反之不确定性就小。同样，)(jiyxI也可以看做是在事件iy给定的条件下，惟一地确定事件ix所必须提供的信息量,显然也有)(jiyxI0。2.1.4 平均自信息量平均自信息量1.基本离散信源基本离散信源自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息，自信息I(ui)是一个随机变量，其中任何一个消息的自信息都代表不了信源所包含的平均自信息量。不能作为整个信源的信息测度，因此定义基本离散信源自信息的数学期望为信源的平均自信息量，即：H(U)Elog)(1iupniiiupup1)(log)(2-9)这个平均自信息量的表达式和统计物理学中“热熵”的表达式很相

49、似。在统计物理学中，“热熵”是一个物理系统杂乱性（无序性）的度量，在概念上两者也有相似之处。因而就借用“熵”这个词把平均自信息量H（U）称为“信息熵”。信息熵的单位由自信息的单位决定，即取决于对数底的选取，当底分别为2、e、10时，信息熵的单位分别为比特(bit)、奈特(nat)/符号、笛特（det)/符号，今后如不特殊说明，信息熵的单位为比特/符号。信源的信息熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体信息测度的。对于某特定的信源（概率空间给定），其信息熵是一个特定的值。不同的信源因统计特性不同，其熵也不同。信息熵是表征信息源的平均不确定性，平均自信息量是消除信源不确定

50、性时所需的信息的量度，即收到一个信源符号可全部解除这个符号的不确定性。或者说，获得这样大的信息量后，信源不确定性就被消除了。信息熵和平均自信息量两者在数值上相等，但含义不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，必有信源的熵值；同时，这个熵值在总体平均上才有意义，因而是一个确定的值。而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，这值本身可以是随机量，也可以与接收者的情况有关。因此说信息熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得信息量。只有在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，从而消除了信