《信息论与编码》课件第5章 信源编码技术

无失真编码等长编码变长编码香农第1定理信息率受到熵的限制，平均码长不小于熵限失真编码平均码长受到信息率失真函数限制香农第3定理在平均失真一定条件下，编码输出码率不小于平均失真所对应信息率通过信源扩展，并对扩展信源序列进行编码，可以有效提高信源编码效率；增加序列的长度，最佳码的平均码长能够逼近信源熵。香农的信源编码理论只是指出了平均码长的界，即阐述了存在性问题，没有给出具体的最佳编码方案。只讨论存在性问题是不够的，信源编码的编码效果毕竟取决于具体的编码方案，为了提高信源编码效率，科学家们进行了大量的卓有成效的研究工作，取得了许多研究成果，并且形成了专门学科。但是信源是复杂的，许多信源不是离散无记忆信源，甚至不是平稳的，而且在许多情况下，信源输出的符号是有限的；所假设的信源编码模型与实际并不相符，等等这些因素都给信源编码造成了困难。至今信源编码技术仍然是研究的重要课题之一，本章主要介绍信源编码技术已经取得的一些研究成果。5.1最佳变长编码具有代表性变长编码方法有：香农码，费诺码和哈夫曼码等。将能够荷载一定信息量，且码字的平均长度最短，可分离的变长码字集合称为最佳变长码。最佳变长码编码的基本原则是：概率大的信源符号分配短的码字，而概率小的信源符号分配长码字，从而使得平均码长最短香农码:是建立在信息科学基础上的第1种信源编码方法，理论意义非常重要；哈夫曼码：信源扩展长度一定情况下，组码中最好的编码算法；在实际信源编码中得到广泛使用。比如：在文本压缩,图像压缩，视频压缩等数据压缩中，最后的熵编码经常采用哈夫曼码照相机、网络上广泛使用的后缀为.jpg图像文件，其图像压缩熵编码器就是哈夫曼码。视频压缩如mpeg2，h.263,h.264都使用哈夫曼编码5.1.1香农码香农根据离散无记忆信源的自信息量构造了一种码，称为香农码；设离散无记忆信源所对应的概率空间为按照每个符号提供的信息量大小分配码字长度；对应码字的长度Li之间满足下列关系这样就可以保证对于每个信源符号而言，码字长度是最佳的。自信息量上取整具体编码方法如下：(1)将信源消息符号按其出现的概率大小依次排列为(2)确定每个信源符号的码长，同时保证码长为满足下列不等式的整数(3)为了编成唯一可译码，计算第i个消息的累加概率(4)将累加概率Pi表示为二进制形式；(5)取二进制数的小数点后Li位作为该消息符号的二进制码字。例5.1设信源共有7个符号消息，按照概率大小排列后的概率分布和累加概率如表5.1所示。根据自信息量定义计算每个信源符号的信息量，然后根据信息量确定码长比如考虑到码长的整数要求，所以取其累计概率二进制表示为编码码字为100累计概率算法：对X取整，整数部分的li位二进制表示就是编码码字表5.1

香农码编码过程消息符号

符号概率

累加概率

I(ai)码长

码字a10.2002.343000a20.190.22.413001a30.180.392.483011a40.170.572.563100a50.150.742.743101a60.100.893.3441110a70.010.996.6671111110比特/符号比特/符号编码效率为平均码长满足香农第一定理问题2.信源只有7个消息符号，即使采用等长编码，平均码长为3小于本例中的3.141.a7对应的码字过长，实际上取为1111即可，所以按信息量分配码长存在问题；由于每个信源符号码长是根据信源符号的信息量选择，从局部来看每个码长的取值都是最佳的，所以香农码是最佳码。但是香农码构造码字时没有综合使用信源统计特性，所以码长并非最短的。香农码编码采用累计概率小数部分的二进制表示作为码字，从而保证了码字是唯一可译码的。

