一种适于硬件实现的算术编码算法

学术论文一种适于硬件实现的算术编码算法彭 云,任俊彦,叶 凡,周 翔(复旦大学专用集成电路与系统国家重点实验室,上海 200433)摘 要:本文提出了一种改进的Q 2co der 算术编码算法。

这种算法的主要特点包括:使用Q 表进行概率估计;采用Wi tten 等人提出的重整化方法;用移位加来代替原算法中的乘法。

采用移位加方法,可以在硬件花费较少的情况下显著提高算法的编码效率;重整化方法可以用来解决硬件实现中的进位翻转问题。

本文还对算法的编码效率提高情况作了定量分析,同时对Q 解码器进行了逻辑综合,结果表明了算法硬件实现的复杂度。

关键词:算术编码;移位加;Q 表;编码效率中图分类号:TN911121 文献标识码:A 文章编号:1000-436X(2001)02-0049-05An improved arithmetic coding algorithmfor VLSI realizationPENG Y un,RE N Jun 2yan,Y E Fan,Z HO U Xiang(ASIC&S ys te m State Key Lab,Fudan Univers tiy,S hanghai 200433,C hina)Abstr act :This paper presents an improv ed arithmetic codi ng algori th m,w hich is co me fro m the original Q 2coderscheme 1We find add 2and 2shi ft will increase the enco din g efficiency dramatically with an acceptable hardwareco mplexi ty 1On the other hand,Witten c s mechanism is used to overco me the carry 2over problem 1An analy ticalresult of o ur scheme is given in co ntrast to the original one 1A nd the sy nthesis result i s also given to sho w theperformance o btained o ver the hard ware co mplexity 1Finally,a pro to type of deco der is co mpleted to veri fy thecorrectness of our impro ved scheme 1Key wor ds :arith metic coding;add 2and 2shift;Q 2co der;encoding efficiency1 简介Shannon 最早提出的算术编码(arithmetic coding)原始概念可表述为[1]:一个码串可以看作指向某个子区间(对应特定的符号次序)的二进制分数。

Elias 把这个概念应用到对区间的连续划分中[2]。

J 1Rissanen 以LIFO 的编码形式引入[3],并由Pasco 将其改成FIFO 的形式[4]。

基本的编码和解码过程需要做乘法运算。

对于软/硬件实现而言,乘法硬件耗费大而且速度慢。

Rissanen 和G 1G 1Langdon 一起将基本算法系统化时省去了乘法[5],因而处理简单。

后来,他们又将其推广应用于二值图像编码[6]:对于二元平稳的Markov 信源,效率可高于95%。

1988年,W 1B 1Pennebaker 等人在其基础上,发表了Q 2coder [7],并将其作为图像压缩标准的一部分提交给CCI TT 和JPEG 。

Q 2coder 算法现在已经是很多图像压缩标准的重要组成部分,例如,JPEG 、JBIG 以及H 1263收稿日期:1999-08-31;修订日期:2000-12-262001年2月第22卷 第2期 通 信 学 报J OURN AL OF C HINA INS TITUTE OF CO MMUNIC ATIO NS Vol.22No.2February 2001等等。

但是由于当时半导体芯片技术的局限性,算法的编码效率还有待提高。

本文通过对原始的Q 2coder 进行分析,提出了一个改进方案。

目的是用较少的硬件代价换取编码效率的提高。

根据芯片工艺技术的迅速发展,可以预计这种方法的可行性。

本文第2节主要介绍了算术编码的基本概念以及原始的Q 2coder 算法。

第3、4节详细给出了本文的编解码方案,并给出了定量编码效率分析。

第五节对样例Q 解码器进行了逻辑综合以考察硬件实现的复杂度。

最后给出了结论。

2 原始的Q 2coder 算法Shannon 指出,一个特定的符号序列可以编码为指向一个子区间的二进制码流。

Elias 将这个概念发展成为对区间的连续划分[2]。

算术编码的思想,是Pasco 在解决区间连续划分的无限精度的问题时产生的[4]。

首先,对当前区间根据p M 和p L 的大小进行划分,其中p M (p L )是大(小)概率符号M(L)的概率值。

对符号串进行编码时,当前符号对应的概率子区间保留下来,做为下次的当前区间。

如果当前符号是大概率符号M,小概率符号L 的概率值p L 加到码流上,使其指向新的区间的下限。

在算术编码的算法中,我们一般约定:A,代表当前区间的大小;C,代表码流或为当前区间的下限。

那么算术编码的递归算法可以归纳为表1。

表1算术编码的递归算法如果编码符号是M如果编码符号是L A i+1=A i *p MC i+1=C i +A i *p L A i+1=A i *p L C i+1=C i如果下一个符号不存在则编码完成。

最后得到的区间下限作为符号串编码得到的码流输出。

而解码端则按照上面的算法逆向得到解码符号流如表2。

