信息论与编码第二版陈运主编课件全套.ppt

《信息论与编码第二版陈运主编课件全套.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第二版陈运主编课件全套.ppt（437页珍藏版）》请在三一办公上搜索。

1、信息论与编码Information Theory and coding,电子信息工程系 宋丽丽Email: ,课程类型：技术基础课学 时：48学时（112周）考 核：平时成绩20（作业、考勤、测验） 期末考试80（闭卷）几点要求：上课尽量不要迟到 课堂上请将手机静音 电子版作业提交到网络教学平台,课程简介,学习目的及意义,最简单的通信系统,信源,信道,信宿,信源熵,信源包含多少信息？信道中传输的是什么形式？信道能传送多少信息？信宿接收到的信息是否正确？,编码,信道容量,检纠错,学习方法,本课程以概率论为基础，数学推导较多，学习时主要把注意力集中到概念的理解上，不过分追求数学细节的推导。建议：上

2、课时紧跟老师思路积极思考，提高听课效率记住概念，知道物理含义及其关系预习和复习自己独立完成作业,概 论,信息的一般概念 信息的分类信息论的起源、发展及研究内容,信息论创始人：C.E.Shannon(香农)美国科学家,概 论,信息科学和材料、能源科学一起被称为当代文明的“三大支柱”。,一位美国科学家说过：“没有物质的世界是虚无的世界；没有能源的世界是死寂的世界；没有信息的世界是混乱的世界。”,信息的存在,花朵开放时的色彩是一种信息，它可以引来昆虫为其授粉； 成熟的水果会产生香味，诱来动物，动物食后为其传播种子，果香也是一种信息；药有苦味，让人难以吞咽，药味是一种信息；听老师讲课可以得到许多知识，

