CABAC中等概率符号的并行解码算法

陈海燕

(华东政法大学计算机科学与技术系，上海 201620)

H.264［1］是最新的国际视频编码标准，在数字电视、视频拍摄、流媒体等方面得到了广泛的应用。由于其高复杂度，对于它的解码算法的优化变得尤为重要。H.264中有两种熵编码算法，一种是基于哈夫曼变长码的内容自适应变长编码(CAVLC)［2］，另一种是基于二进制算术编码的内容自适应二进制算术编码(CABAC)［3］。CABAC中共有3类符号，即一般的二进制位符号、等概率二进制位符号(也叫旁路符号)和终止二进制位符号。其一般的解码流程都是逐位进行解码。CABAC算法目前已经有硬件方面的实现，具体可以参考文献［4］。本文的特色在于使用纯软件的方法，提出一种等概率二进制位符号的多位并行解码算法，用以加快H.264视频解码的速度。

1 技术背景

CABAC是H.264中一种高效的熵编码方法，与基于哈夫曼变长码的方法相比，能节省大约10%的码率，而由于需要逐二进制位算术解码，其计算复杂度也大大提升。在CABAC中，所有待编码符号首先被二进制化为一系列二进制位比特串，然后根据一定的内容模型逐位进行算术编码。二进制位比特串共分为3类，一般的二进制位比特串、等概率二进制位比特串和终止二进制位比特串。等概率二进制位比特串是一种重要的类型，较大的运动向量(MV)和量化DCT系数(Level)、运动向量和DCT系数的符号都需要用等概率二进制位序列编码。对于较大的运动向量和量化DCT系数，数值首先被二进制化为指数－哥伦布码［4］，然后逐位进行等概率符号编码。在解码器中，首先逐位解码出指数－哥伦布码，然后还原出数值。指数－哥伦布码如表1所示，它由两部分组成，第一部分是前导1结构，由n(n≥0)个连续的1最后跟一个0组成，该算法中，称其为前导1符号;第二部分是定长编码部分，其长度为m(m≤n)。如表1中数值3，4，5，6所对应的指数哥伦布码的前导1符号都是110，前导1长度为2，定长编码部分长度也是2。

针对作为等概率符号编码的指数哥伦布码的前导1部分和定长编码部分各提出一种快速的并行解码算法，与原来的逐位解码相比，该算法可以一次解码出数位等概率二进制位，大大提高了解码速度。

表1 指数哥伦布码

2 CABAC中等概率符号的快速解码

2.1 CABAC中等概率符号解码过程

在一个CABAC解码器中，假设多字节基的输入输出，基本变量有 value，bitsleft和 range，其中 range∈［0x100，0x1ff］且 0 ≤ value ＜ (range ＜ ＜ bitsleft)，bitsleft≥0。等概率符号的解码基本过程如下:

当bitsleft递减至小于0时，从码流中读取一定长度字节填充至value末尾，并相应的更新bitsleft。读取n字节具体过程如下:

该算法约定value和bitsleft的初始状态表示为valuen和bitsleftn，当解码了n位等概率二进制位后，其状态分别用valuen和bitsleftn表示，从以上解码过程中易知bitsleftn=bitsleft0－n，如果bitsleftn不小于0，则有0≤valuen＜ (range＜ ＜bitsleftn)。

2.2 前导1部分的并行解码算法

对于前导1结构的解码，其解码就是循环进行等概率二进制位解码直到获得第一个0。假设已连续解码了x个1，根据以上过程，valuex=value0－(range＜＜bitsleft)+(range＜ ＜ (bitsleft－x))，且valuex≥0，如果下一个符号仍然是1，那么有 valuex≥ (range＜＜(bitsleft－x－1))，否则下一个符号为0。所以解码一个前导1符号的本质就是max{x|(value0－(range＜＜bitsleft)+(range＜＜(bitsleft－x)))≥0}，即max{x|(range＜＜(bitsleft－x))≥(range＜＜bitsleft)－value0}。考虑到 range的范围，可以先求出 diff0=(range＜＜bitsleft)－value0，然后用前导0指令，如x86/x64下的BSF或ARM下的CLZ，求出其最高有效位y，即(1＜＜y)≤diff0＜(1＜＜(y+1))，然后和range＜＜(y－8)比较，如果(range＜＜(y－8))≥diff0，那么x=bitsleft－y+8，否则 x=bitsleft－y+9。

以上推导并没有考虑bitsleft可能会变的小于0的问题。在一个实际的实现中，由于MV和Level的最大值是有限制的，所以相应的最大的前导1数目也是有限制的，如19，所以在执行一个前导1并行解码过程前，首先从码流中读取一定数量字节并递增bitsleft，使其长度大于最大前导1数目，这样就可以用上述算法一次解码出一个前导1符号来。

2.3 定长编码部分的并行解码

式中:/表示整数除法;%表示求余指令。在实际的实现中，由于除法运算非常耗时，考虑到range∈［0x100，0x1ff］，可以将65536 /range预先求出并存在一个整数常量 表 L［range］中，于 是 S ≈ Sappro= value0×L［range］＞＞(bitsleft+16－n)，这样就可以用查表运算和乘法运算代替除法运算。由于表示精度问题，通过这种方式计算出的value(S)可能并不能满足0≤value(S)＜(range＜＜(bitsleft－n))。于是可以对边界进行判断，如果value(S)＜0，那么递减S以至value(S)≥0，如果value(S)≥(range＜＜(bitsleft－n))，那么递增S。为了进一步减少运算量，可以设计常量表L［range］，使对于任意value，都有value0－Sappro×(range＜＜(bitsleftn))≥0，于是只需要对右边界进行判断就可以了。一般来说，这个计算过程很精确，判断部分只需要很小的计算量就能满足。

以上推导并没有考虑bitsleft可能会变的小于并行解码位数n的问题。在一个实际的实现中，如要实现一个4个二进制位并行解码模块，可以在解码前首先判断bitsleft是否小于4，如果小于，那么从码流中读入字节并递增bitsleft使其大于等于4。

2.4 算法性能分析

实验在Intel Core 2 Quad 2.5 GHz CPU上进行，DRAM为2 Gbyte。首先用CABAC编码器分别产生1 Mbyte具有不同前导1长度的码流，然后比较逐位解码和本文所述的快速前导1解码算法的性能，结果如表2所示。可以看出当前导1数目较大时，该算法相比逐位解码具有很大的优势。而当前导1数目很小时，该算法比逐位解码的要慢一些。

表2 前导1解码性能比较(基准是逐位解码)

然后比较定长解码的性能。首先用CABAC编码器产生1 Mbyte等概率码流，然后比较4符号并行解码算法和逐位解码的性能。结果表明逐位解码需要4符号并行解码算法2.51倍的时间。

3 结束语

本文针对CABAC中作为等概率符号编码的指数—哥伦布码提出了一种多二进制位并行解码算法，实验结果

表明该算法相比逐位解码具有更快的解码速度。

［1］ITU－T.ISO/IEC International Standard 14496－10 AVC［S］.2004.

［2］RICHARDSON I E G.H.264 and MPEG－4 video compression:video coding for next－generation multimedia［M］.Chichester:John Wiley ＆Sons Ltd.，2003.

［3］MARPE D，SCHWARZ H，WIEGAND T，et al.Context－based adaptive binary arithmetic coding in the H.264/AVC video compression standard［J］.IEEE Trans.Circuits and Systems for Video Technology，2003，13(7):620－636.

［4］姚栋，虞露.H.264指数哥伦布码解码部件的硬件设计和实现［J］.电视技术，2004，28(11):14－16.