CN1267853C

CN1267853C - 同步流水算术编码器的vlsi实现方法

Info

Publication number: CN1267853C
Application number: CN 200410026019
Authority: CN
Inventors: 梅魁志; 郑南宁; 刘跃虎; 姚霁; 王勇
Original assignee: Xian Jiaotong University
Current assignee: Xian Jiaotong University
Priority date: 2004-04-07
Filing date: 2004-04-07
Publication date: 2006-08-02
Anticipated expiration: 2024-04-07
Also published as: CN1564196A

Abstract

本发明属于VLSI设计技术领域，在图像压缩或视频处理的硬件实现中，提供一种同步流水算术编码器的结构设计和其中关键电路设计，具体实施例为JPEG2000芯片中使用的是基于上下文的自适应算术编码器，可实现在N+3个时钟内编码N个输入。为达到上述目的，首先将JPEG2000协议中的算术编码器的流程转化为三步流水线结构和辅助步骤，对流水线中的第2步和第3步提出算法级的优化；提出连续CX输入下的Qe表的index选取逻辑，使用组合逻辑实现的寄存器A的首个非零位检测电路，对第二步和第三步采用多种方法对其关键路径优化，具体的优化结果可满足在.25um工艺下200M时钟的要求。

Description

同步流水算术编码器的VLSI实现方法

技术领域

本发明属于VLSI设计技术领域。具体涉及到在图像压缩或视频处理的硬件实现中的一种同步流水算术编码器的VLSI实现方法。

背景技术

在JPEG2000标准中使用的是基于上下文的自适应算术编码器，但是标准中所提供的流程比较适用于软件的串行实现，在JPEG2000芯片的开发中，如使用标准中的流程，用状态机来实现算术编码器，则至少需要4个时钟编码一个输入，加上byteout，则需要6-7个时钟。M.Tarui在“High speed implementation ofJBIG Arithmetic coder”[1]中提出了使用pipeline来实现JBIG中的算术编码，主要通过改进的Qe表来实现CX表的更新，Keng-Khai在”A high throughput context-based adaptive arithmetic codec for JPEG2000”[2]中在使用流水线设计的同时，提出了一种bitstuffing流程，并给出概要结构设计，K-F.Chen在“Analysis andarchitecture design of EBCOT in JPEG2000”[3]在给出概要结构设计同时，提出将寄存器C(以下称CREG)分成16位和12位以减少关键路径，但[1]主要针对JBIG中算术编码器，且修改Qe表增加了存储器，为4步流水线；[1][2][3]并没有给出关键电路和CX表的操作，同时没有考虑算术编码器流水的完整实现所必须考虑的关键路径的优化、关键电路实现和辅助步骤。

发明内容

根据上述情况，本发明目的在于，提供一种同步流水算术编码器的VLSI实现方法，该方法给出了同步流水算术编码器完整的结构设计和关键电路实现和关键路径的优化。

实现上述目的的技术解决方案是：同步流水算术编码器的VLSI实现方法，按以下步骤进行：

1)首先将JPEG2000协议中的算术编码器的流程转化为三步流水线结构和辅助步骤(协议中的flush流程，见JPEG2000的协议Figure C-11)

2)对三步流水线中的第二步和第三步提出算法级的优化。

3)提出一种连续CX下的Qe表的索引(index)获取方法；这种方法使得并不需要对Qe概率表进行修改。

4)提出一种使用组合逻辑实现的寄存器A的首个非零位检测电路，以加速流水线第二步的实现。

5)对第二步和第三步采用多种方法对其关键路径优化。

所述三步流水线和辅助过程是指将算术编码器的整个流程按实现过程分为四个操作：Cx表的查询，Qe表的查询和qe值的读取(第一步)，寄存器A的更新、寄存器C的低20位更新和CX表的更新(第二步)，寄存器C的更新和字节输出(byteout)(第三步)，和一个辅助过程(flush)，以完成最后的字节输出，如图1所示。

由于在流水线的第二步和第三步中，组合逻辑的路径比较长，因此首先需要在算法上进行优化，以减少关键路径。

按协议中的流程规定，在编码时首先查询CX表，再由CX表得到的Qe表的地址索引查出编码时所需的qe值，再由编码所走的分枝决定CX表的当前CX表项的更新值，因此连续CX输入时的Qe表的index的选择是限制算术编码器流水实现的一个关键所在。

