信息论 第五章

1、信息论 第五章第1页，共65页，2022年，5月20日，1点12分，星期一1、信源编码的目的 在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以便提高信息传输率。2、信道编码的目的 在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。第2页，共65页，2022年，5月20日，1点12分，星期一5.1 编 码 器5.1.1 编码器的构成5.1.2 有关常用码的概念第3页，共65页，2022年，5月20日，1点12分，星期一5.1.1 编码器的构成编码器S: 信源符号码符号，或码元编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。码字长度或码长C

2、码字第4页，共65页，2022年，5月20日，1点12分，星期一(信源符号)(信源序列)码字由码元组成码C由码字 组成编码就是从信源符号 到码字 的一种映射，一一对应，可逆，则可实现无失真编码。第5页，共65页，2022年，5月20日，1点12分，星期一5.1.2 有关常用码的概念1、二元码码符号集为 ，所得码字是二元序列。2、等长码一组码中所有码字的码长都相同。3、变长码一组码中所有码字的码长各不相同。第6页，共65页，2022年，5月20日，1点12分，星期一4、非奇异码C一组码中所有码字都不相同。 即5、奇异码C一组码中有相同的码字。 即6、同价码码符号集 中每个码符号 所占的传输时间都

3、相同。一般二元码是同价码。第7页，共65页，2022年，5月20日，1点12分，星期一对于同价码，等长码中每个码字的传输时间都相同，变长码每个码字的传输时间就不一定相同。7、码的N次扩展码N次扩展信源对应的N个码字组成的码字序列的集合。N次扩展码 B第8页，共65页，2022年，5月20日，1点12分，星期一举例 信源符号的码和二次扩展码的形式信源符号si符号概率P(si)码1码2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111表 5.1等长码变长码非奇异码第9页，共65页，2022年，5月20日，1点12分，星期一表5.2 码2的二次扩展码信源符号扩

4、展码字信源符号扩展码字信源S的二次扩展信源信源S的二次扩展码第10页，共65页，2022年，5月20日，1点12分，星期一8、唯一可译码码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此码称唯一可译码或单译可译码。(1) 信源符号对应的码是非奇异码。(2) 任意有限长的N次扩展码是非奇异的。例：码符号序列 “0 01 0” “001 0”第11页，共65页，2022年，5月20日，1点12分，星期一5.2 等 长 码5.2.1 等长码的唯一可译性5.2.2 等长码的编码长度第12页，共65页，2022年，5月20日，1点12分，星期一5.2.1 等长码的唯一可译性若等长码

5、是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码，因此一定是唯一可译码。信源符号si符号概率P(si)码1码2s1P(s1)0000s2P(s2)0111s3P(s3)1010s4P(s4)1111表 5.3唯一可译码非唯一可译码第13页，共65页，2022年，5月20日，1点12分，星期一5.2.2 等长码的编码长度1、q个信源符号：码元数为r ：则码长 必须满足下式例: (1)(2)（表4.2）必要条件 第14页，共65页，2022年，5月20日，1点12分，星期一 个信源符号：可得到等长非奇异码取对数：当N=1时 是平均每个信源符号所需要的码符号个数2、对N次扩展信源编码第15页，

6、共65页，2022年，5月20日，1点12分，星期一3、等长码的码长仍可压缩考虑符号出现的概率和符号间的依赖关系，码长可压缩。例：其余且二次扩展信源 有 个符号, 压缩至4个符号, 编码即可.第16页，共65页，2022年，5月20日，1点12分，星期一结论: 考虑信源符号间的依赖关系后, 再考虑符号出现的概率时,所需平 均码长可能缩短.第17页，共65页，2022年，5月20日，1点12分，星期一5.3* 渐进等分割性和 典型序列 对于离散无记忆信源 N次扩展信源第18页，共65页，2022年，5月20日，1点12分，星期一当 为有限值时,第19页，共65页，2022年，5月20日，1点12

7、分，星期一弱大数定律 对于独立、等同分布的随机变量 ，只要 n 足够大时， 接近其数学期望 EX。第20页，共65页，2022年，5月20日，1点12分，星期一定理 5.1 渐进等分割性(AEP): 若 随机序列中 相互统计独立并且服从同一概率分布 , 又 ，则 依概率收敛于 。第21页，共65页，2022年，5月20日，1点12分，星期一 可表示成, 对于任意 弱大数定律: 第22页，共65页，2022年，5月20日，1点12分，星期一此渐近等分割性说明,离散无记忆信源的N次扩展信源中,信源序列 的自信息的均值 ，依概率收敛于信源熵 。当N为有限长时,在所有 个长为N的信源序列中必有一些 ,

