◆具体的编码步骤如下: (1)将信源符号出现的概率按由大到小的顺序排序。 (2)将两处最小的概率进行组合相加,形成一个新的概率 (3)将新出现的概率与未编码的字符一起重新排序。 (4)重复步骤(2)、(3),直到出现的概率和为1。 (5)分配代码。代码分配从最后一步开始反向进行,对最后两个概率一个赋 予0代码,一个赋予1代码。如此反向进行到开始的概率排列。在此过程中,若 概率不变则采用原代码
具体的编码步骤如下： （1）将信源符号出现的概率按由大到小的顺序排序。 （2）将两处最小的概率进行组合相加，形成一个新的概率。 （3）将新出现的概率与未编码的字符一起重新排序。 （4）重复步骤（2）、（3），直到出现的概率和为1。 （5）分配代码。代码分配从最后一步开始反向进行，对最后两个概率一个赋 予0代码，一个赋予1代码。如此反向进行到开始的概率排列。在此过程中，若 概率不变则采用原代码
◆例4-1:设输入图像的灰度级{a1a2,a3a4,a5,a6}出现的概率分别是 0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼编码,并计算编码 效率、压缩比、冗余度 04 0 编码步骤 0 (1)初始化,根据符号概率的大小按由大到小 顺序对符号进行排序,如图4-2所示。 a40.151 2)把概率小的两个符号组成一个节点,如图 a30.12 4-2中的a5、a6组成节点P1 (3)重复步骤2,得到节点P2、P3、P4、P5,形a501 成一棵“树”其中P5为根节点人 P 点P5 每个符号的“树 0.03-1 叶”,从上到下标上1(上枝)或者0(下枝),至 于哪个为1哪个为0则无关紧要,最后的结果仅仅是 分配的代码不同,而代码的平均长度是相同的。 最终编码结果为:a1=1, a2=000 a3=011, a4=001,a5=0100,a6=0101
例4-1：设输入图像的灰度级{a1,a2,a3,a4,a5,a6}出现的概率分别是 0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼编码，并计算编码 效率、压缩比、冗余度。 a1 a6 a5 a3 a4 a2 0.4 0.2 0.03 0.1 0.12 0.15 1 1 0 1 0 0 0 1 0 P1 P2 1 P3 P4 P5 编码步骤： （1）初始化，根据符号概率的大小按由大到小 顺序对符号进行排序，如图4-2所示。 （2）把概率小的两个符号组成一个节点，如图 4-2中的a5、a6组成节点P1。 （3）重复步骤2，得到节点P2、P3、P4、P5，形 成一棵“树”，其中P5为根节点。 （4）从根节点P5开始到相应于每个符号的“树 叶”，从上到下标上1（上枝）或者0（下枝），至 于哪个为1哪个为0则无关紧要，最后的结果仅仅是 分配的代码不同，而代码的平均长度是相同的。 最终编码结果为：a1 =1, a2 =000 , a3 =011, a4 =001, a5 =0100, a6 =0101
由公式(46)可求得图像信源熵是: H(X=∑P(x)lg2P(x1 (0.4×log20.4+0.2×0g20.2+0.12×log20.12+ 0.15×|og20.15+0.1×log20.1+0.03×l0g20.03) =2.25bit 根据哈夫曼编码过程图给出的结果,由公式(4-7)可求出它的平均码 长度: Lc=0.4×1+0.2×3+0.15×3+0.12×3+0.1×4+0.03×4=2.33 由公式(4-9)得编码效率为: 2.25 96.6% L.2.33 压缩之前8个符号需要3个比特量化,经过压缩之后的平均码字长度为233, 由公式(4-10)得其压缩比为: 1.2 2.33 由公式(4-8)得冗余度为 r=1-n=3.4%
由公式（4-6）可求得图像信源熵是： H(X)= =-（0.4×log20.4+0.2×log20.2+0.12×log20.12+ 0.15×log20.15+0.1×log20.1+0.03×log20.03） =2.25 bit = − n j j j P x P x 1 2 ( ) log ( ) 根据哈夫曼编码过程图给出的结果，由公式（4-7）可求出它的平均码 字长度： Lc=0.4×1+0.2×3+0.15×3+0.12×3+0.1×4+0.03×4 =2.33 由公式（4-9）得编码效率为： 96.6% 2.33 2.25 L H c = = = 压缩之前8个符号需要3个比特量化，经过压缩之后的平均码字长度为2.33， 由公式（4-10）得其压缩比为： 1.2 2.33 3 C = = 由公式（4-8）得冗余度为： r = 1-η = 3.4%
采用哈夫曼编码时有两个问题值得注意: 1)哈夫曼编码没有错误保护功能,在译码时,如果码 串中没有错误,那么就能一个接一个的正确译出代码。但 如果码串中有错误,哪怕仅是1位出现错误,不但这个码 本身译错,更糟糕的是后面的译码可能全错,这种现象称 为错误传播 ( Error propagation) (2)哈夫曼编码是可变长度码,因此很难随意査找或调 用压缩文件中间的内容,然后再译码,这就需要在存储代 码之前加以考虑
采用哈夫曼编码时有两个问题值得注意： （1）哈夫曼编码没有错误保护功能，在译码时，如果码 串中没有错误，那么就能一个接一个的正确译出代码。但 如果码串中有错误，哪怕仅是1位出现错误，不但这个码 本身译错，更糟糕的是后面的译码可能全错，这种现象称 为错误传播（Error Propagation）。 （2）哈夫曼编码是可变长度码，因此很难随意查找或调 用压缩文件中间的内容，然后再译码，这就需要在存储代 码之前加以考虑
2.算术编码 ◆算术编码( arithmetic coding ac)是利用0和1之间的间隔来表示信源编 碑的一种方法,其编码值是间隔的上、下限包含的相同二进制。编码过程 中的间隔决定了符号压缩后的输出 算术编码用到两个基本的参数:符号的概率和它的编码间隔 信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔, 而这些间隔包含在0到1之间 ◆算术编码器的编码过程可用例42加以解释
2．算术编码 算术编码（arithmetic coding AC）是利用0和1之间的间隔来表示信源编 码的一种方法，其编码值是间隔的上、下限包含的相同二进制。编码过程 中的间隔决定了符号压缩后的输出。 算术编码用到两个基本的参数：符号的概率和它的编码间隔。 信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔， 而这些间隔包含在0到1之间。 算术编码器的编码过程可用例4-2加以解释