在编码过程中，当寄存器A(16位bit)的值小于0X8000H时，需要对A归一化(协议中的Renorme，见Figure C-8)，即左移A，直到A值大于0X8000H，因此为了使其在单时钟内完成，首先需要检测A需要左移的位数，如A＝16’b0001，0100，1000，0001时，A需要左移三位，即要确定A从左算起的首个1前的0的个数，定义为A的零位检测电路，在此给出此实现的组合电路。

在解决以上问题后，为使同步流水算术编码器真正实用，需要对第二步和第三步的主关键路径进行优化，以得到最短的关键路径，目标是在算术编码器的完整的实现中，在25的TSMC的库下，在Synopsys DC的综合下可达到200M。

本发明是一种JPEG2000中的算术编码器的同步流水线VLSI实现方法，实现了算术编码器的1个时钟编码1个输入，并给出了实现的结构设计和关键电路。

附图说明

图1是传统算术编码器流程的简单叙述图；

图2是算术编码流程中step3的说明图；

图3是step3转化为3步流水线结构图；

图4是stage2的流程图；

图5是流水线第三步的主关键路径图；

图6是byteout的实现算法级优化流程图。

具体实施方式

以下结合附图和发明人给出的实施例对本发明作进一步的详细说明。

JPEG2000的算术编码器的流程简述；

step1：INITENC：初始化编码时调用的寄存器

step2：读入CX(context label)，D(0，1)

step3：编码(ENCODE)，在编码中需引入RENORME。

CODEMPS条件：

((D＝0)&(MPS(CX)＝0))||((D＝1)&(MPS(CX)＝1))

CODELPS条件：

((D＝1)&(MPS(CX)＝0))||((D＝0)&(MPS(CX)＝1))

step4：FLUSH，编码结束后将REGC和缓存中的数据输出。

step3的流程如图2所示，当A＜0X8000H时，需对A左移以归一化，以使A＞＝0X8000H，同时在CT为0时，编码码流输出至缓存中(byteout)。可见，一个完整的编码过程至少需要4个时钟周期，如需归一化，则另外需要5、6个时钟，若再加上byteout，则要再加上一到两个时钟，如果对n组(cx、d)进行编码，由于这是串行实现，平均需要6*n个时钟。

本发明的目的在于克服CX表的更新和RENORME流程所中断流水线，使算术编码在step3中能流水实现。下面结合附图和实施例对本发明进一步详细说明，但本发明的关键电路和方法不限于这个实施例，可适应其他算术编码器。

按照本发明的技术方案，发明人给出了本发明的实施例。在本实施例中使用的是JPEG2000标准中MQ算术编码器流程，采用了三步流水线结构，使算术编码能够流水实现，即对连续输入的CX、D输入，对其能进行连续的编码，从而得到连续的输出，则只需N+3个时钟就可以完成对N组输入的编码，在N值足够大时，可完成一个时钟一个输入。

然而，要实现算术编码的流水实现，以下问题成为实现的关键：

首先是CX表并不是一成不变的，它是根据上一个编码的结果进行更新的，这样在下一组(CX，D)输入的时候，上一次的更新结构还未输出，此时查表计算会出错；

其次是byteout操作，并不是每次编码都要进行，所以CODEMPS和CODELPS编码、归一化、甚至有时还有byteout操作，这都要在2个时钟内完成，需要对处理过程进行一些变化和处理才能实现，下面分别讨论这些问题。

1.Qe表索引的获取：

在算术编码的过程中，CX表能否正确及时的更新，是正确编码的必然条件，由图3，我们可以看出，CX表的更新只能发生在第三个时钟，所以在连续的3个CX中，如果CX两两不等，那么在第三个时钟再更新CX表并不影响后面输入的查询，但是如果有相等的情况，CX表还未更新时查表得到的index值就不正确。

在算术编码的流水线结构中，因为CX表的内容并不重要，参与运算的只是qe值，只要能得到连续正确的index值，进而得到连续正确的qe值，则无需考虑CX表是否已经进行了更新。所以，CX表两两不等时，index为查表得到的结果，当有两个连续的CX相等时，index不等于CX的索引值，而是根据对上一个CX编码时所用的TYPE(编码类型)直接选择index＝nmps、nlps或上一个index的值，如果间隔一个相等的话，那么第三个index就直接等于由第一个cx得出的nmps、nlps或index。下面详细说明index的取值(为了便于说明，加上n，n+1，n+2角标表示在实际中的时间顺序)：

