信息论与编码第5章信源编码技术

第5章信源编码技术5.1最佳变长编码回顾：1、根据信源编码理论，将能够荷载一定信息量，且码字的平均长度最短，可分离的变长码字集合称为最佳变长码。2、最佳变长码编码的基本原则是：概率大的信源符号分配短的码字，而概率小的信源符号分配长码字，从而使得平均码长最短。具有代表性变长编码方法有：香农码，费诺码和哈夫曼码等。5.1.1香农码香农码的根据：离散无记忆信源的自信息量设离散无记忆信源所对应的概率空间为对应码字的长度Li应该满足下列关系这样就可以保证对于每个信源符号而言，码字长度是最佳的。符号自信息量香农码编码方法

(1)将信源消息符号按其出现的概率大小依次排列为(2)确定每个信源符号的码长，同时保证码长为满足下列不等式的整数(3)为了编成唯一可译码，计算第i个消息的累加概率

(4)将累加概率Pi表示为二进制形式；(5)取二进制数的小数点后li位作为该消息符号的二进制码字。总结：1、由于每个信源符号码长是根据信源符号的信息量选择，从局部来看每个码长的取值都是最佳的。所以从局部看，香农码是最佳码。但是香农码构造码字时没有综合使用信源统计特性，所以码长并非最短的。2、香农码编码采用累计概率小数部分的二进制表示作为码字，从而保证了码字是唯一可译码的。

5.1.2费诺码费诺码的基本思想：1、按照累加概率尽可能相等的原则对信源符号进行分组：对于二元码，则每次分为两组;对于d元码，则每次分为d个组。并且给不同的组分配一个不同的码元符号。2、对其中的每组按照累计概率尽可能相等的原则再次进行分组，并指定码元符号，直到不能再分类为止。3、然后将每个符号指定的码元符号排列起来就得到相应的码字。费诺二元码的编码步骤

1、将源消息符号按概率大小排序：2、将依次排列的信源符号分为两大组，使每组的概率和尽可能相等，且每组赋与二进制码元“0”和“1”。3、将每一大组的信源符号再分为两组，使每组的概率和尽可能相等，且每组赋与二进制码元“0”和“1”。4、如此重复，直至每组只剩下一个符号。信源符号所对应的码字即费诺码。例5.2对例5.1的信源进行费诺编码,，具体编码过程参见表5.2根据每个信源符号的码长，得到每个符号的平均码长为码元/符号010000011111000100111011011101111用树码表示的费诺码编码过程总结：1、费诺码要比上述香农码的平均码长小，编码效率高。2、从上面的例子可以看出，p(a4)<p(a2)，而码长L4<L2，从统计角度来看，平均码长一定不是最短的;

如果将两个符号对应的码字互换，这样编码得到的平均码长肯定小于原来的平均码长。3、费诺码的平均码长满足编码效率为费诺码的最佳性1、保证每个集合概率和近似相等，保证d个码元近似等概率，每个码字承载的信息量最大，码长近似最短。2、是次最佳的编码方法，只在当信源符号概率满足：时达最佳。012012012012a1a2a3a4a5a6a7a8a9p(a1)=3-1p(a2)=p(a3)=p(a4)=3-2p(a7)=p(a8)=p(a9)=3-3满足Kraft不等式取1，此时费诺码最佳。信源符号概率5.1.3哈夫曼码基本思想：1、概率大的符号分配短码字，而概率小的信源符号分配长码字2、首先为小概率符号分配码元3、分配码元后的符号进行概率合并4、然后按照大小顺序重排概率，并对概率小的符号或者符号集合分配码元，直到概率合并结束为止。5、然后逆向搜索参与概率合并时分配的码元符号，形成对应的码字。Huffman码的最佳性最佳性：所有可能的编码方法中，平均码长最短。定理1对于给定的信源，有最佳唯一可译二元码，其最小概率的两个码字Ck-1和Ck的长度最长并且相等①，它们之间仅最后一位码元的取值不同②（一个为0、一个为1）。关于含义①：对于符号a1,a2，码长分别为n1,n2如果p(a1)>p(a2),那么当n1<n2时，平均常常最短。假如n1<n2，则有n2p(a1)+n1p(a2)>n1p(a1)+n2p(a2)所以，定理的第①部分成立。关于含义②：二元Huffman码不可能出现单分支。对信源且假定对aK-1和aK的码字最后一位分别指定0、1，然后合并，产生辅助符号a’k-1,做一辅助集排序后ak-1ak-1‘

