适于VLSI实现的H.264的CAVLD快速有效的解析方法

摘要

本发明公开了一种适于VLSI实现的H.264的CAVLD快速有效的解析方法，包括如下步骤：将H.264标准给出的系数标记、总零数、前游程的码表重新排序，排序按照如下方式进行：以表征语法单元的比特串为输入，以对应比特串的语法单元的语义值为输出，分列码表的两边；按照表征语法单元的比特串长度，从上到下依次排序，比特串最短的排在最上面；相同长度的比特串，值大的排在上面；根据上述解析码表，按照如下方式得出对应解码码表的多叉查找树：多叉查找树的深度最浅；优先使比特串短的叶节点的深度最浅；有共同逻辑的子树合并成一个树枝；解析语法单元。本发明最快一步、通常两步、最慢也仅需要三步就能解出相应的码字，大大减小了运算量，实现了快速解码。

说明书

技术领域

本发明属于视频编解码技术领域，具体地说，涉及一种适合于VLSI实现的H.264的CAVLD快速有效的解析方法。

背景技术

随着视频编解码技术的发展，产生了许多视频编解码的标准：MPEG1/2/4、H.263/4。H.264是正在被广泛接受的、实现复杂度要比其前几个标准都复杂得多的标准。在设计H.264芯片的时候，需要对H.264算法进行优化：减小内存带宽、减小片内存储、减小运算量、减小程序等，以加快速度、节省资源。

H.264 CAVLD的任务是将H.264的二进制码流解析成有相应语义的语法单元。H.264码流的主要内容是残差距阵变换量化后的非零系数。H.264的非零系数由六个语法单元：系数标记(coeff_token)、拖尾符号标志(trailing_ones_sign_flag)、幅值前缀(level_pretix)、幅值后缀(level_suffix)、总零数(total_zeros)、前游程(run_before)来表达。参考代码给出的拖尾符号标志(trailing_ones_sign_flag)、幅值前缀(level_prefix)、幅值后缀(level_suffix)的解析方法，运算量小，这里不考虑。参考代码给出的系数标记（coeff_token)、总零数(total_zeros)、前游程(run_before)的解析方法，运算量过大，必须进行优化。比如，参考代码每解一个系数标记(coeff_token)，除预测非零系数nC>＝8外，还要对4×17的表进行遍历查找，查找次数最少1次，最多4×17次，平均(4×17+1)/2＝34.5次，并且还要解同样次数的码字，这个运算量非常大，自然导致速度很慢、效率很低，成为解码器实现的瓶颈，必须将这个运算量降下来。参考代码每解一个总系数(total_zeros)、前游程(run_before)，要平均查找解析(1+17)/2＝9次，也存在类似的速度慢、效率低的问题。

分析参考代码中系数标记(coeff_token)、总零数(total_zeros)、前游程(run_before)解析速度慢、效率低的原因，就是因为它们在编码和解码过程中使用的都是编码器的表。比如，对系数标记(coeff_token)这个语法单元，编码时通过对变换量化后的非零系数进行计数，得到总系数(total_coeff)和拖尾(trailing_ones)的值，以总系数(total_coeff)和拖尾(trailing_ones)的值为索引查表，一次查找就可以得到系数标记（coeff_token)的码长和码值，系数标记(coeff_token)就唯一确定了。而解码时还用这个码表，只能是读某个码长的码字，比较该码字的值是否与对应码长的码值相等，若不相等就要循环匹配下去，直到相等为止，这种逐个匹配的查表方法，自然速度慢、效率低。解决这个问题的方法，就是要设计解码器自己的码表及其对应的解析方法。

发明内容

本发明的目的在于，提供一种适于VLSI实现的H.264的CAVLD快速有效的解析方法，以克服现有参考代码给出的系数标记(coeff_token)、总零数(total_zeros)、前游程(run_before)的解析方法使用编码器的码表而导致的速度慢、效率低的技术问题。

为了实现上述发明目的，本发明的技术方案如下：