3、知识也是信息。,信息的存在,总之，信息处处存在，人的眼、耳、鼻、舌、身都能感知信息。,信息的存在,1928年,美国数学家哈 特 莱 (Hartley)在贝尔系统电话杂志上发表了一篇题为信息传输的论文。他认为“信息是选择的自由度”。,？信息究竟是什么呢？,事隔20年， 另一位美国数学家香农 (C. E. Shannon) 在贝尔系统电话杂志发表了题为通信的数学理论的长篇论文。他创立了信息论，但是却没有给出信息的确切定义,他认为“信息就是一种消息”。,美国数学家、控制论的主要奠基人维纳(Wiener）在1950年出版的控制论与社会,中写到：“信息既不是物质又不是能量，信息就是信息”。这句话起初受到

4、批评和嘲笑。它揭示了信息的特质：即信息是独立于物质和能量之外存在于客观世界的第三要素。,最普遍的层次，也是无约束条件的层次，定义事物的“信息是该事物运动的状态和状态改变的方式”。我们把它叫做“本体论”层次。最广义的信息，使用范围也最广。,“本体论”定义,引入一个最有实际意义的约束条件：认识主体。信息定义就转化为“认识论”层次的信息定义。,“认识论”定义,即：信息是认识主体（生物或机器）所感知的或所表述的相应事物的运动状态及其变化方式（包括状态及其变化方式的形式、含义和效用）。,全 信 息,同时考虑事物运动状态及其变化方式的外在形式、内在含义和效用价值的认识论层次信息。,语法信息,语义信息,语用

5、信息,全 信 息,信息的重要性质：,信息消息信号区别与联系：,消息是指担负着传送信息任务的单个符号或符号序列。包括文本、数据、语言、图形和图像等。是具体的。信号是消息的物理体现，为了在信道上传输消息，就必须把消息加载到具有某种物理特征的信号上去。是物理的。信息是消息中的未知成分（不确定性），或者说是消息中的有用成分。是抽象的。通信系统传输的是信号，信号是消息的载体，消息中的未知成分是信息。,信息的直观认识1,信道上传送的是随机变量的值。这就是说，我们在收到消息之前，并不知道消息的内容。否则消息是没有必要发送的。 消息随机变量有一个概率分布。 消息随机变量的一个可能取值就称为一个事件。,信息的直

6、观认识2,事件发生的概率越小，此事件含有的信息量就越大。（不太可能发生的事件竟然发生了，令人震惊）例事件“中国足球队5：0力克韩国足球队” 此事件含有的信息量大。（小概率事件发生了，事件信息量大）例事件“中国足球队0：1负于韩国足球队” 此事件有的信息量小。（大概率事件发生了，事件信息量小）,信息的直观认识3,消息随机变量的随机性越大，此消息随机变量含有的信息量就越大。例消息随机变量X=“中国足球队与巴西足球队比赛的结果” 则消息随机变量X含有的信息量小。例消息随机变量Y=“意大利足球队与德国足球队比赛的结果” 则消息随机变量Y含有的信息量大。,信息的直观认识4,两个消息随机变量的相互依赖性越

7、大，它们的互信息量就越大。例X=呼和浩特明日平均气温, Y=包头明日平均气温，Z=北京明日平均气温，W=纽约明日平均气温。 则X与Y互信息量大， X与Z互信息量小得多， X与W互信息量几乎为0 。,按照信息的性质,按照信息的地位,信息的分类,按照信息的作用,信息的分类,信息的分类,香农信息论主要讨论的是语法信息中的概率信息，本书也以概率信息为主要研究对象。,在人类历史的长河中，信息传输和传播手段经历了五次重大变革：,1,2,3,4,5,信息论的起源、发展及研究内容,1948年以“通信的数学理论”（A mathematical theory of communication）为题公开发表，标志着

8、信息论的正式诞生。,起 源,50 年代，信息论在学术界引起了巨大反响。,60 年代，信道编码技术有了较大发展，使它成为信息论的又一重要分支。,后来，人们逐渐意识到信息安全是通信系统正常运行的必要条件。于是，把密码学也归类为信息论的分支。信息论不仅在通信、广播、电视、雷达、导航、计算机、自动控制、电子对抗等电子学领域得到了直接应用，还广泛地渗透到诸如医学、生物学、心理学、神经生理学等自然科学的各个方面，甚至渗透到语言学、美学等领域。,70年代以后，多用户信息论成为中心研究课题之一。,发 展,信源,信道,信宿,信源编码,加密,信道编码,调制器,解调器,信道译码,解密,信源译码,通信系统模型,信息论

9、研究对象,香农信息论,所有研究信息的识别、控制、提取、变换、传输、处理、存贮、显示、价值、作用、安全以及信息量的大小的一般规律以及实现这些原理的技术手段的工程学科，信息论的完备和延伸，都属于广义信息论的范畴。,广义信息论,总之，人们研究信息论的目的是为了高效、可靠、安全并且随心所欲地交换和利用各种各样的信息。,小 结,信息的理解，信息、信号、消息的联系，信息的性质；信息论的研究内容及意义，通信系统模型；预习第2章中2.1.1,2.1.2,信息论与编码Information Theory and coding,电子信息工程系 宋丽丽Email: ,上次课的回顾,什么是信息？信号，消息，信息的区别

10、？通信系统模型Shannon信息论重点研究内容？,通信系统模型,对信息论的学习从信源开始由于信源发送什么消息预先是不可知的，只能用概率空间来描述信源。,随机变量X、Y分别取值于集合,联合随机变量 取值于集合,记,概率论知识复习,满足下面一些性质和关系：,1,2,3,无条件概率、条件概率、联合概率,4,5,6,问题的引出,信息论的发展是以信息可以度量为基础的，度量信息的量称为信息量。对于随机出现的事件，它的出现会给人们带来多大的信息量？举例： 甲告诉乙“你考上研究生”，那么乙是否得到信息？ 丙再次告诉乙同样的话，那么乙是否得到信息？,2.1 单符号离散信源,第2章：信源和信源熵,信源分类,单符号

11、离散信源,信源发出的消息是离散的，有限的或可数的，且一个符号代表一条完整的消息。例如： 投骰子每次只能是1，2，6中的某一个。 其中的数叫做事件/元素，以一定的概率出现； 信源可看作是具有一定概率分布的某些符号的集合。,对于离散随机变量，取值于集合,单符号离散信源的数学模型为,(2.1.2),单符号离散信源的数学模型,需要注意 的是：大写字母X 代表随机变量，指的是信源整体。带下标的小写字母: 代表随机事件的某一结果或信源的某个元素。两者不可混淆。,单符号离散信源的数学模型,一、信息量,单位：比特(2为底)、奈特、笛特（哈特）三个信息单位之间的转换关系如下：,定义：,由式(2.1.3)可知，一

12、个以等概率出现的二进制码元(0,1)所包含的自信息量为1bit。,例题,例2.1.1,这四种气候的自信息量分别为 :,某地二月份天气的概率分布统计如下：,1,是非负值,2,3,的单调递减函数。,4,自信息量 的性质,必然事件,不可能的事件,联合自信息量,针对两个符号离散信源,代入式(2.1.3)就有,定义：,联合自信息,条件自信息量,定义：,联合自信息量和条件自信息也满足非负和单调递减性 ，同时，它们也都是随机变量，其值随着变量 的变化而变化。,三者之间的关系,二、互信息量和条件互信息量,互信息量,离散信源X的数学模型为,信宿Y的数学模型为,如果信道是理想的，发出ai收到ai则所获得的信息量a

13、i的不确定度I(ai)；如果信道不理想，发出ai收到bj,由bj推测ai的概率，,互信息量的定义,互信息量的定义1,例2.1.2,继续讨论上一节的例题，即某地二月份天气构成的信源为,“今天不是晴天”作为收到的信息b1，计算b1与各天气之间的互信息量。,例题,今天不是晴天。把这句话作为收到的信息 当收到 后，各种天气发生的概率变成后验概率。其中,互信息量的定义2,通信前,先验不定度（联合自信息量）,互信息量的定义3,后验不定度,通信后,互信息量的定义3,这样，通信后流经信道的信息量，等于通信前后不定度的差,互信息量的定义3,互信息的性质,对称性,当X和Y相互独立时，互信息为0,1,2,互信息的性

14、质,互信息量可为正值或负值,3,互信息量为正，bj使ai的不确定度减小，上例中，“今天不是晴天”,为0，二者相互独立，“今天我很高兴”,为负，bj没有使ai的不确定度减小，“今天有风”。,条件互信息量,(2.1.13),在你不知道今天是星期几的情况下，问朋友“明天是星期几”则答案中可能存在的信息量是多少？如果你知道今天是星期四提出同样的问题则答案所含信息量是多少？ A事件-不知道今天是星期几的情况下，问朋友“明天是星期几” B事件-知道今天是星期四明天是星期几,练习,小结,信源类型 信息量及性质互信息量及性质,思考题与作业,思考题: 12枚同值的硬币，一枚为假，其重量与其他不同，用天平（无砝码

15、），找出来这枚硬币所使用的最少次数是多少？作业：2-2，2-3，2-4,信息论与编码Information Theory and coding,电子信息工程系,内蒙古工业大学,上次课内容复习思考题解答,问题的引出,哪个信源的不确定度小？,X的不确定度小，X中a1出现的可能性。,信源熵,已知单符号离散无记忆信源的数学模型,信源熵,信源熵,各离散消息自信息量的数学期望，即信源的平均信息量。,（2.1.16）,信源的信息熵；香农熵；无条件熵；熵函数；熵。单位：比特/符号。（底数不同，单位不同）,例2.1.3,由式(2.1.16)的定义，该信源的熵为,继续讨论上一节的例题，即某地二月份天气构成的信源为

16、,信源熵H(X)表示信源输出后，离散消息所提供的平均信息量。,信源熵H(X)表示信源输出前，信源的平均不确定度。,信源熵H(X)反映了变量X的随机性。,1,2,3,信源熵的意义,H(X)=0.08bit/sign,H(Y)=1bit/sign,说明X的不确定小。,信源熵与信息量的比较,熵 信息量,例题2.1.4：,条件熵,信道疑义度,损失熵,噪声熵,联合熵,非负性 H(X) 00p(ai)1，当取对数的底大于1时，log p(ai)0，- p(ai) log p(ai) 0，即得到的熵为正值。只有当随机变量是一确知量时熵才等于零。,信息熵的基本性质,信息熵的基本性质,对称性 X中的n个消息概率

17、改变顺序，不影响熵的值。,X与Z信源的差别：它们所选择的具体消息/符号含义不同X与Y信源的差别：选择的同一消息,概率不同三者的信源熵是相同的，总体统计特性相同,信息熵的基本性质,定理,信源中包含n个不同离散消息时，信源熵H(X)有,当且仅当X中各个消息出现的概率全相等时，上式取等号。,最大离散熵定理,信息熵的基本性质,证明：,对于单符号离散信源，当信源呈等概率分布时具有最大熵。,二进制信源是离散信源的一个特例。,H(X) = -log (1-) log(1-) =H(),即信息熵H(x)是的函数。取值于0，1区间，可画出熵函数H() 的曲线来，如右图所示。,举例,习题P68 2.6,？H(X)

18、log6 不满足信源熵的极值性,扩展性性质说明：由n个消息增加到n+1个，若它的概率很小，可忽略对熵的贡献，虽然概率很小的事件出现后，给予接收者的信息量很大，但对熵的贡献很小，可以忽略不计,信息熵的基本性质,确定性 H(1,0)=H(1,0,0)=H(1,0,0,0)=0性质说明：从总体来看，信源虽然有不同的输出符号，但它只有一个符号几乎必然出现，而其它符号则是几乎不可能出现，那么，这个信源是一个确知信源，其熵等于零。,信息熵的基本性质,可加性 H(XY) = H(X)+ H(Y) X和Y独立 H（XY）=H（X）+ H（Y/X） H（XY）=H（Y）+ H（X/Y）,信息熵的基本性质,已知Y

19、后，从中得到了一些关于X的信息，从而使X的不确定度下降。,极值性,信息熵的基本性质,可以证明,上凸性 熵函数具有上凸性，所以熵函数具有极值，其最大值存在。,信息熵的基本性质,加权熵从某种程度上反映了人的主观因素,例,下雪,加权熵的概念(了解),小结与作业,信源熵性质，最大离散熵定理作业: 2.5 2.7(1-3),信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系,复习,信源熵及性质互信息量,研究信源中各个消息之间的关系,平均互信息,一、平均互信息量的定义,平均交互信息量；交互熵,同理，X对Y的平均互信息：,平均互信息量的定义,(2.1.45)

20、,信道中流通信息量的整体测度。,平均互信息量的定义,二、平均互信息的物理意义,平均互信息量是收到Y前、后关于X的不确定度减少的量，即由Y获得的关于X的平均信息量。,1,损失熵表示收到Y后，对X仍存在不确定度，代表信道中损失的信息。,平均互信息量是发送X前、后，关于Y的平均不确定度减少的量。,2,平均互信息的物理意义,噪声熵表示发出X后，对Y仍存在不确定度，由于信道中的噪声引起的。,平均互信息量等于通信前、后，整个系统不确定度减少的量。,平均互信息的物理意义,3,三、平均互信息的性质,对称性,1,非负性,2,说明：从X中提取关于Y的信息量与由Y中提取到X的信息量是相同的，是信息流通的总体测度。,

21、说明：信道每传递一条消息，总能提供一定的信息量。,极值性,1,3,2,极值性,凸函数性,4,1,2,多次处理信息量将减少。,数据处理定理,5,1,2,3,等概率信源的熵最大。,4,5,6,7,三、各种熵之间的关系,H(X) ,H(Y) 信源熵，无条件熵H(X/Y) 疑义度，损失熵H(Y/X) 噪声熵H(XY)联合熵I(X;Y)平均互信息量，交互熵,作业,作业：2-11 H(X)，H(Y) ，H(X/Y) ， H(XY)，H(Z)，I(X;Y)。,信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系 宋丽丽Email: ,信源分类,连续信源,随机变

22、量,信源,离散信源,单符号,多符号,随机矢量,随机过程,离散无记忆信源,离散有记忆信源,平稳序列信源,马尔可夫信源,输出的消息序列中各符号之间无相互依赖关系的信源。亦称为单符号离散平稳无记忆信源的扩展信源。序列长度就是扩展次数。,例:单符号信源0，1,经过二次扩展,变成了：00，01，10，11,经过三次扩展，形成的信源？经过N次扩展，形成的信源？,多符号离散平稳无记忆信源,无记忆信源的扩展信源,数学模型,数学模型,可证明序列信息的熵为,信源熵,单符号信源如下,求二次扩展信源熵,扩展信源：,例题,例题,反映信源记忆特性的两方法：,用联合概率反映信源记忆特性平稳序列信源,用条件概率反映信源记忆特

23、性马尔可夫信源,1,2,有记忆信源,各维联合概率均与时间起点无关,离散平稳信源,二维信源,1,二维信源的信源熵,一般地,信源熵的说明,结论：离散无记忆信源的二次扩展信源可以看作二维离散平稳信源的特例,例2.2.3,原始信源：,条件概率：,例题,平均符号熵：,信源熵：,例题,N维信源,2,N维信源的信源熵,平均符号熵：,极限熵：,平均符号熵与极限熵,对离散平稳信源若H1(X) ，则有以下性质：(1) 多维离散有记忆信源的熵是起始时刻随机变量X1的熵与各阶条件熵之和；(2)条件熵H(XN/X1X2XN-1)随N的增加是递减的；,一些性质,(3) 平均符号熵HN (X)也是随N增加而递减的；(4)

24、H 存在，并且:,一些性质,小结,离散无记忆信源的N次扩展离散平稳有记忆信源平均符号熵极限熵,作业,作业 2.13 2.18,信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系 宋丽丽Email: ,有记忆的特点：,有限的相关符号组构成的序列,有限记忆长度；,发出一个个符号，每发一个符号状态要发生转移。,信源输出不仅与符号集有关，而且与状态有关；,1,2,3,以信源输出符号序列内各符号间条件概率来反映记忆特性的一类信源。,某时刻输出符号仅与此刻信源所处的状态有关；,某时刻所处状态由当前输出符号和前一时刻信源状态唯一确定。,1,2,信源输出当前符

25、号仅与前面m个符号有关的马尔可夫信源。,马尔可夫信源稳定后各状态的极限概率（ ）,状态极限概率的求法，状态转移图,例2.2.4,平稳信源（如果不平稳则先把其变成分段平稳的）。,1,2,1,马尔可夫信源发出一个个符号，有限长度有记忆信源发出一组组符号；,一般有记忆信源用联合概率描述符号间的关联关系，马尔可夫信源用条件概率（状态转移概率）来描述符号间的关联关系；,m阶马尔可夫与一般记忆长度为m的有记忆信源的区别：,1,2,2,马尔可夫信源记忆长度虽然有限，但依赖关系延伸到无穷远。长为m的有限记忆信源符号间的依赖关系仅限于每组内，组与组之间没有依赖关系；,3,4,2.2.5 信源冗余度,空格：0.2

26、 E：0.105 T：0.072 O：0.0654 A：0.063 N：0.059 I：0.055 R：0.054 S：0.052 H：0.047 D：0.035 L：0.029 C：0.023 F、U：0.025 M：0.021 P：0.175 Y、W：0.012 G：0.011 B：0.0105 V：0.008 K：0.003 X：0.002 J、Q：0.001 Z：0.001,英文各个字符的统计概率如下：,例2.2.5,英文字母出现概率统计,信息熵的相对率：,信源的冗余度：,信息变差：,对英语信源：,对离散信源，信源符号等概率分布时熵最大，其平均自信息量记为: H0log q由于信源符号

27、间的依赖关系使信源的熵减小，使下式成立：,信源符号之间依赖关系越强，每个符导提供的平均信息量越小。为此，引入信源的冗余度来衡量信源的相关程度(有时也称为多余度)。,例：英语-字母表 以英文字母组成的信源为例，信源的输出是英文字母组成的序列。英文字母共26个加上空格共27个符号。所以由英文字母组成的信源的最大熵： H0log 274.76（比特符号） 考虑到字母之间的依赖关系，可以把英文信源作进一步的近似，看作为M阶马尔可夫信源。这样可以求得： H14.03 比特符号 H23.32 比特符号 H33.1 比特符号 H1.4 比特符号,熵的相对率：=0.29信源剩余度：=0.71,英文信源的剩余度

28、说明：文中有71是由语言结构定好的；只有29是写文字的人可以自由选择的。在传递或存储英语信息时，那些有关联的字母可进行大幅度地压缩。例如100页的书，大约只要存储29页就可以了，其中71页可以压缩掉。信源的剩余度表示这种信源可压缩的程度。德语、法语等自然语言与英语类似，而汉语信源则复杂得多。,冗余度与传输效率,冗余度与传输可靠性,冗余度与英语学习,?,内蒙古工业大学信息工程学院电子系 宋丽丽,信息论与编码Information Theory and coding,Email：,2.3 连续信源,计算连续信源熵的两种方法：,将连续信源的时间抽样，幅度量化，变成离散消息，再用离散熵计算,只进行抽样

29、，把抽样序列看作量化单位趋于0时的情况，然后定义计算信源熵。,1,2,连续信源的熵,一维概率密度函数（边缘概率密度函数）：,连续信源的数学描述,单变量连续信源的数学模型为：,并满足,连续信源的数学描述,中值定理,连续信源的熵的推导,(x)如图,把X分成n个小区间，等宽,则变量落在第i个区间的概率为:,连续信源的熵的推导,连续信源熵（相对熵）定义：,为了在形式上与离散信源熵统一,熵差仍然具有信息的特征,1,2,求均匀分布的连续信源熵,例2.3.1,例题,连续信源熵 相对熵,离散信源熵 绝对熵,连续信源熵的说明,连续信源熵不是实际输出的信息量，因为丢掉了一项无限大量。但是，在讨论熵差时，两个无限大

30、量可以对消，所以熵差具有信息的特征,连续信源的联合熵、条件熵,2.3.2 几种特殊连续信源的熵,均匀分布的连续信源的熵,1,，,，,均匀分布的连续信源的熵,结论：均匀分布的连续信源熵取决于边界,高斯分布的连续信源的熵,2,高斯分布的连续信源的熵,高斯信源的熵仅与方差有关。,指数分布的连续信源的熵,3,取决于均值,2.3.3 连续信源熵的性质及 最大连续熵定理,连续信源熵可为负值,连续信源熵的可加性,推广到N个变量的情况,1,2,连续信源熵的性质,3,连续信源熵的性质,对称性：,数据处理定理：,连续信源熵的性质,最大连续熵定理,限峰值功率的最大熵定理,若代表信源的N维随机变量取值被限定在一定范围

31、内，在有限定义域内均匀分布的连续信源有最大熵。,1,4,连续信源熵的性质,可以证明,限平均功率的最大熵定理,平均功率为P，均值m受限，当信源概率密度函数为正态分布时，具有最大熵。,2,均值受限条件下的最大熵定理,连续信源输出非负信号的均值受限条件下，指数分布的连续信源具有最大熵。,3,连续信源不存在绝对的最大熵。连续最大熵与信源的限制条件有关。在不同的限制条件下，有不同的最大连续熵。,第二章 小结作业 2.22（1）,信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系 宋丽丽Email: ,信道的主要任务：以信号的形式传输和存储信息。问题：在什

32、么条件下，通过信道的信息量最大，即信道容量的问题。,第3章：信道容量,信道的数学模型和分类,信道的数学模型：,X P(Y/X) Y,输入与输出之间一般不是确定的函数关系，而是统计依赖的。,无干扰信道,有干扰信道,信道的分类,有记忆信道,无记忆信道,信道的分类,单符号 信道,多符号信道,信道的分类,单用户信道,多用户信道,信道的分类,信道的分类,信道容量的定义,(bi/ai）信道的转移概率/信道传递概率,信道转移概率矩阵：,信道的信息传输率,信源熵为H(X)，由于干扰的存在，一般只接收到I(X;Y)。定义:平均每个符号能传送的消息总量为信道的信息传输速率（信息率），R， R=I(X;Y)若平均传

33、送一个符号为t秒，则信道每秒钟平均传送的信息量，,信道容量,I(X;Y)是p(ai)和p(bj/ai)的二元函数。当信道特性p(bj/ai)固定后，I(X;Y)随信源概率分布p(ai)变化。,I(X;Y)是p(ai)的上凸函数，总能找到一个p(ai)使得信息率最大。信道容量：信道中最大的传输速率，C，单位：比特/信道符号单位时间的信道容量，比特/秒,信道容量,信道容量,几种特殊离散信道的容量,一、离散无噪信道1、一一对应的无噪信道,X、Y一一对应,此时H(X/Y)=0，H(Y/X)=0，CmaxI(X;Y)log n (p(ai)=1/n即等概),p(ai),一一对应的无噪信道,2、具有扩展功

34、能的无噪信道,此时，H(X/Y)=0，H(Y/X) 0，且 H(X) H(Y)。所以，C = max H(X) = log n (p(ai)=1/n即等概),p(ai),一个输入对应多个输出,2、具有扩展功能的无噪信道,3、具有归并性的无噪信道,H(X/Y) 0，H(Y/X) = 0,多个输入变成一个输出,结论,无噪信道的信道容量只取决于信道的输入符号数n或输出符号数m，与信源无关。,练习: p101 3.14,二、强对称(均匀)离散信道的信道容量,n X n,：总体错误概率,特点及信道容量,每行、每列都是同一集合各元素的不同排列,特点及信道容量,固定Xai，对Y求和，即选定某一行，对各元素自

35、信息量加权求和。,ai不同时，只是求和顺序不同，结果完全一样，所以Hni与X无关，是常数。,信道容量,？输入符号的概率如何分布，才能使得H（Y）达到最大？,相应的,信道容量,结论：,当输入等概率分布时，强对称离散信道能够传输最大的平均信息量，达到信道容量。信道容量只与信道的输出符号n及信道矩阵的某一行矢量有关。,三、对称离散信道的信道容量,矩阵中的每行都 是集合P = p1,p2, , pn中的诸元素的不同排列，称矩阵的行是可排列的。,矩阵中的每列都是集合Q = q1, q2, ,qm中的诸元素的不同排列，称矩阵的列是可排列的。,如果矩阵的行和列都是可排列的，称矩阵是可排列的。如果一个信道矩阵

36、具有可排列性，则它所表示的信道称为,对称信道中，当nm，Q是P的子集；当n=m时，P=Q。,对称信道,对称离散信道,练习：判断下列矩阵表示的信道是否是对称信道,相应的,对称离散信道的信道容量,强对称信道与对称信道比较：,四、准对称信道离散信道的信道容量,若信道矩阵的行是可排列的，但列不可排列，如果把列分成若干个不相交的子集，且由n行和各子集的诸列构成的各个子矩阵都是可排列的，则称相应的信道为准对称信道。例如下面的矩阵：,例题,假设此时将矩阵的列分为S个子集，每个子集的元素个数分别是m1，m2，ms。,例题,例题,作业,3.2，3.11,信息论与编码Information Theory and

37、coding,内蒙古工业大学电子信息工程系 宋丽丽Email: ,多符号离散信道数学模型,多符号离散信道,多符号信源通过离散信道传输形成多符号离散信道。,多符号离散信道的数学模型,有 个元素,信道矩阵,离散无记忆信道的N次扩展信道,离散无记忆信道的N次扩展信道,无记忆：YK仅与XK有关,离散无记忆信道的N次扩展信道,离散无记忆信道的N次扩展信道的平均互信息量不大于N个变量X1X2.XN单独通过信道 的平均互信息量之和。,离散无记忆信道扩展信道信道容量,结论：如果信道是N次扩展信道，信源也是N次扩展信源，则N次扩展信道的信道容量是离散无记忆信道容量的N倍,独立并联信道的信道容量,N次扩展信道的推

38、广，随机变量取值于不同的符号集,作业,3-6,讲解第二章作业,信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系 宋丽丽Email: ,3.5 连续信道,连续信道的数学模型,加性连续信道,加性连续信道,噪声功率,高斯加性连续信道,输入平均功率,输出平均功率,对于高斯加性信道,高斯加性连续信道,信噪功率比,高斯加性连续信道,香农公式,(bit/s),香农公式,练习 P100 3.8,高斯加性信道带宽为1Mhz，1）已知信号和噪声的平均功率比为10，求信道容量；2）如果信噪比下降至5，要达到相同的信道容量，带宽应为多少？3）若频带减为0.5MHz，

39、保持相同的信道容量，信噪比为多少？,练习,第三章 小结,作业,3-18 3-19 3-20,信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程,第5章：信源编码,信源编码,信源编码是以提高通信的有效性为目的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。,编码器,信源编码的基础是信息论中的两个编码定理： 无失真编码定理 限失真编码定理 无失真编码只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行限失真编码,定长编码定理：,1,消息序列,码序列,定理说明,信息率：,编码效率：,m-码序列中每

40、个符号的可能取值，单个符号的信息量为K-定长编码的长度，总信息量L-信源符号的长度，平均每个符号的信息量为,定理说明,信息率略大于信源熵，可做到无失真译码,例题,P66 例2.4.1结论：定长编码简单，但要达到一定的差错率不易实现，且编码效率低。,对离散无记忆信源，消息长度为L，符号熵为H(X),对信源进行m元变长编码，一定存在无失真的信源编码方法,变长编码定理：,2,如何分离码字？,？,变长编码出现的问题,P66 例2.4.1 只要4个符号一起编码即可满足要求，所以为了提高编码效率，采样变长编码。,要求：码是唯一可译,码的分类,判断以下码字是否可分离？,例2.4.1,克拉夫特不等式,m元长度

41、为Ki的异前置码存在的充要条件是,如上例,即时码的树图结构,树与编码的关系树根码的起点树枝码的进制数节点码字或其部分终结点码字节数码长满树等长码非满树变长码,5.1.2 香农编码,设有离散无记忆信源,1,2,3,4,香农编码方法的步骤,按信源符号的概率从大到小的顺序排队,不妨设,例,编码过程,（1）,作业,5.1,信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系,5.1.3 费诺编码,对概率按m进行分组，使每组概率尽可能相等,给每个分组分配一个码元,对每个分组重复2、3步，直到不可分为止,1,2,3,4,设有一单符号离散无记忆信源,试对该信源

42、编二进制费诺码。,例,编码过程,可以看出本例中费诺码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。,树图：,将信源符号按概率由大到小顺序排队,给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队,给缩减信源中概率最小的符号各分配一个码元,重复步骤2、3直至概率和为1,2,1,4,3,5.1.4 赫夫曼编码,设有一单符号离散无记忆信源,试对该信源编二进制哈夫曼码。,例,编码过程,Huffman码的编码方法不是唯一的首先:每次对缩减信源两个最小的符号分配“0”和“1”码元试任意的;其次:若合并后的新符号的概率与其他符号的概率相等，这几

43、个符号的次序可任意排列;一般将合并的概率放在上面，这样可获得较小的码方差。,说明：,例 设有离散无记忆信源,用两种不同的方法对其编二进制huffman码,方法一,方法二,两种不同的编码方法得到的码字和码长的对比,平均码长和编码效率,码字的码长方差比较,可以看出第二种编码方法的码长方差要小许多,码长变化较小，比较接近平均码长。要求：Huffman编码时应使合并的信源符号位于缩减信源序列尽可能高的位置上，码长变化较小，比较接近平均码长，易于实现。,结论：,三种编码的比较,Huffman:不唯一，但对信源没有特殊要求，且编码效率较高，设备要求简单，综合性能优于另外两种。,相同点：三种编码都考虑了信源

44、的统计特性，使经常出现的信源符号对应较短的码字，使平均码长缩短，实现了信源压缩。,不同点：shnnon：有唯一的编码，但编码效率不是很高；,Fano:编码方法不唯一，适合与分组概率相等或相近的信源；,作业,5.2 5.3 5.4(1,2,3),信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系,5.1.5 游程编码,游程：指数字序列中连续出现相同符号的一段。在二元信源中，连续的一段0称为一个0游程，0的个数称为此游程的长度，同样，也有1游程。 游程序列：用交替出现的0游程、1游程的长度，来表示任意二元序列而产生的一个新序列。它和二元序列是一个一

45、一对应的变换。,000101110010001,31132131,若已知二元序列以0起始，从游程序列很容易恢复成原来的二元序列 游程序列是多元序列，各长度可按赫夫曼编码或其它方法处理以达到压缩码率的目的。,多元信源序列：,冗余位,上面二元1表示信息位，0表示冗余位,5.1.6 冗余位编码,冗余位序列,游程编码,信息序列,赫夫曼编码,对于连续信源输出的消息，首先要在时间上进行采样，然后在取值上进行量化并进而编码。,在符合采样定理的条件下，采样所带来的信息失真可以忽略不计。,量化是用值域上有限个称为量化值中的一个来代替信号值，量化必然带来误差；如果量化后采用无失真编码，那么连续信源编码中的信息失真

46、就都来自量化过程。,5.2 连续信源编码,量化方法：一种是将各个采样时刻的信号值逐个进行量化，称为标量量化；另一种是将个采样时刻的信号值组成一组，将其看作一个维矢量，将这些维矢量逐个进行量化，称为矢量量化。,脉冲编码调制（PCM，pulse code modulation）是研究最早、使用最广的一种最佳标量量化编码。,5.2.1 最佳标量量化,PCM的编码原理：,模拟信号 经过采样，成为时间离散的信号序列 ；将各个采样时刻的信号值逐个量化、编码，得到与取值也是离散的信号量化值序列 相对应的二进制编码序列 。,均匀量化是指在整个量化范围内的量化间隔都是相等，也称为线性量化,(a),(b),均匀量

47、化,四舍五入原则的中平量化特性,由于均匀量化正反两个方向的对称性，可以将其分为极性判断和信号绝对值量化两个步骤。,归一化信号绝对值满足 ，信号的量化数目为 ，则量化间隔 ，码长,(1)对信号值进行极性判断，确定极性码；(2)通过信号绝对值与量化码各位权值组合的逐次比 较，确定量化码；(3)将极性码和量化码组合起来，得到均匀量化编码。,【例5.2.1】已知某一采样时刻的归一化信号值 ，设量化间隔 ，求其均匀量化编码。,确定码长： ；,确定极性码：由于信号值 ，所以极性码 ；,编码过程,确定量化码：信号绝对值与量化码最高位权值比较，由于 ，所以 ；与量化码最高位和次高位权值之和比较，由于 ，所 以

48、 ；与量化码最高位和最低位权值之和比较，由 于 ，所以 ；,故量化码 ；,将其组合，归一化信号值 的均匀量化编码为,量化值与信号值之间由于四舍五入而产生的量化误差一般也称为量化噪声。,第三章习题,信息论与编码Information Theory and coding,内蒙古工业大学电子信息工程系,对于有记忆信源，采样后的信号序列存在时间相关性，仍然对各个采样时刻的信号值逐个进行量化，会造成码长的冗余。,1.预测编码 利用信号序列的时间相关性，通过预测以减少信息 冗余后再进行编码2.变换编码 引入某种变换，将信号序列变换为另一个域上彼此独立或者相关程度较低的序列，同时将能量集中在部分样值上，再对

49、这个新序列进行编码。,5.3 相关信源编码,预测编码原理,将第 个时刻的信号值 记为 ，相应第 个时刻的信号值记为 。,对于时间相关的信号序列，由于 与 相关，故只要知道 ，就可对 进行预测。,设预测值为 ，则 ， 称为预测误差。,通过预测，我们将 所携带的信息量分成了两部分：一部分为 所携带的信息量，它实际上是 所携带的信息量；另一部分是 所携带的信息量，它才是 所携带信息量的新增加部分。只要预测足够准确， 就足够小。,因此，如果是对 进行量化、编码而不是对 进行量化、编码，就会减少信息冗余，从而提高编码效率。,由于预测编码是对 进行量化、编码，接收端译码后也只能得到 ；接收端必须重建 ，而

50、 ，因此接收端也同样需要进行预测。,预测编码,线性预测是最常用的预测方法，其表达为 ，式中 ，称为预测阶数， 为加权系数。,预测阶数应该取多大，加权系数又应该怎样选取，才能在性能和简单上得到合理的折中? 最常用的是增量调制（DM）、差分脉冲编码调制（DPCM）和自适应差分脉冲编码调制（ADPCM，），通常也称为差值编码。,预测编码,一、增量调制,增量调制是预测编码中最简单的一种，增量调制原理如下，其中(a)为发送端，(b)为接收端。,(a),(b),差值编码,在发送端，将信号值 与量化预测值 之差 进行1比特量化，所谓1比特量化，就是只对差值的符号而不是大小进行量化，即当 时， ，否则， 。,