3.10 熵编码

3.10.1 熵编码的基本概念

在前面几节中我们分别讨论了预测编码和各种变换编码，这些编码都可以看成是通过解除空间或时间上的相关性，将原始信号转换成另一种形式（预测误差或变换系数）来表达。在这种新形式下，信源可以近似认为是无记忆的，即各样值之间已没有相关性，再经过量化后信源只产生有限个数的符号，因此可近似看成是一个离散无记忆信源（见图3-42）。根据3.2.2节的论述可知，对于离散无记忆信源只要各事件出现的概率不相等，该信源就仍然有冗余存在，还有进一步进行数据压缩的可能性，这就是在熵编码中所考虑的问题。

如前所述，在预测编码、变换编码、子带编码或小波变换之后，将预测误差、变换系数或子带信号量化，将造成少量信息的丢失。存在信息丢失的编码方法称为有损编码。本节介绍的熵编码不引起信息损失。无信息损失的编码方法称为无损编码。

我们以下式所表示的一个具有4个电平（即4个符号）的离散信源为例来进行讨论。

该信源中4个符号出现的概率是比特/符号。如果用表3-1第三行所示的2位的二进制数码来代表这4种电平，例如用10来表示电平s3，这一过程叫编码，10称为码字，如表3-1所示的符号与码字一一对应关系的集合称为码表或码本。

表3-1 一个4符号信源的码表

在第一种编码方式中（表中第三行），每个符号所给予的码字长度都相同，平均码长N＝2比特/符号，N大于熵（1.75比特/符号）。也可以改换成另一种编码方式，如表3-1中第四行所示。在这种编码方式中各符号所对应的码有不同的长度，称为变长编码VLC（VariableLengthCod-ing）。设符号si所对应的码的字长为n（si）比特，则平均码长为

将第二种编码方式中各个符号的码字长及其对应的概率代入（3-150）式，对于本例而言，N＝1.75比特/符号，正好等于信源的熵。显然第二种编码方式比第一种具有更低的数据率，并且已达到了基本极限。这意味着，按照香农信息论，不可能再找到任何其他的无失真编码方式，其平均字长比这种编码方式更短。

当用二进符号表示输出码字时，相当于从一个新符号集A＝｛0，1｝中，选取符号ai（i＝1，2）来代表原信源所输出的序列。为了达到数据压缩的目的，应使新符号集A的概率模型尽可能接近于等概率分布。也就是说，使信源A的熵最大，每个符号ai平均携带的信息量最多，从而表达原信源输出所需要的符号ai数目最少。这从下面的例子中可以得到证实。当采用表3-1中的第2种编码方式时，原输出序列与编码后的序列有如下关系：

可以看出，用方式Ⅱ编码后的序列中0和1出现的重复频率相同，因此这种编码方式能够给出较低的数据率。在（3-151）式中，编码方式Ⅱ只用14个符号，而编码方式Ⅰ需用16个符号表示同一个原始信源序列。

如果编码符号集A中符号的个数为M，经编码以后可能达到的最大熵值则为log2M。若原信源的熵为H（X），经编码后的平均码长为，编码符号集中一个符号所携带的平均信息量则为H（A）＝H（X）/。显然

我们将编码效率η定义为

当η＝1时，有

这就是在编码中可能达到的最小平均码长的极限。当M取2时，例如A＝｛0，1｝，最小平均码长则等于原信源的熵。熵编码的宗旨在于找到信源符号集内的符号与码字的一一对应关系，以使平均码长达到上述极限。不难看出，这种编码方式是无失真的。

实际应用中的熵编码方式主要有霍夫曼编码和算术编码两种，下面分别进行介绍。

3.10.2 霍夫曼编码

霍夫曼（Huffman）编码的基本思想是，对出现概率较大的符号si取较短的码长，而对概率较小的符号则取较长的码长，因此它是一种变长码。霍夫曼码通常被称为最优码。最优的含义是，对于给定的符号集和概率模型，找不到任何其他整数码比霍夫曼码有更短的平均字长。所谓整数码是指每个符号所对应的码字的位数都是整数。

现在通过M＝2的例子来介绍霍夫曼码的编码过程。设原信源为