一种适于VLSI实现的H.264的CAVLD快速有效的解析方法，包括如下步骤：步骤一，将H.264标准给出的系数标记、总零数、前游程的码表重新排序，得到解码码表；排序按照如下方式进行：以表征语法单元的比特串为输入，以对应比特串的语法单元的语义值为输出，分列码表的两边；按照表征语法单元的比特串长度，从上到下依次排序，比特串最短的排在最上面；相同长度的比特串，值大的排在上面，值小的排在下面；步骤二，根据上述解码码表，按照如下方式得出对应解码码表的多叉查找树：多叉查找树的深度最浅；优先使比特串短的叶节点的深度最浅；有共同逻辑的子树合并成一个树枝；步骤三，解析语法单元。

本发明的上述适于VLSI实现的H.264的CAVLD快速有效的解析方法，给出了一种码字由短到长、同等长度码字情况下码值由大到小排序的解码码表，短的码字出现的频率高，因而将频率高的码字排在上面，并尽量使高频率码字的叶节点深度最低。该方法最快一步、通常两步、最慢也仅需要三步就能解出相应的码字，大大减小了运算量，实现了快速解码。

所述共同逻辑是指仅有加、减、移位运算的算术逻辑。

每一个解析码表，都具体对应着一个多叉树；每一个多叉树，都是总结具体码表的规律，设计出来的；设计多叉树的原则，就是查表最快，逻辑最少；码表的解析过程，就是多叉树的查找过程。总结多叉树的查找过程，我们将多叉树的查找分为三种情形。第一种情形的特征是，对应多叉树的码表的比特串，绝大多数有前导零，且码字由短到长变化明显。第二种情形的特征是，对应多叉树的码表的比特串，相当一部分没有前导零，且码字的长度相差不大。第三种情形的特征是，对应多叉树的码表的比特串，码字短的占相当部分，且没有前导零；码字长的有前导零，且前导零后只有比特1。

第一种情形的解析语法单元的步骤依次包括：从桶形移位器中移出0，根据读到的0的个数，进入相应的子树；若进入叶节点，该次查找结束，否则转到下一步；从桶型移位器中移出n个比特(此处n大于零，且n小于或等于码字的长度)，依据返回值，进入相应的子树；若进入叶节点，该次查找结束，否则转到下一步；从桶型移位器中移出n个比特，进入叶节点，查找结束。

第二种情形的解析语法单元的步骤依次包括：从桶型移位器中移出n个比特，依据返回值，进入相应的子树；若进入叶节点，该次查找结束，否则转到下一步；从桶型移位器中移出n个比特(此处n大于零，且n小于或等于码字的长度)，依据返回值，进入相应的子树；若进入叶节点，该次查找结束，否则转到下一步；从桶型移位器中移出n个比特，进入叶节点，查找结束。

第三种情形的解析语法单元的步骤依次包括：从桶型移位器中移出n个比特(此处n大于零，且n小于或等于码字的长度)，依据返回值，进入相应的子树；若进入叶节点，该次查找结束，否则转到下一步；从桶形移位器中移出0，进入叶节点，该次查找结束；或者从桶型移位器中移出n个比特，进入叶节点，查找结束。

附图说明

图1A是本发明的第一种解析方法的查找流程。

图1B是本发明的第二种解析方法的查找流程。

图1C是本发明的第三种解析方法的查找流程。

图2A显示的是0<＝nC<2时total_coeff和trailing_ones的解析码表及对应的多叉树。

图2B显示的是2<＝nC<4时total_coeff和trailing_ones的解析码表及对应的多叉树。

图2C显示的是4<＝nC<8时total_coeff和trailing_ones的解析码表及对应的多叉树。

图2D显示的是nC＝-1时total_coeff和trailing_ones的解析码表及对应的多叉树。

图2E显示的是nC＝-2时total_coeff和trailing_ones的解析码表及对应的多叉树。

