信息论与编码 曹雪芹 Chap5.ppt

信源编码 ;5.1 编码的定义 5.2 无失真信源编码 5.3 限失真信源编码 5.4 常用信源编码方法简介;5.1 编码的定义;信源编码： 无失真信源编码—第一极限定理 离散信源 限失真信源编码—第三极限定理 连续信源 信道编码 第二极限定理 信源编码 在不失真或允许一定失真条件下,如何用尽可能少的符号来传送信源信息,以便提高信息传输率 信道编码 在信道受干扰的情况下如何增加信号的抗干扰能力,同时又使得信息传输率最大。;编码的定义;码序列: 信源输出符号序列变换成适合信道传输的符号序列;信源编码器;编码的定义;对离散无记忆信源的N次扩展信源进行编码得到N次扩展码。; 将信源符号集中的每个信源符号 固定地映射成一个码字 ，这样的码称为分组码，也叫块码;编码的定义;编码的定义;;编码的定义;码树 表示各码字的构成；构造即时码 ;码4;1;编码的定义;定理 设信源符号集为 ，码符号集为 ，对信源进行编码，得到的码为 ，码长分别为 。即时码存在的充要条件是;同样，在li 阶节点上的终端节点使得 个l阶节点不能得到使用。最后l阶节点只剩下;由于即时码必然可以用树图构造。可取l阶的r叉树且 ，在第l阶上共有 个节点，于是长为li 的码字相当于砍去了该叉树第l阶上的 个节点，q个码字共砍去第l阶的节点数必小于 ，即 ， ; 定理 唯一可译码存在的充要条件是;例：设二进制码树中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,应用McMillan不等式,得： ;编码的定义;唯一可译码的判别准则;(1) 考查C中所有的码字，若 是 的前缀，则将相应的后缀作为一个尾随后缀码放入集合 中；; 定理 一个码是唯一可译码的充要条件是的 的并集中没有C中的码字。 ;例;5.2 无失真信源编码;无失真信源编码;无失真信源编码;5.2.1 定长编码定理;定长编码;定长编码;方法1 考虑符号之间的依赖关系，对信源S的扩展信源进行编码。考虑符号之间的相关性，有些符号序列不会出现。 ;定长编码定理;定长编码定理;⑵将定理的条件改写成 其中：左边：KL长码字所能携带的最大信息， 右边：L长信源序列携带的信息量。;定长编码定理;对定长编码,若要实现几乎无失真编码,则信源长度必须满足:;例5-2设离散无记忆信源概率空间;5.2.2 变长编码定理; 定义 设有信源 编码后的码字分别为 ，各码字相应的码长分别为 因为是唯一可译码，信源符号 和码字 一一对应，则定义此码的平均码长为;如果传输一个码符号平均需要t秒时间，则编码后信源每秒钟提供的信息量为; 定义 对于给定的信源和码符号集，若有一个唯一可译码，其平均码长 小于所有其他唯一可译码，则称这种码为紧致码或最佳码。 ;变长编码定理;;变长编码定理;定理5.7是香农信息论的主要定理之一。定理指出，要做到无失真信源编码，每个信源符号平均所需最少的r元码元数就是信源的熵值（以r进制单位为信息量单位）。若编码的平均码长小于信源的熵值，则唯一可译码不存在，在译码或反变换时必然要带来失真或差错，同时定理还指出，通过对扩展信源进行变长编码，当 时，平均码长 可达到这个极限值。;变长编码定理;由;例5-3设离散无记忆信源概率空间;再对长度为L =2的信源序列进行变长编码,其即时码如表;将信源序列的长度增加,L＝3或L=4,对这些信源序列X进行编码,并求出其编码效率为;编码的目的;信源编码： 以提高通信有效性为目的的编码。 通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。 信道编码： 是以提高信息传输的可靠性为目的的编码。 通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码： 是以提高通信系统的安全性为目的的编码。 通常通过加密和解密来实现。从信息论的观点出发 “加密”可视为增熵的过程,“解密”可视为减熵的过程。;信源编码理论是信息论的一个重要分支,其