5.1.2费诺码费诺从概率匹配角度出发，构造了一种编码算法，称为费诺码。其基本思想是：按照累加概率尽可能相等的原则对信源符号进行分组，对于二元码，则每次分为两组，对于元码，则每次分为个组，并且给不同的组分配一个不同的码元符号；对其中的每组按照累计概率尽可能相等的原则再次进行分组，并指定码元符号，直到不能再分类为止。然后将每个符号指定的码元符号排列起来就得到相应的码字。如果采用二元码，则编码步骤为：如果采用二元码，则编码步骤为：（1）将信源消息符号按其出现的概率大小依次排列（2）将依次排列的信源符号分为两大组，使两个组的概率之和尽可能近似相等，并将各组分别赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和尽可能近似相等，并将各组分别赋予一个二进制码元“0”和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。例5.2对例5.1的信源进行费诺编码,具体编码过程如下根据每个信源符号的码长，得到每个符号的平均码长为码元/符号消息符号概率

第一次分组第二次分组第三次分组第四次分组二元码字码长

a10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114显然，费诺码要比上述香农码的平均码长小，编码效率高。从上面的例子可以看出，p(a4)<p(a2)，而码长L4<L2，从统计角度来看，平均码长一定不是最短的;如果将两个符号对应的码字互换，这样编码得到的平均码长肯定小于原来的平均码长。尽管如此，费诺码的平均码长仍然满足编码效率为费诺码是根据信源的统计特性进行编码的，经常出现的信源符号分配短码，以减少平均码长，这是一种好的编码方法。但是当信源符号较多时，符号的概率之间没有特别明显的差距，从而使得后续分组时，每个小组的累加概率相差甚大，并使得平均码长增加，所以费诺码不是最优码。由于先对概率进行排序，再进行分组，并指定码字，使得第一次分组后的部分码长能大于第一组某些符号码长，即较小概率分配较长码字，所以也会导致平均码长增加。5.1.3哈夫曼码哈夫曼提出了一种构造最佳码的方法，编码效率高。其基本思想是：概率大的符号分配短码字，而概率小的信源符号分配长码字，为此首先为小概率符号分配码元，分配码元后的符号进行概率合并，然后按照大小顺序重排概率，并对概率小的符号或者符号集合分配码元，直到概率合并结束为止。然后逆向搜索参与概率合并时分配的码元符号，形成对应的码字。对于二元码，其编码步骤如下：（1）将信源消息符号按其出现的概率大小依次排列为

(2)取两个概率最小的两个信源符号分别分配码元0和1，并将这两个概率相加作为一个新符号的概率，与未分配的二进符号的符号一起重新进行概率排序。(3)对重排后的两个概率最小符号重复步骤（2）的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，反向搜索参与编码的符号，得到各个信源符号所对应的码元序列，即相应的码字。例5.3对例5.1中的信源进行哈夫曼编码，编码过程、产生每个信源符号码字和码长如下表平均码长为编码效率为比较三种编码方法，可以看出哈夫曼的平均码长最小，信息传输速率大，编码效率很高哈夫曼编码方法得到的码并非是唯一的，原因在于：每次对信源缩减时，赋予信源最后两个概率最小的符号，分配码元0和1是可以任意的，即大概率符号或者合并后的符号集合可以分配码元0也可以是1，这种选择任意性可以得到不同的哈夫曼码，但不会影响码字的长度。对信源进行缩减时，如果两个概率最小的符号合并后的概率与其它信源符号的概率相同，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。考虑到合并后概率是多个符号概率累加，应当放在上面，以便减少更多符号分配更长码的可能，这样不仅可以减小平均码长，而且可以减小码的任意性。此外，即使平均码长相等，还存在码字质量的好坏问题。例5.4

设有离散无记忆信源的概率空间为方法1方法2根据两种方法的编码结果，计算两种哈夫曼码的平均码长，结果是两种编码方法的平均码长相等，即码元/符号编码效率也相等，都为但是两种码的质量不完全相同，编码质量可以用码方差衡量，即