假设在CLK_n时的输入为CX_n(CX₁～CX_n没有连续相等的)，用Cx_n-1_reg1表示CX_n-1延时一个时钟的值；

在CLK_n+1时的输入为CX_n+1(假设CX_n+1＝CX_n)，INDEX1_n已产生(为查询CX表的输出值INDEX0_n)；此时CX_n_reg1(CX_n值延时一级)不等于CX_n-1_reg2(CX_n-1_reg1值延时一级)，则此时的INDEX_n为查表得出的INDEX1_n；因此可由INDEX_n查询qe表得到正确的输出：NMPS_n、NLPS_n、SWITCH_n、Qe_n；

CLK_n+2时钟的输入为CX_n+2(假设CX_n+2＝CX_n+1且CX_n+2！＝CX_n)，而此时刻，上次输入为CX_n+1时，INDEX1_n+1为查询CX表的输出值INDEX0_n+1，因此时CX表未进行更新，此时的INDEX1_n+1并不是实际所需的索引值；此时由于CX_n+1_reg1(CX_n+1值寄存一级)等于CX_n_reg2(CX_n_reg1值寄存一级)，则根据第n次编码类型为CODEMPS编码或CODELPS编码可选择出输入n+1时刻的INDEX_n+1的值为NMPS_n_reg1、NLPS_n_reg1或INDEX_n_reg1中的一个；又由INDEX_n+1查询qe表输出：NMPS_n+1、NLPS_n+1、SWITCH_n+1、Qe_n+1；CLK_n+3时钟的输入为CX_n+3；同样可根据第n+1次的编码类型为CODEMPS编码或CODELPS编码可选择出输入n+2时刻的INDEX_n+2的值为NMPS_n+1_reg1、NLPS_n+1_reg1或INDEX_n+1_reg1中的一个；又可由INDEX_n+2查询qe表输出：NMPS_n+2、NLPS_n+2、SWITCH_n+2、Qe_n+2；

……

依次类推，可以处理连续输入的CX值相等的输入，对于间隔一个相等的情况不再赘述，详细的index查询更新逻辑如下：

　　always@(posedge clk)

　　if(cx＝＝cx_reg2)    //间隔一个CX相等的情况

　　     if(CODEMPS)

　　        begin

　　           if(a-qe＞＝0X8000)

　　              index1＜＝index_reg1：

　　           else

　　              index1＜＝nmps_reg1；

　　        end

　　    else      index1＜＝nlps_reg1；

　　else index1＜＝index0；

　　always@(敏感变量全体)

　　if(cx_reg1＝＝cx_reg2)    //连续两个CX相等的情况

　　      if(CODEMPS)

　　            if  (a-qe＞＝0X8000)

　　                   index＝index_reg1；

　　            else

　　                   index＝nmps_reg1；

　　      else

　　                   index＝nlps_reg1；

　　else index＝index1；

[注]：index0为查CX表得出的索引值，

index1实际中为DFF，INDEX在实际中为WIRE型变量。

2.REGA的0位检测电路

在stage2(流水线第2步)中当A更新后，在此阶段对A左移，以使A＞＝8000H，为此需要确定REGA的左移位数shiftbit[3..0]，再进行左移。

下面是其门级电路的伪代码：

if(A15|A14|…..|A8)＝1

shiftbit[3]＝0；

else shiftbit[3]＝1；

if ((A15|A14|A13|A12)＝1)&(shiftbit[3]＝0)

shiftbit[2]＝0

else if(A7|A6|A5|A4＝1)||(shiftbit[3]＝1)

shiftbit[2]＝0

else shiftbit[2]＝1

共分四步，相当于二叉树状搜索来确定左移位数，这样在得到shiftbit时的组合门延时相对较短。

3.C的拆分

将28位的C拆分成C[19:0]和C[27:20]，在CLK3：输入Qe，，TYPE(1为CODEMPS，0为CODELPS)，输出C[19:0]，A，在这里，REGC[19:0]和A一样都完成了与Qe的运算以及移位操作，作为正确的输出进入下一次运算。

而C的高8位和C的低20位和Qe相加而得到的进位位，只参与到byteout运算，可以在下一个时钟进行运算。

4：流水线第三步的主关键路径

在算术编码器的流水线的第三步，除了要做CODEMPS(或CODELPS)编码外，还要进行左移(归一化)以及byteout操作，因为可能遇到连续两次byteout的情况。这样使得关键路径加长，必须对关键路径进行优化。

