第5章-3信息论与编码.ppt

1 5 3限失真信源编码定理 在本章一开始我们就分析了在很多实际信源中 特别在模拟的连续信源中 无失真要求是完全没有必要的 而且也是达不到的 在实际中限失真信源是具有现实意义的 2 限失真信源编码定理 限失真信源编码定理 设离散无记忆信源X的信息率失真函数为R D 当信息率R R D 时 只要信源序列长度L足够长 一定存在一种编码方法 其译码失真小于或等于D 为任意小的正数 反之 若R R D 则无论采用什么样的编码方法 其译码失真必大于D 如是二元信源 则对于任意小的 0 每一个信源符号的平均码长满足如下公式 3 5 4常用信源编码方法 4 常用信源编码 香农编码 费诺编码 哈夫曼编码主要是针对无记忆信源 当信源有记忆时上述编码效率不高 游程编码对相关信源编码更有效 香农编码 费诺编码 哈夫曼编码属于无失真信源编码 游程编码属于限失真信源编码 5 游程编码 游程 数字序列中连续出现相同符号的一段 二元序列的游程 只有 0 和 1 两种符号 连 0 这一段称为 0 游程 它的长度称为游程长度L 0 连 1 这一段称为 1 游程 它的游程长度用L 1 表示 6 游程编码 二元独立序列游程长度概率若规定二元序列总是从 0 开始 第一个游程是 0 游程 则第二个游程必为 1 游程 第三个又是 0 游程 对于随机序列 游程长度是随机的其取值可为1 2 3 直至无穷 游程长度序列 游程序列 用交替出现的 0 游程和 1 游程长度表示任意二元序列 游程变换 是一种一一对应的变换 也是可逆变换 例如 二元序列000101110010001 可变换成如下游程序列31132131 7 游程变换减弱了原序列符号间的相关性 游程变换将二元序列变换成了多元序列 这样就适合于用其他方法 如哈夫曼编码 进一步压缩信源 提高通信效率 编码方法 首先测定 0 游程长度和 1 游程长度的概率分布 即以游程长度为元素 构造一个新的信源 对新的信源 游程序列 进行哈夫曼编码 游程编码 8 多元序列也存在相应的游程序列多元序列变换成游程序列再进行压缩编码没有多大意义游程编码只适用于二元序列 对于多元信源 一般不能直接利用游程编码 9 冗余位编码 游程编码在多元信源的应用 如下多元序列x1 x2 xm1 y y y xm1 1 xm1 2 xm2 y y 可以用下面两个序列表示11 100 011 100 x1 x2 xm1 xm1 1 xm1 2 xm2 1表示信息位 0表示冗余位 10 5 4 2算术编码 算术编码是近十多年来发展迅速的一种无失真信源编码 它与最佳的哈夫曼码相比 理论性能稍加逊色 而实际压缩率和编码效率却往往还优于哈夫曼码 且实现简单 故很受工程上的重视 算术编码不同于哈夫曼码 它是非分组 非块 码 它从全序列出发 考虑符号之间的关系来进行编码 算术编码利用了累积概率的概念 算术码主要的编码方法是计算输入信源符号序列所对应的区间 11 00 360 60 841 算术码的主要概念 算术码的主要概念 把信源输出序列的概率和实数段 0 1 中的一个数C联系起来 设信源字母表为 a1 a2 其概率p a1 0 6 p a2 0 4将 0 1 分成与概率比例相应的区间 0 0 6 0 6 l p a1 p a2 00 61 设信源输出序列S S1S2S3 Sn当信源输出的第一个符号S1 a1时 数C的值处在 0 0 6 当信源输出的第一个符号S1 a2时 数C的值处在 0 6 l 根据信源S1的情况 把C所在的段再次按概率比例划分 p a1a1 p a1a2 p a2a1 p a2a2 随着序列的长度不断增加 C所在区间的长度就越短 也就可以更加精确地确定C的位置 12 累积概率 设信源符号集A a1 a2 an 其相应概率分布为p ai p ai 0 i 1 2 n 信源符号的累积概率为 显然P1 0 P2 p1 P3 p1 p2 而且pr Pr 1 Pr 13 累积概率Pr 1和Pr都是小于1的正数 可用 0 1 区间内的两个点来表示 P1 p1 P2 P3 P4 1 p2 p3 0 pr就是这两点间的小区间的长度 如图 当A 0 1 二元信源时 P 0 0 P 1 p 0 P 0 P 1 0 1 p 0 p 1 14 计算二元无记忆信源序列的累积概率初始时 在 0 1 区间内由P 1 划分成二个子区间 0 P1 和 P1 1 P 1 p 0 子区间 0 P1 的宽度为A 0 p 0 对应于信源符号 0 子区间 P1 1 的宽度为A 1 p 1 对应于信源符号 1 若输入符号序列的第一个符号为S 0 落入 0 P1 区间 得累积概率P S 0 P 0 0 15 若输入第二个符号为 1 S 01 S 01 所对应的区间是在区间 0 P 1 中进行分割 符号序列 00 对应的区间宽度为A 00 A 0 p 0 p 0 p 0 p 00 对应的区间为 0 P S 01 符号序列 01 对应的区间宽度为A 01 A 0 p 1 p 0 p 1 p 01 A 0 A 00 对应的区间为 P S 01 P 1 累积概率 P S 01 p 00 p 0 p 0 16 P 0 0 P 1 1 p 0 设输入符号序列S 011 p 1 P 0 P 1 p 00 P 01 p 01 P 01 P 1 P 011 p 010 p 011 p 0 p 00 p 01 p 01 p 010 p 011 归一律 P 0 0P 01 p 00 P 011 P 01 p 010 17 011 S1 S 01输入序列S1 011 对应的区间是对区间 P S P 1 进行分割序列S0 010 对应的区间宽度为A S 010 A S 01 p 0 A S p 0 其对应的区间为 P S P S A S p 0 序列S1 011 对应的区间宽度为A S 011 A S p 1 A S 01 A S 010 A S A S0 其对应的区间为 P S A S p 0 P 1 18 符号 00 区间宽度A 00 p 00 信源符号0的区间宽度A 0 p 0 P 0 0 P 1 1 p 0 p 1 P 0 P 1 p 00 P S S 01 p 01 P S P 1 P S1 p 010 p 011 当前面输入符号序列为S 若接着输入一个 0 累积概率 P S0 P S 对应区间宽度为 A S0 A S p 0 若接着输入的一个符号是 1 累积概率 P S1 P S A S p 0 对应区间宽度为 A S1 A S p 1 A S A S0 符号1的区间宽度A 1 p 1 信源符号 01 区间宽度A 01 p 01 A 0 A 00 19 符号序列对应的区间宽度A S 0 p 0 A S 1 1 A S 0 p 1 A S 00 p 00 A 0 p 0 p 0 p 0 A S 01 A S 0 A S 00 p 01 A 0 p 1 p 0 p 1 A S 10 p 10 A 1 p 0 p 1 p 0 A S 11 A S 1 A S 10 p 11 A S 1 p 1 p 1 p 1 A S 010 A S 01 p 0 p 01 p 0 p 010 A S 011 A S 01 A S 010 A S 01 p 1 p 01 p 1 p 011 信源符号序列S所对应区间的宽度等于符号序列S的概率p S 20 算术编码 二元信源符号序列的累积概率递推公式 S r 表示前面信源符号序列为S 接着再输入符号为rP 0 0 P 1 p 0 P S0 P S P S1 P S p S p 0 信源符号序列所对应区间的宽度递推公式 21 例 已输入二元符号序列为S 011 接着再输入符号为 1 得序列累积概率为 P S 1 P 0111 P S 011 p 011 p 0 P S 01 p 01 p 0 p 011 p 0 P S 0 p 0 p 0 p 01 p 0 p 011 p 0 0 p 00 p 010 p 0110 对应的区间宽度为A S 1 p S 011 p 1 p 011 p 1 p 0111 22 算术编码 一般多元信源序列的累积概率递推公式 序列的概率公式 23 算术编码 实际应用中 采用累积概率P S 表示码字C S 符号概率p S 表示状态区间A S 则有 C S r C S A S PrA S r A S pr 实际编码时 只需两个存储器 起始时可令 A 1 C 0每输入一个信源符号 存储器C和A就按照上式更新一次 直至信源符号输入完毕 就可将存储器C的内容作为该序列的码字输出 24 算术编码 在编码过程中 每输入一个符号要进行乘法和加法运算 所以称为算术编码 通过关于信源符号序列的累积概率的计算 把区间分割成许多小区间 不同的信源符号序列对应不同的区间为 P S P S p S 可取小区间内的一点来代表这序列 25 算术编码 编码方法 将符号序列的累积概率写成二进位的小数 取小数点后L位 若后面有尾数 就进位到第L位 这样得到的一个数C 并使L满足 代表大于或等于的最小整数 编码效率很高 当序列很长时 可达到概率匹配 平均代码长度接近S的熵值 可以唯一地译码 26 例 设二元无记忆信源S 0 1 其p 0 1 4 p 1 3 4 对二元序列11111100做算术编码 P S p 00000000 p 00000001 p 00000010 p 11111011 1 p 11111111 p 11111110 p 11111101 p 11111100 1 p 111111 1 3 4 6 0 110100100111 得C 0 1101010S的码字为1101010 解 p S 11111100 p2 0 p6 1 1 4 2 3 4 6 27 p 1 3 4 0 11 2 p 11 3 4 2 0 1001 2 p 0 1 4 2 2p S p 0 p S 右移2位 28 例有四个符号a b c d构成简单序列S abda 各符号及其对应概率如下表 算术编解码过程如下 29 设起始状态为空序列 则A 1 C 0 30 C abda 即为编码后的码字010111 31 算术编码过程 32 译码C abda 0 010111 0 1 0 0 1 第一个符号为a放大至 0 1 pa 1 C abda 21 0 10111 0 1 0 110 第二个符号为b去掉累积概率Pb 0 10111 0 1 0 00111 33 放大至 0 1 pb 1 0 00111 22 0 111 0 111 1 第三个