，由于方法2的码方差比方法1的码方差小许多，所以方法2编码质量好。码方差小的编码方法要比码方差大的方法好，这种结论可以这样说明。由于上述的三种编码方法实际上都是产生码表的过程。而在实际应用中，码表的建立是依据大量的统计结果产生的。对于一次具体的信源编码，实际信源的数据统计规律与建立码表使用的统计规律不一定完全一致。比如采用表5.4和5.5产生的码表进行编码，实际信源的统计特性与表中列出的统计特性不同，实际概率为其他概率分布与编码产生使用概率相同。如果采用方法1进行编码，则平均码长为而如果采用方法2产生的码表进行编码，则平均码长为显然采用方法2的码表编码产生的平均码长比采用方法1的码表产生的平均码长短。这是因为当实际概率分布与建立码表使用的概率不同时，根据码方差小的码表编码产生的附加码长更小。由此可见，为得到码方差最小的码，在概率重排过程中，应使合并的信源符号位于尽可能高的位置上，这样就可以减少再次合并的次数，充分利用短码。与费诺码一样，哈夫曼码也是用概率匹配方法进行信源编码的。其主要特点是：·哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；·缩减信源的两个码字的最后一位总是不同，可以保证构造的码字为即时码。哈夫曼码长码的效率是相当高的，既可以使用单个信源符号编码，也可以对信源序列编码。要得到更高的编码效率，可以使用较长的序列进行编码。例5.5信源输出2个符号，概率分布为P=(0.9，0.1)，信源熵H(X)=0.469比特/符号

