首先是误差扩散问题，由于哈夫曼码 是一类无失真信源最佳变长码，这就是说 在研究这类无失真信源编码时认为信道传 输是理想的，是不产生差错的，然而实际 信道中总是存在噪声的，噪声引入后必然 要破坏变长码的结构。同时由于变长码是 不加同步的码，无法自动清洗所产生的影 响，所以必然要产生误差的扩散，这就是 说噪声所影响的不仅是被干扰的码元，而 是一直要扩散下去影响后面的一系列码元。
H(U)≤R＜H(U)+ε
其中ε为任意正数。
5.1.3 最佳变长编码
—哈夫曼编码
1952年，哈夫曼给出一种编码方法， 所得的码字是异前置的变长码，其平均码 长最短，称它为最佳变长码，又称哈夫曼 码。 1956 年，戈罗伯对它进行了改进，使 之更便于实用。
其具体编码方法如下：
(1) 将信源消息(符号)按概率大小
第3个问题是与信源统计特性相匹配的 问题。变长码本身就是与信源统计特性相 匹配的无失真信源编码，因此信源统计特 性的变化对变长码影响很大，它主要体现 在下面两点。 (1) 与信源消息种类多少的关系：一般 变长码更适合于大的消息集，而不大适合 小且概率分布相差很大的集合。小消息集 只有在很特殊情况下才能实现统计匹配。
很多学者深入地研究了离散、随机序 列信源的统计特性，仙农 (1948) 首先发现， 后来麦克米伦(1953)和沃尔夫兹(1961)进一 步严格证明，这类信源具有渐近等同分割 性 ， 或 简 称 为 A.E.P(Asymptotic Equipatition Property)。它的基本思想是， 一个总数为 nL 种的消息序列信源随着消息 序列长度 L 的增长且足够大时，越来越明 显产生两极分化现象。
第5章 信 源 编 码
5.1 无失真信源编码 *5.2 限失真信源编码定理 *5.3 矢量量化编码 5.4 预 测 编 码 5.5 变 换 编 码 5.6 传 真 编 码 5.7 语音压缩编码 5.8 图 像 编 码
5.1 无失真信源编码
离散信源的无失真编码实质上是 一种统计匹配编码。信息论指出信源中 的统计多余度主要决定于以下两个主要 因素：一是消息概率分布的非均匀性， 另一个是消息间的相关性。对无记忆信 源主要决定于概率分布的非均匀性，但 是，对于有记忆信源，两者都起作用， 且后者相关性更加重要。
一、 码树与码字(组)可分Fra bibliotek条件这里，引入较直观的“码树”的概念， 并仍结合表 5-1-1 中的码字 ( 组 ) 来进一步解 释和说明。 码树是图论中的一个分支，又称为树 图。码树编码法是将编码方法形象化为一 棵生成的树。树有树根、树枝、节点、端 点、节数，并有满树与非满树之分。
从图5-1-1上看，要构造出在接收端可 分离的变长码，只要满足被选用的码字必 须为异前置码。在比较简单的信源，我们 可以很方便地用这种码树的方法直接且直 观地构造可分离码，但是，一当信源较复 杂比如信源含有很多消息 ( 符号 ) ，直接画 码树就比较复杂。
以至在低信噪比下无法正常工作。目 前对这类误差扩散还没有特别有效的克服 方法，在工程上一般哈夫曼码只能适合于 高信噪比的优质信道，比如误码率低于10-6 以下，以减小误差扩散所带来的影响。同 时工程上还常常采用定期清洗，比如在文 件和报纸传真中就采用按行清洗的方式， 以牺牲编码效率来达到限制误差扩散的目 的。另一种方法是加检错纠错码。
顺序排队；
(2) 从最小概率的两个消息开始
编码，并给予一定的编码规则，如小
概率的下支路编为 1( 或 0) ，大概率的
上支路编为 0( 或 1) ，若两者概率相等，
仍是下支路为1上支路为0；
(3) 将已编码的两个消息对应概率合并， 并重新按概率大小排队，重复步骤(2)； (4) 重复步骤 (3) ，直至合并概率归一 时为止； (5) 编成的变长码是按后出先编方式， 即从概率归一的树根沿编码路线逆行至对 应的消息，如u3为“110”。
统计匹配编码是根据信源的不同概率 分布而选用与之相匹配的编码，以达到在 系统中传信速率最小，且满足在信宿复制 时无失真或低于某一允许的失真限定值。 下面，我们首先研究这类离散、无失 真、无记忆信源编码的一般模型，并研究 在它基础上应如何编码，从而引出定长和 变长两类编码方法。
5.1.1 等长编码定理
二、 变长编码定理
有了上述讨论的基础，我们下面给 出指导构造变长码的不同类型信源的信 源编码定理。它给出了变长码的平均码 长应该满足的条件。 首先讨论单个消息 ( 符号 ) 信源的变 长编码定理，它是最简单也是最基本的 变长编码定理。
定理5-1-4 ：对于平均消息 (符号 )熵为 H(U)的离散、平稳、无记忆信源，必存在 一种无失真编码方法，使平均每个消息(符 号)的信息率R
其次是速率匹配问题，由于绝大多数 信源其消息是不等概率的，因而编成的变 长码长度也是不相等的，这必然导致信源 输出速率是变化的，然而在实际信道中传 送的信息率是固定不变化的。这就是说信 源给出的是变速的，而信道传送的则是恒 速的，因而信源与信道之间必然存在一个 速率匹配问题。
解决这一矛盾的办法，在工程上一般 是采用缓冲存储器的方法。这个缓存器起 到类似于水库的作用，变速输入、恒速输 出。但是这个缓存器的容量的选取显然与 输入变速特性即信源统计特性和编码方法， 以及输出速率密切相关。容量选大了浪费 设备，容量选小了则可能产生由于输入大 于输出且容量不够而出现溢出现象，或输 入小于输出而出现取空现象。这是一个需 要在实际的工程设计中进一步深入探讨的 问题。
可见，在差错率Pe和编码效率要求 并不十分苛刻的条件下，对这一简单信 源就需要近一百万个信源符号进行联合 编码，这显然是不现实的。因此，为了 解决这一个问题，人们就很自然地转向
于对变长编码的研究。
5.1.2 变长编码定理
等长编码需要取很大数量的符号一起 编码，显然不现实，倘若采用变长编码， 情况就大不一样了。若仍用上述最简单的 离散信源的例子，作变长编码如下，至于 具体编码方法后面将进一步讨论。 可见，若采用上述变长码，即使采用 逐位编码 ( L=1) 效率可达 100% ，这里虽然 是一个特例，不过一般情况下效率都可达 到很高。显然它大大优于等长编码。