1 i N , Ri 被称为量化间隔，且在每个区域内选择一个点作量化级数。这样落
在区域内的随机变量的所有值都被量化为第 i 个量化级数，用 X i 来表示，这就意 味着：
x Ri ( x) xi
显而易见，这类量化引入了失真，其均方误差为：
d i 1 ( x xi ) 2 f x( x)dx

这称为 Kraft 不等式。
q
i 1
r li 1
(8)
由上式可知，给定 r 和 q，只要允许码字长度可以足够长，则码长总可以满 足 Kraft 不等式而得到即时码，Kraft 不等式指出了即时码的码长必须满足的条 件。后来 McMillan 证明对于唯一可译码得码长也必须满足此不等式。在码长的 选择上唯一可译码并不比即时码有更宽松的条件。对于唯一可译码，该不等式又 称为 McMillan 不等式。 唯一可译码存在的充要条件是：
展信源进行编码， 当 N 趋向于无穷时， 平均码长可以趋进该极限值。 还可以证明， 如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平 均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多。 2.4 无失真编码算法 2.4.1 无失真信源编码定理 设单符号、离散、无记忆信源的熵为 H(S)，若用二进制码对其做变字长、非 续长编码，一定可以找到一种编码方式，其平均码长满足：

q
i 1
r li 1
(9)
其中 r 为码符号个数，为码字长度，q 为信源符号个数 无失真变长信源编码定理 离散无记忆信源 S 的 N 次扩展信源 S N ，其熵为 H (S N ) ，并且编码器的码元 符号集为 A : {a1 , a2 ,..., aq } 对信源 S N 进行编码，总可以找到一种编码方法，构成唯 一可译码，使信源 S 中每个符号 Si 所需要的平均码长满足
(11)
可见要提高传输效率，基本任务就是要改造信源，使其熵值最大化，此时η 趋于 1，而这个过程就是信源最佳化得过程。信源熵 H(X)最大化实质上就是寻求一种 最佳的概率分布。 根据熵函数的性质，在离散信源情况下，当各个符号间彼此独立而出现的概
率相等时，信源熵达到最大值。因此，一般的熵值最大化应当包括两个步骤： 1、符号独立化，解除符号间的相关性； 2、各符号概率均匀化。 为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。 设对信源 S 进行无失真编码所得到的平均码长为 L ,则 L H r ( S ) ,定义 H (s) r (12) L 为编码效率， 1 。我们可以采用声码器技术，模式识别技术，变换编码技术以 及相关编码技术等近几年来发展起来的效率较好的压缩信源方法来解除关联、压 缩信源和提高传输效率。经过解除相关性之后，如果再使各符号的概率均匀化， 就能进一步改造有剩余信源的输出，去掉冗余度，提高熵速率，使传输率接近信 道容量进而使传输效率接近 1。如香农-范诺编码，霍夫曼编码。这列编码的基本 思想就是使各符号的概率均匀化，即出现概率大的符号编成短码，出现概率较小 的符号编成长码，只是由于具体方法不同，得到的效果也不同。 2.7 二元霍夫曼编码规则 （1）将信源符号依出现概率递减顺序排序。 （2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信 源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果 得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用 s1 表示。 （3）将缩减信源 s1 的符号仍按概率从大到小顺序排列，重复步骤二，得到 只含（n-2）个符号的缩减信源 s2。 （4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号 的概率之和必为 1，然后从最后一级缩减信源开始，依编码路径向前返回，就得 到各信源符号所对应的码字。 2.8 多元霍夫曼编码规则 由二进制霍夫曼编码的方法很容易推广到 r 进制的情况，只是编码的过程中 构成缩减信源时，每次都是将 r 个概率最小的信源符号合并，然后分别用码符号 0,1，...,(r-1)表示。 为了充分利用短码，使霍夫曼码的平均码长最短，必须使最后一个缩减信源 恰好有 r 个信源符号，因此对于 r 元霍夫曼码，信源 S 符号个数 q 必须满足
H ( S ) LN H ( S ) 1 log(r ) N log(r ) N
当 N 时则有
(10)
LN qN H r(S ) ，λ 式中 L N i 1 P(Si )i ，其中 i 是扩展信源的 N
LN 是 N
信源符号 Si 所对应的码字长度， 因此是扩展信源中每个符号的平均码长， 而
N Ri
(2)
(3)
其中 f(x)是信源随机变量的概率密度函数。信号量化噪声比(SQNR)为：
E[ X 2 ] SQNR 10 log10 d
(4)
信源编码的主要目的是减少冗余，提高编码效率。信源编码可分为两类：无失真 编码和有失真编码。无失真编码只对信源冗余度进行压缩，不会改变信源的熵， 又称冗余度压缩编码，它可以保证码元序列经译码后能无失真的恢复成信源符号 序列，如 huffman 编码，香农编码。有失真编码在允许的失真范围内把编码后的 信息率压缩到最小，有失真信源编码的失真范围受限，所以又称为限失真信源编 码。 信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失 真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总希望把信 源所有的信息毫无保留的传递到接受端，即实现无失真传输，所以首先要对信源 实现无失真编码。 信源编码有以下三种主要方法： （1）匹配编码 根据信源符号的概率不同，编码的码长不同 ,这样使平均码长最短。将要讲 到的霍夫曼编码就是概率匹配编码。 （2）变换编码 先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换 后的信号进行编码。一般是把分布在时空域的信号（如时域的语音信号和平面空 间的图像信号原 来相关性很强的原始信号经过变换后，得到的变换域系数相互独立，并且能量集 中在少数低序系数上，这样只需对少量的变换域的系数进行编码，达到数据压缩 的目的。常用的变换编码有 DFT、沃尔什变换、小波变换等。 (3)识别编码 识别编码主要用于印刷或打字机等有标准形状的文字、符号和数据的编码， 比如中文文字和语音的识别。 变换编码和识别均为有失真的信源编码。 最原始的信源编码就是莫尔斯电码，另外还有 ASCII 码和电报码都是信源编 码。但现代通信应用中常见的信源编码方式有：霍夫曼编码、算术编码、L-Z 编 码，这三种都是无损编码。而霍夫曼编码作为变长码满足变长信源编码定理。该 编码定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编 码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯 一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩
H (S ) m H (S ) 1
(5)
不等式左边表明，信源的熵是作无失真二进制变字长编码平均码长的下限。 如果用符号等于其信息量得码长
mk lbp(ak )
编码，则可以使平均码长达到其下限——熵
m K 1 p (ak )mk k 1 p (a1 )lbp(ak ) H ( S )
信源 S 中单个信源符号所需的平均码长。这里要注意
LN 与 LN 的区别：它们都是 N
单个信源符号所需的码符号的平均数，但是
LN V 的含义是，为了得到这个平均 N
值，不是对单个信源符号进行编码，而是对 N 个信源符号序列进行编码，然后对 N 求平均。 该定理指出，要做到无失真信源编码，每个信源符号平均所需最少的 r 元码 元数就是信源的熵值。 若编码的平均码长小于信源的熵值， 则唯一可译码不存在， 在译码或反变换时必然要带来失真或差错，同时定理还指出，通过对扩展信源进 行变长编码，当 N 时，平均码长 L 可达到这个极限值。可见，信源的信息熵 H(S)是无失真信源编码码长的极限值，也可认为信源熵是表示每个信源符号平均 所需最少的码元符号数。 2.5 信源最佳化 通信系统的传输效率就是指给定信道的信道容量利用率，它表示信道的实际 传信率与信道容量的比值，可以写成： R C
编写 Matlab 函数实现哈夫曼编码的算法
一、 设计目的和意义
在通信的数字化过程中，对于连续的原始语音图像等模拟信号，如果要以数 字化的方式进行传输，在发送端必须进行模/数（A/D）转换，将原始信号转变为 离散的数字信号。模拟信号在数字化之后一般会导致传输信道带宽明显增加，这 样就会占用更多的信道资源，传输效率也会随之较低，有时甚至无法实现实时传 输。 为了提高传输效率，一方面需要采用压缩编码技术，在保证一定信号质量的 前提下，尽可能地去除信号中的冗余信息，从而减少信号速率和传输所用带宽。 另一方面，即使是原本就以数字形式存在的数据和文字信息，也同样存在一个需 要通过压缩编码降低信息冗余提高传输效率的问题。由于这些处理都是针对信源 发送信息所进行的，因此一般将其称为信源编码。 信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在 减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归 入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。作为现代数据无损 压缩的灵魂算法，霍夫曼编码广泛应用于各种图像、音频、视频及各种多媒体信 息的压缩环境中。 本次课程设计的意义在于使我们对我们使用 matlab 工具来实现通信系统的 模拟设计，同时也使我们明白信源在调制前做编码的重要性。
q (r 1) r
(13)
其中 表示信源缩减次数。如果不满足上式，则可以在最后增补一些概率为零的 信源符号，因此上式又可以写成
q i (r 1) r
(14)
i 为增加的信源符号数，并且是满足上式的最小正整数或 0。这样处理后得到的 r 元霍夫曼码可充分利用短码，一定是紧致码。 4.3 扩展信源霍夫曼编码 对离散无记忆信源的 N 次扩展信源进行编码便得到 N 次扩展码。 采用霍夫曼编码法能够使码的平均长度最短，信息的冗余量最小。然而这种编码 方法所形成的码字很不规整，这样不利于硬件的译码。在很多处理机中，我们采 用一种新的折中的方法，称为扩展编码法。这种方法是由定长编码与霍夫曼编码 法相结合形成的。 有等长扩展法和不等长扩展编码方法， 为了便于实现分级译码， 我们一般采用等长扩展编码法，当然，也可以根据具体需要采用每次扩展位数不 等的不等长扩展法。