信息论与编码理论-第三章.ppt

第三章信源编码 一 离散信源无失真编码 3 1信源及其分类3 2离散无记忆信源的等长编码3 3离散无记忆信源的不等长编码3 4最佳不等长编码 3 1信源及其分类 信源及其分类 离散信源 U 2 U 1 U0 U1 U2 Ul取自字母表A无记忆信源 Ul彼此独立有记忆信源 Ul彼此相关简单信源 Ul独立同分布平稳信源 各态历经源M阶记忆源 有限状态马尔可夫链 连续信源时间离散连续源随机波形源 3 2离散无记忆源的等长编码 离散无记忆源 字母表A a1 aK 概率p1 pK 长为L的源输出序列uL u1 uL 共有KL种序列码符号字母表B b1 bD 以码符号表示源输出序列 D元码等长D元码 不等长D元码单义可译码 每个消息都至少有一个码字与之对应 单义可译码存在充要条件DN KLN LlogK logD DMS的等长编码 NlogD LH U H U 是统计平均值 L达到无限时 一个具体的源输出序列的平均每符号的信息量才等于H U 选L足够长 使NlogD L H U eL DMS序列的自信息量 弱 强e典型序列集 信源划分定理 典型序列集 非典型序列集 序列集合 典型序列的比例 编码速率和等长编码定理 R 1 L logM N L logD M为码字总数定义 对于给定信源和编码速率R以及任意e 0 若有L0 以及编译码方法 使得L L0 错误概率小于e R是可达的等长编码定理R H U R是可达的 R H U 是不可达的编码效率 H U R 3 3DMS的不等长编码 平均码长 几个定义 唯一可译码逗点码 无逗点码字头或前缀异字头码或异前缀码树码 满树 非满树 全树树码构造异字头码 例子 Shannon Fano编码 D元码每次信源符号化为概率近似相等的D个子集这样可以保证D个码元近似等概 每个码字承载的信息量近似最大 码就近似最短 理想情况I ak nklogD p ak D nk Kraft不等式 长度为n1 n2 nK的D 元异字头码存在的充分必要条件是 二元异字头码Kraft不等式等号成立 定理 任意唯一可译码必满足Kraft不等式 不等长编码定理 编码速率 3 4最佳不等长编码 Huffman编码的最佳性 所谓最佳 是指在所有可能的编码方法中 其编码得到的平均码长最短 定理3 4 1 对于给定信源 存在有最佳惟一可译二元码 其最小概率的两个码字CK 1和CK的长度最长且相等 它们之间仅最后一位码元取值不同 一个为0 另一个为1 Huffman编码的最佳性 对信源可对aK 1和aK的码字的最后一位分别指定为1和0 然后作一辅助集 Huffman编码的最佳性 定理3 4 2对辅助集U 为最佳的码 对原始消息集U也是最佳的 若C 1 C 2 C K 1是对辅助集U 的最佳码 相应码长为n 1 n 2 n K 1 则对U的码字C1 C2 CK的码长为nk n kk K 2nk n K 1 1k K K 1 Huffman编码的最佳性 例 Huffman编码过程 例 Huffman编码过程 Shannon Fano编码例子 cabcedeacacdeddaaabaababaaabbacdebaceada共40个字母频度a 16 b 7 c 6 d 6 e 51 将给定符号按照其频率从大到小排序 a 16b 7c 6d 6e 52 将序列分成左右两部分 使得左部频率总和尽可能接近右部频率总和 有 a b c d e Shannon Fano编码例子 3 我们把第二步中划分出的上部作为二叉树的左子树 记0 下部作为二叉树的右子树 记1 4 分别对左右子树重复23两步 直到所有的符号都成为二叉树的树叶为止 b a c d e 0 0 1 0 1 0 1 1 a00b01c10d110e111 Shannon Fano编码例子 编码结果Cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010 长91bit采用3bit等长编码需120bit采用ASCII码需要320bit 采用Huffman编码 a16 b7 c6 d6 e5 11 13 24 0 1 0 1 0 1 0 1 a0 b100 c101 d110 e111 总比特数88 信源熵为86 601bit Huffman编码 Shannon Fano编码构造二叉树是自树根到树叶 很难保证最佳性 Huffman编码则是从树叶到树根 是最佳的 总结 Huffman需要知道信源的概率分布 这在实际中有时是比较困难的 采用半静态模型 自适应模型 markov模型 部分匹配预测模型等等解决这一问题 D元Huffman编码 共有K个符号 概率最小的R个符号码长最长K B D m D 1 注意B D 1K 2 m D 1 D 2 B B个 R个 B D 2 K 2 mod D 1 R 2 K 2 mod D 1 Shannon Fano Elias编码 累计分布函数 修正累计分布函数 Shannon Fano Elias编码 采用的数值作为ak的码字码长 Shannon Fano Elias编码 Shannon Fano Elias编码 算术码 应用于JPEG2000 H 263等图像压缩标准 算术码 信源序列 u1u2 un 的累计分布算术编码是计算序列的累计分布 用累计分布值表示序列 所以称为算术编码以二元信源输出序列的编码为例01110 算术码 P 010 P 011 F 011 P 0110 P 0111 F 0111 P 01110 P 01111 F 01111 算术码 信源符号序列u对应区间的宽度等于符号序列的概率 算术编码 F u 将 0 1 分割成许多小区间 取小区间内的一个点代表该序列 以该点数值的二进制小数表示该序列 码字长度为 算术编码 例 P 0 0 25 P 1 0 75 u 11111100P u 11111100 0 7560 252L 7F s 0 110100100111C 1101010编码效率92 7 LZ编码 利用字典编码方法信源符号A a1 aK 将序列分为不同的段取最短长度的连续符号构成段 保证互不相同 先取一个符号分段 若与前面段相同 就再取一个符号 直至序列结束得到字典表 码字由段号加后一个符号组成 单符号的码字 段号为0 LZ编码 LZ编码 00000001100001100001100000010001110 1234567 LZ编码 设长为L的信源序列u