ak01对剩下的符号重复合并最小概率符号，分配码元0、1，到最后对两个符号重复上述操作，编码完成。定理2编码对辅助集最佳，对原始集也最佳。（平均码长最短）原始集平均码长辅助集平均码长合并一次二元码的哈夫曼编码步骤

(1)将信源消息符号按其出现的概率大小依次排列为(2)取两个概率最小的两个信源符号分别分配码元0和1，并将这两个概率相加作为一个新符号的概率，与未分配的二进符号的符号一起重新进行概率排序。(3)对重排后的两个概率最小符号重复步骤（2）的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，反向搜索参与编码的符号，得到各个信源符号所对应的码元序列，即相应的码字。例5.3对例5.1的信源符号进行哈夫曼编码，给出编码过程，每个信源符号的码字，码长，求平均码长、编码效率。信源符号概率0.110.150.170.180.190.200.260.200.190.180.170.350.260.200.190.390.610000011111101021120003001301030110401114码字码长li0.350.260.391.0哈夫曼编码过程平均码长编码效率关于哈夫曼编码的讨论1、每次对信源缩减时，赋予信源最后两个概率最小的符号，分配码元0和1是可以任意的，即大概率符号或者合并后的符号集合可以分配码元0也可以是1，这种选择任意性可以得到不同的哈夫曼码，但不会影响码字的长度。2、对信源进行缩减时，如果两个概率最小的符号合并后的概率与其它信源符号的概率相同,应当放在上面，以便减少更多符号分配更长码的可能。例5.4设有离散无记忆信源的概率空间为方法1方法2合并后的概率尽量往上根据两种方法的编码结果，计算两种哈夫曼码的平均码长，相等，即

码元/符号编码效率也相等，都为两种码的质量不完全相同，用码方差衡量，即

