《信息论 第五章PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息论 第五章PPT讲稿.ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息论 第五章第1页，共65页，编辑于2022年，星期四1、信源编码的目的、信源编码的目的在不失真或允许一定失真条件下，如何在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以用尽可能少的符号来传送信源信息，以便提高信息传输率。便提高信息传输率。2、信道编码的目的、信道编码的目的在信道受干扰的情况下，如何增加信在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传号的抗干扰能力，同时又使得信息传输率最大。输率最大。第2页，共65页，编辑于2022年，星期四5.1 编编 码码 器器5.1.1 5.1.1 编码器的构成编码器的构成5.1.2 5.1.2 有关常用码的概念有
2、关常用码的概念第3页，共65页，编辑于2022年，星期四5.1.1 5.1.1 编码器的构成编码器的构成编码器编码器S:信源符号信源符号码符号，或码元码符号，或码元编码实质上是对信源的原始符号按一定的编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。数学规则进行的一种变换。码字长度或码长码字长度或码长C码字码字第4页，共65页，编辑于2022年，星期四(信源符号信源符号)(信源序列信源序列)码字由码元组成码字由码元组成码码C由码字由码字组成组成编码就是从信源符号编码就是从信源符号到码字到码字的的一种映射，一一对应，可逆，则可实现一种映射，一一对应，可逆，则可实现无失真编码。无失真编码
3、。第5页，共65页，编辑于2022年，星期四5.1.2 5.1.2 有关常用码的概念有关常用码的概念1、二元码、二元码码符号集为码符号集为，所得码字，所得码字是二元序列。是二元序列。2、等长码、等长码一组码中所有码字的码长都相同。一组码中所有码字的码长都相同。3、变长码、变长码一组码中所有码字的码长各不相同。一组码中所有码字的码长各不相同。第6页，共65页，编辑于2022年，星期四4、非奇异码、非奇异码C一组码中所有码字都不相同。一组码中所有码字都不相同。即即5、奇异码、奇异码C一组码中有相同的码字。一组码中有相同的码字。即即6、同价码、同价码码符号集码符号集中每个码符号中每个码符号所占的传输
4、时间都相同。所占的传输时间都相同。一般二元码是同价码。一般二元码是同价码。第7页，共65页，编辑于2022年，星期四对于同价码，等长码中每个码字的传输时对于同价码，等长码中每个码字的传输时间都相同，变长码每个码字的传输时间就间都相同，变长码每个码字的传输时间就不一定相同。不一定相同。7、码的、码的N次扩展码次扩展码N次扩展信源对应的次扩展信源对应的N个码字组成的码字序个码字组成的码字序列的集合。列的集合。N次扩展码次扩展码 B第8页，共65页，编辑于2022年，星期四举例举例信源信源符号的码和二次扩展码的形式符号的码和二次扩展码的形式信源符号si符号概率P(si)码1码2s1P(s1)000s
5、2P(s2)0101s3P(s3)10001s4P(s4)11111表表5.1等长码变长码非奇异码第9页，共65页，编辑于2022年，星期四表表5.2码码2的二次扩展码的二次扩展码信源符号扩展码字信源符号扩展码字信源信源S的二次扩展信源的二次扩展信源信源信源S的二次扩展码的二次扩展码第10页，共65页，编辑于2022年，星期四8、唯一可译码、唯一可译码码的任意一串有限长的码符号序列只能被码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此唯一地译成所对应的信源符号序列，则此码称码称唯一可译码唯一可译码或或单单译译可可译码译码。(1)信源符号对应的码是非奇异码。信源符号对应的
6、码是非奇异码。(2)任意有限长的任意有限长的N次扩展码是非奇异的。次扩展码是非奇异的。例：码符号序列例：码符号序列“0010”“0010”第11页，共65页，编辑于2022年，星期四5.2 等等 长长 码码5.2.1 5.2.1 等长码的唯一可译性等长码的唯一可译性5.2.2 5.2.2 等长码的编码长度等长码的编码长度第12页，共65页，编辑于2022年，星期四5.2.1 5.2.1 等长码的唯一可译性等长码的唯一可译性若等长码是非奇异码，则它的任意有限长若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码，因此一定次扩展码一定也是非奇异码，因此一定是唯一可译码。是唯一可译码。信源
7、符号si符号概率P(si)码1码2s1P(s1)0000s2P(s2)0111s3P(s3)1010s4P(s4)1111表表5.3唯一可译码非唯一可译码第13页，共65页，编辑于2022年，星期四5.2.2 5.2.2 等长码的编码长度等长码的编码长度1、q个信源符号：个信源符号：码元数为码元数为r：则码长则码长必须满足下式必须满足下式例例:(1)(2)（表（表4.2）必要条件必要条件第14页，共65页，编辑于2022年，星期四个信源符号：个信源符号：可得到等长非奇异码可得到等长非奇异码取对数：取对数：当当N=1时时是平均每个信源符号所需要的码符号个数是平均每个信源符号所需要的码符号个数2、
8、对、对N次扩展信源编码次扩展信源编码第15页，共65页，编辑于2022年，星期四3、等长码的码长仍可压缩、等长码的码长仍可压缩考虑符号出现的概率和符号间的依赖关系，码长可考虑符号出现的概率和符号间的依赖关系，码长可压缩。压缩。例：例：其余其余且且二次扩展信源二次扩展信源有有个符号个符号,压缩至压缩至4个符号个符号,编码编码即可即可.第16页，共65页，编辑于2022年，星期四结论结论:考虑信源符号间的依赖关系后考虑信源符号间的依赖关系后,再考虑符号出现的概率时再考虑符号出现的概率时,所需平所需平均码长可能缩短均码长可能缩短.第17页，共65页，编辑于2022年，星期四5.3*渐进等分割性和渐进
9、等分割性和 典型序列典型序列 对于离散无记忆信源对于离散无记忆信源 N次扩展信源次扩展信源第18页，共65页，编辑于2022年，星期四当当为有限值时为有限值时,第19页，共65页，编辑于2022年，星期四弱大数定律弱大数定律对于独立、等同分布的随机变量对于独立、等同分布的随机变量，只要，只要n 足够大时，足够大时，接近其数学期望接近其数学期望EX。第20页，共65页，编辑于2022年，星期四定理定理5.1渐进等分割性渐进等分割性(AEP):若若随机序列中随机序列中相互统计独立并且服从同一概率分布相互统计独立并且服从同一概率分布,又又，则，则依概率收敛依概率收敛于于。第21页，共65页，编辑于2
10、022年，星期四可表示成可表示成,对于任意对于任意弱大数定律弱大数定律:第22页，共65页，编辑于2022年，星期四此渐近等分割性说明此渐近等分割性说明,离散无记忆信离散无记忆信源的源的N次扩展信源中次扩展信源中,信源序列信源序列的自信息的均值的自信息的均值，依概率，依概率收敛于信源熵收敛于信源熵。当当N为有限长时为有限长时,在所有在所有个长为个长为N的的信源序列中必有一些信源序列中必有一些,其自信息其自信息量的均值与信源熵量的均值与信源熵之差小于之差小于,即即:或或称称N长序列长序列为为典型序列典型序列.第23页，共65页，编辑于2022年，星期四中所有中所有典型序列典型序列的集合表的集合表
11、示为示为非非典型序列集典型序列集第24页，共65页，编辑于2022年，星期四(2)若若，则，则(3)设设表示表示典型序列集典型序列集中包含中包含的的典型序列的个数，典型序列的个数，定理定理5.2:对于任意小的正数对于任意小的正数当当N足够大时，则足够大时，则(1)第25页，共65页，编辑于2022年，星期四而而显然显然证明证明:(1)可由定理可由定理5.1直接推得直接推得当当时，时，契比雪夫不等式契比雪夫不等式当当依概率收敛于依概率收敛于第26页，共65页，编辑于2022年，星期四(2)可由可由变形证得。变形证得。推论：推论：当当N足够大时，足够大时，可任意小，可任意小，表明表明典型序列出现的
12、概率近似相等，典型序列出现的概率近似相等，所以称为所以称为渐进等概率序列渐进等概率序列。(3)由上述性质由上述性质(2)证得。证得。第27页，共65页，编辑于2022年，星期四性质性质(1)表明表明，典型序列典型序列是经常是经常出现的信源序列。出现的信源序列。时，成为必时，成为必然事件。然事件。性质性质(2)表明表明接近等概分布接近等概分布性质性质(3)表明表明当当时时,典型序列的总数占信源序列的比值为：典型序列的总数占信源序列的比值为：一般一般所以，当所以，当第28页，共65页，编辑于2022年，星期四是高概率集，它含有序列数是高概率集，它含有序列数常常比非典型序列数要少很多。常常比非典型序
13、列数要少很多。所有信源序列所有信源序列非非典型序列集典型序列集典型序列集典型序列集结论：结论：只对少数的高概率只对少数的高概率典型序列进典型序列进行一一对应的等长编码。码字总数减少，行一一对应的等长编码。码字总数减少，所需码长就可以减少了。所需码长就可以减少了。第29页，共65页，编辑于2022年，星期四AEP结论：结论：当当N足够大时足够大时1.所有所有 典型序列出现的概率近似相典型序列出现的概率近似相 等等.2.可粗略认为可粗略认为 典型序列出现的概率为典型序列出现的概率为3.所有所有 典型序列的概率和接近为典型序列的概率和接近为1,第30页，共65页，编辑于2022年，星期四5.4 等长
14、信源编码定理等长信源编码定理5.4.1 5.4.1 等长信源编码定理等长信源编码定理 5.4.2 5.4.2 平稳有记忆信源的码长平稳有记忆信源的码长5.4.3 5.4.3 对于编码好坏的评价对于编码好坏的评价第31页，共65页，编辑于2022年，星期四5.4.1 5.4.1 等长信源编码定理等长信源编码定理 定理定理5.35.31、定理内容：、定理内容：一个离散无记忆信源，熵为一个离散无记忆信源，熵为 ，信，信源长为源长为N，码符号，码符号 r个，码字个，码字 长，对长，对于任意于任意 ，只要满足，只要满足则当则当N足够大时，可实现几乎无失真编码。足够大时，可实现几乎无失真编码。译码错误概率
15、为任意小。译码错误概率为任意小。若若则不能实现无失真编码，而当则不能实现无失真编码，而当N足够大时，译码足够大时，译码错误概率近似等于错误概率近似等于1。第32页，共65页，编辑于2022年，星期四比较公式比较公式:一般一般，当信，当信源符号有依赖时，源符号有依赖时，所以所以得到压缩得到压缩2、证明：、证明：(1)整理整理错误概率错误概率第33页，共65页，编辑于2022年，星期四设设(3)当二元编码时当二元编码时，定理，定理5.3为为等长编码时平均每个信源符号所需要等长编码时平均每个信源符号所需要的二元码符号的极限值是的二元码符号的极限值是H(s)。(2)选取的码字总数小于集选取的码字总数小
16、于集中可能中可能有的信源序列数，译码时定会产生错误。有的信源序列数，译码时定会产生错误。当当N很长时，很长时，第34页，共65页，编辑于2022年，星期四5.4.2 5.4.2 平稳有记忆信源的码长平稳有记忆信源的码长对平稳有记忆信源：对平稳有记忆信源：用用替代定理替代定理5.3中的中的H(s)无失真编码无失真编码不能实现无不能实现无失真编码失真编码第35页，共65页，编辑于2022年，星期四5.4.3 5.4.3 编码的评价编码的评价定理定理5.3式式(1)表示长为表示长为的码符号载荷的最大信息量的码符号载荷的最大信息量大于信源序列携带的信息量时大于信源序列携带的信息量时,可实现几乎可实现几
17、乎无失真编码无失真编码.式式(2)令令称称编码信息率编码信息率,表示编码后平均每个信表示编码后平均每个信源符号能载荷的最大信息量源符号能载荷的最大信息量.只有编码信息只有编码信息率大于信源的熵率大于信源的熵,才能实现几乎无失真编码才能实现几乎无失真编码.第36页，共65页，编辑于2022年，星期四编码效率编码效率编码效率用来衡量编码效果编码效率用来衡量编码效果等长编码的最佳效率等长编码的最佳效率得得 表示编码前后平均每个信源符号能载荷表示编码前后平均每个信源符号能载荷的最大信息率之比。的最大信息率之比。第37页，共65页，编辑于2022年，星期四即即在已知方差和信源熵的条件下在已知方差和信源熵
18、的条件下,容许错容许错误概率误概率愈小愈小,编码效率编码效率愈高愈高,则信源序列长度则信源序列长度N必须愈长必须愈长.在实际情况下在实际情况下,要实现几乎无失真的等长要实现几乎无失真的等长编码编码,N要大到难以实现的程度要大到难以实现的程度.已知已知当允许错误概率小于当允许错误概率小于时时代入代入第38页，共65页，编辑于2022年，星期四采用二元编码，要求编码效率采用二元编码，要求编码效率 ，允许错误概率允许错误概率 ，求编码长度？，求编码长度？解解:例例5.1已知离散无记忆信源已知离散无记忆信源第39页，共65页，编辑于2022年，星期四当当N取取4120万以上时，才能按要求实现几万以上时
19、，才能按要求实现几乎无失真编码。乎无失真编码。因此因此N有限的等长码往往引入一定的失真有限的等长码往往引入一定的失真和错误。和错误。第40页，共65页，编辑于2022年，星期四5.5 变变 长长 码码5.5.1 5.5.1 唯一可译变长码与即时码唯一可译变长码与即时码5.5.2 5.5.2 即时码的树图构造法即时码的树图构造法5.5.3 5.5.3 克拉夫特（克拉夫特（kraftkraft）不等式）不等式第41页，共65页，编辑于2022年，星期四1、唯一可译码、唯一可译码5.5.1 5.5.1 唯一可译变长码与即时码唯一可译变长码与即时码信源si概率P(si)码1码2码3码4s11/2001
20、1s21/411101001s31/80000100001s41/8110110000001表表 5.4 5.4 奇异码非唯一可译码非即时码即时码第42页，共65页，编辑于2022年，星期四（1 1）在唯一可译变长码中，译码时无需参在唯一可译变长码中，译码时无需参考后续的码符号就能立即作出判断，译考后续的码符号就能立即作出判断，译成对应的信源符号，这类码称为成对应的信源符号，这类码称为即时码即时码 结构特点：结构特点：即时码：即时码：码字不是其它码的前缀或延长码字不是其它码的前缀或延长 非即时码：非即时码：某些码字是其它码的前缀某些码字是其它码的前缀 或延长。或延长。2、即时码、即时码第43页
21、，共65页，编辑于2022年，星期四（2 2）在译码过程中，当收到一个完整的码在译码过程中，当收到一个完整的码符号序列时，无需等待下一个符号到达后作符号序列时，无需等待下一个符号到达后作判断，而能直接译成对应的信源符号。判断，而能直接译成对应的信源符号。3、码的分类及关系、码的分类及关系奇异码奇异码非奇异码非奇异码唯一可译码唯一可译码即时码即时码所有码所有码第44页，共65页，编辑于2022年，星期四5.5.2 5.5.2 即时码的树图构造法即时码的树图构造法1、码树的构造过程、码树的构造过程（1）根：根：从根出发伸出树枝，树枝的数目从根出发伸出树枝，树枝的数目 等于码符号的总数等于码符号的总
22、数r（2）节点：节点：树枝的尽头为节点。从节点树枝的尽头为节点。从节点出发再伸出树枝，每次每个节点出发再伸出树枝，每次每个节点伸出伸出r 枝，依次下去构成一棵树。枝，依次下去构成一棵树。第45页，共65页，编辑于2022年，星期四（3）终端节点：终端节点：被安排为码字的节点被安排为码字的节点,它它不再继续伸枝，用粗黑点表示。不再继续伸枝，用粗黑点表示。（4）中间节点：中间节点：没被安排为码字继续伸出没被安排为码字继续伸出枝的节点，用空心圆表示。枝的节点，用空心圆表示。（5）码字：码字：由从根出发到终端节点走过的由从根出发到终端节点走过的路径所对应的码符号组成。路径所对应的码符号组成。按树图法构
23、成的码一定满足即时码的按树图法构成的码一定满足即时码的要求。要求。第46页，共65页，编辑于2022年，星期四（2）当码字长度给定，即时码不是唯一的当码字长度给定，即时码不是唯一的（4）码树图可用来译码码树图可用来译码从根从根中间节点中间节点终端节点终端节点2、码字与树图的联系、码字与树图的联系（1）当第当第阶的节点作为终端节点，相阶的节点作为终端节点，相应码字的码长为应码字的码长为。（3）当当元元节的码树的所有树枝都被用节的码树的所有树枝都被用上时，第上时，第阶节点共有阶节点共有个终端个终端节节点点对应于对应于长的等长编码长的等长编码等等长长码也是即时码的一种。码也是即时码的一种。第47页，
24、共65页，编辑于2022年，星期四码码3的码树的码树r=2,r=3的三阶节点树图的三阶节点树图画出码画出码4的树图的树图码码4的另一种树图的另一种树图小结：小结：将变长码与码树建立将变长码与码树建立“一一对应一一对应”关系：关系：树根树根 码字起点码字起点树枝数树枝数 码的进制数码的进制数节点节点 码字或码字的一部分码字或码字的一部分终止节点终止节点 码字码字节数节数 码长码长非满树非满树 变长码变长码满树满树 等长码等长码第48页，共65页，编辑于2022年，星期四5.5.3 5.5.3 克拉夫特（克拉夫特（kraftkraft）不等式）不等式1、定理、定理5.4对于码符号为对于码符号为任意
25、即时码任意即时码(非延长码非延长码)，其码字为，其码字为，所对应的码长为，所对应的码长为，则，则必定满足必定满足反之，若码长满足上面不等式，则一定存反之，若码长满足上面不等式，则一定存在具有在具有这样码长的即时码这样码长的即时码。第49页，共65页，编辑于2022年，星期四证明：证明：充分性充分性(1)r元树，第元树，第N阶的总枝数阶的总枝数枝枝(2)第第阶节点作为码字，阶节点作为码字，使第使第N阶减少的枝数阶减少的枝数(3)第第阶的码长阶的码长(4)个码字使第个码字使第N阶减少的树枝阶减少的树枝数数证得证得第50页，共65页，编辑于2022年，星期四Kraft不等式的物理意义：不等式的物理意
26、义：给定信源符号数给定信源符号数q和码符号数和码符号数r，只要，只要允许码字长度可以足够长，就总可以满允许码字长度可以足够长，就总可以满足足Kraft不等式，从而得到即时码。不等式，从而得到即时码。第51页，共65页，编辑于2022年，星期四2、定理、定理5.5将定理将定理5.4中的即时码改为唯一可译码，其中的即时码改为唯一可译码，其余不变。余不变。推论推论:(1)当码长满足当码长满足kraft不等式时，不一定是唯一可不等式时，不一定是唯一可译码。译码。(2)但一定存在至少一种码长相同的唯一可译但一定存在至少一种码长相同的唯一可译码。不一定是即时码。码。不一定是即时码。(3)也一定能找到至少一
27、种相同码长的即时码。也一定能找到至少一种相同码长的即时码。第52页，共65页，编辑于2022年，星期四5.6 变长信源编码定理变长信源编码定理5.6.2 5.6.2 离散无记忆信源的唯一可译码长离散无记忆信源的唯一可译码长 的理论极限的理论极限5.6.1 5.6.1 平均码长平均码长5.6.3 5.6.3 离散无记忆离散无记忆NN次扩展信源编码的次扩展信源编码的 平均码长理论极限平均码长理论极限第53页，共65页，编辑于2022年，星期四5.6.1 5.6.1 平均码长平均码长对应码长为对应码长为，而而1、平均码长、平均码长单位是：码符号单位是：码符号/信源符号信源符号2、每个码元携带的信息量
28、每个码元携带的信息量H(X)每个信源符号携带的信息量每个信源符号携带的信息量H(S)第54页，共65页，编辑于2022年，星期四3、编码后信道的信息传输率、编码后信道的信息传输率显然，显然，越短，越短，越大，信息传输效率越高越大，信息传输效率越高4、最佳码、最佳码或紧致码或紧致码平均长度平均长度最小的唯一可译码。最小的唯一可译码。第55页，共65页，编辑于2022年，星期四5.6.2 5.6.2 离散无记忆信源的唯一可译码长离散无记忆信源的唯一可译码长 的理论极限的理论极限定理定理5.7信源信源S熵为熵为H(S),r个码元可以找个码元可以找到一种唯一可译码，使码长满足到一种唯一可译码，使码长满
29、足且且的理论下限是的理论下限是，获得条，获得条件件第56页，共65页，编辑于2022年，星期四向上取整得香农码长！向上取整得香农码长！第57页，共65页，编辑于2022年，星期四定理定理5.7表达式表达式定理定理5.7可表示成可表示成第58页，共65页，编辑于2022年，星期四5.6.3 5.6.3 离散无记忆离散无记忆NN次扩展信源编码的次扩展信源编码的 平均码长理论极限平均码长理论极限定理定理5.8香农第一定理香农第一定理无失真变长信源编码定理无失真变长信源编码定理信源信源的熵为的熵为，r个码元，个码元，可构成唯一可译码，使信源可构成唯一可译码，使信源S中每个信源中每个信源符号所需的平均码
30、长满足符号所需的平均码长满足或或第59页，共65页，编辑于2022年，星期四且且式中式中是是对应的码字长度对应的码字长度证明：证明：第60页，共65页，编辑于2022年，星期四定理指出，要做到无失真信源编码，编定理指出，要做到无失真信源编码，编码每个信源符号所需要的码元数就是信码每个信源符号所需要的码元数就是信源的熵源的熵(以以r为底为底)。当扩展次数当扩展次数时，平均码长时，平均码长达到极限值达到极限值。推广：当信源是平稳遍历的有记忆信源推广：当信源是平稳遍历的有记忆信源马尔可夫信源时马尔可夫信源时第61页，共65页，编辑于2022年，星期四编码信息率编码信息率信道的信息传输率信道的信息传输
31、率R而而即即所以所以第62页，共65页，编辑于2022年，星期四结论：结论：无失真信源编码应使变换无失真信源编码应使变换(编码编码)后后的码符号信源尽可能为等概分布，以使新信的码符号信源尽可能为等概分布，以使新信源的每个码符号平均所含的信息量最大，使源的每个码符号平均所含的信息量最大，使信源的信息传输率信源的信息传输率R达到信道容量达到信道容量C，实现，实现信源与信道的理想统计匹配。信源与信道的理想统计匹配。编码效率编码效率码的剩余度码的剩余度第63页，共65页，编辑于2022年，星期四例例5.4有一离散无记忆信源有一离散无记忆信源解解：H(S)=0.811(比特比特/符号符号)编码编码对对编
32、编码码与例与例5.1对比对比第64页，共65页，编辑于2022年，星期四定长编码与变长编码效率比较定长编码与变长编码效率比较例例5.1与例与例5.4相比：同一个信源，当要求相比：同一个信源，当要求编码效率达到编码效率达到96时，等长码需要时，等长码需要4120万个符号联合编码；变长码只需万个符号联合编码；变长码只需2个符号个符号（二次扩展信源）联合编码。（二次扩展信源）联合编码。结论：结论：采用变长编码，采用变长编码，N不需要很大就可以不需要很大就可以达到相当高的编码效率，而且可以实现无达到相当高的编码效率，而且可以实现无失真编码。且随着失真编码。且随着N的增大，编码效率越来的增大，编码效率越来越接近于越接近于1。第65页，共65页，编辑于2022年，星期四