采用不同长度符号序列进行二进制哈夫曼编码，序列长度N，编码产生的平均码长也不同N=1时，平均码长N=2时，联合概率分布联合概率分布及编码过程符号序列霍夫曼编码过程码字码长a1a10.810.810.81001a1a20.090.100.191102a2a10.0900.0911003a2a20.0111013比特/2符号平均码长比特/符号同理可以得到比特/符号比特/符号可见，随着序列长度N的增加，平均码长迅速降低，逐渐接近信源熵值产生码表后，就可以根据码表对信源输出的消息符号进行编码。假如使用表5.5码表，信源输出的消息符号为编码器每得到一个输入符号就去查码表，并产生相应的二进制码，将这些二进制码组合到一起就形成编码码流，上述消息符号产生码流为译码器根据码表逐个译码即可重建原始符号编码，译码过程5.2编码的实现上面介绍了几种变长编码方法，相对于等长编码，变长码可以有效提高编码效率。即使采用长度较短的扩展信源进行编码，也能够取得好的编码效果，这是因为变长码利用了信源统计冗余指导编码的结果。实际上，上述的几种变长编码只是产生编码使用的码表，并不是真正意义上的编码实现。信源编码目的是为了更有效地传输信息，即提高通信系统的有效性。为了实现信息传输，信源编码产生的码流传输到信宿之前应当首先进行译码，以便按照先后顺序再现或者重现信源发送的消息符号。对于译码器而言，必须知道信源编码使用的码表和每个码字对应的长度等相关信息，才能够实现正确译码，以便重建信源发送的消息符号序列。信源变长码编码原理框图具体步骤如下：分析给定信源统计特性，得到信源统计规律。对于离散无记忆信源，得到各个符号的概率分布；对于记忆信源，则得到序列的联合概率分布。根据统计特性，码表产生器进行编码，得到每个信源符号或者符号序列对应的码字和码长，即产生码表。对于离散无记忆信源，每个符号都对应一个码字并有一个码长；而对于记忆信源，每个序列对应一个码字和码长。将序列符号、序列长度、码字及码长等信息按照约定规则经过信道传输给译码器，译码器才能够根据这些信息进行正确译码。信源编码器根据码表产生器产生的码表，对给定信源输出符号序列按照先后顺序进行编码，产生码流（码字序列），并经过信道将码流传输给译码器。信源译码器根据接收到的序列符号、序列长度、码字和码长，对接收到的码流进行译码，再现或者重建信源发送的消息。显然，序列符号、序列长度、码字和码长这些辅助信息的传输增加了额外的信息量那么实际编码效率实际编码的平均码长信源输出符号序列个数辅助信息长度理想的编码效率为实际应用中，信源编码使用的码表是根据一类信源的统计特性事先产生的，通过对大量同类信源的分布特性进行分析，在此基础上根据统计得到的分布特性产生码表。对于编码、译码器而言，辅助信息是编译码双方约定的，这些辅助信息不需要再经过信道传输，这样编码器不需要分析信源统计特性，也无需产生和传输码表，从而减轻了编码复杂度采用算法约定码表对给定信源进行编码，这就意味着编码建立码表对应的概率统计特性与给定信源的概率统计特性并不相同，这样就可能会导致编码效率下降。下面对实际信源编码进行分析。不失一般性，首先讨论离散无记忆信源情况。假设码表产生使用的编码概率空间（也称为码表概率空间）为每个消息符号对应码字的长度为li.对于给定的离散无记忆信源，实际的概率空间为如果采用码表概率空间编码，那么信源编码的实际平均码长只有当两种统计特性相近时，采用约定码表进行编码是一种有效的编码方法。反之，如果两种信源统计模型相差甚远，则实际编码的平均码长与理论值相差甚远，此时编码冗余度就会增加，编码效率下降。例5.6采用例5.4方法2产生的码表对给定信源进行编码，信源输出数据长度M=1000，根据频次可以计算各个符号出现的概率填入表中a1a2a3a4a5频次380190160160110概率0.380.190.160.160.11可以计算实际编码的平均码长为根据统计概率，计算出给定信源的熵为实际编码效率为现在改变编码使用的码表,采用例5.4所述的方法1那么平均码长为实际编码效率为如果直接根据信源统计特性编码进行哈夫曼码，平均码长为编码效率为显然相对于直接对给定信源进行编码的效率η,采用给定码表对给定信源进行编码的编码效率有所降低η的计算没有考虑附加信息的影响此外，信源编码的模型与实际的信源模型是否相符，也是影响编码效率的因素之一。如果实际信源模型与编码采用的模型不一致，实际编码的效率也会下降，比如，如果有记忆信源的记忆长度与实际给定信源的长度不一样，则编码效率就会下降。但是在实际应用中，首先需要考虑的是系统编码复杂度，如果实际模型特别复杂，难以实现；而如果采用相对较简单的模型也能够取得好的效果，则就可以简化系统模型，得到有意义的结果。尽管上述讨论是针对平稳离散信源进行的无失真编码，但是得到的结论可以推广到非平稳信源，包括马尔可夫信源等。此外，该结论也适合限失真编码，当统计特性不相符时，限失真编码的信息率失真曲线会向右边移动，在给定码率的情况下，编码产生的失真会增加。由于信源输出符号长度是有限的，而且许多信源是非平稳性、关联性长度也各有差异，直接对数据进行编码并取得好的编码效果十分困难。为了减少这些因素的影响，得到简单的信源模型和统计规律，信源编码大多在变换域进行，而且实际信源编码大多采用混合编码算法以提高编码效率。5.3编码方法简介前面阐述了无失真编码使用的变长编码方法，共同点在于都是采用组码对信源进行编码。对于信源符号数量较少的无记忆信源编码而言，组码是一种简单有效的编码方法，此时可以直接传输码表，当信源输出的长度足够大时，码表的附加信息可以不加考虑。为了提高编码效率，应当对信源进行扩展，使用序列进行编码，而随着序列长度的增加，序列种类也就增加，系统编码复杂度也相应增加。而且使用扩展信源进行编码，效率的提高也是有限的，对记忆信源更是如此。在实际应用中，信源类型众多，统计特性各不相同，特别是大多数信源并不是离散无记忆的、许多信源甚至是非平稳的，而且信源输出的长度也是有限的，所以使用的编码方法需要根据信源的具体特点而设计或者选择。在信源编码理论的指导下，先后出现了许多性能优良的编码方法，这里简单介绍常用编码算法的基本原理。5.3.1游程编码游程编码是经常使用的编码方法之一，当信源出现连续相同符号，或者连续出现的符号在允许失真范围内时，游程编码是一种有效的描述方法。游程编码是利用先后符号之间的关联性进行编码，从而提高编码效率。游程编码的思想特别简单，首先输出符号ai(或者数据)，然后输出连续数据长度li。信源编码时，先根据确定的符号ai和允许误差ɛ搜索后续的符号xj，如果满足，则游程长度加1，如果条件不满足，则游程编码结束，并且根据后续数据重新确定新的编码符号ai+1，然后重复上述过程直至编码结束。游程编码的一般组成框图如图5.3所示。特别地，如果允许失真