在流水线的第三步输入REGC的高8位，和C的低20位和Qe相加而得到的进位位CARRY，CT和SHIFTBIT先比较以确定第一次左移的位数，如果不需要进行第一次BYTEOUT，直接得到下一步操作所需的新的C的高8位，否则要进行第一次BYTEOUT，再判断二次BYTEOUT过程，最后根据两次BYTEOUT的结果再进行第二次左移操作，以得到下一步操作所需的新的C的高8位，同时在BYTEOUT过程中输出编码字节，如附图5所示。

5.详细的byteout的处理

在算术编码器的流水线实现中，最为复杂的是归一化以及byteout了，因为可能遇到连续byteout两次的情况。虽然byteout可以在流水线外执行，但是归一化必须在一个时钟内完成，byteout其过程会改变CT、C的值，就会影响流水线的正常运算。

在type＝0(CODEMPS编码)，当a-qe＞＝0X8000时协议规定不需要进行归一化操作，实际上此时已计算出shiftbit＝0，可看作shiftbit为0的归一化操作，只不过归一化前后的值不变，因此归入shiftbit＜CT的情况统一进行归一化操作。下面分别讨论需要归一化时的操作(变量说明见附录1)：

●shiftbit＜CT，这时仅需要归一化，而不用进行byteout这时tempct＝ct-shiftbit

●shiftbit＞＝CT，这时不但需要归一化，而且要进行byteout操作先进行第一次归一化，对c先移ct位，进行byteout操作，得出第一次byteout后得到的tempc1、tempct1(8 or 7)

此时归一化还未做完，还需要移的位数为(shiftbit-CT)

●如果(shiftbit-CT)＜tempct1，那么tempct＝tempct1+ct-shiftbit，无需进行第二次byteout

●如果(shiftbit-CT)＞tempct1，还需要进行第二次byteout对tempc1先移tempct1位，得到tempc2，进行byteout操作，得出第二次byteout后的tempc3，tempct2(8 or 7)

那么tempct＝tempct2+tempct1+ct-shiftbit

详细的流程见图4。

五优化工作

1.流水线的第二步优化，如图4所示

按原流程存在串行的16位减法(A＝A-Qe)，16位比较器(A、Qe)和16位加法(C＝C+Qe(I(CX)))，在时间成为设计的约束后，将串行流程尽可能改为并行流程。

修改后的流程可以如下：

1^at op(operation)：A＝A-Qe A1＝A-2Qe C1＝C+Qe

2^nd op：根据编码流程选择A值(A2)和C值(C2)

3^rd op：左移位数确定

4^th op：同时左移A2和C2

其中用A1的高位发生借位与否来进行A-Qe与Qe的大小比较，使A1与A并行执行，这样关键路径大为减短。

2.移位的操作

流水线第二步中，执行的操作比较多，为了提高运行速度，加上shiftbit的输出是按高位到低位的顺序依次出现的，所以移位时，可以根据shiftbit的每一位分别进行。

C1temp＝C2＜＜shiftbit[3]

c2temp＝cltemp＜＜shiftbit[2]

c3temp＝c2temp＜＜shiftbit[1]

C3＝c3temp＜＜shiftbit[0]

这样依次左移，其中c1temp，c2temp，c3temp为中间变量，“＜＜”在此用二选一的多路选择器实现。

3.逻辑的简化

实际上a的取值只有可能为qe或者(a-qe)，对协议上的运算逻辑进行化简，可得到以下代码if((type＝＝0&&a_sub_2qe[16]＝＝0)||(type＝＝1&&a_sub_2qe[16]＝＝1))

al＝qe；else al＝a_sub_qe；

【注】a_sub_2qe＝{1’b1，a}-2*qe，a_sub_2qe[16]相当于a-qe与qe的大小比较结果。

文中所用的变量或符号意义说明：

A A 当前的概率区间

B B 压缩数据缓存输出字节

BYTEOUT 算术编码的输出至缓存操作，详细过程见协议

BYTEOUTC 第一次归一化后将要进行第一次BYTEOUT的C值

C CT 移位计数器

CX 即context为计算出的和D对应的上下文

CODEMPS MPS编码类型

CODELPS LPS编码类型

D D D是经分层编码后的数据

DFF

E

F FLUSH 算术编码的结束操作，详细过程见协议

G

H

I index 概率表的索引值