图3A显示的是total_coeff＝1时total_zeros的解析码表及对应的多叉树。

图3B显示的是total_coeff＝2时total_zeros的解析码表及对应的多叉树。

图3C显示的是total_coeff＝3时total_zeros的解析码表及对应的多叉树。

图3D显示的是total_coeff＝4时total_zeros的解析码表及对应的多叉树。

图3E显示的是total_coeff＝5时total_zeros的解析码表及对应的多叉树。

图3F显示的是total_coeff＝6时total_zeros的解析码表及对应的多叉树。

图3G显示的是total_coeff＝7时total_zeros的解析码表及对应的多叉树。

图3H显示的是total_coeff＝8时total_zeros的解析码表及对应的多叉树。

图3I显示的是total_coeff＝9时total_zeros的解析码表及对应的多叉树。

图3J显示的是total_coeff＝10时total_zeros的解析码表及对应的多叉树。

图3K显示的是total_coeff＝11时total_zeros的解析码表及对应的多叉树。

图3L显示的是total_coeff＝12时total_zeros的解析码表及对应的多叉树。

图3M显示的是total_coeff＝13时total_zeros的解析码表及对应的多叉树。

图3N显示的是total_coeff＝14时total_zeros的解析码表及对应的多叉树。

图3O显示的是total_coeff＝15时total_zeros的解析码表及对应的多叉树。

图4A显示的是zeros_left＝1时run_before的解析码表及对应的多叉树。

图4B显示的是zeros_left＝2时run_before的解析码表及对应的多叉树。

图4C显示的是zeros_left＝3时run_before的解析码表及对应的多叉树。

图4D显示的是zeros_left＝4时run_before的解析码表及对应的多叉树。

图4E显示的是zeros_left＝5时run_before的解析码表及对应的多叉树。

图4F显示的是zeros_left＝6时run_before的解析码表及对应的多叉树。

图4G显示的是zeros_left>6时run_before的解析码表及对应的多叉树。

具体实施方式

下面根据图1A至图4G，给出本发明的较佳实施例，并予以详细描述，使能更好地理解本发明的功能、特点。

本发明的适于VLSI实现的H.264的CAVLD快速有效的解析方法，首先是要设定解析码表。

我们这里将H.264标准给出的系数标记(coeff_token)、总零数(total_zeros)、前游程(run_before)的码表按照以下特征重新排序：

1)以表征语法单元的比特串为输入，列在表的左边；以对应比特串的语法单元的语义值为输出，列在表右边。以系数标记(coeff_token)为例，当预测非零系数nC大于等于0且小于2时，当输入的系数标记(coeff_token)的比特串为1时，输出的总系数(total_coeff)和拖尾(trailing_ones的值分别为0、0；当输入的系数标记(coeff_token)的比特串为01时，输出的总系数(total_coeff)和拖尾(trailing_ones)的值分别为1、1；当输入的系数标记(coeff_token)的比特串为001时，输出的总系数(total_coeff)和拖尾(trailing_ones)的值分别为2、2；等等。

2)以表征语法单元的比特串的长度和值为依据，将表从上向下排序；比特串短的排在上面，长的排在下面；等长的比特串，值大的排在上面，值小的排在下面。还以系数标记(coeff_token)为例，当预测非零系数nC大于等于0且小于2时，系数标记(coeff_token)的比特串为1、输出的总系数(total_coeff)为0、拖尾(trailing_ones)为0，这三个数字1、0、0排在最上面，下面依次是：

    01                       1          1

    001                      2          2

    00011                    3          3

    000101                   1          0

    000100                   2          1

    000011                   4          3

    0000101                  3          2

    0000100                  5          3

    ……

然后，仔细观察重新排序的码表，寻找输入(比特串)、输出(语义值)之间的规律，给出对应各码表的多叉查找树。

多叉树遵循以下原则：