，对应于无损编码；否则，游程编码会产生失真。游程编码实际上是一种特殊的序列编码方式，利用了符号（或者是数据）之间的相关性进行编码，从而减少了数据描述长度，提高了编码效率。但是一般情况下，并不单独使用游程编码对数据进行压缩，总是将其作为整体编码算法中的一种编码单元加以使用。游程编码算法在图像压缩中得到广泛应用，连续色调静态图像压缩标准JPEG-LS中就采用了这种游程编码算法，以提高数据压缩效率。游程编码有二进制和非二进制之分，取决于具体编码要求。对于二进制编码，就是统计连续0或者1的个数。由于其特殊性，游程编码可以不输出再现符号，数据长度的交替就是符号0和1之间的交替，这样只需要约定或者在开始时给出再现符号即可。二进制游程编码在信源编码中得到广泛应用，但是经常使用的是上述算法的改进算法。如果信源输出的二进制符号中，符号0的数量很多，而且连续出现的概率也很大，游程编码算法就可以简化。比如，首先约定二进制序列的长度N，如果连续个二进制符号都为0，则输出0；否则输出1，并对序列符号进一步处理。许多实际应用中取N=4，下面以此为例介绍游程编码算法。为了讨论方便，将连续4个符号记作(x1x2x3x4),，并且用两位二进制符号表示序列中首次出现符号1的位置x1x2x3x4b1b21ⅹⅹⅹ0001ⅹⅹ01001ⅹ10000111（1）如果输出一位二进制符号0；（2）如果连续4个符号不全为0，则首先输出一位二进制符号1，并按照表5.7规定输出位置信息，并且顺序输出第一个符号1后的所有信源符号x1x2x3x4码字

码长

00000100011113001ⅹ110x4401ⅹⅹ101x3x451ⅹⅹⅹ100x2x3x46对应的概率为p，其他序列对应概率为q=1-p通常情况下，如果符号序列不全为0，那么第一个符号1出现的位置对应的概率是均等的，所以二进制游程编码的平均码长比特/符号序列当概率p=0.8比特/符号序列,压缩比为2.34当概率p=0.9比特/符号序列,压缩比为2.96二进制游程编码在比特平面编码技术中得到广泛应用，在静态图像压缩标准JPEG和JPEG2000中，都使用这种游程编码作为编码单元，实现二进制符号的初步压缩，为了进一步提高压缩效率，标准中还使用算术编码对游程输出进行进一步压缩5.3.2算术编码从信源编码角度来看，非常希望设计一种有效编码算法对信源符号进行扩展，从而构成尽可能长的序列。尽管哈夫曼编码是一种有效的编码算法，但并不满足这种要求，因为它采用自下而上的编码方法，要求计算特定长度的所有信源序列的概率，并且构造完整的码表。

