信息论第四章.ppt

第四章 无失真信源编码 4.1 编码器 4.1.1 编码器的构成 4.1.2 有关常用码的概念 4.2 等长码 4.2.1 等长码的唯一可译性 4.3 渐进等分割性和 典型序列 对于离散无记忆信源 4.4.1 等长信源编码定理 — 定理4.3 采用二元编码，要求编码效率 ，允许错误概率 ，求编码长度？ 当N取4120万以上时，才能按要求实现几乎无失真编码，很困难的。因此N有限的等长码往往引入一定的失真，但变长码可以实现无失真编码。 4.5 变长码 4.5.1 唯一可译变长码与即时码 （1）在唯一可译变长码中，有一类码，它在译码时无需参考后续的码符号就能立即作出判断，译成对应的信源符号，这类码称为即时码。 结构特点： 即时码：码字不是其它码的前缀或延长 非即时码：某些码字是其它码的前缀 或延长。 （2）若码C中，没有任何完整的码字是其它码字的前缀，此码为即时码，也称非延长码或前缀条件码。 4.5.2 即时码的树图构造法 1、码树的构造过程 （1）根：从根出发伸出树枝，树枝的数目 等于码符号的总数r 例如: r 2，伸出两条树枝。 4.6 变长信源编码定理 比较公式4.3: 显然，一般 ，当信源符号有依赖时， ，所以 得到压缩 2、证明： 1 整理得 此时错误概率，即集 出现的概率 当 时， 设 3 当二元编码时 ，定理4.3成为 等长编码时平均每个信源符号所需要的二元码符号的极限值是H S . 2 即选取的码字总数小于集 中可能有的信源序列数，译码时定会产生错误。当N很长时， 4.4.2 平稳有记忆信源的码长 对于平稳有记忆信源： 用 替代定理4.1, 4.2, 4.3中的H S 可得 无失真编码 不能实现无失真编码 4.4.3 对于编码好坏的评价 定理4.3 得式 1 表示长为 的码符号载荷的最大信息量大于信源序列携带的信息量时,可实现几乎无失真编码. 得式 2 令 称编码信息率,表示编码后平均每个信源符号能载荷的最大信息量.只有编码信息率大于信源的熵,才能实现几乎无失真编码. 编码效率 编码效率用来衡量编码效果 定义4.3要求 最佳等长编码的效率 得 即 在已知方差和信源熵的条件下, 容许错误概率 愈小, 编码效率 愈高, 则信源序列长度N必须愈长. 在实际情况下, 要实现几乎无失真的等长编码, N要大到难以实现的程度. 已知 当允许错误概率小于 时 解: 例4.1 已知离散无记忆信源 4.5 变 长 码 4.5.1 唯一可译变长码与即时码 4.5.2 即时码的树图构造法 4.5.3 克拉夫特（kraft）不等式 1、唯一可译码 1 码本身必须是非奇异的 2 任意有限长N次扩展码必须是非奇异的 0001 1000 01 11 1/8 s4 001 100 00 00 1/8 s3 01 10 10 11 1/4 s2 1 1 0 0 1/2 s1 码4 码3 码2 码1 概率P si 信源si 表 4.3 奇异码 奇异码 非即时码 即时码 码1 是奇异码 非唯一可译码 码2 本身非奇异，但其扩展码是奇异的 例：0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 码3 — 唯一可译码，非即时码。 码4 — 唯一可译码，即时码。 码4中的码符号“1”也称为 “逗点码” 2、即时码 （3）在译码过程中，当收到一个完整的码符号序列时，无需等待下一个符号到达后作判断，而能直接译成对应的信源符号。 3、码的分类及关系 奇异码 非奇异码 唯一可译码 即时码 所有码 （2）节点：树枝的尽头为节点。从节点 出发再伸出树枝，每次每个节点 伸出r枝，依次下去构成一棵树。 （3）终端节点：被安排为码字的节点,它 不再继续伸枝，用粗黑点表示。 （4）中间节点：没被安排为码字继续伸出 枝的节点，用空心圆表示。 （5）码字：由从根出发到终端节点走过的 路径所对应的码符号组成。 显然，按树图法构成的码一定满足是即