《信息论与编码全部课件》由会员分享,可在线阅读,更多相关《信息论与编码全部课件(397页珍藏版)》请在金锄头文库上搜索。
1、1 绪论1.1 信息的概念1.1.1 信息的定义与性质1.1.2 信息的分类1.2 信息传输系统的组成及功能1.2.1 模拟信息传输系统1.2.2 数字信息传输系统1.3 信息论研究对象和内容1.4 信息论发展简史11.1.1 信息的定义与性质古时的通信:烽火台信息传播五阶段:手势和语言文字印刷术电磁波计算机和通信微电子技术、通信技术和计算机技术促进了信息技术发展。信息产业的发展促进了社会产业结构的变化与发展。21.1.1 信息的定义与性质信息信息:认识主体所感受的或所表达的事物的运动状态和运动状态的变化方式。(1)信息是普遍存在的。(2)信息与物质。(3)信息与能量。(4)人类认识事物,变革
2、事物必须要有信息。信息载体信息载体:运载信息的物质。31.1.1 信息的定义与性质消息消息:以文字、语音、图像等这些能够为人们的感觉器官所感知的物理现象,把客观物质运动和主观思维活动的状态表达出来就成为消息。信号信号:消息的表现形式和载体。同一信息可用不同的信号来表示,同一信号也可表达不同的信息。41.1.1 信息的定义与性质信息信息十分抽象而又复杂的概念,是人们对客观事物感触到的新认识。消息消息信息的载荷者,是描述信息的一种表现形式,是对某个事物的描述和反应。信号信号运载或携带消息的任何物理量,达到迅速有效地传递和交换信息的目的。51.1.1 信息的定义与性质性质性质:(1)普遍性普遍性:信
3、息是普遍存在的。(2)无限性无限性:信息是无限的。(3)相对性相对性:对同一事物不同的观察者所获得的信息量可能不同。 w(4)转换性转换性:信息可以在时间上或空间中从一点转移到另一点。w(5)变换性变换性:信息是可变的,它可以由不同的载体或不同的方法来载荷。61.1.1 信息的定义与性质(6)有序性有序性:信息可以用来消除系统的不定性,增加系统的有序性。(7)动态性动态性:信息具有动态性质,一切活的信息都随时间变化,具有时效性。(8)转化性转化性:在一定条件下,信息可以转化为物质、能量、时间等。 w(9)共享性共享性:同一信息可以被无限的人所获得,可以交流而不会减少。w(10)可量度性可量度性
4、:信息的数量与质量是可量度的即信息量。71.1.2 信息的分类(1)从性质性质分:语法信息、语义信息、语用信息。 随机方式模糊状态 半随机方式 确定型方式(模糊信息)连续状态离散状态离散状态无限状态有限状态有限状态 随机方式(概率信息概率信息)明晰状态 半随机方式(偶发信息) 确定型方式(确定信息)语法信息81.1.2 信息的分类举例说明,两个布袋中装有对人手感觉完全一样的球,但颜色和数量不同,(1)50个红球和50个白球(2)红球、白球、黑球、黄球各25个随意拿出一个球,被告知是红球所获得的信息量。91.1.2 信息的分类(2)按观察的过程分:实在信息、先验信息、实得信息。(3)按信息的地位
5、分:客观信息、主观信息。(4)按作用分:有用信息、无用信息、干扰信息。w(5)按逻辑意义分:真实信息、虚假信息、不定信息。w(6)按传递方向分:前馈信息、反馈信息。101.1.2 信息的分类(7)按生成领域分:宇宙信息、自然信息、社会信息、思维信息等。(8)按应用部门分:工业信息、农业信息、军事信息、政治信息、科技信息、文化信息等。w(9)按信息源的性质信息源的性质分:语声信息、图像信息、文字信息、数据信息、计算信息等。w(10)按载体性质载体性质分:电子信息、光学信息、生物信息等。w(11)按携带信息的信号携带信息的信号形式分:连续信息、离散信息、半连续信息等。111.2.1 模拟信息传输系
6、统该系统传递的是模拟信号,它在任意时刻的取值是任意的,是时间的连续函数。基本模型如图1.1 所示:信息源噪声源变换器调制器发射机信道接收机解调器反变换器信息宿接收端发送端信道1.1模拟信息传输系统的一般模型121.2.1 模拟信息传输系统信息源信息源:产生含有信息的消息,是被传输的对象。信息宿信息宿:信息传送的目的地,即原消息的归宿或接受者。131.2.1 模拟信息传输系统变换器变换器:将非电量变换成宜于远距离传输的电信号。反变换器反变换器:将信息信号恢复成原消息。141.2.1 模拟信息传输系统调制器调制器:将频率较低的信号调制到频率更高的载波信号上。(调制方式有调幅AM、调频FM、调相、单
7、边带调制SSB等)。解调器解调器:从已调的高频载波信号中解调出被传输的低频信息信号。151.2.1 模拟信息传输系统发射机发射机:变频器和功率放大器,使已调载波信号的频率和功率达到实际应用所要求的数值。接收机接收机:低噪声高频放大器、混频器、中频放大器,将微弱信号放大到解调器所需强度的信号,并最大限度地降低信道噪声的影响。161.2.1 模拟信息传输系统信道信道:消息的信号从发射端传到接受端的媒质或通道。(有线信道:架空明线、同轴电缆、波导、光纤等;无线信道:无线电波、激光自由空间传播等)噪声源噪声源:实际传输系统中客观存在的干扰源,有内部噪声和外部干扰两方面。171.2.2 数字信息传输系统
8、该系统中传输的是数字信号,它只能取有限个离散值,且出现的时间也是离散的。基本模型如图1.2 所示:信息源噪声源变换器调制器发射机信道接收机解调器反变换器信息宿接收端发送端信道1.2 数字信息传输系统的一般模型信源编码器信道编码器信道译码器信源译码器181.2.2 数字信息传输系统调制方式有幅度键控ASK、频移键控FSK、相移键控PSK等。w信源编码器信源编码器:模/数(A/D)变换器,将模拟信号变换成数字信号。w信源译码器信源译码器:数/模(D/A)变换器,将数字信号变换成模拟信号。w信道编译码器信道编译码器:提高传输系统的抗干扰能力。191.2.2 数字信息传输系统优点优点:(1)抗干扰能力
9、强,特别在中继传输中尤为明显。(2)可以进行差错控制,提高了信息传输的灵活性。w(3)便于使用现代计算机技术对信号进行处理、存储和变换。w(4)便于加密,实现保密信息传输。201.2.2 数字信息传输系统(5)易于与其他系统配合使用,构成综合业务信息传输网。(6)易于集成化和大规模生产,性能一致性好且成本低。w缺点缺点:w(1)占用信道频带较宽。w(2)要有一个复杂的同步系统。211.3 信息论研究对象和内容研究对象研究对象:消息传输系统即信息传输系统,通信系统。w研究目的研究目的:提高通信系统的可靠性和有效性。w(1)可靠性高:使信源发出的消息经过传输后尽可能准确地不失真地再现在接收端。w(
10、2)有效性高:经济效果好,用尽可能短的时间和尽可能少的设备传送一定数量的信息。221.3 信息论研究对象和内容研究内容研究内容:(1)通信的统计理论的研究。(2)信源的统计特性的研究。(3)收信者接受器官的研究。w(4)编码理论与技术。w(5)如何提高信息传输效率。w(6)抗干扰理论与技术。w(7)噪声中信号检测理论与技术。231.3 信息论研究对象和内容信息论的三个层次:(1)信息论基础(狭义信息论)信息论基础(狭义信息论):主要研究信息的测度、信道容量、信源和信道编码理论等问题。(2)一般信息论一般信息论:主要研究信息传输和处理问题,除香农理论外,还包括噪声理论、信号滤波和预测、统计检测与
11、估计理论、调制理论以及信息处理理论等。(3)广义信息论广义信息论:不仅包括上述两方面内容,还包括与信息有关的领域,如心理学、遗传学、神经生理学、语言学、语义学等。241.4 信息论发展简史电信系统电信系统的发展:电磁理论和电子学理论的发展促进了电信系统的创造发明或改进。1823年-1835年,莫尔斯建立了电报系统。1876年,贝尔发明了电话系统。w1895年,马可尼和波波夫发明了无线电通信。w1925年-1927年,建立起电视系统。w二次大战初期,微波通信系统和微波雷达系统迅速发展起来。w20世纪60年代,人类进入光纤通信时代。251.4 信息论发展简史信息理论信息理论的发展:1924年,奈奎
12、斯特首先将信息率与信号带宽联系起来。1928年,哈特莱引入了非统计(等概率事件)信息量概念。w20世纪40年代初期,维纳把随机过程和数理统计的观点引入通信和控制系统中。w1948、1949年,香农用概率测度和数理统计的方法,系统地讨论了通信的基本问题。261.4 信息论发展简史无失真信源编码无失真信源编码的发展:(香农编码理论)惟一可译码费诺码哈夫曼码(最佳码)算术编码LZ码(通用信源编码)。w信道编码信道编码的发展:w纠错码汉明码(代数编码)卷积码(概率编码)并行极点卷积码。272 信息的量度信息的量度2.1 自信息量和条件自信息量自信息量和条件自信息量2.2 互信息量和条件互信息量互信息量
13、和条件互信息量2.3 离散集的平均自信息量离散集的平均自信息量2.4 离散集的平均互信息量离散集的平均互信息量2.5 例题例题282.1 自信息量和条件自信息量自信息量和条件自信息量2.1.1 自信息量自信息量2.1.2 条件自信息量条件自信息量292.1.1 自信息量自信息量信源发出的消息常常是随机的,其状态存信源发出的消息常常是随机的,其状态存在某种程度的不确定性,经过通信将信息在某种程度的不确定性,经过通信将信息传给了收信者,收信者得到消息后,才消传给了收信者,收信者得到消息后,才消除了不确定性并获得了信息。除了不确定性并获得了信息。获得信息量的多少与信源的不确定性的消除有关。不确定度惊
14、讶度信息量302.1.1 自信息量自信息量(1)直观定义信息量为:)直观定义信息量为:收到某消息获得的信息量收到某消息获得的信息量=不确定性减少的量不确定性减少的量=收收到此消息前关于某事件发生的不确定性到此消息前关于某事件发生的不确定性-收到此消收到此消息后关于某事件发生的不确定性息后关于某事件发生的不确定性(2)无噪声时信息量为:收到消息前获得的信息量=收到此消息前关于某事件发生的不确定性=信源输出的某消息中所含有的信息量312.1.1 自信息量自信息量举例说明,一个布袋中装有对人手感觉完举例说明,一个布袋中装有对人手感觉完全一样的球,但颜色和数量不同,问下面全一样的球,但颜色和数量不同,
15、问下面三种情况下随意拿出一个球的不确定程度三种情况下随意拿出一个球的不确定程度的大小。的大小。(1)99个红球和个红球和1个白球个白球(2)50个红球和个红球和50个白球个白球(3)红球、白球、黑球、黄球各)红球、白球、黑球、黄球各25个个322.1.1 自信息量自信息量事件发生的不确定性与事件发生的概率有事件发生的不确定性与事件发生的概率有关,一般情况下,一个信源可以用一个概关,一般情况下,一个信源可以用一个概率空间来描述,信源的不确定程度可以用率空间来描述,信源的不确定程度可以用这个概率空间的可能状态数目及其概率来这个概率空间的可能状态数目及其概率来描述。描述。332.1.1 自信息量自信
16、息量设信源设信源X的概率空间为的概率空间为其中:其中:X是信源的状态空间,即随机事件的是信源的状态空间,即随机事件的状态数;状态数; 是随机事件可能状态的概率分是随机事件可能状态的概率分布,且布,且 ,各状态是相互独立的。,各状态是相互独立的。通常记为通常记为342.1.1 自信息量自信息量应用概率空间的概念分析上例,设取红球应用概率空间的概念分析上例,设取红球的状态为的状态为x1,白球为白球为x2,黑球为黑球为x3,黄球为黄球为x4,则概率空间为:则概率空间为:(1)(2)(3)352.1.1 自信息量自信息量结论:结论:(1)不确定度与信源概率空间的状态数及)不确定度与信源概率空间的状态数
17、及其概率分布有关。其概率分布有关。(2)信源概率空间的概率分布为等概率时不确定度最大。(3)等概率时,不确定度与信源概率空间的状态数或相应的概率有关。362.1.1 自信息量自信息量任意随机事件的自信息量定义为该事件发任意随机事件的自信息量定义为该事件发生概率的对数的负值。若随机事件生概率的对数的负值。若随机事件 出现的出现的概率为概率为 ,那么它的自信息量为,那么它的自信息量为通常取对数的底为通常取对数的底为2,单位为比特(,单位为比特(bit)。)。372.1.1 自信息量自信息量三个单位间的转换关系为:三个单位间的转换关系为:1奈特奈特=log2e 1.433比特比特1哈特莱哈特莱=lo
18、g210 3.332比特比特自信息量非负且单调递减。自信息量非负且单调递减。0x1log2xf(x)-log2x0x1f(x)382.1.1 自信息量自信息量例:某地的天气情况分布是:晴天占例:某地的天气情况分布是:晴天占1/2,阴天占,阴天占1/4,雨,雨天占天占1/8,雪天占,雪天占1/8。求各种天气的自信息量。求各种天气的自信息量。解:设晴天、阴天、雨天、雪天的状态分别为解:设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4392.1.1 自信息量自信息量在二维联合集在二维联合集 上的元素上的元素 的联合自信的联合自信息量定义为息量定义为其中,其中, 为元素为元素 的二维联合概率
19、。当的二维联合概率。当二者相互独立时二者相互独立时 ,则有,则有 。元素。元素 的不确定度在数值上也等于他们的不确定度在数值上也等于他们的自信息量。的自信息量。402.1.1 自信息量自信息量例例2.1.1 在盒子中放入在盒子中放入n个不同阻值的电阻,随机个不同阻值的电阻,随机取出一个并猜测阻值,概率空间为取出一个并猜测阻值,概率空间为其中其中xi代表阻值为代表阻值为 表示取出电表示取出电阻值为阻值为i 的电阻的概率。假定取出电阻是等概率的,的电阻的概率。假定取出电阻是等概率的,即即 那么被告知取出阻值那么被告知取出阻值为为i的电阻,所获得的信息量为的电阻,所获得的信息量为 412.1.1 自
20、信息量自信息量若盒中放入若盒中放入 个不同阻值的电阻,其中阻个不同阻值的电阻,其中阻值为值为1欧姆的欧姆的1个,个,2欧姆的欧姆的2个,个, n欧姆的欧姆的n个。个。概率空间为概率空间为其中其中xi代表阻值为代表阻值为 表示取出电表示取出电阻值为阻值为i 的电阻的概率。那么被告知取出阻值为的电阻的概率。那么被告知取出阻值为i的电阻,所获得的信息量为的电阻,所获得的信息量为 422.1.2 条件自信息量条件自信息量在联合集在联合集 对事件对事件 ,设在条件设在条件 下,随下,随机事件机事件 的条件概率为的条件概率为 ,那么其条件,那么其条件自信息量定义为自信息量定义为三种自信息量的关系三种自信息
21、量的关系:432.1.2 条件自信息量条件自信息量例例2.1.2 设在一正方形棋盘上共有设在一正方形棋盘上共有64个方格,个方格,如果甲将一粒棋子随机地放在棋盘中某方如果甲将一粒棋子随机地放在棋盘中某方格内让乙猜。格内让乙猜。(1)将方格按顺序编号,猜测顺序号;)将方格按顺序编号,猜测顺序号;(2)将方格按行和列编号并告知行或列编)将方格按行和列编号并告知行或列编号,猜测位置。号,猜测位置。442.1.2 条件自信息量条件自信息量解:由于棋子位置是二维等概率分布,故解:由于棋子位置是二维等概率分布,故 (1)在二维联合集)在二维联合集 上的元素上的元素 的自信息量的自信息量为为(2)在二维联合
22、集在二维联合集 上,元素上,元素 相对相对 的条件的条件自信息量为自信息量为452.2 互信息量和条件互信息量互信息量和条件互信息量2.2.1 互信息量互信息量2.2.2 互信息量的性质互信息量的性质2.2.3 条件互信息量条件互信息量462.2.1 互信息量互信息量(1)通常预先知道信源集合通常预先知道信源集合X的概率空间,的概率空间,即即其中其中 为集合为集合X中各个消中各个消息的取值,概率息的取值,概率 称为称为先验概率先验概率。472.2.1 互信息量互信息量(2)信宿收到的消息符号集合)信宿收到的消息符号集合Y的概率空间为的概率空间为其中其中 为集合为集合Y中各个消息中各个消息的取值
23、。当信宿收到集合的取值。当信宿收到集合Y中的一个符号消息中的一个符号消息后,接收者重新估计关于信源各个消息后,接收者重新估计关于信源各个消息Xi发生发生的概率就成为条件概率的概率就成为条件概率 也称为也称为后验概后验概率率。482.2.1 互信息量互信息量对两个离散随机事件对两个离散随机事件X和和Y,事件事件 的出现给出关的出现给出关于事件于事件 的信息量定义为互信息量的信息量定义为互信息量 ,即,即互信息量定义为后验概率与先验概率比值的对数,也等于自信息量减去条件自信息量。当对数底分别为2、e、10时,互信息量的单位分别为比特、奈特、哈特莱。492.2.1 互信息量互信息量例例2.2.1:当
24、告知不是晴天时,某地的天气情况分:当告知不是晴天时,某地的天气情况分布是阴天占布是阴天占1/2,雨天占,雨天占1/4,雪天占,雪天占1/4。求不是。求不是晴天时,获得的各种天气的互信息量。晴天时,获得的各种天气的互信息量。解:设晴天、阴天、雨天、雪天的状态分别为解:设晴天、阴天、雨天、雪天的状态分别为x1,x2,x3,x4。不是晴天的状态为不是晴天的状态为y1502.2.1 互信息量互信息量此时,各种天气的条件自信息量:此时,各种天气的条件自信息量:512.2.2 互信息量的性质互信息量的性质(1)互信息量的互易性)互信息量的互易性对称性对称性证:证:522.2.2 互信息量的性质互信息量的性
25、质(2)当事件)当事件xi和和yj相互独立时,互信息量相互独立时,互信息量为零。为零。证:由证:由 得得532.2.2 互信息量的性质互信息量的性质(3)互信息量可正可负)互信息量可正可负当后验概率 大于先验概率 时,互信息量为正值,反之为负值。互信息量为正意味着事件 的出现有助于肯定事件 的出现,反之是不利的。542.2.2 互信息量的性质互信息量的性质(4)任何两个事件的互信息量不可能大于)任何两个事件的互信息量不可能大于其中任一事件的自信息量。其中任一事件的自信息量。证:由于证:由于故故552.2.2 互信息量的性质互信息量的性质例例2.2.2 某人某人A预先知道他的三个朋友预先知道他的
26、三个朋友B、C、D中中有一人晚上到他家,且这三人来的可能性相同,有一人晚上到他家,且这三人来的可能性相同,先验概率先验概率 P(B)= P(C)= P(D)=1/3 。但上午A接到D的电话说不能来了,将这次电话作为事件E,那么有后验概率P(D|E)=0, P(B|E)= P(C|E)=1/2。下午又接到C的电话说不能来,将此作为事件F,则有P(C|EF)= P(D|EF)=0, P(B|EF)= 1。562.2.2 互信息量的性质互信息量的性质在接到上午电话后,在接到上午电话后,A获得关于获得关于B、C、D的互信息量为的互信息量为因为因为P(D|E)=0 ,故无需考虑事件故无需考虑事件D与事件
27、与事件E间的互信息量。间的互信息量。在接到两次电话后,在接到两次电话后,A获得关于获得关于B、C、D的互信息量为的互信息量为因为因为P(C|EF)= P(D|EF)=0,故无需考虑事件故无需考虑事件D与事件与事件E间的间的互信息量。互信息量。572.2.3 条件互信息量条件互信息量在联合集在联合集 ,在给定在给定 的条件下,的条件下, 之间之间的互信息量。的互信息量。在联合集在联合集 ,还存在还存在 与与 之间的互信息之间的互信息量。量。582.3 离散集的平均信息量离散集的平均信息量2.3.1 平均自信息量(熵)平均自信息量(熵)2.3.2 熵函数的数学特性熵函数的数学特性2.3.3 条件熵
28、条件熵2.3.4 联合熵(共熵)联合熵(共熵)2.3.5 各种熵的性质各种熵的性质2.3.6 加权熵加权熵592.3.1 平均自信息量(熵)平均自信息量(熵)自信息量是一个随机变量,不能作为整个信源的自信息量是一个随机变量,不能作为整个信源的信息测度,故引入平均自信息量,即信息熵。信息测度,故引入平均自信息量,即信息熵。信息熵H(X)是从整个信源的统计特性来考虑的,是从平均意义上表征信源的总体特性。对某特定的信源,其信息熵只有一个。定义集X上,随机变量自信息I(xi)的数学期望为平均自信息量H(X)即信息熵,简称熵。602.3.1 平均自信息量(熵)平均自信息量(熵)例例2.3.1 有一个布袋
29、内放有一个布袋内放100个球,其中个球,其中80个红球,个红球,20个白球。随便摸一个球猜测是个白球。随便摸一个球猜测是什么颜色,求平均摸取一次获得的信息量。什么颜色,求平均摸取一次获得的信息量。解:设事件解:设事件x1表示摸到红球,事件表示摸到红球,事件x2表示摸表示摸到白球,则概率空间为到白球,则概率空间为612.3.1 平均自信息量(熵)平均自信息量(熵)当告知摸出的是红球时,获得的信息量当告知摸出的是红球时,获得的信息量当告知摸出的是白球时,获得的信息量当告知摸出的是白球时,获得的信息量若每次摸出一个球后又放回去,进行第二次摸取,那么摸取n次中,红球出现的次数为nP(x1) ,白球出现
30、的次数为nP(x2) 。则摸取n次后获得的信息量为62 2.3.1 平均自信息量(熵)平均自信息量(熵)平均随机摸取一次所能获得的信息量为平均随机摸取一次所能获得的信息量为632.3.1 平均自信息量(熵)平均自信息量(熵)信息熵分别为信息熵分别为可见可见 H(Y)H(X) 例2.3.2 比较两个信源642.3.1 平均自信息量(熵)平均自信息量(熵)信息熵的三种物理含义:信息熵的三种物理含义:(1)表示信源输出后每个消息所提供的平)表示信源输出后每个消息所提供的平均信息量。均信息量。(2)表示信源输出前信源的平均不确定性。)表示信源输出前信源的平均不确定性。(3)表征变量的随机性。)表征变量
31、的随机性。652.3.2 熵函数的数学特性熵函数的数学特性因为随机变量集的熵因为随机变量集的熵H(X)只是其概率分布只是其概率分布的函数,所以熵函数的函数,所以熵函数H(X)又可记为又可记为由于概率的完备性 , H(P)实际上是(q-1)元函数。如二元熵 H(P)=Hp,(1-p)=H(p)。662.3.2 熵函数的数学特性熵函数的数学特性设设 为一多元函数,若对于为一多元函数,若对于任意小于任意小于1的正数的正数 以及函数定义域以及函数定义域内的任意两个矢量内的任意两个矢量X1和和X2有有则称则称f(X)为定义域上的上凸函数。为定义域上的上凸函数。0xx1x2f(x1)f(x2)f(x)67
32、2.3.2 熵函数的数学特性熵函数的数学特性(1)对称性)对称性当概率矢量中的各个分量的次序任意互换时,熵函数的值当概率矢量中的各个分量的次序任意互换时,熵函数的值不变,即不变,即例如两个信源例如两个信源信息熵为信息熵为 682.3.2 熵函数的数学特性熵函数的数学特性(2)非负性(离散信源)非负性(离散信源)等号成立的充要条件是当且仅当某等号成立的充要条件是当且仅当某Pi=1,其余的其余的 Pk=0 。这表明确定信源的熵最小。这表明确定信源的熵最小。证:证: 当每一项为零时等号成立,由于 ,故只能有某一个Pi=1,其余的Pk=0692.3.2 熵函数的数学特性熵函数的数学特性(3)扩展性)扩
33、展性证:因为证:因为说明信源的取值数增多时,若这些取值对应的概率很小(接近于零),则信源的熵不变。702.3.2 熵函数的数学特性熵函数的数学特性(4)可加性)可加性如果有两个随机变量如果有两个随机变量X和和Y,他们不是相互他们不是相互独立的,则二维随机变量的熵独立的,则二维随机变量的熵H(XY)等于等于X的无条件熵的无条件熵H(X)加上当加上当X已给定时已给定时Y的条件的条件概率定义的熵的统计平均值概率定义的熵的统计平均值H(Y|X) 。 H(XY) =H(X) +H(Y|X) H(XY) =H(Y) +H(X|Y)712.3.2 熵函数的数学特性熵函数的数学特性(5)极值性)极值性式中,式
34、中,n是集合是集合X的元素数目。的元素数目。上式表明,在离散情况下,集合上式表明,在离散情况下,集合X中的各事中的各事件依件依等概率等概率发生时,熵达到极大值,即发生时,熵达到极大值,即最最大熵定理大熵定理。722.3.2 熵函数的数学特性熵函数的数学特性(6)确定性)确定性从总体看,信源虽然有不同的输出符号,从总体看,信源虽然有不同的输出符号,但当它只有一个符号几乎必然出现,而其但当它只有一个符号几乎必然出现,而其他符号都是几乎不可能出现时,那么这个他符号都是几乎不可能出现时,那么这个信源是一个信源是一个确知信源确知信源,其熵等于零。,其熵等于零。(7)上凸性)上凸性732.3.3 条件熵条
35、件熵条件熵是在联合符号集条件熵是在联合符号集XY上的条件自信息量的联上的条件自信息量的联合概率加权统计平均值。合概率加权统计平均值。条件熵H(X|Y)表示收到全部输出符号后,对信道输出符号集还存在的平均不确定性,称为信道疑义度信道疑义度。条件熵H(Y|X)可以衡量信号通过信道后损失信息量的多少。742.3.4 联合熵(共熵)联合熵(共熵)联合熵是在符号集联合熵是在符号集XY上的每个元素对上的每个元素对xiyj的的自信息量的概率加权统计平均值,其定义自信息量的概率加权统计平均值,其定义式为式为752.3.5 各种熵的性质各种熵的性质(1)联合熵与信源熵、条件熵的关系)联合熵与信源熵、条件熵的关系
36、若集若集X和集和集Y相互独立则有相互独立则有表示熵的可加性。表示熵的可加性。称为熵的强可加性。称为熵的强可加性。762.3.5 各种熵的性质各种熵的性质推广到多个随机变量构成的概率空间之间推广到多个随机变量构成的概率空间之间的关系。设有的关系。设有N个变量个变量 ,其联,其联合熵可表示为合熵可表示为若若N个变量相互独立,则有个变量相互独立,则有772.3.5 各种熵的性质各种熵的性质(2)联合熵与信源熵的关系)联合熵与信源熵的关系当且仅当两个集合相互独立时,上式取等号,此当且仅当两个集合相互独立时,上式取等号,此时可得联合熵的最大值,即时可得联合熵的最大值,即此性质同样可推广到N个变量构成的概
37、率空间等号成立的充要条件是概率空间相互独立。782.3.5 各种熵的性质各种熵的性质(3)信源熵与条件熵的关系)信源熵与条件熵的关系当且仅当两个集合相互独立时,上式取等号。当且仅当两个集合相互独立时,上式取等号。792.3.5 各种熵的性质各种熵的性质例例2.3.3 输入输出的联合分布如下表输入输出的联合分布如下表 Y Xy1y2y3y4x10.25000x20.100.3000x300.050.100x4000.050.10x5000.050802.3.5 各种熵的性质各种熵的性质例例2.3.4 P(x),P(y|x) ,P(xy)如下表如下表 XABC P(x)1/21/31/6P(y|x
38、)D1/43/101/6E1/41/51/2F1/41/51/6G1/43/101/6 P(xy) XABC YD1/81/101/36E1/81/151/12F1/81/151/36G1/81/101/36812.3.5 各种熵的性质各种熵的性质例例2.3.5 P(ij) i012 j01/41/18011/181/31/18201/187/36 P(j|i) i012 j09/111/8012/113/42/9201/87/903121/32/3P(v)1.50.55/9v一个连续信源的概率分布密度822.3.6 加权熵加权熵设有随机变量设有随机变量X,引入事件的重量后,其概率空间为引入事
39、件的重量后,其概率空间为其中其中离散无记忆信源离散无记忆信源X P W的加权熵定义为的加权熵定义为832.3.6 加权熵加权熵重要性质:重要性质:842.4 离散集的平均互信息量离散集的平均互信息量2.4.1 平均条件互信息量平均条件互信息量2.4.2 平均互信息量平均互信息量2.4.3平均互信息量的性质平均互信息量的性质852.4 离散集的平均互信息量离散集的平均互信息量以以X P表示输入概率空间表示输入概率空间862.4 离散集的平均互信息量离散集的平均互信息量以以Y P表示输出概率空间表示输出概率空间872.4 离散集的平均互信息量离散集的平均互信息量X和和Y的联合空间的联合空间882.
40、4 离散集的平均互信息量离散集的平均互信息量以以XY p(xy)表示联合概率空间,一般有表示联合概率空间,一般有当事件当事件xi和和yj相互独立时有相互独立时有若上式对所有的若上式对所有的i,j成立,则称集成立,则称集X与与Y统计统计独立,否则称为统计相关。独立,否则称为统计相关。892.4.1 平均条件互信息量平均条件互信息量在联合集在联合集XY上,上,由由yj提供的关于提供的关于集集X的的平均条件互信息量平均条件互信息量等于由等于由yj提供的互信息量在整个提供的互信息量在整个X中的后验概率加权的平中的后验概率加权的平均值,其定义式为均值,其定义式为联合集XY上的平均条件互信息量有当且仅当集
41、X中的各个xi都与事件yj相互独立时取等号。902.4.2 平均互信息量平均互信息量互信息量在整个集上的概率加权平均值,称为平互信息量在整个集上的概率加权平均值,称为平均互信息量均互信息量当事件xi与yj相互独立时912.4.3 平均互信息量的性质平均互信息量的性质(1)非负性:)非负性: 当且仅当事件当且仅当事件xi与与yj相相互独立时取等号。互独立时取等号。(2)对称性922.4.3 平均互信息量的性质平均互信息量的性质(3)平均互信息与各类熵的关系)平均互信息与各类熵的关系用维拉图表示为用维拉图表示为H(X)H(Y)H(X|Y)I(X;Y)H(Y|X)H(XY)932.4.3 平均互信息
42、量的性质平均互信息量的性质(4)极值性)极值性(5)凸函数性平均互信息量是信源概率分布p(x)和信道传递概率p(x|y)的凸函数。943 无失真信源与信息熵无失真信源与信息熵3.1 信源的数学模型及其分类信源的数学模型及其分类3.2 离散无记忆信源离散无记忆信源3.3 离散无记忆信源的扩展信源离散无记忆信源的扩展信源3.4 离散平稳信源离散平稳信源3.5 马尔可夫信源马尔可夫信源3.6 信源的相关性和剩余度信源的相关性和剩余度953.1 信源的数学模型及其分类信源的数学模型及其分类3.1.1 信源的数学模型信源的数学模型3.1.2 信源的分类信源的分类963.1.1 信源的数学模型信源的数学模
43、型(1) 离散信源离散信源信源输出的是单个符号或代码的消息,信源符号信源输出的是单个符号或代码的消息,信源符号集的取值是有限的或可数的,可以用一维离散型集的取值是有限的或可数的,可以用一维离散型随机变量来描述,其数学模型是随机变量来描述,其数学模型是973.1.1 信源的数学模型信源的数学模型(2) 连续信源连续信源信源输出的是单个符号或代码的消息,信源符号信源输出的是单个符号或代码的消息,信源符号集的取值是连续的,可以用一维连续型随机变量集的取值是连续的,可以用一维连续型随机变量来描述,其数学模型是来描述,其数学模型是其中其中p(x)为连续随机变量为连续随机变量X的概率密度函数,的概率密度函
44、数,(a,b)为为X的存在域。的存在域。983.1.1 信源的数学模型信源的数学模型若若N维随机矢量维随机矢量 中中信源的信源的N重概率空间为重概率空间为这个空间共有元素qN个,取决于序列长度N和符号集的符号个数q 。993.1.2 信源的分类信源的分类(1)按照消息取值集合以及取值时刻集合)按照消息取值集合以及取值时刻集合的离散性和连续性,信源可分为的离散性和连续性,信源可分为数字信源数字信源和模拟信源(波形信源)和模拟信源(波形信源)。(2)按照某取值时刻消息的取值集合的离散性和连续性,信源可分为离散信源离散信源和连续信源和连续信源。1003.1.2 信源的分类信源的分类(3)按照信源输出
45、消息所对应的随机序列)按照信源输出消息所对应的随机序列的平稳性,信源可分为的平稳性,信源可分为平稳信源和非平稳平稳信源和非平稳信源。信源。w(4)按照信源输出的信息所对应的随机)按照信源输出的信息所对应的随机序列中随机变量前后之间有无统计依赖关序列中随机变量前后之间有无统计依赖关系,信源可分为系,信源可分为无记忆信源和有记忆信源。无记忆信源和有记忆信源。1013.1.2 信源的分类信源的分类在某些简单情况下,信源发出的一个个符在某些简单情况下,信源发出的一个个符号是彼此统计独立的,并且它们具有相同号是彼此统计独立的,并且它们具有相同的概率分布,则的概率分布,则N维随机矢量的概率分布满维随机矢量
46、的概率分布满足足其中,其中,这种信源称为离散无记忆信源。这种信源称为离散无记忆信源。1023.1.2 信源的分类信源的分类在通常情况下,信源发出的符号是彼此依在通常情况下,信源发出的符号是彼此依赖的,要引入赖的,要引入条件概率条件概率分布来说明它们间分布来说明它们间的关联,这种信源称为的关联,这种信源称为有记忆信源有记忆信源。w有记忆信源可用有限状态马尔可夫链来有记忆信源可用有限状态马尔可夫链来描述。当信源记忆长度为描述。当信源记忆长度为m+1时,称为时,称为m阶马尔可夫信源阶马尔可夫信源,即信源每次发出的符号,即信源每次发出的符号只与前只与前m个有关个有关,与更前面的符号无关。与更前面的符号
47、无关。1033.2 离散无记忆信源离散无记忆信源在信源在信源X中,事件中,事件xi发生的概率为发生的概率为p(xi) ,则,则xi所所含的自信息量定义为含的自信息量定义为 I(xi) =-logp(xi)信源输出各消息的自信息信源输出各消息的自信息I(xi)的数学期望为的数学期望为信源的平均自信息量信源的平均自信息量H(X)即信源的信息熵。即信源的信息熵。1043.3 离散无记忆信源的扩展信源离散无记忆信源的扩展信源3.3.1 最简单的离散信源最简单的离散信源3.3.2 N次扩展信源次扩展信源3.3.3 N次扩展信源的熵次扩展信源的熵1053.3.1 最简单的离散信源最简单的离散信源最简单的离
48、散信源的输出可用一维离散随机变量描述。最简单的离散信源的输出可用一维离散随机变量描述。对于二进制信源,其数学模型为对于二进制信源,其数学模型为1063.3.2 N次扩展信源次扩展信源(1)离散无记忆二进制信源)离散无记忆二进制信源X的二次扩展的二次扩展信源信源每两个二进制数字组成一组,新的等效信源的输出符号为每两个二进制数字组成一组,新的等效信源的输出符号为x1=00, x2= 01, x3= 10, x4= 11。二次扩展信源的数学模型为二次扩展信源的数学模型为其中其中1073.3.2 N次扩展信源次扩展信源(2)离散无记忆二进制信源)离散无记忆二进制信源X的的三次扩展三次扩展信源信源每三个
49、二进制数字组成一组,新的等效信源的输出符号为每三个二进制数字组成一组,新的等效信源的输出符号为x1=000, x2= 001, x3= 100, ,x8= 111。三次扩展信源的数学模型为三次扩展信源的数学模型为其中其中1083.3.2 N次扩展信源次扩展信源以此类推,由以此类推,由N个二进制数字为一组构成的个二进制数字为一组构成的新信源共有新信源共有2N个符号,每个符号长度为个符号,每个符号长度为N ,称为称为二进制信源的二进制信源的N次扩展信源。次扩展信源。1093.3.2 N次扩展信源次扩展信源(3)离散无记忆信源的)离散无记忆信源的N次扩展次扩展设一个离散无记忆信源设一个离散无记忆信源
50、X的概率空间为的概率空间为wq为信源的符号个数,则信源为信源的符号个数,则信源X的的N次扩展信源用次扩展信源用XN表示,表示,它是具有它是具有qN个符号的离散信源,其个符号的离散信源,其N重概率空间为重概率空间为1103.3.3 N次扩展信源的熵次扩展信源的熵根据信息熵的定义,离散无记忆信源根据信息熵的定义,离散无记忆信源X的的N次扩展信源次扩展信源XN的熵等于信源的熵等于信源X的熵的的熵的N倍,倍,即即 H(XN)=NH(X) 证明:证明: 见教材见教材47页页1113.3.3 N次扩展信源的熵次扩展信源的熵例例3.3.1(见教材(见教材48页)页)X2信源符号xix1x2x3x4x5x6x
51、7x8x9符号序列x1 x1x1 x2x1 x3x2 x1x2 x2x2 x3x3 x1x3 x2x3 x3概率p(xi)1/41/81/81/81/161/161/81/161/161123.4 离散平稳信源离散平稳信源3.4.1 定义定义3.4.2 N长信源序列的熵长信源序列的熵1133.4.1 定义定义定义:定义:信源产生的随机序列信源产生的随机序列 满足满足:1)所有)所有 都取值于有限的信源符都取值于有限的信源符号集号集 ;2)随机序列是平稳的,即对所有的非负整)随机序列是平稳的,即对所有的非负整数数 有有1143.4.1 定义定义一维平稳信源:一维平稳信源:任意两个不同时刻信源发出
52、符号的概率分任意两个不同时刻信源发出符号的概率分布完全相同,即布完全相同,即其中,其中,i,j为任意整数为任意整数1153.4.1 定义定义二维平稳信源:二维平稳信源:除上述条件外,如果联合概率分布除上述条件外,如果联合概率分布p(x1x2)也与时间起点无关,即也与时间起点无关,即其中,其中,i,j为任意整数为任意整数1163.4.1 定义定义完全平稳信源:完全平稳信源:如果各维联合概率分布均与时间起点无关,如果各维联合概率分布均与时间起点无关,即当即当t=i,t=j,(i,j为任意整数且不相等)时有为任意整数且不相等)时有1173.4.2 N长信源序列的熵长信源序列的熵平稳有记忆信源平稳有记
53、忆信源发出符号序列为发出符号序列为 ,假设,假设信源符号间的依赖长度为信源符号间的依赖长度为N,则联合概率为则联合概率为1183.4.2 N长信源序列的熵长信源序列的熵1193.4.2 N长信源序列的熵长信源序列的熵例:设有一信源,产生例:设有一信源,产生0,1序列的消息,且序列的消息,且在任意时间,不论前面发生过什么符号,在任意时间,不论前面发生过什么符号,均按均按P(0)=0.4, P(1)=0.6的概率发出符号。的概率发出符号。(1)试问这个信源是否是平稳的。)试问这个信源是否是平稳的。(2)计算)计算(3)计算)计算H(X4)并写出并写出X4信源中可能有的信源中可能有的所有符号。所有符
54、号。1203.4.2 N长信源序列的熵长信源序列的熵解解:(1)依题意,信源发出符号的概率分布与)依题意,信源发出符号的概率分布与时间平移无关,且信源发出的序列之间也时间平移无关,且信源发出的序列之间也是彼此无依赖的,故此信源是平稳信源,是彼此无依赖的,故此信源是平稳信源,而且是离散无记忆信源。而且是离散无记忆信源。1213.4.2 N长信源序列的长信源序列的熵熵(2)信源概率空间为信源概率空间为可计算得可计算得因为信源是平稳无记忆信源,所以因为信源是平稳无记忆信源,所以1223.4.2 N长信源序列的熵长信源序列的熵(3)X4信源中可能有的符号有信源中可能有的符号有16种种000000010
55、01001001000001101101100010110101001110111100111101111111233.4.2 N长信源序列的熵长信源序列的熵对于离散、平稳、有记忆信源,当对于离散、平稳、有记忆信源,当 时,时,下列结论成立:下列结论成立:(1)条件熵)条件熵 随随N的增加是的增加是非递增的(即非递增的(即N的单调非增函数的单调非增函数););(2)(4)(3)HN (X)是随是随N的增加是非递增的(即的增加是非递增的(即N的的单调非增函数);单调非增函数);1243.5 马尔可夫信源马尔可夫信源3.5.1 有限状态马尔可夫链有限状态马尔可夫链3.5.2 马尔可夫信源马尔可夫信
56、源1253.5.1 有限状态马尔可夫链有限状态马尔可夫链设设 为一随机序列,时间参数集为一随机序列,时间参数集 ,其状态空间,其状态空间 ,若对所有的,若对所有的 ,有,有则称则称 为马尔可夫链。为马尔可夫链。1263.5.1 有限状态马尔可夫有限状态马尔可夫链链转移概率转移概率性质:性质:1273.5.1 有限状态马尔可夫链有限状态马尔可夫链当当n-m=1时,即时,即pij(m,m+1)的情况下,将其的情况下,将其记为记为pij(m) , 称为称为基本基本转移概率或转移概率或一步一步转移概率。转移概率。定义定义k步步转移概率转移概率规定规定零步零步转移概率转移概率1283.5.1 有限状态马
57、尔可夫链有限状态马尔可夫链由于系统在任一时刻可处于状态空间中任由于系统在任一时刻可处于状态空间中任一状态,故转移概率是一个矩阵,也是一一状态,故转移概率是一个矩阵,也是一个个随机矩阵随机矩阵。w一般情况下,状态空间一般情况下,状态空间 是一是一个可数无穷集合,故转移矩阵是一个无穷个可数无穷集合,故转移矩阵是一个无穷列的随机矩阵。列的随机矩阵。1293.5.1 有限状态马尔可夫链有限状态马尔可夫链如果在马尔可夫链中如果在马尔可夫链中即从状态即从状态i转移到状态转移到状态j的概率与的概率与m无关,则称这类无关,则称这类马尔可夫链为马尔可夫链为时齐时齐马尔可夫链或马尔可夫链或齐次齐次马尔可夫链,马尔
58、可夫链,也称为也称为具有平稳转移概率具有平稳转移概率的马尔可夫链。的马尔可夫链。如果状态空间如果状态空间 是无穷集合,是无穷集合,则称为则称为可数无穷状态可数无穷状态的马尔可夫链。的马尔可夫链。w如果状态空间如果状态空间 是有限的,是有限的,则称为则称为有限状态有限状态的马尔可夫链。的马尔可夫链。1303.5.1 有限状态马尔可夫链有限状态马尔可夫链对于具有对于具有m+r步转移概率的时齐马尔可夫链,存在步转移概率的时齐马尔可夫链,存在切切-柯柯方程方程利用该式就可以用一步转移概率表达多步转移概率。利用该式就可以用一步转移概率表达多步转移概率。但是转移概率不包含初始分布。但是转移概率不包含初始分
59、布。1313.5.1 有限状态马尔可夫链有限状态马尔可夫链若若齐次马尔可夫链对一切齐次马尔可夫链对一切i,j存在不依赖于存在不依赖于i的极限的极限则称其具有则称其具有遍历性遍历性,pj称为称为平稳分布平稳分布,也是该马,也是该马尔可夫链的初始分布。尔可夫链的初始分布。1323.5.1 有限状态马尔可夫链有限状态马尔可夫链成为成为遍历遍历马尔可夫链的充分条件是具有马尔可夫链的充分条件是具有不不可约性可约性和和非周期性非周期性。1333.5.1 有限状态马尔可夫链有限状态马尔可夫链不可约性不可约性指对于任意一对指对于任意一对i和和j ,都存在至少都存在至少一个一个k,使,使pij(k)0,即从即从
60、si开始总可能到达开始总可能到达sj。s1s20.50.50.5s30.51可约马尔可夫链1343.5.1 有限状态马尔可夫链有限状态马尔可夫链0.5s1s20.50.50.5s4s30.50.50.50.5周期性马尔可夫链非周期性非周期性指所有指所有pii(n)0的的n中没有比中没有比1大的公大的公因子。因子。1353.5.1 有限状态马尔可夫链有限状态马尔可夫链对于一个有对于一个有r个状态的马尔可夫链,若令个状态的马尔可夫链,若令1363.5.1 有限状态马尔可夫链有限状态马尔可夫链1373.5.1 有限状态马尔可夫链有限状态马尔可夫链对于有限状态马尔可夫链,如果存在一个数集对于有限状态马
61、尔可夫链,如果存在一个数集 ,且满足,且满足则称该马尔可夫链的则称该马尔可夫链的稳态分布稳态分布存在,并有如下性存在,并有如下性质:质:(1)完备性完备性w(2)不变性不变性 WP=W , 若若W(0)=W 则则W(n)=Ww(3)惟一性惟一性1383.5.2 马尔可夫信源马尔可夫信源马尔可夫信源马尔可夫信源:信源输出的符号序列和状态序列满足以下条件:信源输出的符号序列和状态序列满足以下条件:(1)某一时刻信源符号的)某一时刻信源符号的输出输出只与只与当时的信源状态当时的信源状态有关,有关,而与以前的状态无关,即而与以前的状态无关,即w(2)信源状态信源状态只由只由当前输出当前输出符号和符号和
62、前一时刻信源的状态前一时刻信源的状态惟一确定,即惟一确定,即1393.5.2 马尔可夫信源马尔可夫信源例例3.5.1 有一个二进制一阶马尔可夫信源有一个二进制一阶马尔可夫信源X,其信其信源符号集为源符号集为0,1,条件概率为,条件概率为p(0|0)=0.25, p(1|0)=0.75, p(0|1)=0.50, p(1|1)=0.50。求各状求各状态的稳态概率分布态的稳态概率分布W1, W2 。解:信源有两个状态解:信源有两个状态S1=0, S2=1。状态转移矩阵状态转移矩阵 010:0.50:0.251:0.751:0.5状态转移图1403.5.2 马尔可夫信源马尔可夫信源根据稳态分布的性质
63、(根据稳态分布的性质(1)和()和(2)可得:)可得:1413.5.2 马尔可夫信源马尔可夫信源由于状态转移概率完全依赖于给定的条件概由于状态转移概率完全依赖于给定的条件概率,故对一般的率,故对一般的m阶马尔可夫信源阶马尔可夫信源通过引入状态转移概率而转化为马尔可夫链。通过引入状态转移概率而转化为马尔可夫链。其中,状态转移概率其中,状态转移概率 由信源符号条件由信源符号条件概率概率 确定且确定且 。1423.5.2 马尔可夫信源马尔可夫信源当时间足够长后,遍历的当时间足够长后,遍历的m阶马尔可夫信源阶马尔可夫信源可视为可视为平稳信源平稳信源来处理。又因为信源发出来处理。又因为信源发出的符号只与
64、的符号只与最近的最近的m个个符号有关,所以符号有关,所以1433.5.2 马尔可夫信源马尔可夫信源对于时齐、遍历的马尔可夫链,其状态对于时齐、遍历的马尔可夫链,其状态Sj由由 惟一确定,因此有惟一确定,因此有1443.5.2 马尔可夫信源马尔可夫信源1453.5.2 马尔可夫信源马尔可夫信源例例3.5.2 有一个二进制二阶马尔可夫信源有一个二进制二阶马尔可夫信源X,其信其信源符号集为源符号集为0,1,条件概率为,条件概率为p(0|00)= p(1|11)= 0.8, p(1|00)= p(0|11)= 0.2, p(0|01)= p(0|10)=p(1|01)= p(1|10)=0.5。(1)
65、求各状态的稳态概率分布求各状态的稳态概率分布W1, W2 , W3, W4(2)求稳定后各符号的概率分布求稳定后各符号的概率分布p(0),p(1)(3)求信源熵。求信源熵。1463.5.2 马尔可夫信源马尔可夫信源 解:信源有四个状态解:信源有四个状态S1=00, S2=01, S3=10, S4=11 。符号条件概率矩阵为符号条件概率矩阵为01101:0.50:0.5110:0.21:0.81:0.2000:0.5s1s4s2s30:0.81:0.5状态转移图1473.5.2 马尔可夫信源马尔可夫信源(1)根据稳态分布的性质()根据稳态分布的性质(1)和()和(2)可得:)可得:1483.5
66、.2 马尔可夫信源马尔可夫信源 (2)稳定后各符号的概率分布)稳定后各符号的概率分布1493.5.2 马尔可夫信源马尔可夫信源( 3 )信源熵1503.6 信源的相关性和剩余度信源的相关性和剩余度由于信源符号间的由于信源符号间的依赖关系依赖关系使信源的熵减使信源的熵减小,就是信源的相关性。小,就是信源的相关性。如果信源输出符号间的相关性如果信源输出符号间的相关性越长越长,则信,则信源熵源熵减小减小,趋于,趋于极限熵极限熵 。w若相关程度若相关程度减小减小,信源实际熵,信源实际熵增大增大。w只有当信源符号彼此间只有当信源符号彼此间无依赖、等概无依赖、等概率分布率分布时,信源的熵时,信源的熵最大为
67、最大为H0。1513.6 信源的相关性和剩余度信源的相关性和剩余度一个信源输出的符号前后有相关性时,信源输出一个信源输出的符号前后有相关性时,信源输出的熵将减少,输出的总信息量也下降,这就是一的熵将减少,输出的总信息量也下降,这就是一种形式的种形式的剩余或多余剩余或多余。输出同样的信息量有剩余的信源输出的符号数要输出同样的信息量有剩余的信源输出的符号数要比无剩余的信源多。比无剩余的信源多。信源剩余度信源剩余度定义为定义为其中,其中, 为信源为信源实际熵实际熵;H0= Hmax为信源为信源最最大熵大熵,当信源输出符号集有,当信源输出符号集有q个元素且为等个元素且为等概分布时概分布时H0= Hma
68、x=logq ; 称为称为相对率相对率。1523.6 信源的相关性和剩余度信源的相关性和剩余度信源最大可能熵与实际熵的差值定义为信源最大可能熵与实际熵的差值定义为内熵内熵。相对率、剩余度、内熵均可用来表示信源的相对率、剩余度、内熵均可用来表示信源的剩余情况。剩余情况。信源的剩余度表示信源的信源的剩余度表示信源的可压缩程度可压缩程度。w从提高信息传输效率的观点出发,总是希望从提高信息传输效率的观点出发,总是希望减少或去掉剩余度(信源编码)。减少或去掉剩余度(信源编码)。w从提高抗干扰能力的角度出发,总是希望增从提高抗干扰能力的角度出发,总是希望增加或保留剩余度(信道编码)加或保留剩余度(信道编码
69、) 。1533.6 信源的相关性和剩余度信源的相关性和剩余度例:黑白气象传真图的消息只有黑色和白色两种,例:黑白气象传真图的消息只有黑色和白色两种,黑色出现的概率为黑色出现的概率为P(黑黑)= 0.3,白色出现的概率为,白色出现的概率为P(白白)= 0.7。(1)假设图上黑白消息出现前后没有关联,求熵)假设图上黑白消息出现前后没有关联,求熵H(X)。(2)假设消息前后有关联,其依赖关系为假设消息前后有关联,其依赖关系为P(白白|白白)=0.9, P(黑黑|白白)=0.1, P(白白|黑黑)=0.2, P(黑黑|黑黑)=0.8,求熵,求熵H2。(3)分别求上述两种信源的剩余度,并比较分别求上述两
70、种信源的剩余度,并比较H(X)和和H2的大小,说明其物理意义。的大小,说明其物理意义。1543.6 信源的相关性和剩余度信源的相关性和剩余度解:解: 设状态设状态x1=黑,黑,x2=白白(1)假设图上黑白消息出现前后没有关联,)假设图上黑白消息出现前后没有关联,则等效为一个离散无记忆信源,概率空间则等效为一个离散无记忆信源,概率空间为为信息熵信息熵1553.6 信源的相关性和剩余度信源的相关性和剩余度(2)假设消息前后有关联时假设消息前后有关联时,从其依赖关从其依赖关系看出其满足一阶马尔可夫信源的定义,系看出其满足一阶马尔可夫信源的定义,状态空间为状态空间为状态转移矩阵状态转移矩阵黑白0.10
71、.80.20.9状态转移图S2S11563.6 信源的相关性和剩余度信源的相关性和剩余度由图可知,此马尔可夫链满足不可约性和由图可知,此马尔可夫链满足不可约性和非周期性,其稳态分布存在,分别设为非周期性,其稳态分布存在,分别设为P(S1)=W1, P(S2)=W21573.6 信源的相关性和剩余度信源的相关性和剩余度信息熵信息熵1583.6 信源的相关性和剩余度信源的相关性和剩余度(3)两种信源的剩余度)两种信源的剩余度w结果说明,当信源的消息符号之间有依赖时,结果说明,当信源的消息符号之间有依赖时,信源输出消息的不确定性减弱。信源输出消息的不确定性减弱。w信源剩余度反映了消息符号间依赖关系的
72、强信源剩余度反映了消息符号间依赖关系的强弱,剩余度越大,符号间的依赖关系越大。弱,剩余度越大,符号间的依赖关系越大。1594 信道及其容量信道及其容量4.1 信道的分类与描述信道的分类与描述4.2 离散无记忆信道离散无记忆信道4.3 离散无记忆的扩展信道离散无记忆的扩展信道4.4 信道的组合信道的组合4.5 信道容量信道容量4.6 信源与信道的匹配信源与信道的匹配1604.1 信道的分类与描述信道的分类与描述信道是所传信息的载体(消息)的具体形信道是所传信息的载体(消息)的具体形式(信号)所要通过的通道或媒介。式(信号)所要通过的通道或媒介。信息是抽象的但信道是具体的。信息是抽象的但信道是具体
73、的。在信息系统中,信道的主要作用是传输与存储在信息系统中,信道的主要作用是传输与存储信息,而在通信系统中则主要是传输信息,对信息,而在通信系统中则主要是传输信息,对其研究的主要目的是为了描述、度量、分析不其研究的主要目的是为了描述、度量、分析不同类型信道,计算其容量。同类型信道,计算其容量。1614.1 信道的分类与描述信道的分类与描述(一)信道的分类(一)信道的分类(1)按传输媒介的类型划分)按传输媒介的类型划分明线 市内电话的对称电缆电缆 长途电话(小同轴,中同轴)长波中波短波超短波微波(视距接力,卫星电缆,散射通信)光波传输媒介类型有线信道无线信道(空气介质)固体介质混合介质(波导,光缆
74、) 1624.1 信道的分类与描述信道的分类与描述(2)按决定信道的信号与干扰的类型与描述划分)按决定信道的信号与干扰的类型与描述划分 无源热噪声线性叠加干扰 有源散弹噪声 天电脉冲干扰离散-数字信道连续-模拟信道半连续或半离散信号与干扰类型干扰类型信号类型有干扰无干扰 交调乘性干扰 衰落 码间干扰1634.1 信道的分类与描述信道的分类与描述(3)按信道的物理性质(信道的统计特性)按信道的物理性质(信道的统计特性)划分划分线性时变信道非线性时变信道信道参量性质恒参信道(时不变信道)变参(随参)信道1644.1 信道的分类与描述信道的分类与描述(4)按用户类型划分)按用户类型划分(5)按信道的
75、记忆特性划分)按信道的记忆特性划分用户类型二用户信道(点对点通信或两端通信)多用户信道(通信网或多端通信)记忆特性无记忆信道有记忆信道1654.1 信道的分类与描述信道的分类与描述(二)信道描述(二)信道描述三要素:三要素:(1)信道输入统计概率空间:)信道输入统计概率空间:X,p(X)(2)信道输出统计概率空间:信道输出统计概率空间:Y,p(Y)(3)信道本身的统计特性,即转移概率矩阵:信道本身的统计特性,即转移概率矩阵:p(y|x)由此构成对信道整体的描述为:由此构成对信道整体的描述为: X,p(X), p(y|x),Y,p(Y)简记为:简记为: X, p(y|x),Y1664.1 信道的
76、分类与描述信道的分类与描述对离散序列信源可以描述为:对离散序列信源可以描述为:其中:其中:信道转移概率为信道转移概率为1674.2 离散无记忆信道离散无记忆信道(一)离散信道的数学模型(一)离散信道的数学模型1684.2 离散无记忆信道离散无记忆信道1694.2 离散无记忆信道离散无记忆信道根据信道的统计特性不同,离散信道又可分为三根据信道的统计特性不同,离散信道又可分为三种情况:种情况:(1)无干扰信道。输入与输出之间有确定的一一)无干扰信道。输入与输出之间有确定的一一对应关系,即对应关系,即y=f(x),(2)有干扰无记忆信道。有干扰无记忆信道。(3)有干扰有记忆信道。)有干扰有记忆信道。
77、1704.2 离散无记忆信道离散无记忆信道(二)单符号离散信道(二)单符号离散信道1714.2 离散无记忆信道离散无记忆信道(1)二进制对称信道(二元对称信道)二进制对称信道(二元对称信道BSC信道)信道)输入符号集输入符号集A=0,1;输出符号集输出符号集B =0,1;传传递概率为递概率为 1724.2 离散无记忆信道离散无记忆信道且传递概率满足:且传递概率满足:传递矩阵为传递矩阵为XYa1=0a2=1b1=0b2=11-p1-ppp二元对称信道1734.2 离散无记忆信道离散无记忆信道(2)二进制删除信道)二进制删除信道输入符号集输入符号集A=0,1;输出符号集输出符号集B =0,?,1传
78、递矩阵为传递矩阵为且有且有XYa1=0a2=1b1=0b2=1pq1-p1-q二元删除信道?1744.2 离散无记忆信道离散无记忆信道提示:在离散信道中,一般概率关系有:提示:在离散信道中,一般概率关系有:(1)若输入符号的概率已知,)若输入符号的概率已知, 则输入和输出符号的联合概率则输入和输出符号的联合概率而且而且其中其中p(bj|ai)是信道传递概率,称为是信道传递概率,称为前向前向概率,概率, p(ai |bj) 称为称为后向概率后向概率,也是输入符号的,也是输入符号的后验后验概率,概率, p(ai) 是输入符号的是输入符号的先验先验概率。概率。1754.2 离散无记忆信道离散无记忆信
79、道(2)根据联合概率可得出输出符号的概率)根据联合概率可得出输出符号的概率或或P为信道矩阵。为信道矩阵。1764.2 离散无记忆信道离散无记忆信道(3)根据贝叶斯定律可得后验概率)根据贝叶斯定律可得后验概率1774.2 离散无记忆信道离散无记忆信道(三)信道疑义度及平均互信息(三)信道疑义度及平均互信息(1)信道疑义度信道疑义度输入空间输入空间X对输出空间对输出空间Y的条件熵为信道疑的条件熵为信道疑义度,即义度,即表示在输出端收到全部输出符号后,对于表示在输出端收到全部输出符号后,对于输入符号集仍然存在的平均不确定性。输入符号集仍然存在的平均不确定性。1784.2 离散无记忆信道离散无记忆信道
80、(2)平均互信息)平均互信息定义:原始信源熵与信道疑义度之差为平定义:原始信源熵与信道疑义度之差为平均互信息,即均互信息,即特性特性:1)交互性(对称性)交互性(对称性)2)非负性)非负性3)极值性)极值性1794.2 离散无记忆信道离散无记忆信道4)平均互信息与各类熵的关系)平均互信息与各类熵的关系H(X)H(Y)H(X|Y)I(X;Y)H(Y|X)H(XY)维拉图1804.2 离散无记忆信道离散无记忆信道5)平均互信息)平均互信息I(X;Y)是信源概率分布是信源概率分布p(x)的上凸函数,是信道传递概率的上凸函数,是信道传递概率p(y|x)的下凸的下凸函数。函数。例例4.2.1 参见教材参
81、见教材82页页例例4.2.2 参见教材参见教材84页页1814.3 离散无记忆的扩展信道离散无记忆的扩展信道(一)(一)N次扩展信道数学模型次扩展信道数学模型离散无记忆信道的数学模型基本同于单符离散无记忆信道的数学模型基本同于单符号离散信道的数学模型,用概率空间号离散信道的数学模型,用概率空间X,p(bj|ai),Y来描述,但它的输入输出不是单来描述,但它的输入输出不是单个随机变量个随机变量X和和Y ,而是随机而是随机序列序列,传递概率等于对应时刻随机变量的传递概传递概率等于对应时刻随机变量的传递概率的乘积。率的乘积。1824.3 离散无记忆的扩展信道离散无记忆的扩展信道因为输入序列中的每个变
82、量因为输入序列中的每个变量 各取值于同一输入符号集各取值于同一输入符号集X,而符号集而符号集X中中共有共有q个符号,所以随机矢量个符号,所以随机矢量X的可能取值的可能取值有有qN个,同理,随机矢量个,同理,随机矢量Y的可能取值有的可能取值有sN个。根据信道无记忆特性有个。根据信道无记忆特性有N次扩展信道XNYN1834.3 离散无记忆的扩展信道离散无记忆的扩展信道1844.3 离散无记忆的扩展信道离散无记忆的扩展信道(二)(二)N次扩展信道平均互信息次扩展信道平均互信息定理定理1 若信道的输入随机序列为若信道的输入随机序列为 ,通过信,通过信道传输,接收到的随机序列为道传输,接收到的随机序列为
83、 。若。若信道是信道是无记忆无记忆的,即信道传递概率满足的,即信道传递概率满足式中式中Xi和和Yi是随机序列对应的第是随机序列对应的第i位随机变量。位随机变量。1854.3 离散无记忆的扩展信道离散无记忆的扩展信道定理定理2 若信道的输入随机序列为若信道的输入随机序列为 ,经信道,经信道传输接收到的随机序列为传输接收到的随机序列为 。信道传递概率。信道传递概率为为p(y|x),若若信源是无记忆信源是无记忆的,即满足的,即满足式中式中Xi和和Yi是随机序列对应的第是随机序列对应的第i位随机变量。位随机变量。1864.3 离散无记忆的扩展信道离散无记忆的扩展信道若若信道和信源都是无记忆信道和信源都
84、是无记忆的,则的,则一般情况,信道的输入随机序列一般情况,信道的输入随机序列 中的中的随机变量随机变量 取值于同一信源符号集取值于同一信源符号集X,并且具有同一概率分布,而且经相同的信道传输,并且具有同一概率分布,而且经相同的信道传输,接收到的随机序列接收到的随机序列 中的随机变量中的随机变量 也取值于同一符号集也取值于同一符号集Y ,因此有因此有式中式中N是随机序列的长度。是随机序列的长度。1874.4 信道的组合信道的组合(一)串联信道(一)串联信道信道1p(y|x)信道2p(z|xy)XZY串联信道的示意图1884.4 信道的组合信道的组合定理定理1:级联信道中的平均互信息满足以:级联信
85、道中的平均互信息满足以下关系:下关系:定理定理2:若:若X,Y,Z组成一个马尔可夫链,则有组成一个马尔可夫链,则有也称为数据处理定理,表明了信息不增性原理。也称为数据处理定理,表明了信息不增性原理。例例4.4.1 参见教材参见教材92页页1894.4 信道的组合信道的组合(二)并联信道(二)并联信道信道1信道2xyyy两个独立信道的并联xyXx1904.4 信道的组合信道的组合(三)和信道(三)和信道信道1信道2X1Y= Y1+ Y2Y1和信道的模型X2Y2X=X1+X21914.5 信道容量信道容量(一)基本定义(一)基本定义(1)信道的)信道的信息传输率信息传输率R信息传输率信息传输率R是
86、平均每个符号所能传送的信息是平均每个符号所能传送的信息量,而平均互信息量,而平均互信息I(X;Y)就是接收到符号集就是接收到符号集Y后后平均每个符号获得的关于平均每个符号获得的关于X的信息量,故信道的信息量,故信道的信息传输率就是平均互信息量。的信息传输率就是平均互信息量。R=I (X;Y)=H (X)-H (X|Y) 比特比特/符号符号若平均传输一个符号需要若平均传输一个符号需要t秒,则信道每秒钟平秒,则信道每秒钟平均传输的信息量为均传输的信息量为R=I (X;Y)/t 比特比特/秒秒1924.5 信道容量信道容量(2)信道容量)信道容量C的定义的定义定义最大的信息传输率为信道容量定义最大的
87、信息传输率为信道容量C,即即其单位是比特其单位是比特/符号或奈特符号或奈特/符号,相应的符号,相应的p(x)称为称为最佳输入分布最佳输入分布。若平均传输一个符号需要若平均传输一个符号需要t秒钟,则信道单秒钟,则信道单位时间内平均传输的最大信息量为位时间内平均传输的最大信息量为1934.5 信道容量信道容量二进制对称信道的平均互信息为二进制对称信道的平均互信息为它对它对 存在一个极大值,存在一个极大值,因此它的信道容量为因此它的信道容量为C=1-H(p),它只是信道它只是信道传输概率传输概率p的函数,与输入符号集的概率分的函数,与输入符号集的概率分布布p(x)无关。无关。1944.5 信道容量信
88、道容量(二)几种典型信道的容量计算(二)几种典型信道的容量计算(1)离散单个消息信道容量)离散单个消息信道容量1有噪无损信道:一个输入对应多个互不相有噪无损信道:一个输入对应多个互不相交的输出。交的输出。a1a2a3b1b3b5b2b4b6XY有噪无损信道B2B1B31954.5 信道容量信道容量信道的后向概率为信道的后向概率为信道疑义度信道疑义度H(X|Y)=0。信源发生符号信源发生符号ai,并并不依一定概率取不依一定概率取Bi中的某一个中的某一个bj ,因此噪因此噪声熵声熵H(Y |X)0 。平均互信息为平均互信息为I(X;Y)=H(X)0 平均互信息为平均互信息为I(X;Y)=H(Y)N
89、H(S)左边左边表示长为表示长为l的码字符号序列能载荷的最的码字符号序列能载荷的最大信息量。大信息量。右边右边表示长为表示长为N的信源序列平均携带的信息量。的信源序列平均携带的信息量。n故只要码字传输的信息量大于信源序列携故只要码字传输的信息量大于信源序列携带的信息量,总可以实现几乎无失真编码。带的信息量,总可以实现几乎无失真编码。2385.1.3 等长信源编码定理等长信源编码定理编码速率:编码速率:编码效率:编码效率:取等号时得到最佳编码效率。取等号时得到最佳编码效率。2395.1.3 等长信源编码定理等长信源编码定理当允许错误概率当允许错误概率 时,信源序列长时,信源序列长度必满足度必满足
90、2405.1.3 等长信源编码定理等长信源编码定理例例5.1.2 设一简单离散信源如下设一简单离散信源如下对其进行等长近似无失真编码,若取编码对其进行等长近似无失真编码,若取编码效率为效率为95%,差错概率,差错概率 ,求信源符,求信源符号联合编码长度。号联合编码长度。2415.1.3 等长信源编码定理等长信源编码定理解:解:2425.1.4 变长编码定理变长编码定理若对该信源进行变长编码若对该信源进行变长编码2435.1.4 变长编码定理变长编码定理对一个信源中的不同符号采用不同长度的对一个信源中的不同符号采用不同长度的码字表示,就称为码字表示,就称为变长编码变长编码或不等长编码。或不等长编
91、码。要实现无失真的信源编码,变长码必须是要实现无失真的信源编码,变长码必须是惟一可译码。为了能即时进行译码,变长惟一可译码。为了能即时进行译码,变长码还必须是即时码。码还必须是即时码。2445.1.4 变长编码定理变长编码定理基本思想:基本思想:一般离散无记忆信源输出的各消息概率是一般离散无记忆信源输出的各消息概率是不等的,若对概率大的采用较短的码字,不等的,若对概率大的采用较短的码字,对概率小的采用较长的码字,使编码的对概率小的采用较长的码字,使编码的平平均码长最短均码长最短,也实现了与信源统计特性相,也实现了与信源统计特性相匹配。匹配。2455.1.4 变长编码定理变长编码定理定理:对于熵
92、为定理:对于熵为H(S)的离散无记忆信源的离散无记忆信源若用具有若用具有r个码符号的集个码符号的集 对其进行对其进行编码,则一定存在一种编码方法构成惟一可译码,编码,则一定存在一种编码方法构成惟一可译码,其平均码长其平均码长 满足:满足:2465.1.4 变长编码定理变长编码定理定理:设离散无记忆信源定理:设离散无记忆信源S的熵为的熵为H(S),其,其N次扩展信源次扩展信源为为SN其信源熵为其信源熵为H(SN)。用码符号集用码符号集 对对SN进行进行编码,总可以找到一种编码方法构成惟一可译码,使信源编码,总可以找到一种编码方法构成惟一可译码,使信源S的每个信源符号所需的码字平均码长满足:的每个
93、信源符号所需的码字平均码长满足:2475.1.4 变长编码定理变长编码定理 是无记忆是无记忆N次扩展信源次扩展信源SN中每个信源符号中每个信源符号ai所所对应的平均码长对应的平均码长式中,式中, li是是ai所所对应的码字长度。对应的码字长度。n 和和 两者都是每个两者都是每个原始信源符号原始信源符号si所需所需要的码符号的平均数。要的码符号的平均数。 n前者是直接对单个信源符号前者是直接对单个信源符号si进行编码。进行编码。n后者是对后者是对N次扩展信源次扩展信源SN符号符号序列序列ai进行编码。进行编码。2485.1.4 变长编码定理变长编码定理编码速率:编码后平均每个信源符号能载荷的编码
94、速率:编码后平均每个信源符号能载荷的最大信息量。最大信息量。n码率:编码后平均每个码符号携带的信息量,码率:编码后平均每个码符号携带的信息量,即编码后信道的信息传输率。即编码后信道的信息传输率。2495.1.4 变长编码定理变长编码定理编码效率:编码效率:用来衡量各种编码距极限压缩值的情况。用来衡量各种编码距极限压缩值的情况。码的剩余度:码的剩余度:2505.1.4 变长编码定理变长编码定理1香农编码方法香农编码方法第一步:将信源发出的第一步:将信源发出的N个消息符号按其个消息符号按其概率的递减概率的递减次序次序排列。排列。第二步:按下式计算第第二步:按下式计算第i个消息的二进制代码组的码长个
95、消息的二进制代码组的码长li并并取整取整第三步:计算第第三步:计算第i个消息的个消息的累加概率累加概率 。第四步:将累加概率第四步:将累加概率Pi变换成二进制数。变换成二进制数。第五步:去掉小数点,根据码长取小数点后第五步:去掉小数点,根据码长取小数点后li位位数作为第数作为第i个消息代码组个消息代码组2515.1.4 变长编码定理变长编码定理例:例:信源符号si符号概率p(si)累加概率Pi-logp(si)代码组长度li二进制代码组S10.2002.343000S20.190.202.413001S30.180.392.483011S40.170.572.563100S50.150.742
96、.743101S60.100.893.3441110S70.010.996.66711111102525.1.4 变长编码定理变长编码定理该信源共有该信源共有5个个3位的码字,且各码字之间至少位的码字,且各码字之间至少有一位不相同,故是惟一可译码,同时这有一位不相同,故是惟一可译码,同时这7个个码字都不是延长码,属于即时码。码字都不是延长码,属于即时码。2535.1.4 变长编码定理变长编码定理2费诺码费诺码第一步:将信源符号按其第一步:将信源符号按其概率的递减概率的递减次序排列;次序排列;第二步:将它们分成第二步:将它们分成概率之和近似相等概率之和近似相等的两组,并给予一的两组,并给予一定的
97、编码规则,如下支路为定的编码规则,如下支路为1,上支路为,上支路为0;第三步:将每一大组的符号再分成概率之和近似相等的两第三步:将每一大组的符号再分成概率之和近似相等的两组,并各赋一个码元,如下支路为组,并各赋一个码元,如下支路为1,上支路为,上支路为0 ;第四步:重复步骤第四步:重复步骤3,直至每组只剩下一个信源符号为止,直至每组只剩下一个信源符号为止,所对应的码符号序列即为所编码字。所对应的码符号序列即为所编码字。2545.1.4 变长编码定理变长编码定理例:例:符号si概率p(si)第一次第二次第三次第四次二元码组S10.20 0 000S20.19 10010S30.181011S40
98、.17 1010S50.1510110S60.101011110S70.0111112555.1.4 变长编码定理变长编码定理n费诺码比香农码的平均码长小,消息传输率费诺码比香农码的平均码长小,消息传输率大,编码效率高。大,编码效率高。n香农编码法冗余度较大,实用性不强,但具香农编码法冗余度较大,实用性不强,但具有重要的理论意义。有重要的理论意义。2565.1.4 变长编码定理变长编码定理平均码长为最短的即时码称为平均码长为最短的即时码称为最佳码最佳码,又称为,又称为紧紧致码致码。对于某个给定分布的离散信源,存在一个二元最对于某个给定分布的离散信源,存在一个二元最佳码,此码满足如下性质:佳码,
99、此码满足如下性质:(1)概率大的信源符号所对应的码长必不大于概)概率大的信源符号所对应的码长必不大于概率小的信源符号所对应的码长。率小的信源符号所对应的码长。(2)两个最小概率的信源符号所对应的码字必具)两个最小概率的信源符号所对应的码字必具有相同的码长,且其差别必是最后一位码元不同。有相同的码长,且其差别必是最后一位码元不同。2575.1.4 变长编码定理变长编码定理3霍夫曼编码霍夫曼编码最佳变长编码最佳变长编码第一步:将信源符号按其概率的递减次序排列;第一步:将信源符号按其概率的递减次序排列;第二步:从最小概率的两个消息开始编码,并给予一定的第二步:从最小概率的两个消息开始编码,并给予一定
100、的编码规则,如下支路为编码规则,如下支路为1,上支路为,上支路为0;第三步:将已编码的两个消息对应概率合并,并重新按概第三步:将已编码的两个消息对应概率合并,并重新按概率大小排队,重复步骤率大小排队,重复步骤2;第四步:重复步骤第四步:重复步骤3,直至合并概率达,直至合并概率达1.0为止,划出由每为止,划出由每个信源符号概率到个信源符号概率到1.0的路径,记下沿路径的的路径,记下沿路径的1和和0;第五步:编码按后编先出的方式进行第五步:编码按后编先出的方式进行。2585.1.4 变长编码定理变长编码定理例例5.1.5:例例5.1.7 参见教材参见教材142页页消息(U)概率(pi)u11/2u
101、21/4u31/8 0u41/8 11/21/4 01/4 11/2 11/2 01.0编码C1010000012595.1.4 变长编码定理变长编码定理例:例:sip(si) 编码过程码组S10.20 0 10.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.390110S20.1911S30.18000S40.17001S50.15010S60.100110S70.0101112605.1.4 变长编码定理变长编码定理可见,哈夫曼码的平均码长最小,消息传输率可见,哈夫曼码
102、的平均码长最小,消息传输率最大,编码效率最高。最大,编码效率最高。2615.1.4 变长编码定理变长编码定理哈夫曼编码方法得到的码哈夫曼编码方法得到的码不是惟一的不是惟一的,原因是:,原因是:(1)每次对信源缩减时,赋予信源最后两个概率)每次对信源缩减时,赋予信源最后两个概率最小的符号,用最小的符号,用0和和1是任意的,所以可得到不同是任意的,所以可得到不同的码,但不会影响码长。的码,但不会影响码长。(2)新合并的概率与其他符号的概率相等时,在)新合并的概率与其他符号的概率相等时,在缩减信源时,其位置次序是任意的,故可得到不缩减信源时,其位置次序是任意的,故可得到不同的码,并且对码长有影响。同
103、的码,并且对码长有影响。2625.1.4 变长编码定理变长编码定理在编码中,将在编码中,将新合并的概率放在上支路新合并的概率放在上支路,可减少再次合并的次数,充分利用短码,可减少再次合并的次数,充分利用短码,缩短码长的方差,编出的码更接近于等长缩短码长的方差,编出的码更接近于等长码。码。2635.1.4 变长编码定理变长编码定理哈夫曼码是用概率匹配方法进行信源编码哈夫曼码是用概率匹配方法进行信源编码的,有两个明显的特点:的,有两个明显的特点:(1)该方法保证了概率大的符号对应于短)该方法保证了概率大的符号对应于短码,概率小的符号对应于长码,充分利用码,概率小的符号对应于长码,充分利用了短码。了
104、短码。(2)缩减信源的最后两个码字总是最后)缩减信源的最后两个码字总是最后一位不同,从而保证了是即时码。一位不同,从而保证了是即时码。2645.1.4 变长编码定理变长编码定理误差扩散:噪声所影响的不仅是被干扰的误差扩散:噪声所影响的不仅是被干扰的码元,而是一直要扩散下去影响后面的一码元,而是一直要扩散下去影响后面的一系列码元。系列码元。解决方法:定期清洗或加检错纠错码。解决方法:定期清洗或加检错纠错码。2655.1.4 变长编码定理变长编码定理速度匹配:信源输出速率是变化的,而信速度匹配:信源输出速率是变化的,而信道传送的信息率是固定不变的,因而存在道传送的信息率是固定不变的,因而存在速率匹
105、配问题。速率匹配问题。解决方法:采用缓冲存储器。解决方法:采用缓冲存储器。2665.1.4 变长编码定理变长编码定理概率匹配:变长码是与信源统计特性相匹概率匹配:变长码是与信源统计特性相匹配的无失真信源编码,信源统计特性的变配的无失真信源编码,信源统计特性的变化对变长码影响很大。化对变长码影响很大。n解决方法:扩张信源。解决方法:扩张信源。2675.1.4 变长编码定理变长编码定理例:若有一信源例:若有一信源每秒钟发出每秒钟发出2.66个信源符号。将此信源的输出符个信源符号。将此信源的输出符号送入某一个二进制信道中进行传输(设信道是号送入某一个二进制信道中进行传输(设信道是无噪无损的),信道每
106、秒钟只能传递无噪无损的),信道每秒钟只能传递2个二元符号。个二元符号。试问信源不通过编码能否直接与信道连接?若通试问信源不通过编码能否直接与信道连接?若通过适当编码能否在此信道中实现无失真传输?若过适当编码能否在此信道中实现无失真传输?若能连接,试说明如何编码并说明原因。能连接,试说明如何编码并说明原因。2685.1.4 变长编码定理变长编码定理解:信源熵和信源输出的信息速率为解:信源熵和信源输出的信息速率为 Rt=2.66*H(S)=1.921 比特比特/秒秒n信道的最大信息传输率为信道的最大信息传输率为n C=1 比特比特/符号符号n Ct=2*C=2 比特比特/秒秒2695.1.4 变长
107、编码定理变长编码定理可见,可见, Rt Dmax时,时, R(D) =0。(2) R(D)是关于失真度是关于失真度D的下凸函数。的下凸函数。(3) R(D)是关于失真度是关于失真度D的严格递减函数。的严格递减函数。3115.2 限失真信源编码定理限失真信源编码定理定理(保真度准则下的信源编码定理):定理(保真度准则下的信源编码定理):设设R(D)为一离散无记忆信源的信息率失真为一离散无记忆信源的信息率失真函数,并且具有有限的失真测度。对于任函数,并且具有有限的失真测度。对于任意意 ,以及任意足够长的码长,以及任意足够长的码长l ,则一定存在一种信源编码则一定存在一种信源编码C ,其码字个其码字
108、个数为数为而编码后的平均失真度为而编码后的平均失真度为3125.2 限失真信源编码定理限失真信源编码定理从定理可知,当信源给定后,无失真信源从定理可知,当信源给定后,无失真信源数据压缩的下限是信源熵数据压缩的下限是信源熵H(S),而允许失而允许失真度为真度为D的情况下,限失真数据压缩的下限的情况下,限失真数据压缩的下限是信息率失真函数是信息率失真函数R(D)。3135.2 限失真信源编码定理限失真信源编码定理二元离散信源二元离散信源汉明失真下汉明失真下3145.2 限失真信源编码定理限失真信源编码定理例:若有一信源例:若有一信源每秒钟发出每秒钟发出2.66个信源符号。将此信源的输出符个信源符号
109、。将此信源的输出符号送入某一个二进制信道中进行传输(设信道是号送入某一个二进制信道中进行传输(设信道是无噪无损的),信道每秒钟只能传递无噪无损的),信道每秒钟只能传递2个二元符号。个二元符号。试问(试问(1)信源能否在此信道中实现无失真传输?)信源能否在此信道中实现无失真传输?(2)若在汉明失真下,问允许信源平均失真多大)若在汉明失真下,问允许信源平均失真多大时,此信源可以在此信道中传输时,此信源可以在此信道中传输。3155.2 限失真信源编码定理限失真信源编码定理解:信源熵和信源输出的信息速率为解:信源熵和信源输出的信息速率为 Rt=2.66*H(S)=2.66 比特比特/秒秒n信道的最大信
110、息传输率为信道的最大信息传输率为n C=1 比特比特/符号符号n Ct=2*C=2 比特比特/秒秒3165.2 限失真信源编码定理限失真信源编码定理可见,可见, Rt Ct(1)根据无失真信源编码定理可知,对信源进行根据无失真信源编码定理可知,对信源进行任何编码,都不能使此信源能在此信道中进行无任何编码,都不能使此信源能在此信道中进行无失真传输。失真传输。3175.2 限失真信源编码定理限失真信源编码定理(2)汉明失真下,二元信源的信息率失真)汉明失真下,二元信源的信息率失真函数为函数为R(D) =H(w)-H(D) 比特比特/信源符号信源符号Rt=2.66*R(D) 比特比特/秒秒当当Rt
111、=Ct时时,此信源在信道中传输时不会引起错,此信源在信道中传输时不会引起错误,即不会因信道增加信源新的损失,总的信源误,即不会因信道增加信源新的损失,总的信源失真是信源压缩编码造成的允许失真失真是信源压缩编码造成的允许失真D。3185.2 限失真信源编码定理限失真信源编码定理2.66*1-H(D) =0.2481D=0.0415故允许信源平均失真度故允许信源平均失真度D=0.0415时,可以在此信道中传输。时,可以在此信道中传输。 3196 信道编码信道编码6.1 信道编码的基本概念信道编码的基本概念6.2 有噪信道编码有噪信道编码6.3 线性分组码线性分组码3206.1 信道编码的基本概念信
112、道编码的基本概念(一)信道编码的地位和作用(一)信道编码的地位和作用数字通信系统的主要技术指标:数字通信系统的主要技术指标:(1)传输速率)传输速率1码元传输速率码元传输速率:指携带数据信息的信号单元,每秒钟通过信道传输的码元数称为码元传输速率,单位是波特,故简称波特率,又称为调制速率。3216.1 信道编码的基本概念信道编码的基本概念2比特传输速率:比特传输速率:每秒钟通过信道传输的信息量称为比每秒钟通过信道传输的信息量称为比特传输速率特传输速率.单位是比特单位是比特/秒,简称比特率。秒,简称比特率。3226.1 信道编码的基本概念信道编码的基本概念对二进制来说,每个码元的信息含量为对二进制
113、来说,每个码元的信息含量为1比特,因此,二进制的码元传输速率与比比特,因此,二进制的码元传输速率与比特传输速率在数值上是相等的。特传输速率在数值上是相等的。对对M进制来说,每一码元的信息含量为进制来说,每一码元的信息含量为logM比特,如果码元传输速率为比特,如果码元传输速率为rs波波特,则相应的比特传输速率特,则相应的比特传输速率rb为为rs logM。3236.1 信道编码的基本概念信道编码的基本概念(2)差错率)差错率1码元差错率码元差错率:在传输的码元总数中发生差错的:在传输的码元总数中发生差错的码元数所占的比例(平均值),简称误码率,用码元数所占的比例(平均值),简称误码率,用符号符
114、号pE表示。表示。2比特差错率比特差错率:在传输的比特总数中发生:在传输的比特总数中发生差错的比特数所占的比例(平均值),用符号差错的比特数所占的比例(平均值),用符号pBE表示。在二进制传输系统中,码元差错率表示。在二进制传输系统中,码元差错率就是比特差错率。就是比特差错率。3码组差错率码组差错率:在传输的码组总数中发生差:在传输的码组总数中发生差错的码组数所占的比例(平均值)。错的码组数所占的比例(平均值)。3246.1 信道编码的基本概念信道编码的基本概念(3)可靠性)可靠性在数字通信系统中信息的传输(或存储)在数字通信系统中信息的传输(或存储)遇到的主要问题就是遇到的主要问题就是:在传
115、输过程中出现差错问题,也就是传输在传输过程中出现差错问题,也就是传输的可靠性问题。的可靠性问题。3256.1 信道编码的基本概念信道编码的基本概念出错的主要原因是出错的主要原因是(1)不同的传输系统有不同的性能以及在不同的传输系统有不同的性能以及在传输过程中干扰不同;传输过程中干扰不同;(2)不同用户或不同的传输系统对差错率不同用户或不同的传输系统对差错率的要求不同。的要求不同。3266.1 信道编码的基本概念信道编码的基本概念降低误码率通常有两种途径:降低误码率通常有两种途径:一是降低信道(包括调制解调器、传输媒一是降低信道(包括调制解调器、传输媒介)本身所引起的误码率;介)本身所引起的误码
116、率;二是采用信道编码,在数字通信系统中二是采用信道编码,在数字通信系统中增加差错控制设备。增加差错控制设备。3276.1 信道编码的基本概念信道编码的基本概念降低信道所引起的误码率的主要方法有:降低信道所引起的误码率的主要方法有:一是选择合适的传输线路;一是选择合适的传输线路;二是改进传输线路的传输特性或增加发送二是改进传输线路的传输特性或增加发送信号的能量;信号的能量;三是用潜在抗干扰性较强的调制解调方案。三是用潜在抗干扰性较强的调制解调方案。3286.1 信道编码的基本概念信道编码的基本概念某些情况下,信道的改善可能较困难或不某些情况下,信道的改善可能较困难或不经济,此时就要采用信道编码。
117、经济,此时就要采用信道编码。信息源噪声源变换器调制器发射机信道接收机解调器反变换器信息宿接收端发送端信道有编码的数字通信系统框图信源编码器信道编码器信道译码器信源译码器3296.1 信道编码的基本概念信道编码的基本概念(二)信道编码的基本思想和分类(二)信道编码的基本思想和分类差错的基本形式:差错的基本形式:一是一是随机错误随机错误,即数据序列中前后码元之,即数据序列中前后码元之间是否发生错误彼此无关,产生这种错误间是否发生错误彼此无关,产生这种错误的信道称为无记忆信道或随机信道。的信道称为无记忆信道或随机信道。二是二是突发错误突发错误,即错误之间有相关性,即错误之间有相关性,成串出现,称这类
118、信道为突发差错信道。成串出现,称这类信道为突发差错信道。3306.1 信道编码的基本概念信道编码的基本概念设信道输入的发送序列为设信道输入的发送序列为00000,由于干扰,由于干扰,信道输出的接收序列为信道输出的接收序列为00100,相当于信道,相当于信道中有一个差错序列中有一个差错序列00100发送序列与接收序列对应位的模发送序列与接收序列对应位的模2和就是信和就是信道的道的错误图样错误图样。这个差错序列与发送序列逐为模这个差错序列与发送序列逐为模2相加,相加,就得到了接收序列,称这个差错序列为就得到了接收序列,称这个差错序列为信道错误图样。信道错误图样。3316.1 信道编码的基本概念信道
119、编码的基本概念信息序列信息序列:信源编码器输出的数字序列:信源编码器输出的数字序列M,通常是由二元符号通常是由二元符号0和和1组成,且符号组成,且符号0和和1是相互独立等概率的。是相互独立等概率的。信道编码信道编码:按一定规律在待发送的信息码:按一定规律在待发送的信息码中加入一些人为制作的码元,以保证传输中加入一些人为制作的码元,以保证传输过程可靠性。过程可靠性。检错码检错码:用于检测差错的信道码。:用于检测差错的信道码。纠错码纠错码:可以检测和校正差错的信道码。:可以检测和校正差错的信道码。3326.1 信道编码的基本概念信道编码的基本概念从原理分:从原理分:如果规则是线性的,即码元之间的关
120、系是如果规则是线性的,即码元之间的关系是线性关系,则称这类信道编码为线性关系,则称这类信道编码为线性码线性码,否则称为否则称为非线性码非线性码。从信息序列所对应的编码方式分:从信息序列所对应的编码方式分:如果将信源的信息序列按照独立分组进如果将信源的信息序列按照独立分组进行处理和编码,则称为行处理和编码,则称为分组码分组码,否则称为,否则称为非分组码非分组码。3336.1 信道编码的基本概念信道编码的基本概念在线性分组码中,通常把码组中所含在线性分组码中,通常把码组中所含“1”的数目定义为的数目定义为码组重复(码重)码组重复(码重),记为,记为W(c)。把两个码组中对应位置上不同分量数把两个码
121、组中对应位置上不同分量数目定义为目定义为码组距离码组距离,记为,记为d(ci, cj)。码组间最小距离码组间最小距离dmin的大小直接决定的大小直接决定线性分组码的检错能力。线性分组码的检错能力。3346.1 信道编码的基本概念信道编码的基本概念若要若要发现发现e个独立随机错误则要求:个独立随机错误则要求:若要若要纠正纠正t个独立随机错误则要求:个独立随机错误则要求:若要发现若要发现e个独立随机错误,同时能纠正个独立随机错误,同时能纠正t个个独立随机错误则要求:独立随机错误则要求:3356.1 信道编码的基本概念信道编码的基本概念(n,1)重复码重复码(1)不重复不重复:最简单但没有任何抗干扰
122、能:最简单但没有任何抗干扰能力,既不能发现更不能纠正错误。力,既不能发现更不能纠正错误。(2)重复一次重复一次:效率降低一倍但在传输过:效率降低一倍但在传输过程中允许错一位,能发现但不能纠正错误。程中允许错一位,能发现但不能纠正错误。(3)重复两次重复两次:效率降低两倍,能发现两:效率降低两倍,能发现两个错误或纠正一个错误。个错误或纠正一个错误。3366.1 信道编码的基本概念信道编码的基本概念偶(奇)监督码偶(奇)监督码编码规则:编码规则:上式是模上式是模2相加和。这种偶数监督码,要保相加和。这种偶数监督码,要保证码组中证码组中“1”的个数是偶数,即满足在码的个数是偶数,即满足在码组中信息位
123、和监督位模组中信息位和监督位模2和为和为0,能发现奇,能发现奇数个差错。数个差错。3376.1 信道编码的基本概念信道编码的基本概念例:例:同理可设计奇数监督码,只是码组中同理可设计奇数监督码,只是码组中“1”的个数是奇数。的个数是奇数。这类偶(奇)监督码可记为这类偶(奇)监督码可记为(n,n-1)码码。c0c100011011c0c100011011c201103386.1 信道编码的基本概念信道编码的基本概念(n,1)重复码和重复码和(n,n-1)偶(奇)监督码虽然偶(奇)监督码虽然构造都很简单,但性能远不能满足既有可构造都很简单,但性能远不能满足既有可靠性又有有效性的要求。靠性又有有效性
124、的要求。3396.1 信道编码的基本概念信道编码的基本概念对对(n,1)重复码,随着码长重复码,随着码长n增大,可靠性增大,可靠性虽可不断提高,但编码效率虽可不断提高,但编码效率 在不断在不断降低。降低。对对(n,n-1)偶(奇)监督码,随着码长偶(奇)监督码,随着码长n增大,增大,有效性很高即编码效率有效性很高即编码效率 ,但抗干,但抗干扰性很差。扰性很差。3406.1 信道编码的基本概念信道编码的基本概念线性分组码线性分组码在构造时,在构造时,将输入信息分成将输入信息分成k位一组进行编码,位一组进行编码,按照一定线性规律加上人为多余的码元,按照一定线性规律加上人为多余的码元,构成构成n(n
125、k)位一组的输出,位一组的输出,故可采用符号故可采用符号(n,k)表示。表示。3416.1 信道编码的基本概念信道编码的基本概念其中其中n表示输出的码组长度,表示输出的码组长度,k表示输入信表示输入信息分组,即输出码中息分组,即输出码中信息码信息码位数,余下的位数,余下的r=n-k位码元表示在编码过程中人为加入的位码元表示在编码过程中人为加入的多余码多余码元。元。这些多余码元是供接收端检查、纠正这些多余码元是供接收端检查、纠正在传输中产生错误的码元,故称其为在传输中产生错误的码元,故称其为监督码元监督码元或或校验码元校验码元。3426.1 信道编码的基本概念信道编码的基本概念(三)差错控制基本
126、方式(三)差错控制基本方式有两类:有两类:一类是接收端检测到传输的码字有错后,一类是接收端检测到传输的码字有错后,收端译码器收端译码器自动地纠正错误自动地纠正错误;另一类是收端接收到错误后,通过反馈信另一类是收端接收到错误后,通过反馈信道发送一个道发送一个应答信号应答信号,要求发端重传有错误,要求发端重传有错误的消息,从而达到纠正错误的目的。的消息,从而达到纠正错误的目的。3436.1 信道编码的基本概念信道编码的基本概念在数字和数据的信息与通信系统中,利用信道编在数字和数据的信息与通信系统中,利用信道编码提高系统的可靠性,控制差错,主要方式有四码提高系统的可靠性,控制差错,主要方式有四种:种
127、:(1)前向纠错)前向纠错(FEC)发端收端纠错码优点:不要反馈信道,适于广播系统,译码延时优点:不要反馈信道,适于广播系统,译码延时固定,较适于实时传输系统。固定,较适于实时传输系统。缺点:要求预先确定信道的差错统计特性。缺点:要求预先确定信道的差错统计特性。3446.1 信道编码的基本概念信道编码的基本概念(2)反馈重传)反馈重传(ARQ)发端收端检错码应答信号优点:只需少量的多余码元就能获得极低的输优点:只需少量的多余码元就能获得极低的输出误码率,检错码基本与信道的差错统计特性出误码率,检错码基本与信道的差错统计特性无关。无关。缺点:要反馈信道,不能用于单项传输系统,缺点:要反馈信道,不
128、能用于单项传输系统,也难以用于同播系统,控制较复杂,不大适于也难以用于同播系统,控制较复杂,不大适于实时传输系统。实时传输系统。3456.1 信道编码的基本概念信道编码的基本概念(3)混合纠错)混合纠错(HEC)发端收端纠检错码应答信号具有具有FEC和和ARQ的优点,避免了的优点,避免了FEC方式所需方式所需的复杂译码器及不能适应差错能力变化的缺点,的复杂译码器及不能适应差错能力变化的缺点,还能克服还能克服ARQ方式信息连贯性差,有时通信效率方式信息连贯性差,有时通信效率低的缺点。特别选用于环路延时大的高速传输系低的缺点。特别选用于环路延时大的高速传输系统(如卫星系统)中。统(如卫星系统)中。
129、3466.1 信道编码的基本概念信道编码的基本概念(4)信息反馈)信息反馈(IRQ)发端收端数据信息数据信息优点:不需要纠错、检错编译码器,控制设备优点:不需要纠错、检错编译码器,控制设备和检错设备均较简单。和检错设备均较简单。缺点:发端需要一定容量的存储器以存储发送缺点:发端需要一定容量的存储器以存储发送码组,适用于传输速率较低、数据信道差错率码组,适用于传输速率较低、数据信道差错率较低、具有双向传输线路及控制简单的系统中。较低、具有双向传输线路及控制简单的系统中。3476.2 有噪信道编码有噪信道编码信道的输入和输出端连接着编码器和译码信道的输入和输出端连接着编码器和译码器,形成了一个新的
130、信道,将这种变换后器,形成了一个新的信道,将这种变换后具有新特性的信道称为编码信道。具有新特性的信道称为编码信道。 编码器信道信源编码器X译码器Y信源译码器编码信道3486.2 有噪信道编码有噪信道编码在有噪信道中传输消息是会发生错误在有噪信道中传输消息是会发生错误的,的,错误概率错误概率和和信道的统计特性信道的统计特性、译译码过程码过程以及以及译码规则译码规则有关。有关。 3496.2 有噪信道编码有噪信道编码设信道输入符号集为设信道输入符号集为 ,输出符,输出符号集为号集为 。若对每一个输出符。若对每一个输出符号号yj都有一个确定的函数都有一个确定的函数F(yj),使,使yj对应惟对应惟一
131、的一个输入符号一的一个输入符号xi,则称这样的函数为则称这样的函数为译译码规则码规则,记为,记为显然,对于有显然,对于有r个输入、个输入、s个输出的信道,个输出的信道,按上述定义可得到译码规则有按上述定义可得到译码规则有rs种。种。3506.2 有噪信道编码有噪信道编码例:已知信道矩阵和两种译码规则例:已知信道矩阵和两种译码规则3516.2 有噪信道编码有噪信道编码在确定译码规则在确定译码规则F(yj)=xi后,信道输出端接后,信道输出端接收到的符号为收到的符号为yj,而发送的不是而发送的不是xi ,就认为就认为有错误,这种错误概率有错误,这种错误概率p(e|yj)称为称为条件错条件错误概率误
132、概率.则译码的则译码的条件正确概率条件正确概率为为条件错误概率与条件正确概率间的关系条件错误概率与条件正确概率间的关系3526.2 有噪信道编码有噪信道编码因为译码过程有统计平均作用,经过译码因为译码过程有统计平均作用,经过译码后的后的平均错误概率平均错误概率pE为为选择译码规则总的原则是使选择译码规则总的原则是使pE最小,最小,上式右边是非负项之和,应使每一项最小,上式右边是非负项之和,应使每一项最小,因为因为p(yj)与译码规则无关,故要使与译码规则无关,故要使p(e|yj)最小。最小。3536.2 有噪信道编码有噪信道编码为了使为了使p(e|yj)最小,就应最小,就应使使pF(yj) |
133、yj最大,最大,即选择译码函数即选择译码函数F(yj)=x*使之满足对所有使之满足对所有i因此,如果采用的译码函数对于每一个输出译码符号因此,如果采用的译码函数对于每一个输出译码符号均译成具有最大后验概率的那个输入符号,则信道错均译成具有最大后验概率的那个输入符号,则信道错误概率就能最小。这个规则称为误概率就能最小。这个规则称为最大后验概率规则最大后验概率规则或或最小错误概率准则最小错误概率准则。3546.2 有噪信道编码有噪信道编码根据贝叶斯定律,上式可写成根据贝叶斯定律,上式可写成为了便于计算,忽略信源的统计特性,为了便于计算,忽略信源的统计特性,选择译码函数选择译码函数F(yj)=x*使
134、之满足对所有使之满足对所有i称为称为极大似然译码规则极大似然译码规则。3556.2 有噪信道编码有噪信道编码平均错误概率平均错误概率3566.2 有噪信道编码有噪信道编码用条件概率表示用条件概率表示如果如果p(x)是等概率的是等概率的p(x)=1/r,则则此时译码错误概率可以用信道矩阵中的元素,此时译码错误概率可以用信道矩阵中的元素,去去掉每列中的掉每列中的F(yj)=x*项项,求和来表示。,求和来表示。平均正确概率为平均正确概率为3576.2 有噪信道编码有噪信道编码费诺不等式费诺不等式表明了平均错误概率表明了平均错误概率pE与信道疑义度与信道疑义度H(X|Y)间的关系。间的关系。可知,接收
135、到可知,接收到Y后关于后关于X的平均不确定性分的平均不确定性分为两部分:一是接收到为两部分:一是接收到Y后是否产生错误的后是否产生错误的不确定性;二是错误发生后,到底是哪个输不确定性;二是错误发生后,到底是哪个输入符号发送而造成错误的不确定性。入符号发送而造成错误的不确定性。3586.2 有噪信道编码有噪信道编码例:已知信道矩阵例:已知信道矩阵并设并设p(x1)=1/2, p(x2)=p(x3)=1/4, 分别用分别用最小错误概率准则和最大似然译码准则确最小错误概率准则和最大似然译码准则确定相应的译码规则,并计算平均错误概率。定相应的译码规则,并计算平均错误概率。3596.2 有噪信道编码有噪
136、信道编码解:由于输入符号不是等概率分布,所以对于最小解:由于输入符号不是等概率分布,所以对于最小错误概率准则必须根据联合概率的大小来选择。错误概率准则必须根据联合概率的大小来选择。p(x1y1)=1/4, p(x2y1)=1/24,p(x3y1)=1/12p(x1y2)=1/6, p(x2y2)=1/8,p(x3y2)=1/24p(x1y3)=1/12, p(x2y3)=1/12,p(x3y3)=1/8故译码规则是故译码规则是F(y1)=x1, F(y2)=x1, F(y3)=x33606.2 有噪信道编码有噪信道编码对于最大似然译码准则,可以直接从信道对于最大似然译码准则,可以直接从信道矩阵
137、的传递概率来选择,译码规则是矩阵的传递概率来选择,译码规则是F(y1)=x1, F(y2)=x2, F(y3)=x3平均错误概率为平均错误概率为pE=1/24+1/12+1/6+1/24+1/12 +1/12 =12/24pE=1/24+1/12+1/8+1/24+1/12 +1/12 =11/24 pE3616.2 有噪信道编码有噪信道编码选择最佳译码规则只能使错误概率选择最佳译码规则只能使错误概率pE有限有限地减小,无法使其任意的小。要想进一步地减小,无法使其任意的小。要想进一步减小错误概率,必须优选信道编码方法。减小错误概率,必须优选信道编码方法。3626.2 有噪信道编码有噪信道编码(
138、1)简单重复编码)简单重复编码XYa1=0a2=1b1=0b2=11-p=0.991-ppp3636.2 有噪信道编码有噪信道编码000=b1010=b3100=b5001=b2011=b4101=b6110=b7111=b8a1 = 000010=a3100=a5001=a2011=a4101=a6110=a7a8= 111二元对称信道的三次扩展信道未用码字许用码字输出端接收序列3646.2 有噪信道编码有噪信道编码3656.2 有噪信道编码有噪信道编码此时可采用此时可采用“择多译多择多译多”的译码原则,即的译码原则,即根据信道输出端接收序列中根据信道输出端接收序列中0多还是多还是1多,多,
139、如果如果0多译码器就判决为多译码器就判决为0,1多就判决为多就判决为1。同样可得同样可得pE =错错3个码元的概率个码元的概率 +错错2个码元的概率个码元的概率 =3*10-43666.2 有噪信道编码有噪信道编码如果进一步增大重复次数如果进一步增大重复次数n,M仍取仍取2,可得,可得pE能继续降低,但同时能继续降低,但同时R=logM/n也要减小。也要减小。由此可见,利用简单重复编码来减小平均错由此可见,利用简单重复编码来减小平均错误概率是以降低信息传输率为代价的。误概率是以降低信息传输率为代价的。3676.2 有噪信道编码有噪信道编码(2)消息符号个数)消息符号个数M在一个二元信道的在一个
140、二元信道的n次无记忆扩展信道中,次无记忆扩展信道中,输入端共有输入端共有2n个符号序列可能作为消息符号个符号序列可能作为消息符号,现仅选其中,现仅选其中M个作为消息符号传递,则当个作为消息符号传递,则当M选得大,选得大, pE也跟着大,也跟着大,R也大。也大。3686.2 有噪信道编码有噪信道编码(1)n=3,M=2, pE=3*10-4R=logM/n=1/3比特比特/码符号码符号(2)n=3,M=4, pE=2*10-2R=logM/n=2/3比特比特/码符号码符号(3)n=3,M=8, pE=3*10-2R=logM/n=1比特比特/码符号码符号3696.2 有噪信道编码有噪信道编码(3
141、)(5,2)线性码线性码采用采用(5,2)线性码,并适当增大线性码,并适当增大n和和M,可以可以得到低的平均错误概率和较好的信息传输得到低的平均错误概率和较好的信息传输速率。速率。n=5,M=4, pE=7.8*10-4R=logM/n=2/5比特比特/码符号码符号3706.2 有噪信道编码有噪信道编码输入符号的输入符号的4个码字采用如下编码方法:个码字采用如下编码方法:所以,输入端发送序列为所以,输入端发送序列为00000,01101,10111,110103716.2 有噪信道编码有噪信道编码0000000100100000000101000100010001100010000000000
142、0扩展信道译码规则发送码字输出端接收序列3726.2 有噪信道编码有噪信道编码01101010011110101100001011110001110011110110101101扩展信道译码规则发送码字输出端接收序列3736.2 有噪信道编码有噪信道编码10111111111011010101001110011010100100111011110111扩展信道译码规则发送码字输出端接收序列3746.2 有噪信道编码有噪信道编码11010111100101011011100100101111001110001101011010扩展信道译码规则发送码字输出端接收序列3756.2 有噪信道编码有噪信
143、道编码(4)汉明距离)汉明距离长度为长度为n的两个二进制序列(码字)的两个二进制序列(码字) 之之间的距离是指间的距离是指 对应位置上码元取值不对应位置上码元取值不同的个数,用符号同的个数,用符号 表示。表示。例如:例如:若令若令3766.2 有噪信道编码有噪信道编码汉明距离满足以下性质:汉明距离满足以下性质:(1)非负性)非负性(2)对称性)对称性(3)三角不等式)三角不等式3776.2 有噪信道编码有噪信道编码在二进制码在二进制码C中,任意两个码字的汉明距离中,任意两个码字的汉明距离的最小值称为该码的最小值称为该码C的最小距离,即的最小距离,即最小距离最小距离Dmin越大,受干扰后,越不容
144、易把越大,受干扰后,越不容易把一个码字变为其他码字,因而平均错误概一个码字变为其他码字,因而平均错误概率率pE越小。越小。故在选择编码规则时,应使码字间的距离故在选择编码规则时,应使码字间的距离越大越好。越大越好。3786.2 有噪信道编码有噪信道编码(5)用汉明距离表示极大似然译码规则)用汉明距离表示极大似然译码规则设码字设码字xi与与yj之间的距离为之间的距离为D,则表示在则表示在传输过程中有传输过程中有D个位置发生了错误,个位置发生了错误,n-D个位置没有错误。个位置没有错误。二进对称信道的传输错误概率为二进对称信道的传输错误概率为p,当信当信道是无记忆时,编码后信道的传递概率为道是无记
145、忆时,编码后信道的传递概率为当当p0.5时时,D越大越大 p(yj |xi)越小越小3796.2 有噪信道编码有噪信道编码极大似然译码规则可表示为:当收到码字极大似然译码规则可表示为:当收到码字yj后后,在输入码字集,在输入码字集 中寻找一个中寻找一个x*,使之与使之与yj的的距离(汉明距离)最短。距离(汉明距离)最短。即选取译码函数即选取译码函数F(yj)=x*使之满足使之满足3806.2 有噪信道编码有噪信道编码例:某二元码字例:某二元码字111000,001011,010110,101110(1)如果码字等概率分布,求码率。)如果码字等概率分布,求码率。(2)采用最大似然准则,收到)采用
146、最大似然准则,收到110110如何如何译码。译码。3816.2 有噪信道编码有噪信道编码解:解:(1)码组的码率为)码组的码率为(2)采用最大似然准则,收到)采用最大似然准则,收到110110后,后,与码字集中各码字的汉明距离分别为与码字集中各码字的汉明距离分别为3,5,1,2,故应译码为,故应译码为0101103826.2 有噪信道编码有噪信道编码(三)有噪信道编码定理(三)有噪信道编码定理定理(香农第二定理):设某信道定理(香农第二定理):设某信道有有r个输入符号,个输入符号, s个输出符号,信道容量为个输出符号,信道容量为C 。当信息传输率当信息传输率RC时,只要码时,只要码长长n足够长
147、,总可以在输入符号集中找足够长,总可以在输入符号集中找到到M个码字(代表个码字(代表M个等可能性的消息)组成的一个等可能性的消息)组成的一个码(个码( 是一任意小的正数)和它相应的是一任意小的正数)和它相应的译码规则,使信道输出的错误概率译码规则,使信道输出的错误概率pE任意小。任意小。3836.3 线性分组码线性分组码分组码是由码字或码组构成,码字是一组分组码是由码字或码组构成,码字是一组固定长度的向量,其长度就是该向量的个固定长度的向量,其长度就是该向量的个数数N。一个码字的元素从一个码字的元素从q个元素的字符中选取。个元素的字符中选取。当字符由元素当字符由元素0和和1组成时,得到的码称为
148、组成时,得到的码称为二进制码,码字的元素称为比特。二进制码,码字的元素称为比特。3846.3 线性分组码线性分组码在分组编码器中,在分组编码器中,k个比特信息被编成个比特信息被编成n个个比特,增加了比特,增加了n-k个冗余比特,其作用是检个冗余比特,其作用是检测和纠正错码。测和纠正错码。分组码也称为分组码也称为(n,k)码,其码率定义码,其码率定义为为3856.3 线性分组码线性分组码分组码的性质:分组码的性质:(1)线性:假设)线性:假设C1与与C2是是(n,k)分组码中分组码中的两个码字,令的两个码字,令 是从字符表中任意选是从字符表中任意选择的两个元素,则当且仅当择的两个元素,则当且仅当
149、 也是也是一码字时,分组码是线性分组码。一码字时,分组码是线性分组码。一个线性码必定包含全零的码字,一个一个线性码必定包含全零的码字,一个固定码重的码是非线性的。固定码重的码是非线性的。3866.3 线性分组码线性分组码(2)系统性:若一个码字,它前面的若干)系统性:若一个码字,它前面的若干比特等同于信息比特,剩余的比特是这些比特等同于信息比特,剩余的比特是这些信息比特的线性组合,则称之为系统码。信息比特的线性组合,则称之为系统码。对一个对一个(n,k)分组码,其前面分组码,其前面k个比特等同个比特等同于信息比特,并且每个码字的剩余于信息比特,并且每个码字的剩余n-k比比特是特是k个信息比特的
150、线性组合。个信息比特的线性组合。3876.3 线性分组码线性分组码(3)循环性:若)循环性:若 是一个码字,是一个码字,且由且由C的循环移位得到的的循环移位得到的 也是也是一个码字,则称码字具有循环特性。一个码字,则称码字具有循环特性。循环码是线性码集合中满足循环移位特性循环码是线性码集合中满足循环移位特性的一个子集合,即循环码的码字的一个子集合,即循环码的码字C的所有循的所有循环移位都是码字。环移位都是码字。3886.3 线性分组码线性分组码令令 是已被信道编码成的码字是已被信道编码成的码字cm的的k个信息码元。用行向量分别表示个信息码元。用行向量分别表示k个信息个信息码元的向量和编码器输出
151、向量为码元的向量和编码器输出向量为3896.3 线性分组码线性分组码线性二进制分组编码器的编码运算可以用线性二进制分组编码器的编码运算可以用n个方程组表示为个方程组表示为将其表示成矩阵形式为将其表示成矩阵形式为这表明码字向量这表明码字向量c是由信息码元向量是由信息码元向量x生成生成的,故将的,故将G称作码字的称作码字的生成矩阵生成矩阵。3906.3 线性分组码线性分组码若令若令则任何一个码字都可以表示为生成矩阵的行向量则任何一个码字都可以表示为生成矩阵的行向量的线性组合,即的线性组合,即这表明这表明gi是是(n,k)分组码的基向量,它不是分组码的基向量,它不是惟一的,故生成矩阵也不是惟一的。惟
152、一的,故生成矩阵也不是惟一的。3916.3 线性分组码线性分组码一个一个(n,k)分组码的任何生成矩阵都可以表示成下分组码的任何生成矩阵都可以表示成下面的面的系统形式系统形式:式中式中Ik是是k*k单位矩阵,单位矩阵,P是是k*(n-k)矩阵,它决定矩阵,它决定n-k个冗余码元即奇偶校验码元。个冗余码元即奇偶校验码元。3926.3 线性分组码线性分组码如果引入如果引入(n-k)*n矩阵矩阵H ,其转置矩阵其转置矩阵HT和和G满足正交关系满足正交关系GHT=0 ,则知则知也把也把H称作称作一致校验矩阵一致校验矩阵或一致或一致监督监督矩阵。矩阵。3936.3 线性分组码线性分组码例:某线性分组码生成矩阵为例:某线性分组码生成矩阵为(1)求)求n,k的值,并写出全部的码字,若的值,并写出全部的码字,若收到收到000110,判断其是否正确。,判断其是否正确。(2)求一致校验矩阵。)求一致校验矩阵。3946.3 线性分组码线性分组码解:生成矩阵是解:生成矩阵是3行行6列,可知列,可知n=6,k=33956.3 线性分组码线性分组码写出所有的码字为:写出所有的码字为:若收到若收到000110则出错了。则出错了。0000000010110101101001010111011011101100111110003966.3 线性分组码线性分组码一致校验矩阵为一致校验矩阵为397