8、其自信息量的均值与信源熵 之差小于 ,即:或称N长序列 为 典型序列.第23页，共65页，2022年，5月20日，1点12分，星期一中所有 典型序列 的集合表示为非 典型序列集第24页，共65页，2022年，5月20日，1点12分，星期一(2) 若 ，则(3) 设 表示 典型序列集 中包含 的 典型序列的个数，定理5.2: 对于任意小的正数 当N足够大时，则(1)第25页，共65页，2022年，5月20日，1点12分，星期一而显然证明: (1)可由定理5.1直接推得当 时，契比雪夫不等式当 依概率收敛于 第26页，共65页，2022年，5月20日，1点12分，星期一(2) 可由变形证得。推论：

9、当N足够大时， 可任意小，表明 典型序列出现的概率近似相等，所以称为渐进等概率序列。(3)由上述性质(2)证得。第27页，共65页，2022年，5月20日，1点12分，星期一性质(1)表明， 典型序列 是经常出现的信源序列。 时，成为必然事件。性质(2)表明 接近等概分布性质(3)表明当 时, 典型序列的总数占信源序列的比值为：一般所以，当第28页，共65页，2022年，5月20日，1点12分，星期一 是高概率集，它含有序列数常常比非典型序列数要少很多。所有信源序列非 典型序列集 典型序列集结论：只对少数的高概率 典型序列进行一一对应的等长编码。码字总数减少，所需码长就可以减少了。第29页，共

10、65页，2022年，5月20日，1点12分，星期一AEP结论：当N足够大时 所有 典型序列出现的概率近似相 等.2. 可粗略认为 典型序列出现的概率为3. 所有 典型序列的概率和接近为1,第30页，共65页，2022年，5月20日，1点12分，星期一5.4 等长信源编码定理5.4.1 等长信源编码定理 5.4.2 平稳有记忆信源的码长5.4.3 对于编码好坏的评价第31页，共65页，2022年，5月20日，1点12分，星期一5.4.1 等长信源编码定理 定理5.31、定理内容：一个离散无记忆信源，熵为 ，信源长为N，码符号 r个，码字 长，对于任意 ，只要满足则当N足够大时，可实现几乎无失真编

11、码。译码错误概率为任意小。 若则不能实现无失真编码，而当N足够大时，译码错误概率近似等于1。第32页，共65页，2022年，5月20日，1点12分，星期一 比较公式: 一般 ，当信源符号有依赖时， ，所以 得到压缩2、证明：(1) 整理 错误概率第33页，共65页，2022年，5月20日，1点12分，星期一设 (3) 当二元编码时 ，定理5.3为等长编码时平均每个信源符号所需要的二元码符号的极限值是H(s)。(2) 选取的码字总数小于集 中可能有的信源序列数，译码时定会产生错误。当N很长时，第34页，共65页，2022年，5月20日，1点12分，星期一5.4.2 平稳有记忆信源的码长对平稳有记

12、忆信源：用 替代定理5.3中的H(s) 无失真编码不能实现无失真编码第35页，共65页，2022年，5月20日，1点12分，星期一5.4.3 编码的评价定理5.3 式(1) 表示长为 的码符号载荷的最大信息量大于信源序列携带的信息量时,可实现几乎无失真编码. 式(2) 令 称编码信息率,表示编码后平均每个信源符号能载荷的最大信息量.只有编码信息率大于信源的熵,才能实现几乎无失真编码.第36页，共65页，2022年，5月20日，1点12分，星期一编码效率编码效率用来衡量编码效果等长编码的最佳效率得 表示编码前后平均每个信源符号能载荷的最大信息率之比。第37页，共65页，2022年，5月20日，1

13、点12分，星期一即在已知方差和信源熵的条件下, 容许错误概率 愈小, 编码效率 愈高, 则信源序列长度N必须愈长.在实际情况下, 要实现几乎无失真的等长编码, N要大到难以实现的程度.已知 当允许错误概率小于 时代入第38页，共65页，2022年，5月20日，1点12分，星期一采用二元编码，要求编码效率 ，允许错误概率 ，求编码长度？解: 例5.1 已知离散无记忆信源第39页，共65页，2022年，5月20日，1点12分，星期一当N取4120万以上时，才能按要求实现几乎无失真编码。因此N有限的等长码往往引入一定的失真和错误。第40页，共65页，2022年，5月20日，1点12分，星期一5.5

14、变 长 码5.5.1 唯一可译变长码与即时码5.5.2 即时码的树图构造法5.5.3 克拉夫特（kraft）不等式第41页，共65页，2022年，5月20日，1点12分，星期一1、唯一可译码5.5.1 唯一可译变长码与即时码信源si概率P(si)码1码2码3码4s11/20011s21/411101001s31/80000100001s41/8110110000001表 5.4 奇异码非唯一可译码非即时码即时码第42页，共65页，2022年，5月20日，1点12分，星期一（1）在唯一可译变长码中，译码时无需参考后续的码符号就能立即作出判断，译成对应的信源符号，这类码称为即时码 结构特点： 即时

