《信源编码的类型和基本要求》由会员分享，可在线阅读，更多相关《信源编码的类型和基本要求（31页珍藏版）》请在金锄头文库上搜索。
1、信源编码的类型和基本要求信源编码的类型和基本要求 1 香农编码 2 费诺编码 3 哈夫曼编码 1 1 31 31 2 2 31 31 本章节教学内容 基本要求 重点与难点 1 教学内容 信源编码的概念 三种最佳的信源编码 2 教学基本要求 掌握香农编码 掌握费诺编码 掌握哈夫曼编码 3 重点与难点 信息率 平均码长和编码效率的计算 多进制哈夫曼编码 引言引言 香农编码定理虽然指出了理想编码器的存在性 但是并 没有给出实用码的结构及构造方法 编码理论正是为了解决这一问题而发展起来的科学理论 编码的目的是为了优化通信系统 使通信系统的性能指 标有效性 可靠性 安全性和经济性达到最佳 3 3 31
2、31 按不同的编码目的 编码分为三类 信源 编码 信道编码和安全编码 加密编码 信源编码 提高信息传输的有效性 通常通 过压缩信息的冗余度来实现 信道编码 提高信息传输的可靠性 通常通 过增加信息的冗余度来实现 与信源编码正 好相反 加密编码 提高通信系统的安全性 通常通 过加密和解密来实现 从信息论的观点出发 加密 可视为增熵的过程 解密 可视为减 熵的过程 4 4 31 31 信源编码信源编码 信源编码理论是信息论的一个重要分支 其理论基础是信源编码的两个定理 香农第一定理 无失真信源编码定理 是 离散信源 数字信号编码的基础 香农第三定理 限失真信源编码定理 是 连续信源 模拟信号编码的
3、基础 信源编码的分类 离散信源编码 可做到无失真编码 连续信源编码 只能做到限失真信源编码 5 5 31 31 编码理论编码理论 无失真信源编码定理 定长编码定理 一个熵为H X 的离散无记忆信源X1X2 Xl XL 对信源 长为L的符号序列进行定长编码 设码字是从m个信源符号集内选取K 个码元组成Y1Y2 Yk YK 对于任意 0 0只要满足 K L log2m H X 则当L足够大时 必可使译码差错小于 即译码错误概率能为任意小 变长编码定理 K L log2m H X 其中K为平均码长 限失真信源编码定理 对于给定的失真D 总可以找到一种信源编码方 法 只要传输速率R大于R D 就可以在
4、平均失真任意接近D的条件下 实现波形重建 说明1 R D 称为率失真函数 它是单调非增函数 速率越高 平 均失真越小 说明2 为了保证在一定速率下的失真 必需采用信源编码 因而 会引入编码延时 6 6 31 31 香农编码香农编码 设离散无记忆信源 二进制香农码的编码步骤如下 4步 将信源符号按概率从大到小的顺序排列 p x1 p x2 p xn 令p x0 0 用pa xj j i 1表示第i个码字的累加概率 确定满足下列不等式的整数ki 并令ki为第i个码字的长度 log2 p xn ki 1 log2 p xn 将pa xj 用二进制表示 并取小数点后ki 位作为符号xi的编 码 7 7
5、 31 31 例 有一单符号离散无记忆信源 l 对该信源编二进制香农码 其编码过程如表所示 8 8 31 31 香农码的平均码长 l 若对上述信源采用等长编码 要做到无失真译码 每个符号至少要用3 个比特表示 相比较 香农编码对信源的等长编码而言有0 3比特 符号 的压缩 9 9 31 31 l由离散无记忆信源熵定义 可计算出 l对上述信源采用香农编码的信息率为 l编码效率为信源熵和信息率之比 则 l可以看出 编码效率并不是很高 费诺编码费诺编码 费诺编码也是一种常见的信源编码方法 编码步骤如下 将概率按从大到小的顺序排列 令 p x1 p x2 p xn 按编码进制数将概率分组 使每组概率尽
6、可能接近或相等 如编二进制码就分成两组 编m进制码就分成m组 给每一组分配一位码元 将每一分组再按同样原则划分 重复步骤2和3 直至概率 不再可分为止 1010 31 31 例 与香农编码一样的单符号离散信源 l 对该信源编二进制费诺码 编码过程如表 1111 31 31 上述码字还可用码树来表示 如图所示 1212 31 31 l 该信源的熵为 l 平均码长为 l 编码效率为 l 费诺编码有较高的编码效率 费诺码比较适合于每次分组概率都很 接近的信源 特别是对每次分组概率都相等的信源进行编码时 可 达到理想的编码效率 1313 31 31 例 有一单符号离散无记忆信源 l 对该信源编二进制费
7、诺码 编码过程如表 1414 31 31 l 码树图如图 l 信源熵为 H X 2 75 比特 符号 l 平均码长为 l 信息率 l 编码效率为 100 因为每次所分两组的概率恰好相等 1515 31 31 5 4 1 5 4 1 编码步骤编码步骤 哈夫曼 Huffman 编码是一种效率比较高的变长无失真信源编码方法 将信源符号按概率从大到小的顺序排列 令 p x1 p x2 p xn 给两个概率最小的信源符号p xn 1 和p xn 各分配一个码位 0 和 1 将这两个信源符号合并成一个新符号 并用这两个最小的概率之和 作为新符号的概率 结果得到一个只包含 n 1 个信源符号的新信源 称为信
8、源的第一次缩减信源 用S1表示 将缩减信源S1的符号仍按概率从大到小顺序排列 重复步骤2 得到 只含 n 2 个符号的缩减信源S2 重复上述步骤 直至缩减信源只剩两个符号为止 此时所剩两个符 号的概率之和必为1 然后从最后一级缩减信源开始 依编码路径向 前返回 就得到各信源符号所对应的码字 1616 31 31 哈夫曼编码 例 设单符号离散无记忆信源如下 要求对信源编二进制哈夫曼码 1717 31 31 l 将上图左右颠倒过来重画一下 即可得到二进制哈夫曼码的码树 如图所示 1818 31 31 l 信源熵为 l 平均码长为 l 编码效率为 l 若采用定长编码 码长K 3 则编码效率 l 可见
9、哈夫曼的编码效率提高了12 7 1919 31 31 注意 哈夫曼的编码并不惟一 每次对缩减信源两个概率最小的符号分配 0 和 1 码元是任意的 所以可得到不同的码字 只要在各次缩减信源中保持码元分配的 一致性 即能得到可分离码字 不同的码元分配 得到的具体码字不同 但码长ki不变 平均码长 也不变 所以没有本质区别 缩减信源时 若合并后的新符号概率与其他符号概率相等 从编 码方法上来说 这几个符号的次序可任意排列 编出的码都是正 确的 但得到的码字不相同 不同的编法得到的码字长度ki也不尽 相同 2020 31 31 举例说明上述问题 例 单符号离散无记忆信源 方法一 合并后的新符号排在其它
10、相同概率符号的后面 2121 31 31 2222 31 31 方法二 合并后的新符号排在其它相同概率符号的前面 2323 31 31 2424 31 31 l 单符号信源编二进制哈夫曼码 编码效率主要决定于信源熵和平均 码长之比 对相同的信源编码 其熵是一样的 采用不同的编法 得到的平均码长可能不同 平均码长越短 编码效率就越高 l 编法一的平均码长为 l 编法二的平均码长为 l 可见 本例两种编法的平均码长相同 所以编码效率相同 2525 31 31 讨论 哪种方法更好 定义码字长度的方差 2 长度ki与平均码长 之差的平方的数学 期望 即 编法一码字长度方差 编法二码字长度方差 2626
11、 31 31 l可见 编法二的码长方差要小许多 意味着第二种编码方法的码长变 化较小 比较接近于平均码长 l编法一的5个码字有4种不同的码长 而编法二的码字只有2种不同 的码长 显然 编法二的方法更简单 更容易实现 所以更好 结论 在哈夫曼编码过程中 对缩减信源符号按概率由大到小的顺序 重新排列时 应使合并后的新符号尽可能排在靠前的位置 这样可使 合并后的新符号重复编码次数减少 使短码得到充分利用 mm进制哈夫曼编码进制哈夫曼编码 全树 概念 定义 码树图中每个中间节点后续的枝数为m时称为全树 若有些 节点的后续枝数不足m 就称为非全树 二进制码不存在非全树的情况 因为后续枝数是一时 这个枝就
12、可 以去掉使码字长度缩短 对m进制编码 若所有码字构成全树 可分离的码字数 信源个数 必为 m k m 1 k为信源缩减次数 若信源所含的符号数n不能构成m进制全树 必须增加s个不用的码 字形成全树 显然s m 1 若s m 1 意味着某个中间节点之后 只有一个分枝 为了节约码长 这一分枝可以省略 2727 31 31 例 对前面的单符号离散无记忆信源编三进制哈夫曼码 这里 m 3 n 8 l 令k 3 m k m 1 9 则 s 9 n 9 8 1 l 所以第一次取m s 2个符号进行编码 2828 31 31 2929 31 31 l 平均码长为 l 信息率为 l 编码效率为 l 可见 哈夫曼的编码效率相当高 对编码器的要求也简单 得多 3030 31 31 小结小结 香农码 费诺码 哈夫曼码都考虑了信源的统计特性 使经常出现的信源符号对应较短的码字 使信源的平均 码长缩短 从而实现了对信源的压缩 香农码效率不是很高 费诺码比较适合于对分组概率相等或接近的信源编码 哈夫曼码对信源的统计特性没有特殊要求 编码效率比 较高 对编码设备的要求也比较简单 因此综合性能优 于香农码和费诺码 3131 31 31