理想编码方法是：能够任意扩展序列长度，而又不重复构造码表，然后再进行编码，算术编码能够实现这样的编码要求。与变长编码算法一样，算术编码是以信源的概率分布作为编码的依据。其基本思想是：对于给定的信源序列，计算扩展长度为N的序列的联合概率和累加概率

，从而将信源输出序列

与累计概率

对应起来，即用有限精度的累计概率表示信源输出序列，准确地讲，是使用概率间隔

表示序列。然后将

用

位精度表示，就是用一个有限精度的概率表示信源序列的一个码字。显然信源发送的序列符号不同，对应的累加概率也不相同，而且当序列长度N

一定时，在不同序列之间不会产生概率间隔的重叠，从而保证了码的唯一性。

下面简单描述算术编码的方法。假设序列长度N是一定的，即对信源编、译码器而言序列长度N是已知的。不失一般性，假设信源输出为二元符号0和1，定义符号序列

的大小测度为：如果信源输出符号数量为

q，且符号集合为{0,1,….q-1}，序列的大小测度只需用q来代替2即可。通过大小测度

可以比较序列大小，如果

，则称序列

大于

；反之，如果

，则称序列

小于

。这样就可以定义序列

的累加概率为：其中

表示序列

对应的概率。为了有效计算累加概率，一般采用迭代算法，假设当前对信源输出的第n位符号进行编码，得到累加概率为

，信源输出下一个符号

，算术编码器对

进行编码后得到的累加概率为：表示为迭代形式为：上述关系可以用如图5.4所示的树码表示。图5.4累加概率示意图由于

表示长度为n序列的码字，长度为n+1的序列码字用表示，

表示序列的概率，这也是一个累计过程，而只是与当前输入有关的条件概率累加值。为了方便起见，令于是得出下列迭代算法：这样不仅可以迭代计算出序列对应的概率范围

，而且迭代计算状态累计概率

。

如果信源是平稳无记忆信源，满足所以有这样条件累计概率

只与符号取值有关，而与过去的状态没有关系，而状态概率的迭代计算也可以简化了。对于无记忆二进制信源，条件累计概率简化为:其中p

表示符号x=0的概率。对于齐次马尔可夫信源，当输出符号序列n大于马尔可夫链的阶次m+1

时，上述公式可以简化为条件累计概率状态

的计算只与有限个状态有关，而与更早的时刻无关，所以可以事先计算出所有

。同理，由于

与时刻无关，状态概率

的计算相应简化。进一步，当m=1时，表示式进一步简化为综合上述，算术编码过程如下：(1)初始化A=1

，C=0

；(2)根据前面参数和当前输入

编码符号，迭代计算累加概率C和状态累计概率

A(3)重复(2)直到所有序列符号编码结束；(4)确定码长

(5)取累加概率小数点后面的

位二进制数据作为码字。译码过程是编码逆过程，根据输入的码字确定所对应的概率范围，译码出相应的符号。译码过程是一个逐渐细化的过程，具体算法如下：(1)初始化m=1

，C为输入码字对应概率；(2)判断C所在的概率范围，如果，则译码当前符号为；(3)规一化概率范围，

；(4)判断译码是否结束，如果

，则m++跳转到（2）继续译码；否则译码结束。其中

为译码出的符号，

表示译码符号数。将译码输出的符号依次排列得到相应重建符号序列。

(5)取累加概率小数点后面的

位二进制数据作为码字。译码过程是编码逆过程，根据输入的码字确定所对应的概率范围，译码出相应的符号。译码过程是一个逐渐细化的过程，具体算法如下：初始化m=1

，C为输入码字对应概率；(2)判断C所在的概率范围，如果

，则译码当前符号为

；(3)规一化概率范围，

；(4)判断译码是否结束，如果

，则m++跳转到(2)继续译码；否则译码结束。其中

为译码出的符号，L表示译码符号数。将译码输出的符号依次排列得到相应重建符号序列。例5.7

离散无记忆信源X的概率空间为信源输出符号序列

，描述算术编码实现过程。解：首先计算条件累计概率同时