编码理论第5章.ppt

《编码理论第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章无失真信源编码方法5.1霍夫曼码5.2香农编码5.3费诺编码5.4算术编码编码原理5.5算术编码方法第5章信源压缩编码方法5.1无失真信源编码方法5.1.1霍夫曼码1.二元霍夫曼码二元霍夫曼码编码步骤如下：(1)将n元信源U的各个符号按概率分布以递减次序排列起来。(2)将两个概率最小的信源符号合并成一个新符号，新符号的值为两个信源符号值的和，从而得到只包含n－1个符号的新信源，称为U信源的缩减信源U1。(3)把缩减信源U1的符号仍按概率大小以递减次序排列，然后将其中两个概率最小的符号合并成一个符号，这样又形成了n－2个符号的

2、缩减信源U2。(4)依次继续下去，直至信源最后只剩下１个符号为止。(5)将每次合并的两个信源符号分别用0和1码符号表示。(6)从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得各信源符号对应的码字。1001图5-1例5-1霍夫曼编码01［例5-1］离散无记忆信源解：对应霍夫曼编码如图5-1所示信源熵:平均码长：编码效率：[例5-2]离散无记忆信源给出两种霍夫曼编码如图5-2所示信源熵:平均码长编码效率00001111(a)图5-2例5-2两种霍夫曼编码00001111图5-2例5-2两种霍夫曼编码(b)方法

3、（a）的方差比方法（b）的方差要小许多。方法(a）的具体编码原则是，把合并后的概率总是放在其它相同概率的信源符号之上（或之左），方法（b）的编码原则是，把合并后的概率放在其它相同概率的信源符号之下（或之右），从上面的分析可以看出，方法（a）要优于方法（b）。可见，霍夫曼码得到的码并非是唯一的。因为对缩减信源的两个概率最小的符号，用0和1码时可以任意的，所以可得到不同的码，但它们只是码字具体结构不同，而其码长不变，平均码长也不变，所以没有本质区别。另外，若当缩减信源中缩减合并后的符号的概率与其它信源符号概率相同时，从编码方法上来说，

4、对等概率的符号那个放在上面，那个放在下面是没有区别的，但得到的码是不同的。对这两种不同的码，它们的码长各不同，然而平均码长是相同的。在编码中，对等概率消息，若将新合并的消息排列到上支路，可以证明它将缩短码长的方差，即编出的码更接近等长码；同时可使合并的元素重复编码次数减少，使短码得到充分利用。2.m元霍夫曼码为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此对于m元编码，信源U符号个数n必须满足：n＝（m－1）Q＋m（5-1）式中：n—信源符号个数；m—码元数；Q—缩减次数。对于m元码，n为任意正

5、整数时不一定能找到一个Q满足式（5-1），此时，可以人为地增加一些概率为零的符号，以满足式（5-1）。m元霍夫曼编码步骤：(1)验证所给n是否满足式（5-1），若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号；(2)取概率最小的m个符号合并成一个新结点，并分别用0，1，．．．，（m－１）给各分支赋值,把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复（2），如此下去直至树根。(4)取树根到叶子（信源符号对应结点）的各树枝上的赋值，得到各符号码字[例5-3]已知信源求其三元霍夫曼

6、编码及四元霍夫曼编码。解：为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此对于m元编码，信源U符号个数n必须满足：n＝（m－1）Q＋m其三元霍夫曼编码此式成立，四元霍夫曼编码需加2个概率为零的符号。根据m元霍夫曼编码步骤，其三元霍夫曼编码如图5-4所示，四元霍夫曼编码如图（5-5）所示。图5-4三元霍夫曼编码121002图5-5四元霍夫曼编码313210025.2香农编码二元香农码的编码步骤(1)将信源发出n个消息（符号）按其概率递减次序依次排列。(2)为了编成惟一可译码，首先计算第i个信源符号

7、的累加概率(5-2)(3)将累加概率变换成二进制数。(4)取小数点后位数作为第i个信源符号的码字。由下式确定。(5-3)式中：－取大于或等于X的最小整数。[例5-4]已知求：香农编码。解：计算第i个信源符号的码字。设i=4，首先求第4个信源符号的二元码字长再计算累加概率将累加概率变换成二进制数故变换成二进制数为0.100…，根据码长取小数点后三位100,作为第4个信源符号的码字。信源符号概率累加概率码字长度二元码字0.200.002.3430000.190.202.4130010.180.392.4830110.170.572.5

8、631000.150.742.7431010.100.893.34411100.010.996.6671111110其它信源符号的二元码字可用同样方法求得，如表5-1所示。由表5-1可以看出，一共有5个三位的码字，各码字之间至少有一位数字不相同，故