信息论与编码2012

将每一分组再按同样原则划分，重复步骤2和3，直至概率 不再可分为止。
14
4.3 费诺编码
[例3.3.1] 设有一单符号离散信源

对该信源编二进制费诺码。编码过程如表3.3.1。
表 3.3.1 二进制费诺编码 信源符号 x1 x2 x3 x4 x5 x6 概率 0.32 0.22 0.18 0.16 0.08 0.04 1 0 0 1 0 0 1 1 0 1 编码 码字 00 01 10 110 1110 1111 码长 2 2 2 3 4 4
也不变，所以没有本质区别； 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编 码方法上来说，这几个符号的次序可任意排列，编出的码都是正 确的，但得到的码字不相同。不同的编法得到的码字长度ki也不 尽相同。
26
4.4.2 二进制哈夫曼编码
举例说明上述问题 例[3.4.2] 单符号离散无记忆信源 ，用 两种不同的方法对其编二进制哈夫曼码。 方法一：合并后的新符号排在其它相同概率符号的后面。
35
4.4.3 m进制哈夫曼编码
若信源所含的符号数n不能构成m进制全树，必须增加s个不用的码 字形成全树。显然s<m－1，若s=m－1，意味着某个中间节点之后 只有一个分枝，为了节约码长，这一分枝可以省略。
34
4.4.3 m进制哈夫曼编码
在编m进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减 信源有m个信源符号。非全树时，有s个码字不用： 第一次对最小概率符号分配码元时就只取(m－s)个，分别配以 0,1,…,m－s－1，把这些符号的概率相加作为一个新符号的概率， 与其它符号一起重新排列。 以后每次就可以取m个符号，分别配以0,1,…,m－1；…；如此 下去，直至所有概率相加得1为止，即得到各符号的m进制码字。
码字 00 01 100 101 1100 1101 1110 1111
码长 2 2 3 3 4 4 4 4
18
4.3 费诺编码

码树图如右图。


信源熵为 H(X)=2.75(比特/符号) 平均码长为 编码效率为η=1。之所以如此，因为每次所分两组的概率恰好相等。
19
4.4 哈夫曼编码
哈夫曼(Huffman)编码是一种效率比较高的变长 无失真信源编码方法。
10
4.2 香农编码
怎样把十进制数转换成二进制数
1）十进制整数转换成二进制整数 连续用该整数除以2，取余数，直到商等于0为止。再把得 到的各个余数按相反的顺序排列。——简称“除2取余法” 2） 十进制小数转换成二进制小数 连续用2乘以该小数，取乘积的整数部分，直到乘积的小数 部分为0或达到所需的精确度为止，然后把得到的各个整数 按原顺序排列。——简称为“乘2取整法”
信源编码的分类：离散信源编码、连续信源编 码和相关信源编码三类。
离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。
5
4.1 信源编码概述
有些编码原理和技术在通信原理和信号处理等相 关课程中介绍。例如：
连续信源编码：脉冲编码调制(PCM)、矢量量化技术； 相关信源编码： 预测编码：增量编码、差分脉冲调制(DPCM)、自 适应差分脉冲调制(ADPCM)、线性预测声码器； 变换编码：K－L变换、离散变换、子带编码、小波 变换。

在图中读取码字的时候，一定要从后向前读，此时编出来的码字才 是可分离的异前置码。若从前向后读取码字，则码字不可分离。
23
4.4.2 二进制哈夫曼编码

将图3.4.1左右颠倒过来重画一下，即可得到二进制哈夫曼码的码 树，如下图所示。
24
4.4.2 二进制哈夫曼编码

信源熵为

平均码长为

编码效率为
3） 既有整数，又有小数 整数、小数分别转换，再相加。 （25.75）10=（11001）2+（0.11）2 =11001.11
11
4.2 香农编码
计算出给定信源香农码的平均码长

若对上述信源采用等长编码，要做到无失真译码，每个符 号至少要用3个比特表示。相比较，香农编码对信源进行了 压缩。
12
4.2 香农编码

对该信源编二进制费诺码，编码过程如表3.3.2。
表 3.3.2 二进制费诺编码 编码 0 0 1 0 0 1 0 1 0 1 1 0 1 1
信源符号 x1 x2 x3 x4 x5 x6 x7 x8
概率 0.25 0.25 0.125 0.125 0.0625 0.0625 0.0625 0.0625
15
4.3 费诺编码
上述码字还可用码树来表示，如下图所示。
16
4.3 费诺编码

该信源的熵为

平均码长为

编码效率为

