五章节信源编码

第五章第五章 信源编码信源编码 信息通过信道传输到信宿的过程即为通信。要做到既不失真又快速地通信，需要解决两个问题：在不失真或允许一定失真条件下，如何提高信息传输速度-这是本章要讨论的信源编码问题.在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大-这是下章要讨论的信道编码问题.一般来说，抗干扰能与信息传输率二者相互矛盾。然而编码定理已从理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。信源编码的基本途径有两个:一是编码后使序列中的各个符号之间尽可能地 互相独立，即解除相关性-方法包括预测编 码和变换编码.二是使编码后各个符号出现的概率尽可能相等，即均匀化分布-方法主要是统计编码.信源编码常分为无失真信源编码和限失真信源编码，前者主要用于文字、数据信源的压缩，后者主要用于图像、语音信源的压缩。本章主要介绍信源编码的基本思路与主要方法，以无失真、统计编码为主，期望通过本章学习能建立起信源压缩编码的基本概念。5.1 编码器及相关概念 为了分析方便和突出问题的重点，当研究信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码。同样，在研究信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码。5.1.1 码的分类 一.编码器模型 由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。下图为一个编码器模型:输入是信源符号集:x为编码器所用的编码符号集，包含r个元素 ，称为码符号(码元).由码符号 组成的输出序列 称为码字.其长度 称为码字长度或码长，全体码字 的集合C称为码或码书.编码器将信源符号集中的信源符号 （或长为N的信源符号序列 ）变成由码符号组成的长为的与信源符号一一对应的输出序列。即:12,qSs ss ixrxxx,.,21iWiliWisi12(1,2,)(1,2,)(,),iiiiiilijs iqW iqxxxxX 二.码的分类:对于编码器而言，根据码符号集合X X中码元的个数不同以及码字长度是否一致，有以下一些常用的编码形式：(1)二元码和r元码 若码符号集 ，编码所得码字为一些适合在二元信道中传输的二元序列，则称二元码。二元码是数字通信与计算机系统中最常用的一种码。若码符号集共有 r 个元素，则所得之码称为 r 元码.(2)等长码 若一组码中所有码字的长度都相同-（即 ），则称为等长码.0,1X ,1,ill iq(3)变长码 若一组码中码字的码长各不相同（即码字长度 不等），则称为变长码变长码.如表中“编码1”为等长码，“编码2”为变长码。il信源符号si符号出现概率p(si)编码1编码2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)11101(4)分组码 若每个信源符号按照固定的码表映射成一个码字，则称为分组码。否则就是非分组码.如果采用分组编码方法，需要分组码具有某些属性，以保证在接收端能够迅速而准确地将接收到的码译成与信源符号对应的消息。下面讨论分组码的一些直观属性。1）非奇异码和奇异码 若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列)，则称为非奇非奇异码异码。反之，则为奇异码。如表中的“编码2”是奇异码，其他码是非奇异码。()ip a1a2a3a4a概率信源符号 编码1编码2编码3编码4编码51/20000011/4010110011/8101001100011/81110111110001 2）同价码 若码符号集X：中每个码符号所占的传输时间都相同，则所得的码为同价码同价码。我们一般讨论同价码，对同价码来说等长码中每个码字的传输时间相同，而变长码中每个码字的传输时间就不一定相同。rxxx,.,21 3）码的N次扩展码 假定某一码，它把信源 中的符号 一一变换成码C中的码字 ，则码C的N次扩展码是所有N个码字组成的码字序列的集合。12,qSs ss isiW 例如：若码 满足：则码C的N次扩展码集合 ,其中：即码C的N次扩展码中，每个码字 与信源的N次扩展信源 中的每个信源符号 是一一对应的：12,qCW WW 12(,),iiiiiiliilsWxxxsS xX 12,NqBB BB 121,;,1,;1,NNiiiiNBW WWiiqiq iBNS12,iiiiNsss 12(,),NlNiiiiiiiBW WWSWC 4）惟一可译码 若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（或称单义可译码）。否则就称为非惟一可译码或非单义可译码。若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一地分割成一个个的码字。例如：对于二元码 ，当任意给定一串码字序列，例如“10001101”，只可唯一地划分为1,00,01,1,01，因此是惟一可译码；而对另一个二元码 ，当码字序列为“01001”时，可划分为0,10,01或01,0,01，所以是非惟一可译的。11,01,00C 20,10,01C 对惟一可译码又分为即时码和非即时码：如果在接收端收到一个完整的码字后，就能立即进行译码，这样的码叫做即时码；而在接收端收到一个完整的码字后，还需等下一个码字接收后才能判断是否可以译码，这样的码叫做非即时码。即时码又称为非延长码，对即时码而言，在码本中任意一个码字都不是其它码字的前缀部分。对非即时码来说，有的码是惟一可译的，有的码是非惟一可译的，主要取决于码的总体结构。综上所述，可将码作所示的分类：5.1.2 码树 对于给定码字的全体集合，可以用码树码树来描述。对于r进制的码树，如下页图所示，其中图(a)为二元码树，图(b)为三元码树。在码树中点是树根树根，从树根伸出个树枝树枝，构成元码树。树枝的尽头是节点节点，一般中间节点中间节点会伸出树枝，不伸出树枝的节点为终端节点终端节点，编码时应尽量在终端节点安排码字。码树中自树根经过一个分枝到达一阶节点，一阶节点最多为r个，二阶节点的可能个数为r2个，n阶节点最多有rn个，若将从每个节点发出的个分枝分别标以0，1，r-1，则每个n阶节点需要用n个r元数字表示。如果指定某个n阶节点为终端节点，用于表示一个信源符号，则该节点就不再延伸，相应的码字即为从树根到此端点的分枝标号序列，该序列长度为n，用这种方法构造的码满足即时码的条件，因为从树根到每一个终端节点所走的路径均不相同，所以一定满足对即时码前缀的限制。如果有个q信源符号，那么在码树上就要选择q个终端节点，用相应r的元基本符号表示这些码字。若树码的各个分支都延伸到最后一级端点，此时将共有个码字，这样的码树称为整树，如图(a)所示。否则就称为非整树，如图(b)所示，这时的码字就不是等长码了。因此，码树与码之间具有如下一一对应的关系：树根码字起点；树枝数码的进制数；节点码字或码字的一部分；终端节点码字；阶数码长；非整树变长码；整树等长码。5.1.3 Kraft不等式 利用码树可以判断给定的码是否为惟一可译码，但需要画出码树。在实际中，我们可以利用克拉夫特（Kraft）不等式，直接根据各码字的长度来判断惟一可译码是否存在，即各码字的长度应符合克拉夫特不等式：式中，r为进制数也即码符号的个数，q为信源符号数。11iqlir Kraft不等式是惟一可译码存在的充要条件，其必要性表现在如果码是惟一可译码，则必定满足Kraft不等式;充分性表现在如果满足Kraft不等式，则这种码长的惟一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是惟一可译码。因此，克拉夫特不等式是惟一可译码存在的充要条件，而不是惟一可译码的充要条件。5.2 变长编码 变长码往往在码长的平均值不很大时，就可编出效率很高而且无失真的码，其平均码长受香农第一定理所限定，即：若对信源离散无记忆信源S的N次扩展信源 进行编码，则总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：NSrSHNLNrSHNlog)(1log)(且当 时有：其中，为N次扩展信源的平均码长，为信源符号扩展序列 的码长.为对扩展信源进行编码后，每个信源符号 编码所需的等效的平均码长。N1lim()()()log()qNrririNiLHSHSp ap aN1()NqNiiiLpl iliNLN 要做到无失真的信源编码，平均每个信源符号所需最少的r元码元数为信源的熵 。即 它是无失真信源压缩的极限值。若编码的平均码长小于信源的熵值 ，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。通过对扩展信源进行变长编码，当N时，平均码长()rHS()rHS()rHS 无失真信源编码的实质实质：对离散信源进行适当的变换，使变换后形成的新的码符号信源(即信道的输入信源)尽可能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，使信道的信息传输率达到信道容量，实现信源与信道理想的统计匹配。这实际上就是香农第一定理的物理意义。为了衡量各种编码是否达到极限情况，定义变长码的编码效率为：常通过编码效率来衡量各种编码的优劣.为了衡量各种编码与最佳码的差距，定义码的剩余度为：信息传输率定义为：注意:虽然与在数值上相同，但它们的单位不同，编码效率没有单位，而信息传输率的单位是比特/码符号。LSHr)(LSHr)(11LSHR)(在二元无噪无损信道中 在二元信道中，若编码效率 =1，R=1比特码符号，则达到信道的信道容量，此时编码效率最高，码的剩余度为零。前面已经说明，对于某一个信源和某一符号集来说，凡是满足克拉夫特不等式的惟一可译码可以有多种，在这些惟一可译码中，如果有一种（或几种）码，其平均编码长度小于所有其他惟一可译码的平均编码长度，则该码称为最佳码（或紧致码）。()2,()(),rHSrHSHSL 为了使得平均编码长度为最小，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字。能获得最佳码（或次最佳码）的编码方法有很多，本节重点介绍：香农(shannon)编码、费诺(Fano)编码、霍夫曼(Huffman)编码。5.2.1 香农码 香农第一定理指出，可选择每个码字的长度满足关系式：或：x 表示不小于 x 的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。log()log()1(1,)iiip slp siq 1lo g(1,)()iiliqps 一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，也即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。香农码的编码步骤如下：1）将个信源符号按概率递减的方式进行排列：2）按香农不等式计算出每个信源符号的码长 ；3）为了编成惟一可译码，计算第i个信源符号的累加概率 4）将累加概率 用二进制数表示。5）取 对应二进制数的小数点后位构成该信源符号的二进制码字。12qppp il11iikkPp iPiP 例例:设信源共有七个信源符号，其概率分布如表所示，试对该信源进行香农编码。解:计算过程见下页 码的性能分析：通过计算可得此信源的熵:(比特符号)而码的平均长度:(二元码符号符号)编码效率：71()()log()2.61iiiH Sp ap a 71()3.1 4iiiLp al 0.831 ()ip aiP1log()ip sil1a2a3a4a5a6a7a概率累加概率码长信源符号对应的二进制数码字0.2000.0002.3430000.190.20.00112.4130010.180.390.01102.4830110.170.570.10012.5631000.150.740.10112.7431010.100.890.11103.34411100.010.990.11111106.66711111105.2.2 费诺码 费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。()ilip sr 费诺码的编码步骤如下：1）信源符号以概率递减的次序排列起来；2）将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号“0”和“1”；3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号；4）依次下去，直至每个小组只剩一个信源符号为止；5）信源符号所对应的码字即为费诺码。例例:将下列消息按二元费诺码方法进行编码。解:其编码过程如下页：码的性能分析：此信源的熵 (比特符号)，而码的平均长度 (二元码符号符号)显然，该码是紧致码，编码效率：该码之所以能达到最佳，是因为信源符号的概率分布正好满足式，否则，在一般情况下是无法达到编码效率等于“1”的。()2.75H S 2.75L 1 费诺码具有如下的性质：费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用:当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。r 元费诺码 前面讨论的费诺码是二元费诺码，对r元费诺码，与二元费诺码编码方法相同，只是每次分组时应将符号分成概率分布接近的r个组。5.2.3 霍夫曼码 1952年，霍夫曼（Huffman）提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编码方法，一般就称作霍夫曼码霍夫曼码。设信源 ，其对应的概率分布为 ，则对二元霍夫曼码而言，其编码步骤如下：12,.,qSs ss 12(),.,iqp sppp 1）将q个信源符号按概率递减的方式排列起来；2）用“0”、“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称之为S信源的S1缩减信源；3）将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”、“1”码符号表示，这样又形成了由q-2个符号构成的缩减信源S2；4）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用“0”、“1”码符号表示；5）从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。例例:对离散无记忆信源 进行霍夫曼编码。解:编码过程如表所示：1)将信源符号按概率大小由大至小排序。2)从概率最小的两个信源符号和开始编码，并按一定的规则赋予码符号，如下面的信源符号（小概率）为“1”，上面的信源符号（大概率）为“0”。若两支路概率相等，仍为下面的信源符号为“1”上面的信源符号为“0”。3)将已编码两个信源符号概率合并，重新排队，编码。4)重复步骤3）直至合并概率等于“1.0”为止。5)从概率等于“1.0”端沿合并路线逆行至对应消息编码.12345()0.40.20.20.10.1iSsssssp s 码的性能分析：信源的熵为：(比特符号)从 ，可得平均码长为：编码效率为：()2.61H S :2,2,3,3,3,4,4il71()2.7 2iiiLpal96.0)(LSH 按霍夫曼码的编码方法，可知这种码有如下特征特征：它是一种分组码：各个信源符号都被映射成一组固定次序的码符号；它是一种惟一可解的码：任何码符号序列只能以一种方式译码；它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀，霍夫曼编码所得的码字一定是即时码。所以一串码符号中的每个码字都可不考虑其后的符号直接解码出来。霍夫曼码的译码：对接收到的霍夫曼码序列可通过从左到右检查各个符号进行译码。说明：霍夫曼码是一种即时码，可用码树形式来表示。每次对缩减信源最后两个概率最小的符号，用“0”和“1”码是可以任意的，所以可得到不同的码，但码长不变，平均码长也不变。当缩减信源中缩减合并后得到的新符号的概率与其他信源符号概率相同时，从编码方法上来说，它们概率的排序是没有限制的，因此也可得到不同的码。即对给定信源，用霍夫曼编码方法得到的码并非是惟一，但平均码长不变。r 元霍夫曼码 对二元霍夫曼码的编码方法同样可以推广到元编码中。不同的只是每次把概率最小的个符号合并成一个新的信源符号，并分别用0，1，r-1，等码元表示。为了使短码得到充分利用，使平均码长为最短，必须使最后一步的缩减信源有r个信源符号。因此对于r元编码，信源S的符号个数q必须满足：q=n(r-1)+r.其中，n表示缩减的次数，r-1为每次缩减所减少的信源符号个数。对于二元码（r=2），信源符号个数必须满足：q=n+r,因此q可等于任意整正数。注意:对于r元码时，不一定能找到一个使式q=n(r-1)+r成立。在不满足上式时，可假设一些信源符号：作为虚拟的信源，并令它们对应的概率为零，即：,而使 能成立，这样处理后得到的r元霍夫曼码可充分利用短码，一定是紧致码。tqqqsss,.,210.21tqqqppp(1)qtn rr 例例 对信源进行四元霍夫曼码编码。表列出了四元霍夫曼码的编码方法及其对应的码字。5.3 限失真信源编码 由实际生活经验我们知道，一般人们并不要求完全无失真地恢复消息。对人的心理视觉研究表明，人们在观察图像时主要是寻找某些比较明显的目标特征，而不是定量地分析图像中每个像素的亮度，或者至少不是对每个像素都等同地分析。例如观看一段视频或观察一幅图像，人们可能会关注其主要情节，对视频或图像中的细节并不是那么注意，此时便允许视频或图像有一定程度的失真。由香农第一定理知，无论哪种信道，只要信息传输率R小于信道容量C，总能找到一种编码方法，使得在信道上能以任意小的错误概率，以任意接近的传输率来传送信息。实际信道中，信源输出的信息传输率R一般都会超过信道容量，因此也就不可能实现完全无失真地传输信源的信息。由香农第三定理知，在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，只要信息传输率R大于R(D)，一定能找到一种编码方法，使得译码后的失真小于D。香农第三定理从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。一般情况下信源编码可分为离散信源编码、连续信源编码和相关信源编码三类。前两类编码方法主要讨论独立信源编码问题，后一类编码方法讨论非独立信源编码问题。离散信源可做到无失真编码，而连续信源则只能做到限失真编码。5.4 实用信源编码方法 无失真和限失真信源编码定理，说明了最佳码的存在性，但没有给出具体构造码的方法，实用的编码方法需要根据信源的具体特点来决定。霍夫曼码在实际中已得到应用，但它仍存在一些分组码所具有的缺点，例如概率特性必须精确地测定，如果信源概率特性稍有变化，就必须更换码表；对于二元信源，常需多个符号合起来编码，才能取得较好的效果，但是如果合并的符号数目不大时，编码效率提高得不多，特别是对于相关信源，霍夫曼编码不能给出令人满意的结果。因此在实用中常需作一些改进，同时也就有必要研究非分组码。在编码理论的指导下，先后出现了许多性能优良的编码方法，本节介绍一些实用的编码方法.5.4.1 游程编码 游程（Run-Length，简记RL）是指符号序列中各个符号连续重复出现而形成符号串的长度，又称游程长度游程长度或游长游长。游程编码游程编码（Run-Length Coding，简记RLC）就是将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。游程编码特别适用于对相关信源的编码。对二元相关信源，其输出序列往往会出现多个连续的“0”或连续的“1”。在信源输出的二元序列中，连续出现的“0”符号称为“0游游程程”，连续出现的“1”符号称为“1游程游程”，对应连续同一符号的个数分别称为“0”游程长度和“1游程”长度，因为游程长度是随机的，其取值可以是1，2，3，。对二元序列，“0”游程和“1游程”总是交替出现的，如果规定二元序列是以“0”开始的，那么第一个游程是“0”游程，第二个游程必为“1”游程，第三个游程又是“0”游程等等。将任何二元序列变换成游程长度序列，这种变换是一一对应的，因此是可逆的、无失真的。因为游程长度是随机的、多值的，所以游程序列本身是多元序列，对游程序列可以按霍夫曼编码或其他编码方法进行处理以达到压缩码率的目的。对于r元序列也存在相应的游程序列。在r元序列中，可有r种游程。连续出现的符号 的游程，其长度L(i)就是“i游程”长度。用L(i)也可构成游程序列，但此时由于游程所对应的信源符号可有r种，因此，这种变换必须再加一些标志信源符号取值的识别符号，才能使编码以后的游程序列与原来的r元序列一一对应。所以把r元序列变换成游程序列再进行压缩编码通常效率不高。ia 游程编码仍是变长码，有着变长码固有的缺点，即需要大量的缓冲和优质的通信信道。此外，由于游程长度可从“1”直到无穷大，这在码字的选择和码表的建立方面都有困难，实际应用时尚需采取某些措施来改进。例如，通常长游程出现的概率较小，所以对于这类长游程所对应的小概率码字，在实际应用时采用截断处理的方法。游程编码已在图文传真、图像传输等通信工程技术中得到应用。在实际中还常常将游程编码与其他编码方法综合起来使用，以期得到更好的压缩效果。下面以三类传真机中使用的压缩编码的国际标准MH编码为例说明游程编码的实际应用。MH编码:文件传真是指一般文件、图纸、手写稿、表格、报纸等文件的传真，这种信源是黑白二值的，也即信源为二元信源（q=2）。MH编码是一维编码方案，它是一行一行的对文件传真数据进行编码。编码将游程编码和霍夫曼码相结合，是一种改进的霍夫曼码。对黑白二值文件传真，每一行由连续出现的“白（用码符号0表示）像素”或连续出现“黑（用码符号1表示）像素”组成。MH码分别对“黑”、“白”像素的不同游程长度进行霍夫曼编码，形成黑、白两张霍夫曼码表。MH码的编、译码都通过查表进行。MH码以国际电话电报咨询委员会（CCITT）确定的8幅标准文件样张为样本信源，对这8幅样张作统计，计算出“黑”、“白”各种游程长度的出现概率，然后根据这些概率分布，分别得出“黑”、“白”游程长度的霍夫曼码表。码编码规则如下：1)游程长度在063时，码字直接用相应的终端码表示。2)游程长度在641728，用一个形成码加上一个终端码作为相应码字。3)规定每行都从白游程开始。若实际出现黑游程开始的话，则在行首加上长度为零的白游程码字，每行结束时用一个结束码(EOL)作标记。4)每页文件开始第一个数据前加一个结束码，每页结尾连续使用6个结束码表示结尾。5)译码时，每一行的码都应恢复出1728个像素，否则有错。6)为了在传输时可实现同步操作，规定T为每个编码行的最小传输时间，一般规定T最小为20，最大为5。若编码行传输时间小于T，则在结束码之前填上足够的“0”码元(称填充码)。如果采用编码仅仅是用于存储，则可省去步骤中的4)至6)步。例例 设某页传真文件中某一扫描行的像素点为：17白 5黑 55白 10黑 l641白 解:通过查表可得该扫描行的码为：17白 5黑 55白 10黑 1600白（+）41白 EOL 101011 0011 01011000 0000100 010011010 00101010 000000000001 该行经编码后只需用54位二元码元，而原来一行共有1728个像素，如用“0”表示白，用“l”表示黑，则共需1728位二元码元。可见，这一行数据的压缩比为1728:5432，因此压缩效率很高。5.4.2 算术编码 前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上的，这种编码方法我们通常称为块码或分组码，此时信源符号一般应是多元的，而且不考虑信源符号之间的相关性。如果要对最常见的二元序列进行编码，则需采用游程编码或合并信源符号等方法，把二元序列转换成多值符号，转换后这些多值符号之间的相关性也是不予考虑的。这就使信源编码的匹配原则不能充分满足，编码效率一般就不高。为了克服这种局限性，就需要跳出分组码的范畴，研究非分组码的编码方法，而下面要介绍的算术编码即为一种非分组码。在算术编码中，信源符号和码字间的一一对应关系并不存在，它是一种从整个符号序列出发，采用递推形式进行编码的方法 算术编码的基本思路是：从整个符号序列出发，将各信源序列的概率映射到0，1）区间上，使每个符号序列对应于区间内的一点，也就是一个二进制的小数。这些点把0，1）区间分成许多小段，每段的长度等于某一信源序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的。这种方法与香农编码法有些类似，只是它们考虑的信源对象有所不同，在香农编码中考虑的是单个信源符号，而在算术码中考虑的是信源符号序列。如果信源符号集为 ，信源序列 ，则总共有 种可能的序列。由于考虑的是整个符号序列，因而整页纸上的信息也许就是一个序列，所以序列长度L一般都很大。在实际中很难得到对应信源序列的概率，一般我们从已知的信源符号概率 递推得到。12,nAaaa 12(,),iiiliLilaaaaaA Ln12,nPppp 定义各符号的积累概率为：那么可得 由于 和 都是小于“1”的正数，可用0，1）区间内的两个点来表示，而 就是这两个点之间的长度，如图所示。11iillPp 12131222110,nnnPPp PppPpPPp iP1iP 1ip 不同的信源符号有不同的概率区间，它们互不重叠，因此可以用这个小区间中的任意一点的取值，作为该信源符号的代码。我们所需确定的是这个代码所对应的长度，应使这个长度与信源符号的概率相匹配。同样对于整个信源符号序列而言，要把一个算术码字赋给它，则必须确定这个算术码字所对应的位于0，1）区间内的实数区间，即由整个信源符号序列的概率本身确定0和1之间的一个实数区间。随着符号序列中的符号数量的增加，用来代表它的区间减小，而用来表达区间所需的信息单位(如比特)的数量则增大。每个符号序列中随着符号数量的增加，即信源符号的不断输入，用于代表符号序列概率的区间将随之减小，区间减小的过程如图所示。区间宽度的递推公式为：累积概率的递推公式为：其中 为信源符号序列的累积概率，为信源符号序列的联合概率，而 ，。我们可取该小区间内的一点来代表这个信源符号序列，那么选取此点方法可以有多种，实际中常取小区间的下界值。对信源符号序列的编码方法也可有多种，下面介绍常用的一种算术编码方法。()()()()()()0,1ArAp rpp rprr ()()()()0,1PrPpP rr ()P()p(0)0P(1)(0)Pp 将信源符号序列 的累积概率值写成二进位的小数 ，取小数点后L位，若后面有尾数，就进位到第L位，并使L满足:式中 表示大于或等于x的最小整数。这样得到信源符号序列所对应的一个算术码：12()0.,0,1LiPc ccc 1l o g()Lp x 12Lc cc 如果是多元信源序列，则其累积概率和区间宽度的递推公式分别为：其中 为信源符号序列的累积概率，为信源符号序列的联合概率，而 按式 计算。()()()()()()()()kkkkkPaPpP aAapaAp a ()P()p()kkP aP 11iillPp 例例 设二元无记忆信源 ，其中 。对二元序列 进行算术编码。解解：根据上面介绍的编码方法，先计算信源符号序列 的联合概率：决定信源符号序列的算术码字长度：0,1S 13(0),(1)44pp 11111100 62()(11111100)(1)(0)pppp 62(3/4)(1/4)0.011123661lo g6.4 97()Lp 再计算信源符号序列的累积概率，按递推公式有：信源符号序列 的累积概率值的变化及区间宽度减小的过程如图所示。累积概率值 即为输入符号序列“11111100”区间的下界值。()(11111100)PP (0)(10)(110)(1110)(11110)(111110)pppppp 2345(1/4)(3/4)(1/4)(3/4)(1/4)(3/4)(1/4)(3/4)(1/4)(3/4)(1/4)0.82202148 20.1101001001()P 取 二进制表示小数点后L位，得到信源符号序列的算术码字为：。本例对输入信源符号序列进行算术编码后平均码长为：编码效率为：因为这里需编码的序列长为八位，所以一共要把半开区间0，1）分成256个小区间，以对应任一个可能的序列。由于任一个码字必在某个特定的区间，所以其解码具有唯一性。()P 110101078L()0.8110.9277/8H SL 算术码的译码:对二元算术码而言，其译码过程是一系列比较过程：每一步比较 与 ，这里 为前面已译出的序列串，是序列串 对应的宽度，是序列 的累积概率值，即为 对应区间的下界限，是此区间内下一个输入为符号“0”所占的子区间宽度。译码规则为：若 ，则译输出符号为“0”；若 ，则译输出符号为“1”。()CP ()(0)Ap()A()P()(0)Ap()CP ()(0)Ap()CP ()(0)Ap()CP 从性能上来看，算术编码具有许多优点，它所需的参数较少、编码效率高、编译码简单，不象霍夫曼码那样需要一个很大的码表，在实际实现时，常用自适应算术编码对输入的信源序列自适应地估计其概率分布。算术编码在图像数据压缩标准（如JPEG）中得到广泛的应用。5.4.3 预测编码 预测编码是数据压缩三大经典技术（统计编码、预测编码、变换编码）之一，它是建立在信源数据相关性之上的。由信息理论可知，对于相关性很强的信源，条件熵可远小于无条件熵，因此人们常采用尽量解除相关性的办法，使信源输出转化为独立序列，以利于进一步压缩码率。常用的解除相关性的措施是预测和变换，其实质都是进行序列的一种映射。一般来说，预测编码有可能完全解除序列的相关性，但必需确知序列的概率特性；变换编码一般只解除矢量内部的相关性，但它可有许多可供选择的变换方法，以适应不同的信源特性。下面介绍预测编码的一般理论与方法。预测编码的基本思想是通过提取与每个信源符号有关的新信息，并对这些新信息进行编码来消除信源符号之间的相关性。实际中常用的新信息为信源符号的当前值与预测值的差值，这里正是由于信源符号间存在相关性，所以才使预测成为可能，对于独立信源，预测就没有可能。预测的理论基础主要是估计理论。所谓估计就是用实验数据组成一个统计量作为某一物理量的估值或预测值。若估值的数学期望等于原来的物理量，就称这种估计为无偏估计；若估值与原物理量之间的均方误差最小，就称之为最佳估计，基于这种方法进行预测，就称为最小均方误差预测，所以也就认为这种预测是最佳的。要实现最佳预测就是要找到计算预测值的预测函数。设有信源序列 ，k阶预测就是由 的前k个数据来预测 。可令预测值为：式中 是待定的预测函数。要使预测值具有最小均方误差，必须确知k个变量的联合概率密度函数 ，这在一般情况下较难得到，因而常用比较简单的线性预测方法。线性预测是取预测函数为各已知信源符号的线性函数，即取 的预测值为：其中 为预测系数。21,rkrrsss rsrs12(,)rrrrksf sss ()f 21,rkrrsss rs1kririisa s ia 最简单的预测是令 称为前值预测，常用的差值预测就属于这类。利用预测值来编码的方法可分为两类：一类是对实际值与预测值之差进行编码，也叫差值预测编码。另一类方法是根据差值的大小，决定是否需传送该信源符号。例如，可规定某一阈值T，当差值小于T时可不传送，对于相关性很强的信源序列，常有很长一串符号的差值可以不传送，此时只需传送这串符号的个数，这样能大量压缩码率。这类方法一般是按信宿要求来设计的，也就是压缩码率引起的失真应能满足信宿需求。1rrss 下面简单介绍差值预测编码系统。如果信源的相关性很强，则采用差值编码可得较高的压缩率。由于相关性很强的信源可较精确地预测待编码的值，使得这个差值的方差将远小于原来的信源取值，所以在同样失真要求下，量化级数可大大减少，从而较显著地压缩码率。差值预测编码系统的框图如下图所示，在编码端主要由一个符号编码器和一个预测器组成，在解码端主要由一个符号解码器和一个预测器组成。编码器解码器 当输入信源序列逐个进入编码器时，预测器根据若干个过去的输入产生对当前输入像素的估计值。预测器的输出舍入成最近的整数，并被用来计算预测误差：在解码器中根据接收到的变长码字重建 ，并执行下列操作：而 可通过式 进行预测得到。rrress rerrrses rs 1kririisa s 差值编码的特点：在差值编码中所能取得的压缩率与预测误差序列所产生的熵的减少量直接有关。通过预测可消除相关，所以预测误差的概率分布一般在零点附近有一个高峰，并且与输入信源分布相比其方差较小。5.4.4 变换编码 由前节已经看到，对于有记忆信源，由于信源前后符号之间具有较强相关性，要提高信息传输的效率首先需要解除信源符号之间的相关性，解除相关性可以在时域上进行（如前面介绍的预测编码方法），也可以在变换域上进行，这就是本节要介绍的变换编码方法。对于图像信源等相关性更强的信源，常采用基于正交变换的变换编码方法进行数据压缩。变换编码的基本原理是将原来在空间（时间）域上描述的信号，通过一种数学变换（例如傅里叶变换等），将信号变到变换域（例如频域等）中进行描述，在变换域中，变换系数之间的相关性常常显著下降，并常有能量集中于低频或低序系数区域的特点，这样就容易实现码率的压缩，并还可大大降低数据压缩的难度。最早将正交变换思想用于数据压缩是在20世纪60年代末期，由于快速傅里叶变换的出现，人们开始将离散傅里叶变换用于图像压缩；之后在1969年哈达玛变换用于图像压缩；1971年KL变换用于图像压缩，得到了最佳的性能，故KL变换又称为最优变换；1974年出现了综合性能较好的离散余弦变换（DCT），并很快得到广泛的应用；20世纪80年代后期，国际电信联盟(ITU)制订的图像压缩标准H.261选定DCT作为核心的压缩模块；随后国际标准化组织(ISO)制定的活动图像压缩标准MPEG-1也以DCT作为视频压缩的基本手段；更新的视频压缩国际标准中也有用到DCT。下面我们首先介绍变换编码的基本原理，然后介绍变换编码中常用的几种变换。(1)变换编码的基本原理 设信源连续发出的两个信源符号 之间存在相关性，如果均为3比特量化，即它们各有八种可能的取值，那么 之间的相关特性可用图表示。12,s s12,s s 图中的椭圆区域表示s1与s2相关程度较高的区域，此相关区关于s1轴和s2轴对称。显然如果s1与s2的相关性越强，则椭圆形状越扁长，而且变量s1与s2幅度取值相等的可能性也越大，二者方差近似相等，即 。如果我们将s1与s2的坐标轴逆时针旋转45，变成 平面，则椭圆区域的长轴落在 轴上，此时当 取值变动较大时，所受影响很小，说明 与 之间的相关性大大减弱。同时由图可以看出：随机变量 与 的能量分布也发生了很大的变化，在相关区域内的大部分点上的 方差均大于的 方差，即 .2212 12y Oy1y1y1y1y1y2y2y2y2y2212yy 另外，由于坐标变换不会使总能量发生变化，所以有：由此可见，通过上述坐标变换，使变换后得到的新变量 、呈现两个重要的特点：变量间相关性大大减弱；能量更集中，即 ，且 小到几乎可忽略.这两个特点正是变换编码可以实现数据压缩的重要依据。2212 2212yy 1y2y2212yy22y 上述坐标旋转对应的变换方程为：因为 因此，坐标旋转变换矩阵 是一个正交矩阵，由正交矩阵决定的变换称为正交变换。1122cossinsincosysys cossincossin10sincossincos01T cossinsincosT 一般的变换编码系统框图如图所示 高性能的变换编码方法不仅能使输出的压缩信源矢量中各分量之间的相关性大大减弱，而且使能量集中到少数几个分量上，在其他分量上数值很小，甚至为“0”。因此在对变换后的分量(系数)进行量化再编码时，因为在量化后等于“0”的系数可以不传送，因此在一定保真度准则下可达到压缩数据率的目的，量化参数的选取主要根据保真度要求或恢复信号的主观评价效果来确定。在变换编码方法中最关键的是正交变换的选择，最佳的正交变换是KL变换，这一变换的基本思想是由Karhunen和Loeve两人分别于1947年和1948年单独提出的，主要用于图像信源的压缩。由于KL变换使变换后随机矢量的各分量之间完全独立，因而它常作为衡量正交变换性能的标准，在评价其它变换的性能时，常与KL变换的结果进行比较。KL变换的最大缺点是计算复杂，而且其变换矩阵与信源有关，实用性不强。为此人们又找出了各种实用化程度较高的变换，如离散傅里叶变换（DFT）、离散余弦变换（DCT）、沃尔什变换（WHT）等等，其中性能较接近KL变换的是离散余弦变换（DCT），在某些情况下，DCT能获得与KL变换相同的性能，因此DCT也被称为准最佳变换。(2)离散余弦变换 DCT是根据DFT的不足，按实际需要而构造的一种实数域的变换，由于DCT源于DFT，这里我们先考察DFT。DFT是一种常见的正交变换，在数字信号处理中得到广泛应用，离散傅里叶变换对定义为：设长度为的离散序列为 ，DFT定义为：正变换 反变换 其中:将正变换写成矩阵形式:其中:T为离散傅里叶变换的变换矩阵。110011()()exp2/=()(u0,1,2,.,N-1)NNuxxxF ufxjuxNfx WNN 110011()()exp2/()0,1,2,.,N-1NNuxuufxFujuxNFu WxNN 2/ejNW ()()F uTf x 00000121012(1)(1)(1)1NNNNNWWWWWWWWTNWWWW 12,Nfff 虽然DFT为频谱分析提供了有力的工具，但是通常DFT是复数域的运算，尽管有快速傅里叶变换（FFT），在实际应用中仍有许多不便。如果将一个实函数对称延拓成一个实偶函数，由于实偶函数的傅里叶变换也是实偶函数，只含有余弦项，因此构造了一种实数域的变换，即离散余弦变换。设长度为的离散序列为 ，DCT定义为：正变换 反变换 其中:将正变换写成矩阵形式:其中:12,Nfff10(21)()()()cos 0,12NxxuF ua ufxuNN 10(21)()()()cos 0,1,12Nuxufxa u F uxNN 1,.,2,1u /20u /1)(NNNua()()CF uT f x 111.2223(21)2coscos.cos222:.:(1)3(1)(21)(1)coscos.cos222CNTNNNNNNNNNNN 例例 给定两幅图像信源如图所示，对它们进行DCT，则其DCT系数图所示，图中亮度越大表示对应的DCT系数数值也越大。(3)沃尔什-哈达玛变换 离散沃尔什哈达玛变换(WHT)，其变换矩阵是由“+1”和“-1”组成的，因此在变换过程中只有加法和减法，计算速度快而且易于用硬件实现。设长度为N的离散序列为 ，当 时，WHT变换对定义为：12,Nfff2nN 正变换 反变换 其中指数上的求和是以“2”为模的，是D的二进制表达式中的第i位的取值。例如当n=3时，对 ，有 。比较可知,WHT正变换和反变换只差一个常数项，所以用于正变换的算法也可用于反变换，这使得WHT的使用非常方便。()ib D26(110)D 012()0,()1,()1bDb DbD WHT变换矩阵是一个对称的正交矩阵，例如当N=8时的WHT变换矩阵为：111111111111111111111111111111111111111118111111111111111111111111HT 对WHT变换矩阵而言，其构成规律具有简单的迭代性质，可以方便地产生各阶变换矩阵。最小阶(N=2)的TH为：如果用 代表N阶WHT变换矩阵，则上面所述的迭代关系如下：21111HT NHT2NNNNNHHHHHTTTTT 例例 给定如图(a)所示的图像信源，对其进行WHT，则WHT系数图(b)所示，同样在图中亮度越大表示对应的WHT系数的取数值也越大。从本例可以看到，经沃尔什-哈达玛变换后图像信号的能量向左上角集中，因而有利于数据的压缩。但WHT的能量集中能力不如DCT。许多信号变换方法都可用于变换编码。需要注意的是数据的压缩并不是在变换步骤取得的，而是在量化变换系数时取得的，因为在实际编码时，对应于方差很小的分量，往往可以不传送，从而使数据得到压缩。对某一个给定的编码应用，如何选择变换取决于可容许的重建误差和计算要求。变换具有将信号能量集中于某些系数的能力，不同的变换信号能量集中的能力不同。对常用的变换而言，DCT比DFT和WHT有更强的信息集中能力。从理论上说，KL变换是所有变换中信息集中能力最优的变换，但KLT的变换矩阵与输入数据有关，所以不太实用。实际中用的变换其变换矩阵都与输入数据无关，在这些变换中，非正弦类变换（如WHT)实现起来相对简单，但正弦类变换(如DFT和DCT)更接近KLT的信息集中能力。近年来，由于DCT的信息集中能力和计算复杂性综合得比较好，而得到了较多的应用，DCT已被设计在单个集成块上。另外，近年来得到广泛研究和应用的一些编码方法（例如子带编码、小波变换编码、分形编码等）也直接或间接地与变换编码相关，在实际应用中，需要根据信源特性来选择变换方法以达到解除相关性、压缩码率的目的。另外还可以根据一些参数来比较各种变换方法间的性能优劣，如反映编码效率的编码增益、反映编码质量的块效应系数等。当信源的统计特性很难确知时，可用各种变换分别对信源进行变换编码，然后用实验或计算机仿真来计算这些参数，从而选择合适的编码。