表2解码符号流如果编码符号是M如果编码符号是L A i+1=A i -p LC i+1=C i +p L A i+1=p L C i+1=C i考虑到增量输出和固定精度问题,硬件实现的时候要进行重整化。

在Q 2coder 算法方案中,每次将A(s)重整到区间[0175,115)。

然后作近似A(s)~1,同时就可以去除基本算法中的乘法:Q 编码算法采用固定的Q 表来确定概率值(这也是Q 编码器名称的由来)[8]。

Q 表相当于一个状态机:如果L PS 出现,则L PS 计数值为1,M PS 计数值仍太小以致不能产生一M PS 重新归一化。

由此引起估计状态变化到更大的L PS 概率估计。

因此,如果发生M PS 重新初始化,则L PS 计数值仍为0,这导致向更小的L PS 概率估计变化。

假设M PS 和L PS 转向最接近的状态,则将状态机平衡于一L PS 概率估计,这里,M PS 和L PS 重新归一化的概率大致相等。

3 进位翻转问题但是,重整化和部分输出又带来了实现过程中的另一个问题)))进位翻转(carry 2over)问#50#通 信 学 报 2001年题。

有时,当A(s 0)加到码流C(s)上时,一个加法进位会传播出固定精度的q 个比特,需要修改已经部分输出的部分,这样就造成了进位翻转问题。

进位翻转问题可以采用所谓比特填充(bit stuffing)的方法加以解决[6]。

它的基本思想是,设置一个字长为v 比特的缓冲寄存器,用以保存最近的v 比特码字。

若这v 比特全为/10,则在最后一个/10的后面插入一个/00以/阻塞0连续进位。

译码时,要不断监测移入该缓冲寄存器的v 比特码字,进行相应的处理。

在本文中采取与上述有所不同的重整化方法。

它基于Witten [9]等人提出的方法。

主要思想是:如果当前区间离1/2点很近,又跨越了1/2,不能使当前区间太小。

重复执行如下的重整化步骤,直到循环中止。

u 如果新的区间不完全属于区间[0,1/2),[1/4,3/4)或[1/2,1)中的任何一个,退出循环,并返回u 如果新的区间属于[0,1/2),输出0以及由f ollow 计数标明的所有的1;然后把区间大小加倍,将区间[0,1/2)线性映射到[0,1)u 如果新的区间属于[1/2,1),输出1以及由f ollow 计数标明的所有的0;然后把区间大小加倍,将区间[1/2,1)线性映射到[0,1)u 如果新的区间属于[1/4,3/4),我们把f ollow 计数加一,记录这个事实以备将来使用;然后把区间大小加倍,将区间[1/4,3/4)线性映射到[0,1) 如果我们对Langdon 的比特填充方法[6]进行仔细的研究,可以发现,需要填充比特的情形就是上面提到的当前区间跨越1/2的情形。

上面的这种机制在完成重整化的同时,也起到了防止进位翻转的作用。

4 移位加方案及其编码效率在较近的算术编码算法中,移位加(shift 2and 2add)的概念更加普遍[10~12]。

与上面简单的近似相比较,移位加明显地提高了编码的效率,当然,硬件实现更复杂。

对于一个硬件解码器而言,总是要对编码效率和硬件复杂度做折衷考虑。

由于芯片制造工艺技术的迅速发展,可以允许设计者选择比以前更为复杂的硬件实现来提高编码效率。

在本文的设计中,把移位加的概念同传统的Q 编码器结合起来,力求得到反映当代技术的编码/解码器。

经过Witten 等人的重整化机制之后,区间大小A 被重整到区间[0125,1)。

我们可以做一个近似:A U b,使b =i j [A <0128125[A <0134375[A <0140625[A <0146875[A <0153125[A <0159375[A <016875[A <018125[A <0190625[A <019687596875[A <1#51#第2期 彭云等:一种适于硬件实现的算术编码算法这样,A *p L U b *p L =p L *2i ?p L *2j =(p L n i)?(p L n j)乘法运算就被转化为移位运算和加减运算,而这些运算,都是较易于用硬件实现的。

下面,我们对使用移位加的编码效率做一个解析的分析。

在理想情况下,根据Shannon 的信息论[1],平均码字长度li,为li =-p L log 2p L -p M log 2p M我们可以把使用的近似,归纳到上述式子中la =-p L log 2pa L -p M log 2pa M其中,la 指实际的平均码字长度,pa 指考虑了上面的近似后使用的实际概率,pa 可以写为子区间和当前区间的大小之比,或pa L =A(s L)A(s) pa M =A(s M)A(s)那么,la =-p L log 2A(sL)A(s)-p M log 2A(sM)A(s)某个算法的编码效率降低D 可以定义为D =la -li由于我们进行两种使用Q 表算法的对比,我们可以假设:从Q 表得到的概率就是理想概率。