无失真的信源编码.ppt

第八章无失真的信源编码 8 1霍夫曼 Huffman 码 8 2费诺 Fano 码 8 3香农 费诺 埃得斯码 8 4游程编码和MH编码 8 6字典码 8 5算术编码 8 1霍夫曼 Huffman 码 设离散无记忆信源二进制香农码的编码步骤如下 将信源符号按概率从大到小的顺序排列 为方便起见 令p x1 p x2 p xn 令p x0 0 用pa xj j i 1表示第i个码字的累加概率 则 确定满足下列不等式的整数ki 并令ki为第i个码字的长度 log2p xn ki log2p xn 1将pa xj 用二进制表示 并取小数点后ki位作为符号xi的编码 例有一单符号离散无记忆信源对该信源编二进制香农码 其编码过程如下表所示 8 1霍夫曼 Huffman 码 计算出给定信源香农码的平均码长若对上述信源采用等长编码 要做到无失真译码 每个符号至少要用3个比特表示 相比较 香农编码对信源进行了压缩 由离散无记忆信源熵定义 可计算出 对上述信源采用香农编码的信息率为编码效率为信源熵和信息率之比 则可以看出 编码效率并不是很高 8 1霍夫曼 Huffman 码 第六节费诺编码 费诺编码也是一种常见的信源编码方法 编码步骤如下 将概率按从大到小的顺序排列 令p x1 p x2 p xn 按编码进制数将概率分组 使每组概率尽可能接近或相等 如编二进制码就分成两组 编m进制码就分成m组 给每一组分配一位码元 将每一分组再按同样原则划分 重复步骤2和3 直至概率不再可分为止 第六节费诺编码 例设有一单符号离散信源对该信源编二进制费诺码 编码过程如下表 第六节费诺编码 该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率 费诺码比较适合于每次分组概率都很接近的信源 特别是对每次分组概率都相等的信源进行编码时 可达到理想的编码效率 第六节费诺编码 题中码字还可用码树来表示 如图所示 第七节霍夫曼编码 霍夫曼 Huffman 编码是一种效率比较高的变长无失真信源编码方法 编码步骤二进制哈夫曼编码m进制哈夫曼编码 第七节霍夫曼编码 编码步骤 将信源符号按概率从大到小的顺序排列 令p x1 p x2 p xn 给两个概率最小的信源符号p xn 1 和p xn 各分配一个码位 0 和 1 将这两个信源符号合并成一个新符号 并用这两个最小的概率之和作为新符号的概率 结果得到一个只包含 n 1 个信源符号的新信源 称为信源的第一次缩减信源 用S1表示 将缩减信源S1的符号仍按概率从大到小顺序排列 重复步骤2 得到只含 n 2 个符号的缩减信源S2 重复上述步骤 直至缩减信源只剩两个符号为止 此时所剩两个符号的概率之和必为1 然后从最后一级缩减信源开始 依编码路径向前返回 就得到各信源符号所对应的码字 第七节霍夫曼编码 二进制哈夫曼编码 例设单符号离散无记忆信源如下 要求对信源编二进制霍夫曼码 编码过程如下图 后页 在图中读取码字的时候 一定要从后向前读 此时编出来的码字才是可分离的异前置码 若从前向后读取码字 则码字不可分离 第七节霍夫曼编码 二进制哈夫曼编码 第七节霍夫曼编码 二进制哈夫曼编码 将上图左右颠倒过来重画一下 即可得到二进制哈夫曼码的码树 信源熵为 平均码长为编码效率为若采用定长编码 码长K 3 则编码效率可见哈夫曼的编码效率提高了12 7 第七节霍夫曼编码 二进制哈夫曼编码 第七节霍夫曼编码 二进制哈夫曼编码 注意 哈夫曼的编法并不惟一 每次对缩减信源两个概率最小的符号分配 0 和 1 码元是任意的 所以可得到不同的码字 只要在各次缩减信源中保持码元分配的一致性 即能得到可分离码字 不同的码元分配 得到的具体码字不同 但码长ki不变 平均码长也不变 所以没有本质区别 缩减信源时 若合并后的新符号概率与其他符号概率相等 从编码方法上来说 这几个符号的次序可任意排列 编出的码都是正确的 但得到的码字不相同 不同的编法得到的码字长度ki也不尽相同 例 单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码 0 1 0 1 0 1 方法一 合并后的新符号排在其它相同概率符号的后面 第七节霍夫曼编码 二进制哈夫曼编码 0 1 0 1 0 1 这两种编码哪一种更好呢 我们来计算一下二者的码长 方法二 合并后的新符号排在其它相同概率符号的前面 第七节霍夫曼编码 二进制哈夫曼编码 两种编码的平均码长是一样的 都是2 2 那一种更好呢 我们可以计算一下平均码长的方差 定义码字长度的方差 2 第七节霍夫曼编码 二进制哈夫曼编码 第七节霍夫曼编码 二进制哈夫曼编码 可见 第二种编码方法的码长方差要小许多 意味着第二种编码方法的码长变化较小 比较接近于平均码长 第一种方法编出的5个码字有4种不同的码长 第二种方法编出的码长只有两种不同的码长 显然 第二种编码方法更简单 更容易实现 所以更好 结论 在哈夫曼编码过程中 对缩减信源符号按概率由大到小的顺序重新排列时 应使合并后的新符号尽可能排在靠前的位置 这样可使合并后的新符号重复编码次数减少 使短码得到充分利用 第七节霍夫曼编码 m进制哈夫曼编码 全树 概念定义 码树图中每个中间节点后续的枝数为m时称为全树 若有些节点的后续枝数不足m 就称为非全树 二进制码不存在非全树的情况 因为后续枝数是一时 这个枝就可以去掉使码字长度缩短 对m进制编码 若所有码字构成全树 可分离的码字数 信源个数 必为m k m 1 k为信源缩减次数 若信源所含的符号数n不能构成m进制全树 必须增加s个不用的码字形成全树 显然s m 1 若s m 1 意味着某个中间节点之后只有一个分枝 为了节约码长 这一分枝可以省略 第七节霍夫曼编码 m进制哈夫曼编码 在编m进制哈夫曼码时为了使平均码长最短 必须使最后一步缩减信源有m个信源符号 非全树时 有s个码字不用 第一次对最小概率符号分配码元时就只取 m s 个 分别配以0 1 m s 1 把这些符号的概率相加作为一个新符号的概率 与其它符号一起重新排列 以后每次就可以取m个符号 分别配以0 1 m 1 如此下去 直至所有概率相加得1为止 即得到各符号的m进制码字 第七节霍夫曼编码 m进制哈夫曼编码 例 对如下单符号离散无记忆信源 例5 4 1 编三进制哈夫曼码 这里 m 3 n 8令k 3 m k m 1 9 则s 9 n 9 8 1所以第一次取m s 2个符号进行编码 第七节霍夫曼编码 m进制哈夫曼编码 第七节霍夫曼编码 m进制哈夫曼编码 平均码长为 信息率为 编码效率为 可见 哈夫曼的编码效率相当高 对编码器的要求也简单得多 一些结论 香农码 费诺码 哈夫曼码都考虑了信源的统计特性 使经常出现的信源符号对应较短的码字 使信源的平均码长缩短 从而实现了对信源的压缩 香农码有系统的 惟一的编码方法 但在很多情况下编码效率不是很高 费诺码和哈夫曼码的编码方法都不惟一 费诺码比较适合于对分组概率相等或接近的信源编码 哈夫曼码对信源的统计特性没有特殊要求 编码效率比较高 对编码设备的要求也比较简单 因此综合性能优于香农码和费诺码 第八节游程编码 算术编码 香农编码 费诺编码 哈夫曼编码主要是针对无记忆信源 当信源有记忆时上述编码效率不高 游程编码对相关信源编码更有效 香农编码 费诺编码 哈夫曼编码属于无失真信源编码 游程编码属于限失真信源编码 2020 3 16 27 可编辑 第八节游程编码 算术编码 冗余编码 游程 数字序列中连续出现相同符号的一段 二元序列的游程 只有 0 和 1 两种符号 连 0 这一段称为 0 游程 它的长度称为游程长度L 0 连 1 这一段称为 1 游程 它的游程长度用L 1 表示 游程编码 二元独立序列游程长度概率若规定二元序列总是从 0 开始 对于随机序列 游程长度是随机的其取值可为1 2 3 直至无穷 游程长度序列 游程序列 用交替出现的 0 游程和 1 游程长度表示任意二元序列 游程变换 是一种一一对应的变换 也是可逆变换 例如 二元序列 000101110010001 可变换成如下游程序列 31132131 第八节游程编码 算术编码 冗余编码 游程变换减弱了原序列符号间的相关性 游程变换将二元序列变换成了多元序列 这样就适合于用其他方法 如哈夫曼编码 进一步压缩信源 提高通信效率 编码方法 首先测定 0 游程长度和 1 游程长度的概率分布 即以游程长度为元素 构造一个新的信源 对新的信源 游程序列 进行哈夫曼编码 游程编码 第八节游程编码 算术编码 冗余编码 二元独立序列游程长度的熵若二元序列的概率特性已知 由于二元序列与游程变换序列的一一对应性 可计算出游程序列的概率特性 令 0 和 1 的概率分别为p0和p1 则 0 游程长度L 0 的概率为p L 0 p0L 0 1p1式中L 0 1 2 在计算p L 0 时必然已有 0 出现 否则就不是 0 游程 若下一个符号是 1 则游程长度为1 其概率是p1 1 p0 若下一个符号为 0 再下一个符号为 1 则游程长度为2 其概率将为p0p1 依此类推 游程编码 第八节游程编码 算术编码 冗余编码 游程编码 游程长度至少是1 理论上 游程长度可以是无穷 但很长的游程实际出现的概率非常小 同理可得 1 游程长度L 1 的概率为 P L 1 p1L 1 1p0 0 游程长度的熵 第八节游程编码 算术编码 冗余编码 二元独立序列的平均游程长度 0 游程序列的平均游程长度同理可得 1 游程长度的熵和平均游程长度 游程编码 第八节游程编码 算术编码 冗余编码 游程编码 二元独立序列的熵 0 游程序列的熵与 1 游程长度的熵之和除以它们的平均游程长度之和 即为对应原二元序列的熵H X 游程变换后符号熵没有变 因为游程变换是一一对应的可逆变换 所以变换后熵值不变 第八节游程编码 算术编码 冗余编码 游程变换有较好的去相关效果 因而对游程序列进行哈夫曼编码可获得较高的编码效率 假设 0 游程长度的哈夫曼编码效率为 0 1 游程长度的哈夫曼编码效率为 1 由编码效率的定义和式 5 4 9 可得对应二元序列的编码效率 信源熵和信息率之比为编码效率 H X R 当 0 游程和 1 游程的编码效率都很高时 采用游程编码的效率也很高 至少不会低于较小的那个效率 要想编码效率尽可能高 应尽可能提高熵值较大的游程编码效率 游程编码 第八节游程编码 算术编码 冗余编码 算术编码 算术编码不同于哈夫曼码 它是非分组 非块 码 它从全序列出发 考虑符号之间的关系来进行编码 算术编码利用了累积概率的概念 算术码主要的编码方法是计算输入信源符号序列所对应的区间 因为在编码过程中 每输入一个符号要进行乘法和加法运算 所以称此编码方法为算术编码 二元序列的算术编码可用于黑白图像的编码 例如传真 第八节游程编码 算术编码 冗余编码 算术编码 设信源符号集A a1 a2 an 其相应概率分布为P ai P ai 0 i 1 2 n 信源符号的累积分布函数为 所得累积分布函数为每台级的下界值 则其区间为 0 1 左闭右开区间 F a1 0F a2 P a1 F a3 P a1 P a2 当A 0 1 二元信源时 F 0 0 F 1 P 0 第八节游程编码 算术编码 冗余编码 算术编码 计算二元无记忆信源序列的累积分布函数初始时 在 0 1 区间内由F 1 划分成二个子区间 0 F 1 和 F 1 1 F 1 P 0 子区间 0 F 1 的宽度为A 0 P 0 对应于信源符号 0 子区间 F 1 1 的宽度为A 1 P 1 对应于信源符号 1 若输入符号序列的第一个符号为s 0 落入 0 F 1 区间 得累积分布函数F s 0 F 0 0 第八节游程编码 算术编码 冗余编码 算术编码 输入第二个符号为 1 s 01 s 01 所对应的区间是在区间 0 F 1 中进行分割 符号序列 00 对应的区间宽度为 A 00 A 0 P 0 P 0 P 0 P 00 对应的区间为 0 F s 01 符号序列 01 对应的区间宽度为A 01 A 0 P 1 P 0 P 1 P 01 A 0 A 00 对应的区间为 F s 01 F 1 累积分布函数F s 01 P 00 P 0 P 0 第八节游程编码 算术编码 冗余编码 算术编码 第八节游程编码 算术编码 冗余编码 算术编码 输入第三个符号为 1 输入序列可记做s1 011 若第三个符号输入为 0 可记做s0 010 现在 输入序列s1 011 对应的区间是对区间 F s F 1 进行分割 序列s0 010 对应的区间宽度为A s 010 A s 01 P 0 A s P 0 其对应的区间为 F s F s A s P 0 序列s1 011 对应的区间宽度为A s 011 A s P 1 A s 01 A s 010 A s A s0 其对应的区间为 F s A s P 0 F 1 符号序列s1 011 的累积分布函数为F s1 F s A s P 0 若第三个符号输入为 0 符号序列s0 010 的区间下界值仍为F s 得符号序列s0 010 的累积分布函数为F s0 F s 第八节游程编码 算术编码 冗余编码 算术编码 归纳当已知前面输入符号序列为s 若接着再输入一个符号 0 序列s0的累积分布函数为 F s0 F s 对应区间宽度为 A s0 A s P 0 若接着输入的一个符号是 1 序列的累积分布函数为 F s1 F s A s P 0 对应区间宽度为 A s1 A s P 1 A s A s0 第八节游程编码 算术编码 冗余编码 算术编码 符号序列对应的区间宽度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 第八节游程编码 算术编码 冗余编码 算术编码 二元信源符号序列的累积分布函数的递推公式F sr F s P s F r r 0 1 sr表示已知前面信源符号序列为s 接着再输入符号为rF 0 0 F 1 P 0 F s0 F s F s1 F s P s F 1 F s P s P 0 A sr P sr P s P r r 0 1 A s0 P s0 P s P 0 A s1 P s1 P s P 1 第八节游程编码 算术编码 冗余编码 算术编码 举例 已输入二元符号序列为s 011 接着再输入符号为 1 得序列累积分布函数为 F s1 F 0111 F s 011 P 011 P 0 F s 01 P 01 P 0 P 011 P 0 F s 0 P 0 P 0 P 01 P 0 P 011 P 0 0 P 00 P 010 P 0110 对应的区间宽度为A s1 P s 011 P 1 P 011 P 1 P 0111 上述整个分析过程可用图5 6 1描述式 5 6 1 和 5 6 2 是可递推运算 在实际中 只需两个存储器 把P s 和F s 存下来 然后 根据输入符号和式 5 6 1 5 6 2 更新两个存储器中的数值 因此在编码过程中 每输入一个符号要进行乘法和加法运算 所以称为算术编码 第八节游程编码 算术编码 冗余编码 算术编码 第八节游程编码 算术编码 冗余编码 算术编码 通过关于信源符号序列的累积分布函数的计算 把区间分割成许多小区间 不同的信源符号序列对应不同的区间为 F s F s P s 可取小区间内的一点来代表这序列 编码方法 将符号序列的累积分布函数写成二进位的小数 取小数点后k位 若后面有尾数 就进位到第k位 这样得到的一个数C 并使k满足举例 第八节游程编码 算术编码 冗余编码 算术编码 编码效率这样选取的数值C 一般根据二进小数截去尾数的影响得C F s C而P s 1 2k信源符号序列对应区间的上界为F s P s F s 1 2k C可见 数值在区间 F s F s P s 内 而信源符号序列对应的不同区间 左封右开 是不重叠的 所以编得的码是即时码 第八节游程编码 算术编码 冗余编码 算术编码 算术编码的编码效率很高