1)树的深度最浅，比特串短的叶节点的深度尽量浅。深度越浅，说明查找速度越快。以系数标记(coeff_token)为例，当预测非零系数nC大于等于0且小于2时，系数标记(coeff_token)对应多叉树的深度为3，出现概率最高的短比特串1、01、001的深度为1，大部分叶节点的深度为2，少数叶节点的深度为3。与4 x 17次的查表比，速度大大加快。

2)树的子树最少，有共同逻辑的子树可以合并成一个树枝。树枝越少，说明逻辑越少。还以系数标记(coeff_token)为例，当预测非零系数nC大于等于0且小于2时，系数标记(coeff_token)的比特串1、01、001有共同逻辑，可合并为一个树枝；比特串00000111、00000110、00000101、00000100、000000111、000000110、000000101、000000100、0000000111、0000000110、0000000101、0000000100、00000000111、00000000110、00000000101、00000000100有共同逻辑，可合并成一个树枝。附图中的虚线，与其上方相邻的实线，有共同逻辑。实线表达的多叉树，与实线、虚线共同表达的多叉树比，小了很多，逻辑就减少了很多，达到节约资源(逻辑电路)的目的。

多叉树的查找过程就是语法单元的解析过程。多叉树的查找有两个基本的操作：

     read_leading_zero_bits(max_zeros)      (1)

     read_n_bits(n)                         (2)

函数(1)从桶形移位器中移出0，若遇到1或0的个数等于max_zeros，则函数推出。

函数(2)从桶型移位器中移出n个比特。

我们通过寻找码表的规律，来确定各个码表对应的多叉树。总结多叉树的查找过程，我们将多叉树的查找分为三种情形，各情形的查找步骤将在下面详细描述。

多叉树的查找过程，就是码流的解析过程。图2A、2B、2C、2D、2E、3A、3K、3L、3M、3N的多叉树查找过程归纳为第一种情形，采用本发明的第一种解析方法。图3B、3C、3D、3E、3O、4A、4B、4C、4D、4E、4F归纳为第二种情形，采用本发明的第二种解析方法。图3F、3G、3H、3I、3J、4G归纳为第三种情形，采用本发明的第三种解析方法。

下面详细描述三个多叉树，分别对应上述三种情形的查找逻辑，也分别说明语法单元系数标记(coeff_token)、总零数(total_zeros)、前游程(run_before)的解析过程。

当4×4矩阵的预测非零系数nC＝0或1时，或者4×4矩阵是4:4:4的chromaDC时，解析语法单元系数标记(coeff_token)为总系数(total_coeff)和拖尾(trailing_ones)的多叉树如图所示。该多叉树的查找逻辑对应着本发明的第一种解析方法，该方法的查找过程如下：

第一步执行zeros＝read_leading_zero_bits(14)。当zeros＝0、1、2时，有共同逻辑：total_coeff＝trailing_ones＝zeros，移出比特1，该语法解析完成，该次查找结束。三个叶节点共用一个树枝，树枝深度为1，一步找到。

当zeros＝3、4时，有共同逻辑，共用一个树枝，执行第二步value＝read_n_bits(2)。若value＝3，则trailing_ones＝value，total_coeff＝zeros，该语法解析完成，该次查找结束，两个叶节点共用一个树枝，树枝深度为2，两步找到。若value＝2，执行第三步value1＝read_n_bits(1)。有共同逻辑：trialing_ones＝(((zeros-value)>>1)<<1)+(1-value1)，total_coeff＝trailing_ones+1+((trailing_ones+1)>>2)。该语法解析完成，该次查找结束，四个叶节点共用一个树枝，树枝深度为3，三步找到。

当zeros＝5、6、7、8时，执行第二步value＝read_n_bits(3)。有共同逻辑：trailing_ones＝3-(value&3)，total_coeff＝(zeros-3)+trailing_ones+((trailing_ones+1)>>2)。该语法解析完成，该次查找结束，16个叶节点共用一个树枝，树枝深度为2，两步找到。