15、码：码字不是其它码的前缀或延长 非即时码：某些码字是其它码的前缀 或延长。2、即时码第43页，共65页，2022年，5月20日，1点12分，星期一（2）在译码过程中，当收到一个完整的码符号序列时，无需等待下一个符号到达后作判断，而能直接译成对应的信源符号。3、码的分类及关系奇异码非奇异码唯一可译码即时码所有码第44页，共65页，2022年，5月20日，1点12分，星期一5.5.2 即时码的树图构造法1、码树的构造过程（1）根：从根出发伸出树枝，树枝的数目 等于码符号的总数r（2）节点：树枝的尽头为节点。从节点 出发再伸出树枝，每次每个节点 伸出r 枝，依次下去构成一棵树。第45页，共65页，2

16、022年，5月20日，1点12分，星期一（3）终端节点：被安排为码字的节点,它 不再继续伸枝，用粗黑点表示。（4）中间节点：没被安排为码字继续伸出 枝的节点，用空心圆表示。（5）码字：由从根出发到终端节点走过的 路径所对应的码符号组成。按树图法构成的码一定满足即时码的要求。第46页，共65页，2022年，5月20日，1点12分，星期一（2）当码字长度给定，即时码不是唯一的（4）码树图可用来译码从根 中间节点 终端节点2、码字与树图的联系（1）当第 阶的节点作为终端节点，相 应码字的码长为 。（3）当 元 节的码树的所有树枝都被用 上时，第 阶节点共有 个终端节 点 对应于 长的等长编码 等长

17、码也是即时码的一种。第47页，共65页，2022年，5月20日，1点12分，星期一码3的码树 r=2, r=3 的三阶节点树图画出码4的树图 码4的另一种树图小结：将变长码与码树建立“一一对应”关系：树根 码字起点树枝数 码的进制数节点 码字或码字的一部分终止节点 码字节数 码长非满树 变长码满树 等长码第48页，共65页，2022年，5月20日，1点12分，星期一5.5.3 克拉夫特（kraft）不等式1、定理5.4 对于码符号为 任意即时码(非延长码)，其码字为 ，所对应的码长为 ，则必定满足反之，若码长满足上面不等式，则一定存在具有这样码长的即时码。第49页，共65页，2022年，5月2

18、0日，1点12分，星期一证明：充分性(1) r元树，第N阶的总枝数 枝(2) 第 阶节点作为码字，使第N 阶减少的枝数 (3) 第 阶的码长 (4) 个码字使第N阶减少的树枝数证得第50页，共65页，2022年，5月20日，1点12分，星期一Kraft不等式的物理意义：给定信源符号数q和码符号数r，只要允许码字长度可以足够长，就总可以满足Kraft不等式，从而得到即时码。第51页，共65页，2022年，5月20日，1点12分，星期一2、定理5.5 将定理5.4中的即时码改为唯一可译码，其余不变。推论:(1)当码长满足kraft不等式时，不一定是唯一可 译码。(2) 但一定存在至少一种码长相同的

19、唯一可译 码。不一定是即时码。(3) 也一定能找到至少一种相同码长的即时码。第52页，共65页，2022年，5月20日，1点12分，星期一5.6 变长信源编码定理5.6.2 离散无记忆信源的唯一可译码长 的理论极限5.6.1 平均码长5.6.3 离散无记忆N次扩展信源编码的 平均码长理论极限第53页，共65页，2022年，5月20日，1点12分，星期一5.6.1 平均码长对应码长为 ，而1、平均码长单位是：码符号/信源符号2、每个码元携带的信息量H (X)每个信源符号携带的信息量H(S)第54页，共65页，2022年，5月20日，1点12分，星期一3、编码后信道的信息传输率显然， 越短， 越大

20、，信息传输效率越高4、最佳码 或紧致码平均长度 最小的唯一可译码。第55页，共65页，2022年，5月20日，1点12分，星期一5.6.2 离散无记忆信源的唯一可译码长 的理论极限定理5.7 信源S熵为H(S), r个码元可以找 到一种唯一可译码，使码长满足且 的理论下限是 ，获得条件第56页，共65页，2022年，5月20日，1点12分，星期一向上取整得香农码长！第57页，共65页，2022年，5月20日，1点12分，星期一 定理5.7 表达式定理5.7可表示成第58页，共65页，2022年，5月20日，1点12分，星期一5.6.3 离散无记忆N次扩展信源编码的 平均码长理论极限定理 5.8 香农第一定理 无失真变长信源编码定理信源 的熵为 ， r个