，由于方法2的码方差比方法1的码方差小许多，所以方法2编码质量好。哈夫曼码的主要特点1、哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；2、缩减信源的两个码字的最后一位总是不同，可以保证构造的码字为即时码。3、哈夫曼码的效率是相当高的，既可以使用单个信源符号编码，也可以对信源序列编码。4、要得到更高的编码效率，可以使用较长的序列进行编码。算术编码适用于JPEG2000,H.263等图像压缩标准。特点：1、随着序列的输入，就可对序列进行编码2、平均符号码长满足3、需要知道信源符号的概率是对shanno-Fanno-Elias编码的改进。（最佳编码）累计分布函数的定义设信源输出累计分布函数定义为算术编码是累计函数的二进制表示加截短。算术编码的定义算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码。例如，对输出的二元序列01110进行编码，将[0,1)区间分为25=32个区段，每个序列对应一个区段，这个区段的每个数值可用来表示这个序列，一般用区段的最左边的值来表示序列。算术编码对于长为n的符号序列序列个数共有个(若每个符号可取2个值，比如0,1)分别是对应概率序列k的累计分布函数累计分布函数的计算递推公式：已输入序列：当前输入符号算术编码将[0,1)分割成小区间，如长为n的二元序列，分为2n个区间，用区间[F(u),F(u)+p(u)）表示序列u,实际取F(u)。将F(u)截短，截断长度为每个区间的宽度等于序列的概率。序列u的自信息量算术码的截短规则假如累计函数表示为只要第L位后面的小数不为0，就要向第L位进位，进位后得数值C。例5.7离散无记忆信源X的概率空间为信源输出符号序列，描述算术编码过程。解：首先计算条件累计概率令，然后编码。（1）对第一个符号进行编码，得到（2）对第二个符号进行编码，得到（3）对第三个符号进行编码，得到（4）对四个符号进行编码，得到将用位二进制表示将小数点后8位作为码字输出，得编码图算术码译码去掉累计概率P2，码字,得符号放大到[0,1),去掉累计概率P3，去掉累计概率P1，放大到[0,1),放大到[0,1),,得符号,得符号,得符号算术编码的特点1、能够任意扩展序列长度，而又不重复构造码表，然后再进行编码，算术编码能够实现这样的编码要求。2、平均符号码长满足并且唯一可译，因此最佳。5.2编码的实现上面介绍了几种变长编码方法，相对于等长编码，变长码可以有效提高编码效率。即使采用长度较短的扩展信源进行编码，也能够取得好的编码效果，这是因为变长码利用了信源统计冗余指导编码的结果。实际上，上述的几种变长编码只是产生编码使用的码表，并不是真正意义上的编码实现。信源编码目的是为了更有效地传输信息，即提高通信系统的有效性。为了实现信息传输，信源编码产生的码流传输到信宿之前应当首先进行译码，以便按照先后顺序再现或者重现信源发送的消息符号。对于译码器而言，必须知道信源编码使用的码表和每个码字对应的长度等相关信息，才能够实现正确译码，以便重建信源发送的消息符号序列。信源变长码编码原理框图具体步骤如下：分析给定信源统计特性，得到信源统计规律。对于离散无记忆信源，得到各个符号的概率分布；对于记忆信源，则得到序列的联合概率分布。根据统计特性，码表产生器进行编码，得到每个信源符号或者符号序列对应的码字和码长，即产生码表。对于离散无记忆信源，每个符号都对应一个码字并有一个码长；而对于记忆信源，每个序列对应一个码字和码长。

将序列符号、序列长度、码字及码长等信息按照约定规则经过信道传输给译码器，译码器才能够根据这些信息进行正确译码。信源编码器根据码表产生器产生的码表，对给定信源输出符号序列按照先后顺序进行编码，产生码流（码字序列），并经过信道将码流传输给译码器。信源译码器根据接收到的序列符号、序列长度、码字和码长，对接收到的码流进行译码，再现或者重建信源发送的消息。实际应用中，信源编码使用的码表是根据一类信源的统计特性事先产生的，通过对大量同类信源的分布特性进行分析，在此基础上根据统计得到的分布特性产生码表。对于编码、译码器而言，辅助信息是编译码双方约定的，这些辅助信息不需要再经过信道传输，这样编码器不需要分析信源统计特性，也无需产生和传输码表，从而减轻了编码复杂度采用算法约定码表对给定信源进行编码，这就意味着编码建立码表对应的概率统计特性与给定信源的概率统计特性并不相同，这样就可能会导致编码效率下降。下面对实际信源编码进行分析。不失一般性，首先讨论离散无记忆信源情况。假设码表产生使用的编码概率空间（也称为码表概率空间）为每个消息符号对应码字的长度为li.对于给定的离散无记忆信源，实际的概率空间为如果采用码表概率空间编码，那么信源编码的实际平均码长只有当两种统计特性相近时，采用约定码表进行编码是一种有效的编码方法。反之，如果两种信源统计模型相差甚远，则实际编码的平均码长与理论值相差甚远，此时编码冗余度就会增加，编码效率下降。此外，信源编码的模型与实际的信源模型是否相符，也是影响编码效率的因素之一。如果实际信源模型与编码采用的模型不一致，实际编码的效率也会下降，比如，如果有记忆信源的记忆长度与实际给定信源的长度不一样，则编码效率就会下降。但是在实际应用中，首先需要考虑的是系统编码复杂度，如果实际模型特别复杂，难以实现；而如果采用相对较简单的模型也能够取得好的效果，则就可以简化系统模型，得到有意义的结果。尽管上述讨论是针对平稳离散信源进行的无失真编码，但是得到的结论可以推广到非平稳信源，包括马尔可夫信源等。此外，该结论也适合限失真编码，当统计特性不相符时，限失真编码的信息率失真曲线会向右边移动，在给定码率的情况下，编码产生的失真会增加。由于信源输出符号长度是有限的，而且许多信源是非平稳性、关联性长度也各有差异，直接对数据进行编码并取得好的编码效果十分困难。为了减少这些因素的影响，得到简单的信源模型和统计规律，信源编码大多在变换域进行，而且实际信源编码大多采用混合编码算法以提高编码效率。5.3编码方法简介前面阐述了无失真编码使用的变长编码方法，共同点在于都是采用组码对信源进行编码。对于信源符号数量较少的无记忆信源编码而言，组码是一种简单有效的编码方法，此时可以直接传输码表，当信源输出的长度足够大时，码表的附加信息可以不加考虑。为了提高编码效率，应当对信源进行扩展，使用序列进行编码，而随着序列长度的增加，序列种类也就增加，系统编码复杂度也相应增加。而且使用扩展信源进行编码，效率的提高也是有限的，对记忆信源更是如此。在实际应用中，信源类型众多，统计特性各不相同，特别是大多数信源并不是离散无记忆的、许多信源甚至是非平稳的，而且信源输出的长度也是有限的，所以使用的编码方法需要根据信源的具体特点而设计或者选择。在信源编码理论的指导下，先后出现了许多性能优良的编码方法，这里简单介绍常用编码算法的基本原理。5.3.1游程编码游程编码是经常使用的编码方法之一，当信源出现连续相同符号，或者连续出现的符号在允许失真范围内时，游程编码是一种有效的描述方法。游程编码是利用先后符号之间的关联性进行编码，从而提高编码效率。游程编码实际上是一种特殊的序列编码方式，利用了符号（或者是数据）之间的相关性进行编码，从而减少了数据描述长度，提高了编码效率。但是一般情况下，并不单独使用游程编码对数据进行压缩，总是将其作为整体编码算法中的一种编码单元加以使用。游程编码算法在图像压缩中得到广泛应用，连续色调静态图像压缩标准JPEG-LS中就采用了这种游程编码算法，以提高数据压缩效率。游程编码有二进制和非二进制之分，取决于具体编码要求。对于二进制编码，就是统计连续0或者1的个数。由于其特殊性，游程编码可以不输出再现符号，数据长度的交替就是符号0和1之间的交替，这样只需要约定或者在开始时给出再现符号即可。二进制游程编码在信源编码中得到广泛应用，但是经常使用的是上述算法的改进算法。如果信源输出的二进制符号中，符号0的数量很多，而且连续出现的概率也很大，游程编码算法就可以简化。比如，首先约定二进制序列的长度N，如果连续个二进制符号都为0，则输出0；否则输出1，并对序列符号进一步处理。许多实际应用中取N=4，下面以此为例介绍游程编码算法。5.3.2算术编码从信源编码角度来看，非常希望设计一种有效编码算法对信源符号进行扩展，从而构成尽可能长的序列。尽管哈夫曼编码是一种有效的编码算法，但并不满足这种要求，因为它采用自下而上的编码方法，要求计算特定长度的所有信源序列的概率，并且构造完整的码表。

理想编码方法是：能够任意扩展序列长度，而又不重复构造码表，然后再进行编码，算术编码能够实现这样的编码要求。与变长编码算法一样，算术编码是以信源的概率分布作为编码的依据。其基本思想是：综合上述，算术编码过程如下：5.4变换编码

在许多情况下，信源输出符号之间具有很强的相关性，如果按照前面介绍的哈夫曼、算术编码等编码算法来实现高效数据压缩，需要使用扩展信源进行编码，因此需要知道序列之间的联合概率分布。当信源符号数量较多，编码算法已经比较复杂，如果采用较长的序列进行编码，会进一步增加编码系统的复杂度。为了提高编码效率，同时降低编码复杂度，可以对信源输出的数据进行变换，