其编码的具体步骤如下。

（1）合并：将信源中最小概率的两个事件合并成一个事件。由于这些事件是统计独立的，合并后的事件出现的概率等于原来两个事件的概率和。

（2）置换：将合并后的信源的事件重新按概率大小排列（概率相等的事件可按任意顺序排列）。

（3）若合并后的信源中事件的个数大于2，重复执行步骤（1）和（2）；若合并信源中事件个数等于2，则进行步骤（4）。

（4）赋值：在最后得到的信源

中，给x（m－2）1和x（m－2）2分别赋值0（或1）和1（或0）。

（5）反推：由于x2（m－2）（或x1（m－2））一定是由两个事件构成的，因此，对应于这两个事件的码字由x2（m－2）的码字分别加上0和1构成。以此类推，一直到返回原信源符号为止。

现在利用图3-43来说明上述编码过程。假设构成信源的符号以及它们各自出现的概率为

图3-43中从左到右用虚线标出的4个部分表示4个合并与置换的步骤。在第1步中，概率最小的s4和s5合并，其合成事件的概率为13/60。由于1/5＜13/60＜1/4，因此合成事件在第2步中排在s2和s3之间。以此类推，在第4步中，只剩下了两个事件，合并过程结束。然后给每一个节点（图中〇点处）的两个分支分别赋以0和1。如图所示的树状结构称为码树。从树根（图中用箭头指出的节点）到左端树梢的各个分支所经过的码串接起来就构成该树梢上符号所对应的码字。例如，从树根经过两个节点到s3所构成的码为11。

由于一个节点的上下两个分支既可赋值0（或1），也可赋值1（或0值），而且对概率相同的两个事件的排列顺序也是任意的，因此对同一信源所构成的霍夫曼码并不是唯一的，但是它们的平均字长却是一样的。

这样构造的霍夫曼码是无歧义的。所谓无歧义是指在译码过程中，对某个码字的解释是唯一的。现在举一个例子来说明。对于表3-1所给出的信源概率模型，读者根据霍夫曼码的构码过程，可以证明表中给出的第二种码即为霍夫曼码。假设该信源输出序列和编码后的序列如（3-151）式所示，当接收端收到码流01001101000111…时，按照码表，以0开头的码字只有0，因此解出第一个符号为s1；除去已解的码0以后，码流则剩下1001101000111，码表中以一个1开头的码只有10，因此得到第二个符号s2；除掉10之后，码流剩下01101000111，第一个码0决定了译码结果只能是s1；在剩余码流1101000111中，开头的两个码为11，而码表中2比特的码字只有10，因此可以断定应该按3位来译码，得到s3；以此类推。

由以上译码过程可以看出，虽然霍夫曼码是变长的，码流中又没有分隔码字的标识符，但由于它独特的前缀（Prefix）特性，即短码字永远不会成为长码字的开头，因此，完全能够从码流直接恢复原信源所输出的符号序列来。

值得注意的是：①由于霍夫曼构码过程的最基本依据是信源的概率分布，如果信源的实际概率模型与构码时所假设的概率模型有差异，实际的平均码长将大于预期值，编码效率下降。如果差异很大，则有可能比使用定长码（如表3-1中的第一种编码方式）的平均字长还要长。对于这种情况，解决的办法是更换码表，使之与实际概率模型相匹配；或者直接使用定长码。②霍夫曼码对传输错误十分敏感，如果码流中出现1比特错误，不仅对应的码字会译错，而且由于前缀特性被破坏，可能使后续的译码在错误的码字边界上进行，从而使错误传播下去。

3.10.3 算术编码

算术编码是另一种能够趋近于熵极限的最佳编码方式，它与霍夫曼编码一样，也是对出现概率较大的符号采用短码，对概率较小的符号采用长码。但是它的编码原理却与霍夫曼编码很不相同，也不局限于非使用整数码不可，这使得它比霍夫曼码有更高的效率。

1.算术编码的基本原理