当zeros＝9、10、11、12时，执行第二步value＝read_n_bits(4)。对zeros＝9的前七个叶节点，有共同逻辑：trailing_ones＝3-(value&3)，total_coeff＝6+trailing_ones+((trialing_ones+1)>>2)+((15-value)>>2)，另一叶节点有单独的逻辑：total_coeff＝8，trailing_ones＝0。对zeors＝10、11的16个叶节点，有共同逻辑：trailing_ones＝3-(value&3)，total_coeff＝9+(trailing_ones>>1)+((16-value)>>2)+((zeros-10)<<1)。对zeros＝12的八个叶节点，有共同逻辑：trailing_ones＝3-(value&3)，total_coeff＝12+trailing_ones+((value&2)>>1)+((15-value)>>2)。树枝深度都是2，两步找到。

当zeros＝13时，执行第二步value＝read_n_bits(3)。前三个叶节点有共同逻辑：trailing_ones＝3-(value&3)，total_coeff＝14+trailing_ones+((value&2)>>1)。第四个叶节点有单独逻辑：total_coeff＝16，trailing_ones＝0。叶节点深度都为2，两步找到。

当zeros＝14时，逻辑为：total_coeff＝13，trailing_ones＝1，执行read_n_bits(1)后，解析结束，叶节点深度是1，一步找到。

对2<＝nC<4、4<＝nC<8、nC＝-1、nC＝-2时，total_coeff和trailing_ones的解析逻辑、多叉树的查找过程，这里不一一描述，附图2C、2D、2E的虚实线、树枝深度，基本显示了我们所做的优化。

下面简要描述对应着第二种情形的图3B，来说明total_zeros的解析过程：

第一步执行value＝read_n_bits(3)。当value＝7、6、5、4、3时，有共同逻辑：total_zeors＝7-value。一步解析完成。

当value＝2、1时，执行第二步value1＝read_n_bits(1)，有共同逻辑：total_zeros＝10-((value<<1)+value1)，两步解析完成。

当value＝0时，执行第二步value＝read_n_bits(2)。若value＝3、2，有共同逻辑：total_zeros＝12-value，两步解析完成。若vlaue＝1、0，执行第三步value1＝read_n_bits(1)，有共同逻辑：total_zeros＝14-((value<<1)+value1)，三步解析完成。

附图3A、3C、3D、3E、3F、3G、3H、3I、3J、3K、3L、3M、3N、3O的解析与图3B解析过程类似，不一一细述。

下面简要描述对应着第三种情形的图4G，来说明run_before的解析过程。

第一步执行value＝read_n_bits(3)。当value＝7、6、5、4、3、2、1时，有共同逻辑：run_before＝7-value，一步解析完成。

当value＝0时，执行第二步zeros＝read_leading_zero_bits(7)，有共同逻辑：run_before＝7+zeros，两步解析完成。

附图4A、4B、4C、4D、4E、4F的解析过程与图4G解析过程类似，不再一一细述。

多叉树查找是由程序(逻辑电路)来实现和维持的。多叉树方法在减小运算量、加快速度的同时，却极大地增加了程序。为节约资源(逻辑电路)，减小程序又变得很有必要。仔细观察解析码表及对应的多叉树，我们会发现规律，相邻的若干个树枝，有共同的逻辑。将若干个有共同逻辑的树枝，由一个树枝的逻辑来实现，自然就减少了逻辑电路，达到了节省资源的目的。

这里的共同逻辑，一般由仅有加、减、移位运算的算术逻辑运算表达式表示。这些表达式，将在后边的具体实施方式中，针对每个多叉树的各个树枝相应给出。在附图中，有共同逻辑的若干个树枝，第一个树枝由黑线表示，其余树枝由虚线表示。

前面提供了对较佳实施例的描述，以使本领域内的任何技术人员可使用或利用本发明。对该较佳实施例，本领域内的技术人员在不脱离本发明原理的基础上，可以作出各种修改或者变换。应当理解，这些修改或者变换都不脱离本发明的保护范围。