INITENC 算术编码的初始化操作，详细过程见协议

J

K

L

M MPS 用于上下文的大概率的判断

MQ

N NMPS 下一个MPS的索引值

NLPS 下一个LPS的索引值

O

P

Q QE 概率

R RENORME 算术编码的归一化操作，详细过程见协议

S SETBITS 算术编码的结束操作，详细过程见协议

SWITCH 索引值的标志

SHIFTBIT A的左移位数

T TYPE 表示编码类型，0为CODEMPS，1为CODELPS

TEMPC 计算C的中间变量

TEMPC1 第一次BYTEOUT后得出的新的C值

TEMPC2 第一次归一化后将要进行第二次BYTEOUT的C值

TEMPC3 第二次BYTEOUT后得出的新的C值

TEMPCT 计算CT的中间变量

TEMPCT1 第一次BYTEOUT后得出的新的CT值

TEMPCT2 第二次BYTEOUT后得出的新的CT值

Claims

1.一种同步流水算术编码器的VLSI实现方法，包括结构设计和其中关键电路设计，按以下步骤进行：

1)首先将JPEG2000协议中的算术编码器的流程转化为三步流水线和辅助过程，将算术编码器的整个流程按实现过程分为四个操作：

第一步：CX表的查询，Qe表的查询和qe值的读取；

第二步：寄存器A的更新、寄存器C的低20位更新和CX表的更新；

第三步：寄存器C的更新和字节输出；

辅助过程：以完成最后的字节输出；

2)对三步流水线中的第二步和第三步提出算法级的优化

流水线的第二步步骤主要包括4个顺序操作：

第一个操作为三个并行的加或减法：A-Qe，A-2Qe，C+Qe；

第二个操作根据编码流程从A-Qe，Qe中选择A值，从C+Qe和C中选择C值，

第三个操作：利用在4)中提出的寄存器A的首个非零位检测电路，来确定左移位数

第四个操作：利用此左移位数对A和C做左移已得到新的A和C，在一个时钟沿到来时，用新的A和C来更新寄存器A和C的值；

流水线的第三步步骤最终化为以下顺序操作：

操作1：C的高8位和第二步的进位位加法，以及第一次任意位左移位数确定；

操作2：第一次任意位左移；

操作3：第一次byteout；

操作4：第二次byteout；

操作5：第二次任意位左移；

3)任意CX输入下的Qe表索引的选取的逻辑如下：

设n，n+1，n+2分别表示连续3次输入CX下的流水线的时间角表：

当CX_n≠CX_n+1≠CX_n+2时

index_n，index_n+1，index_n+2依次为查询CX表得到的结果index₀

当CXn＝CXn+1≠CXn+2，

index_n+1不等于查询得到的index₀，而是根据TYPE_n即编码类型和A_n-qe_n的值在nmps(index_n)，nlps(index_n)，index_n中选择一个；

当CXn＝CXn+1＝CXn+2时，

则index_n+2不等于查询得到的index₀，而是根据TYPE_n+1即编码类型和A_n+1-qe_n+1的值在nmps(index_n+1)，nlps(index_n+1)，index_n+1中选择一个；

当(CXn＝CXn+2)≠CXn+1，

则index_n+2仍然是根据TYPE_n即编码类型和A_n-qe_n的值在nmps(index_n)，nlps(index_n)，index_n中选择一个；

4)提出一种使用组合逻辑实现的寄存器A的首个非零位检测电路，以加速流水线第二步的实现；

5)对第二步和第三步采用关键路径优化

其优化的方法如下：

[1]移位的操作

假设shiftbit是需要左移的位数，C2是需要左移的数，当shiftbit的输出顺序，其在组合电路内部的稳定顺序为C2＞shiftbit[3]＞……＞shiftbit[0]，则按以下方式左移，速度最快：

C3＝(((C2＜＜shiftbit[3])＜＜shiftbit[2])＜＜shiftbit[1])＜＜shiftbit[0]

“＜＜”在此用二选一的多路选择器实现；

[2]当a_sub_2qe＝{1’b1，a}-2*qe，用a_sub_2qe[16]判断a-qe与qe的大小比较结果；

[3]将C拆分成C[19:0]和C[27:20]

其中结构设计和关键电路设计和关键路径的优化为一个整体，目的为了保证可实现在N+3个时钟内编码N个输入，具体的优化后的电路在.25um工艺下的工作时钟为200M的要求。