假设一个具有4个电平的信源，其概率模型如表3-2所示。把各符号出现的概率表示在如图3-44（a）所示的单位概率区间之中，区间的宽度代表概率值的大小。由图可以看出，各符号所对应的子区间的边界值，实际上是从左到右各符号的累积概率。在算术编码中通常采用二进制的分数来表示概率，表3-2和图3-44（a）中都标出了相应的二进概率数值。每个符号所对应的概率区间都是半开区间，即该区间包括左端点，而不包括右端点，如s1对应[0，0.001），s2对应[0.001，0.011），等等。

表3-2 一个4符号信源的概率模型

现在以符号序列s3s3s2s4…为例来解释编码过程。算术编码所产生的码字实际上是一个二进制分数值的指针，该指针指向所编的符号对应的概率区间。按照这一法则，序列的第一个符号为s3，我们用指向图3-44（a）中第三个子区间的指针来代表这个符号。从原理上来讲，指针指向[0.011，0.111）区间内的任何部位都可代表s3，但通常约定为指向它的左端点，由此得到码字0.011。后续的编码将在前面编码指向的子区间内进行。将[0.011，0.111）区间再按符号的概率值划分成4份，如图3-44（b）所示。对第二个符号s3，指针指向0.1001（s3区间的左端），也就是码字串变为0.1001。然后如图（b）所示，s3所对应的子区间又被划分为4份，开始对第三个符号进行编码。余下的步骤以此类推。

总结上述划分子区间的递归过程，可将算术编码的基本法则归纳如下：

（1）初始状态

　　　编码点（指针所指处）C＝0

　　　区间宽度A＝1.0

（2）新编码点C＝原编码点C＋原区间A×Pi（3-158）

　　　新区间A＝原区间A×pi（3-159）

其中pi和Pi分别为所编符号si对应的概率和累积概率。

根据上述法则，对序列s3s3s2s4…进行编码的过程如下。

第一个符号（s3）：

第二个符号（s3）：

第三个符号（s2）：

第四个符号（s4）：

该码字串0.1010011用7b表示了4个符号，平均码长为7/4＝1.75b/符号。

在解码器中，当收到码字串0.1010011时，由于这个码字串指向子区间[0.011，0.111）[见图3-44（a）]，因此，解出的第一个符号应为s3。然后，采取与编码过程相反的步骤，即从码字串中减去已解符号子区间的左端点的数值（累积概率），并将差值除以该子区间的宽度（概率值），则得到新码字串（0.1010011－0.011）÷（0.1）＝0.100011。由图3-44（a）中可以看出，新码字串仍落在[0.011，0.111）区间之内，因此，解出的第二个符号仍为s3。后面的过程可以此类推。

在算术编码中，一个值得注意的问题是进位。在霍夫曼编码中，如（3-151）式所示，后续符号的码字只是简单地附加到已编好的码字串之尾，并不改变已有的码字串。而在算术编码中则不同，如在上面的例子中，编完第三个符号之后得到的码字串为0.10011，在对第四个符号编码时，将码串的前3位由0.100变成0.101，这便是由于相加运算中的进位引起的。

2.二进制算术编码

二进制算术编码是一种常用的算术编码方法，所谓二进制是指输入的字符只有两种。如果信源字符集内包含有多个字符，则先将这些字符经过一系列的二进判决，变成二进制字符串。图3-43所示的霍夫曼树就是这样的判决方法之一（不遵从霍夫曼概率置换原则的二进树也可以）。在那里，字符s4的转换过程可以分解成3次二进判决（100）。

在二进制算术编码器的两个输入字符中，出现概率较大的一个通常称为MPS（More Probable Symbol），另一个称为LPS（Less Probable Symbol）。假设LPS出现的概率为Qe，MPS出现的概率则为（1－Qe），图3-45表示出这两个符号所对应的概率区间。

对这两个符号构成的序列的编码与前面介绍的算术编码的基本原理是相同的，仍然是不断划分概率子区间的递归过程。如果我们规定编码指针指向子区间的底部（见图3-45），那么编码规则为：

对于MPS

C＝C 　（3-160）

A＝A（1－Qe）＝A－AQe 　（3-161）

对于LPS

C＝C＋A（1－Qe）＝C＋A－AQe　（3-162）

A＝AQe　（3-163）

在霍夫曼编码中，最短的码字为1比特，所以即使在对最常出现的符号进行编码时，也需要在前面已编好的码字串上再增加1比特。而在算术编码中，由（3-160）式可以看出，对MPS编码不增加已编好的码字串的长度。这是算术编码比霍夫曼编码优越的地方。

在具体实现上述算法时，如下几个问题值得注意：

①在概率子区间不断划分的过程中，区间宽度A越来越小，因此，用来表示A的数字的位数则需要越来越多；

②完成（3-161）式至（3-163）式的运算都要用到成本较高（无论是用硬件实现还是用软件实现）的乘法运算；

③当已编好的码字串中连续出现多个1时，若后续编码过程中在最后一位上加1，将连续改变前面已编好的码字，产生连续多个0，直到出现1为止，这就是前面提到过的进位问题。

为了有效地实现编码算法，人们提出了若干办法来解决上述问题，从而构成了不同类型的二进制算术编码器，如Q编码器、QM编码器和MQ编码器等。下面我们仅简单介绍其中的QM编码器。

用有限精度的算术运算来计算概率区间A，可以保证A的有效数字的位数不至于随码字串的增加而增加。例如A＝0.001可以用1.0×2－3来表示，当A被分割到更小值时，则增加指数值，而有效数字的位数仍保持在规定的范围之内。假设这个范围选择在0.75到1.5（十进制数字）之间，当A＜0.75时，将A乘以2（相当于2的负指数增加1），使有效数字保持在0.75～1.5之间，这样，仍然可以用原来的位数表示，这无论对用硬件还是用软件来实现编码都是有利的。上述过程称之为重新归一化。乘2运算可以由将数据在寄存器中左移一位的操作来完成。显然，当区间A重新归一后，码字串C也应当随之归一，否则C将不能指向正确的区间。

当1.5＞A≥0.75时，AQe≈Qe。利用这个近似式，可将（3-161）式至（3-163）式简化而无需做乘法。此时二进概率区间变成如图3-46所示。Qe一般比较小，只有当Qe接近于0.5的情况下，上述近似式引入的误差才比较明显。

当Qe接近0.5时，由此近似产生的误差有可能发生LPS区间大于MPS区间的情况，图3-47给出了一个例子。图（a）中Qe＝0.5，初始的A＝1.35，MPS和LPS的区间分别为[0.0，0.85）和[0.85，1.35）。在下一个编码周期中（图（b）），区间A更新为A＝A－Qe＝0.85，LPS区间Qe＝0.5，MPS区间变成A－Qe＝0.35。在这种情况下，即Qe＞A－Qe时，需要将MPS和LPS符号及区间互换，这称为条件互换（Conditional exchange）。图（b）表示出了条件互换后的结果。在需要进行条件互换时，由于Qe≤0.5，我们有0.5≥Qe＞A－Qe，此时，两个子区间（Qe和A－Qe）都小于0.75，肯定需要重新归一化A和C。因此，条件互换总是放在编码器检测到需要重新归一化之后再进行。

将重新归一化和条件互换结合进（3-160）式至（3-163）式所表示的编码过程，得到QM编码器的编码算法为：

对于MPS：

相应的解码算法为：

为了简单起见，这里没有考虑条件交换。

关于进位的问题，可以用在编码器输出之前设置一个缓存器的办法来解决。连续出现1的码字串（如连续的8个1）先不输出，而将它送入一个堆栈暂存，若后续编码引起进位，则改变堆栈中的数据后再输出。若不引起进位，则直接输出堆栈中的码字。

与霍夫曼编码一样，如果输入信号的实际概率模型（二进编码中的Qe值）与假设值不一样，算术编码的效率也要下降。为了提高编码效率，可以通过一定方式实时地对实际输入信号的Qe值进行估计，编码器则根据所估值动态地更新Qe，这就构成了所谓的自适应二进制算术编码。在QM编码中，对概率的估值是通过一个预先设定的Qe表来实现的。该表包括一组按大小排序的Qe值，当编码过程进行重新归一化时，若因编码LPS而导致归一化，Qe更新为表中下一个较低的值；若因编码MPS而导致归一化，Qe则更新为相邻的较高的值。