信息论与编码第5章（完整）.pptVIP

信源编码 第5章 5.1 编码的定义 5.2 无失真信源编码 5.3 限失真信源编码 5.4 常用信源编码方法简介 信源编码： 无失真信源编码—第一极限定理 离散信源 限失真信源编码—第三极限定理 连续信源 信道编码 第二极限定理 信源编码 在不失真或允许一定失真条件下,如何用尽可能少的符号来传送信源信息,以便提高信息传输率 信道编码 在信道受干扰的情况下如何增加信号的抗干扰能力,同时又使得信息传输率最大。 编码的定义 信源编码: 将信源输出符号,经信源编码器后变换成另外的压缩符号,然后将压缩后信息经信道传送给信宿 信源符号之间存在分布不均匀和相关性,使得信源存在冗余度,信源编码的主要任务就是减少冗余,提高编码效率。 针对信源输出符号序列的统计特性,寻找一定的方法把信源输出符号序列变换为最短的码字序列。 编码的定义 编码定理证明: 必存在一种编码方法,使代码的平均长度可任意接近但不能低于符号熵; 达到这目标的途径就是使概率与码长匹配。 统计匹配编码： 根据信源的不同概率分布而选用与之匹配的编码,以达到在系统中传信速率最小。 编码的定义 等长码：码中所有码字的长度都相同 变长码：码中的码字长短不一 非奇异码：信源符号与码字是一一对应的 奇异码：码1 编码的定义 唯一可译码： 任意有限长的码元序列,只能被唯一地分割成一个个的码字。 例：{0,10,11}是一种唯一可译码。 任意一串有限长码序列,如100111000,只能被分割成10,0,11,10,0,0。任何其他分割法都会产生一些非定义的码字。 奇异码不是唯一可译码 非奇异码 唯一可译码 — 码3 非唯一可译码 — 码2 编码的定义 唯一可译码 非即时码： 如果接收端收到一个完整的码字后不能立即译码,还需等下一个码字开始接收后才能判断是否可以译码 即时码： (非延长码) (异前缀码) 在译码时无需参考后续的码符号就能立即作出判断,译成对应的信源符号。 任意一个码字都不是其它码字的前缀部分 在延长码中,有的码是唯一可译的,取决于码的总体结构 编码的定义 码 码树 表示各码字的构成 树码 如果有n个信源符号,那么在码树上就要选择n个终端节点,用相应的r元基本符号表示这些码字。 编码的定义 码3对应的树如下图: 编码的定义 满树： 每个节点上都有r个分枝的树——等长码 非满树： 变长码 用树的概念可导出唯一可译码存在的充分和必要条件,即各码字的长度Ki应符合Kraft不等式 例：设二进制码树中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得： 编码的定义 必须注意： Kraft不等式只是用来说明唯一可译码是否存在,并不能作为唯一可译码的判据。 如码字{0，10，010，111}虽然满足Kraft不等式,但它不是唯一可译码。 无失真信源编码 信源编码器输入的消息序列: X=(X1 X2…Xl …XL), Xl∈{a1,…an}, 输入的消息总共有nL种可能的组合 输出的码字为: Y=(Y1 Y2 …Yk… YK ) , Yk∈{b1,…bm} 输出的码字总共有mK种可能的组合。 无失真信源编码 实现无失真的信源编码,要求: 信源符号X1 X2…Xl …XL 是一一对应的 码字Y1 Y2…Yk… YK 能够无失真或无差错地从Y恢复X,也就是能正确地进行反变换或译码 ; 传送Y时所需要的信息率最小 5.2.1 定长编码定理 在定长编码中,K是定值。 我们的目的是寻找最小K值。 编码器输入X=(X1 X2…Xl …XL), Xl∈{a1,…an}, 输入的消息总共有nL种可能的组合 输出的码字Y=(Y1 Y2 …Yk… YK ) , Yk∈{b1,…bm} 输出的码字总共有mK种可能的组合。 若对信源进行定长编码,必须满足: nL≤mK 定长编码 若对信源进行定长编码,必须满足: 定长编码 实际英文电报符号信源,在考虑了符号出现的概率以及符号之间的依赖性后,平均每个英文电报符号所提供的信息量约等于1.4比特,大大小于5比特。 编码后5个二元符号只携带约1.4比特信息量。 定长编码的信息传输效率极低。 定长编码定理 定长编码定理： 由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1…Xl…XL,可用 K个符号Y1…Yk…YK(每个符号有m种可能值)进行定长编码。对任意ε＞0,δ＞0,只要 则当L足够大时,必可使译码差错小于δ;反之,当 时,译码差错一定是有限值