信息论与编码4----无失真编码.ppt

作业: pp.126 4.4 ; 4.7 ; 4.10 信息编码实践1 选题一. Huffman编码 对任意的符号序列（如abbccccdddddddddddddddd） 进行huffman编码，并给出编码效率。 选题二. Fano编码 对任意的符号序列（如aabbccccdddddddd）进行Fano 编码，并给出编码效率。 （2）有效的信源编码可使输出码元概率均匀化。 设单符号无失真定长编码的码字为 把编码器的输出看作一个新的信源，其取值符号表就是码元表X ={0,1} ，概率空间为 现在求X 的概率分布。 * 设平均每个码字所含码元“0”和“1”的个数为分别为 和 ，根据上面的等长码字可求得 码元/符号 码元/符号 于是 原信源7个符号的概率从 到 ，差别很大，编码之后所得的新信源2个符号的概率分别为0.6和0.4，差别缩小，概率得到一定程度的均匀。 * 再看霍夫曼编码， 码元/符号 码元/符号 于是 此时，码元的概率分布完全均匀化了。 * 霍夫曼编码过程中，由于码元分配的任意性，会造成码字不唯一。但平均码长是相同的，因而编码效率是相同的，看下例。 例 对如下DMS 进行2进制霍夫曼编码。 解 采用霍夫曼编码方法，会出现两种情况。 * 符号 概率 码字 码长 6 000000 0.005 6 000001 0.005 5 00001 0.04 4 0001 0.10 3 001 0.20 2 01 0.30 1 1 0.35 霍夫曼编码之一 1 1 1 1 1 1 0 0 0 0 0 0 1.00 0.01 0.05 0.15 0.35 0.65 * 符号 概率 码字 码长 5 00000 0.005 5 00001 0.005 4 0001 0.04 3 001 0.10 2 01 0.20 2 10 0.30 2 11 0.35 霍夫曼编码之二 1 1 1 1 1 1 0 0 0 0 0 0 1.00 0.01 0.05 0.15 0.35 0.65 * 分别求得平均码长为 码元/符号 和 码元/符号 两种情况下，码字不同，码长也不同，但平均码长是相同的，因此编码效率是相同的。 * 两种码的其它性能还是有差别的。在相同的编码效率下，我们希望得到码长变化小的码，于是引入码长的方差 ： 大，说明码长变化大。分别计算两种码的 ： 因此后者的码较好，其码长变化相对较小。 * * 霍夫曼编码的基本特点 编出的码是非续长码：霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树。 平均码长最小：霍夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。 码字不唯一：每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，码字不唯一。 r 进制霍夫曼编码 每次求缩减信源时，改为求r个最小概率之和，即将r个概率最小的符号缩减为一个新符号，直到概率之和为1终止。 为保证平均码长最小，希望缩减到最后刚好还剩下r个符号，为达到此目的，可给信源添加几个无用的符号，这些无用的符号概率为零，使得信源符号数q满足 其中 为信源缩减的次数。 * 例 四元Huffman码 补二项 符号 概率 码字 码长 0.00 3 001 0.04 3 002 0.08 2 01 0.16 2 02 0.1