本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组 概率都很接近的信源。特别是对每次分组概率都相等的信源进行 编码时，可达到理想的编码效率。
17
4.3 费诺编码
[例3.3.2] 有一单符号离散无记忆信源

若采用定长编码，码长K=3，则编码效率

可见哈夫曼的编码效率提高了12.7%。
25
4.4.2 二进制哈夫曼编码
注意：哈夫曼的编法并不惟一。
每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意 的，所以可得到不同的码字。只要在各次缩减信源中保持码元分 配的一致性，即能得到可分离码字。
不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长
6
4.2 香农编码
设离散无记忆信源
二进制香农码的编码步骤如下： 将信源符号按概率从大到小的顺序排列，为方便起见， 令 p(x1)≥ p(x2)≥…≥ p(xn) 令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率， 则
7
4.2 香农编码

确定满足下列不等式的整数ki ，并令ki为第i个码字的 长度 －log2 p(xi)≤ki<1－ log2 p(xi) 将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi 的编码。

第一种方法编出的5个码字有4种不同的码长； 第二种方法编出的码长只有两种不同的码长； 显然，第二种编码方法更简单、更容易实现，所以更好。
结论：在哈夫曼编码过程中，对缩减信源符号按概率由大 到小的顺序重新排列时，应使合并后的新符号尽可能 排在靠前的位置，这样可使合并后的新符号重复编码 次数减少，使短码得到充分利用。
9
4.2 香农编码

ቤተ መጻሕፍቲ ባይዱ
十进制小数转换为二进制小数
十进制小数转换成二进制小数采用"乘2取整， 顺序排列"法。具体做法是：用2乘十进制小数， 可以得到积，将积的整数部分取出，再用2乘余 下的小数部分，又得到一个积，再将积的整数部 分取出，如此进行，直到积中的小数部分为零， 或者达到所要求的精度为止。 然后把取出的整 数部分按顺序排列起来，先取的整数作为二进制 小数的高位有效位，后取的整数作为低位有效位。
8
4.2 香农编码
[例3.2.1]有一单符号离散无记忆信源

对该信源编二进制香农码。其编码过程如表3.2.1所示。
表 3.2.1 二进制香农编码 xi x1 x2 x3 x4 x5 x6 p(xi) 0.25 0.25 0.20 0.15 0.10 0.05 pa(xj) 0.000 0.250 0.500 0.700 0.850 0.950 ki 2 2 3 3 4 5 码字 00(0.000)2 01(0.010)2 100(0.100)2 101(0.101)2 1101(0.1101)2 11110(0.11110)2
33
4.4.3 m进制哈夫曼编码
(1) “全树”概念
定义：码树图中每个中间节点后续的枝数为m时称为全树；若有些 节点的后续枝数不足m，就称为非全树。 二进制码不存在非全树的情况，因为后续枝数是一时，这个枝就 可以去掉使码字长度缩短。
对m进制编码：若所有码字构成全树，可分离的码字数（信源个数） 必为 m+k(m－1)。k为信源缩减次数。
Stay hungry， Stay foolish
-Steve Jobs
第四章 信源编码
4.1 信源编码续 4.2 香农编码 4.3 费诺编码 4.4 哈夫曼编码 4.5 游程编码 4.6 算术编码 4.7 冗余编码 4.8 LZ编码 4.9 信源编码总结
2
4.1 编码的目的
香农编码定理虽然指出了理想编码器的存在性,但是并 没有给出实用码的结构及构造方法； 编码理论正是为了解决这一问题而发展起来的科学理论； 编码的目的是为了优化通信系统，就是使这些指标达到 最佳； 通信系统的性能指标主要是有效性、可靠性、安全性和 经济性，除了经济性外，这些指标正是信息论研究的对 象。 按不同的编码目的，编码分为三类：信源编码、信道编 码和安全编码/密码。
3
4.1 编码的目的
信源编码：以提高通信有效性为目的的编码。通常通过压
缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的 平均比特数或信源的码率。即同样多的信息用较少的码率传送， 使单位时间内传送的平均信息量增加，从而提高通信的有效性。
信道编码：以提高信息传输的可靠性为目的的编码。通常
通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。 与信源编码正好相反。
27
4.4.2 二进制哈夫曼编码
0 0 0 1 0 x1 1 x2 0 1 x5 x3 0 x4
图5.4.4 例5.4.2的二进制哈夫曼码树(编法一)
28
4.4.2 二进制哈夫曼编码
方法二：合并后的新符号排在其它相同概率符号的前面。
29
4.4.2 二进制哈夫曼编码