CORDIC算法在DSP算法硬件实现中的应用进展

1、收稿日期:2002-04-15CO RD I C算法在D SP算法硬件实现中的应用进展CORD I C A lgor ith ms Appl ica tion s and D evelop m en ts i n D SP Hardware Rea l iz i ng李岩1 L i Yan1汪海明1W ang H ai m ing1郭士德2Guo Sh ide2赵建业1Zhao J ianye1余道衡1Yu D aoheng1(1北京大学电子学系声场与声信息处理国家重点实验室北京100871;2北京大学遥感所北京100871 (1D ep1of E lectronics,N at1L ab1o

2、f M ach ine Percep ti on,Pek ing U niversity,Beijing,1008712,Ch ina;2T he Institute of R e mo te Ssensing and G IS,Pek ing U niversity,Beijing,100871,Ch ina摘要CORD I C算法被广泛应用于数字信号处理算法的硬件实现中。由于它将许多复杂的算术运算化成简单的加法和移位操作,因此它在许多D SP算法的硬件实现中都有着极为重要的意义。有了它,许多难于实现而又极具应用价值的算术函数的硬件实现成为了可能。本文首先介绍了CORD I C算法的理论概要

3、,然后给出了CORD I C算法在国内外的应用现状。最后,给出了作者自行设计的基于CORD I C算法的可参数化的FFT模型。关键词数字信号处理CORD I C算法硬件实现CORD I C算法(T he Coo rdinate Ro tati onal D igi2 tal Com pu ter是V o lder等人于1959年在美国航空控制系统的设计中提出来的,它是一种用于计算一些常用的基本运算函数和算术操作的循环迭代算法,其基本思想是用一系列与运算基数相关的角度的不断偏摆从而逼近所需旋转的角度1。从广义上讲它是一个数值性计算逼近的方法,由于这些固定的角度与计算基数有关,运算只有移位和加减。

4、可用该算法来计算的函数包括乘、除、平方根、正弦、余弦、反正切、向量旋转(即复数乘法以及指数运算等。1971年, J1S1W alther提出了统一的CORD I C算法形式2,把圆周旋转、双曲旋转和直线旋转统一到同一个CORD I C迭代方程里,为同一硬件实现多功能提供了前提。随着VL S I技术的不断发展,CORD I C算法越来越受到研究与应用人员的重视,更加展示出广泛的应用发展前景。在传统的硬件算法设计中,乘、除等基本数学函数运算是一种既耗时又占用面积大的运算,甚至有时是难以实现的,CORD I C算法正是为解决这种问题而产生的。它从算法本身入手,将其分解成为一些简单的且在硬件中容易实现

5、的基本算法,如加法、移位等,因此使得这些算法在硬件上可以得到较好的实现。又由于该算法是一种规则化的算法,它满足了硬件对算法的模块化、规则化的要求,因此CORD I C算法可以充分发挥硬件的优势,利用硬件的资源,从而实现硬件与算法相结合的一种优化方案。正是由于上述原因,CORD I C算法的原始思想一经提出,就受到了人们的普遍关注,40年来人们不断地对其进行探索研究,并提出了各种改进算法和优化方案以适应各种不同的需求35。我们觉得有必要介绍并讨论这一算法,使国内注意到CORD I C算法的这一新的发展动向。1COR D I C算法理论概要下面简要介绍一下CORD I C算法理论。设输入为x in

6、,y in,z in,参数为m,则CORD I C算法如式(1所示:x i+1=x i+mii y iy i+1=y i+mii x iz i+1=z i+ii(1式(1中当m=-1时,i=tanh-1(i;当m=0时,i=i;当m=1时,i=tan-1(i。AbstractW ith the increased dem and of h igh density,h igh speed board designs,signal integrity si m ulati on is becom ing mo re i m po rtant1Cadence A llegro is just the

7、 too l that can m eet the need1It delivers an econom ic front to back advanced environm ent fo r the physical design of comp lex m ulti-layer PCB designs1T h is paper m ainly introduces how to using th is too ls1 Keywordsh igh speed PCB,A llegro file change,signal integrity si m ulati on作者简介李新男,西安电子

8、科技大学研究生,研究方向:计算机系统结构。58x1=x in;y1=y in;z1=z in其中i表示循环的次数,其范围是1N;i可取1或-1,其值由x i、y i、z i的符号决定;i取值为2-i;m为参数,可取0,-1,+1。当m取0时,最后得到的函数称为线性函数;当m取1时,得到的函数为平方函数;当m取-1时,得到的函数为立方函数。这3种函数的具体形式在文献6中已经给出。2COR D I C算法硬件实现研究的国内外现状近年来,由于现代电子技术的飞速发展,对电子系统的速度和体积的要求也越来越高,实时快速已经成为电子领域发展的一大趋势。在信号处理领域,用硬件来实现以往通常用软件来完成的设计思

9、想已经在国内外悄然兴起,并逐渐为广大电子工程师所接受。众所周知,许多软件算法包含着复杂的算术运算,用硬件实现起来十分困难。而CORD I C算法正是为解决这种问题而产生的,它将许多复杂的算法化成简单的加法和移位操作,从而,使许多难于实现而又极具有应用价值的因此也是急需解决的算术函数的硬件实现成为了可能,尤其在微电子技术的巨大成就的鼓舞下,人们更增加了对CORD I C算法D SP硬件实现的兴趣。应用CORD I C算法,国内外已经用硬件实现了许多D SP算法。这里,将主要论述CORD I C算法的应用。211国外的研究现状由于CORD I C算法实现硬件算法的有效性,它一提出,就得到了广泛的应

10、用。国外的研究人员利用CORD I C算法,许多数字信号处理算法(如:快速傅立叶变换,小波变换,离散余弦变换,离散H artley变换,各种滤波器等已经用硬件得到实现。另外, CORD I C算法还应用于许多实际的问题中,如特征向量分解(SVD,用于并行特征值计算的雅可比算法,医用超声波图像相位补偿系统,人工神经网络,超声波波束发生器,QAM,频率合成,A D转换等,凡是涉及到实时高速,联系到硬件的地方,几乎都可以看到CORD I C算法的身影。(1离散傅立叶变换与快速傅立叶变换众所周知,傅立叶变换的应用极其广泛,尤其对于离散傅立叶变换(D FT中快速傅立叶变换(FFT应用更加广泛。以前的FF

11、T多用软件编程实现,缺陷是速度慢,实时性差,影响了工作效率。但自1959年CORD I C算法提出至1971年J1W alther完善后,人们对傅立叶变换的硬件实现做了大量的研究,在减少硬件的复杂性,提高运算速度和精度的前提下,提出了许多实用可行的方案,但几乎在每种方法中都要用到CORD I C旋转算法。近年来,随着VL S I技术的飞速发展,也出现了利用CORD I C算法实现FFT 的新技术。1994年,R1Sar m ien to等人利用018m的砷化镓技术实现了16位复数据的1024点FFT7。工作频率为1GH z。1998年,R1Sar m ien to等人又在原来的基础上利用016

12、m的砷化镓技术实现了16位复数1024点FFT,此时工作频率超过700M H z,运算时间小于8s8。2000年,又出现了用CORD I C实现FFT的新算法9。(2参数化正交小波变换中的CORD I C技术在小波变换的参数化设计中,实现网格滤波器(lattice filter的旋转变换时用到了CORD I C算法,具体的应用过程简述如下:要实现小波变换的参数化,就需要确定变换的参数空间,小波变换的参数空间由旋转角构成,而这些旋转角用于网格滤波器中的正交2乘2旋转来实现小波变换的级连。由旋转角组成的参数空间表示出了正交小波变换的不同特性,即参数不同,所做出的小波函数所具有的性能也不一样。它被限

13、制在简单正交旋转所给出的旋转角的集中。实践表明,正交2乘2旋转是CORD I C算法中一个必要的递归步骤。网格滤波器是实现小波变换的重要组成部分,用网格滤波器组(lattice filter-bank可以实现所有的正交小波变换。理论与实验表明,假如实现网格滤波器的所有旋转角之和恒为-45,即存在:kk=-45(2网格滤波器实现的就是一个小波变换,而与旋转角的个数和大小无关10。(3离散余弦变换离散余弦变换(DCT在信号处理中有着广泛的应用,如图像处理的JPEG、M PEG、H261压缩,话音编码以及时分复用和频分复用的系统中都要用到DCT变换,在这些处理中,DCT算法的实时、快速问题一直困绕着

14、人们。为了解决这一问题,研究人员对DCT算法的硬件实现作了大量深入细致的研究11。在国外,一维和二维DCT变换已经得到实现,实现的方法很多,但它们多数是基于CORD I C脉动处理器阵列结构的。上面简要介绍了几个国外利用CORD I C算法的例子,除了以上几个CORD I C硬件实现的例子外,国外还利用CORD I C算法完成了许多实际问题,如已经完成多种实用滤波器的设计,并且,研究人员正不断地探索新方法来改进实现方法,如CORD I C自适应网68格滤波器,低灵敏度正交数字滤波器,A RM A滤波器, II R数字滤波器,自适应滤波器实现方法等1214。在这些应用中,CORD I C处理器都

15、被用作基本的旋转模块。另外,CORD I C算法还在神经网络、相位补偿等系统中应用,具体原理这里不在赘述。总之,近年来,随着微电子技术的发展,国外对CORD I C算法的研究已经成为一个热点。212国内的研究现状与国外相比,国内对CORD I C算法的研究和应用起步较晚,虽然取得了一定的成果,但是和国外相比还有一定的差距,仅仅实现了一些较简单的应用,复杂算法的实现还是一个盲点。就目前已经发表的论文来看,大体有以下几方面的应用:三角函数发生器,优化数学算法(如把算法中的复杂的平方和立方运算化为加法和平移操作,快速傅立叶变换(FFT等,下面,分别加以简要介绍。(1三角函数发生器在数字信号处理中,高

16、速高精度的三角函数发生器有着广泛的应用。传统的实现方法是采用查表、多项式展开或近似的方法。这些方法在速度、精度、简单性和高效方面不能兼顾。而用CORD I C算法实现的三角函数发生器能很好的兼顾这几个方面,并且极适合于VL S I实现15。具体算法及流程如下:由式(1可知,在m=+1的情况下,CORD I C 公式最后的迭代结果为:x n=x0co s z0-y0sin z0;y n=y0co s z0+x0sin z0;z n0(3如给定x0=K+1,y0=0,迭代结果为:x n= co s z0;y n=sin z0;z n0其中K+1成为模校正因子,值为11+2-2i,对于字长一定的运算

17、,它是一个常数。所以,将所需产生的角度值作为z0的输入,迭代结果输出x n和y n就是需要的三角函数值。(2G I V EN S算法的优化在阵列处理技术中,经常需要对一个数据矩阵X 进行变为上三角阵R的处理,这时就要寻求酉阵Q (QQ H=I,而这种酉阵可由一系列的G I V EN S旋转实现,标准的G I V EN S旋转包含开方运算,在满足一定的精度和稳定性的情况下,运算量相当大,因而最好寻求无开方的处理形式。用CORD I C算法可以实现上述目的,具体的算法流程参见文献16。(3快速傅立叶变换(FFT目前,在国内FFT的实现方案中,也要用到CORD I C算法,但一般是利用CORD I

18、C旋转器完成与旋转因子的相乘17。以上探讨了CORD I C算法在国内的三个应用,除了这些,CORD I C算法还应用在许多其他的方面,如i预测,坐标变换,离散余弦变换(DCT,R-变换等,这里不在赘述。从这些结果我们可以看到,在我国,对于CORD I C算法的研发工作仅仅涉及简单的算法实现和简单的应用,还远远落后于国外。然而,这是个用于硬件实现的关键理论和技术,所以我们有必要对其加以介绍,引起人们的重视,促进这方面研究的发展。3可参数化的FFT模型我们利用CORD I C算法自行设计的一个可变参数的FFT核心函数。它以16为底数,可在点数为N=2m (m=410之间自动切换。其结构框图示于图

19、1。下面,对核心函数的几个关键模块做简要的说明。31116点的FFT模块在图1中,包含有4个16点的FFT运算模块。在进行参数设定时,即进行点数的选择时,核心函数根据所设定的参数选定被启动的16点FFT运算模块的个数。例如,当要进行点数为48的FFT时,可选中4个模块中的任意3个模块来进行并行运算。再如,若要实现点数为256的FFT运算,可将4个16点的FFT运算模块一起选中,使得这4个模块一起并行工作。根据前面的高点数的FFT的公式,可以看出,对于256点的FFT的运算,只有4个点数为16的FFT 运算模块一起工作,还没有达到完全高度并行流水的效率。之所以这样选择是由16点FFT的运算量和硬

20、件的结构和容量来决定的。在实际运行时,可以将256个点的数据分为16组,每组16个复数数据点。然后,先取头4组的第一个数据,将它们送入核心函数模块中进行运算;然后,再取5到8组的第一个数据,送入运算模块中进行运算;这样依次类推;当循环完一次后,再取头4组的第2个数据进行运算,这样循环下去直到所有256个点的数据都进行完一次蝶形变换。接下来,再进行第二次蝶形变换运算,过程同上。根据运算量的粗略估计,4个16点的FFT运算模块的运算量还在硬件可承受的范围之内,如果个数进一步提高,硬件恐怕就难以承受了;另外,选中16点的运算模块作为较大点数的基本运算模块可以使得运算模块个数尽可能减少,从而减少了控制

21、模块的控制任务量。78图1可变参数的FFT核心函数312小点数的FFT运算模块图1中所示的小点数的FFT运算模块包括2点、4点、8点的FFT,由于点数较小,所以实现起来比较容易,可以在可编程逻辑器件中占用较小的面积来实现。建议在小点数的FFT的算法实现中,如果用到乘法时,采用高效的乘法器结构,以减小硬件的运算负荷量,减小结构的复杂性。在前面所述的过程结束后,对于点数少于256个点的FFT运算,控制模块发出信号启动小点数的FFT运算模块,然后地址映射模块发出相应的地址信号从RAM中取出数据,将其送入小点数的FFT运算模块中进行运算。313CORD I C处理器CORD I C处理器是专门为点数不

22、能分解为两个互为质数的因子的乘积的FFT而设定的。它用于对输入的复数数据点进行任意角度的向量旋转。在这里建议使用位串行的CORD I C处理器,以减轻硬件的复杂性。对于这类FFT运算,当16点的FFT运算结束后,控制模块发出信号启动CORD I C处理器,然后地址映射模块发出相应的地址信号从RAM中取出数据,将其送入处理器中进行向量旋转运算。还要说明一点的是,对256点、512点、1024点的FFT,还要第二次启动16点的FFT模块;对于512、1024个点的FFT,还要在第二次运行16点的FFT完毕后,第二次启动小点数的FFT模块。上述内容是关于可参数化FFT核心函数大体结构的设计。它是以实

23、际工作结果和经验为基础做出的设计,因此无论从硬件的结构上还是从语言的实现上以及速度与面积的比率上都具有可行性。目前,图1中的16点的FFT模块已经利用A tera公司的FL EX10K为目标器件,在M A X+PLU S II软件上用V HDL语言得到实现,其他的模块尚在研究中。4结论与展望CORD I C算法是一种循环迭代算法,主要用于在复杂角度旋转的情况下,把旋转运算转变为加减和移位运算。在数字信号处理算法硬件实现的情况下,用途极其广泛。随着微电子技术的突飞猛进,近十年来,尤其是小波变换的快速算法提出以来,CORD I C算法在D SP硬件实现中的研究已经形成了新的热潮。由于D SP算法的

24、CORD I C硬件实现不仅需要算法自身的改进和优化,而且还和微电子技术的发展水平以及数字信号处理理论和技术水平息息相关。可以这样说, CORD I C算法、微电子技术和信号处理技术的有机结合,将在未来信息社会中起到巨大的作用。目前,我国上述领域的发展水平与国外还有较大的差距。因此,我国相关行业应该统筹规划,在“十五”计划期间加大资金投入,组织协同攻关,使我国在D SP算法的硬件实现方面尽快赶上国际先进水平。参考文献1V o lder J E1T he CORD I C T rigonom etric Com p u ting T echn ique I R E1T ran s1on E le

25、ctron ic Com pu ter,Sep t, 88 19592YU H en H u1on the convergence of the CORD I C adap tive lattice filtering(CAL FA lgo rithm1IEEE tran sac2 ti on on signal p ro sessing,V o l146,N o17,Ju ly,1998,186118713T so b ing,Juang,H siu feng lin1CORD I C algo rithm fo r vecto ring m ode w ithou t con stan t

26、 scaling fac2 to rs1E lectron ics letters110th June,1999,V o l135,N o112:9719724E lisardo A n telo,Tom as,Javier B ruguara DB1V ery h igh radix circu lar CORD I C:V ecto ring and un ified ro2 tati on vecto ring1IEEE tran sacti on on com pu ter,V o l1491N o17,Ju ly,2000,7277395Cheng Sh ing W u,A n Ye

27、u W u1M odified V ecto r Ro tati onal CORD I C(M V R-CORD I CA lgo rithm and A r2 ch itectu re1IEEE tran sacti on on circu it and system II:analog and digital signal p rocessing,V o l48,N o16, June,2001,5485616X iaobo Ronald H u,H arber G,Steven B ass C1Expanding the range of Convergence of the CORD

28、 I C of the CORD I C A lgo rithm1IEEE T ran sacti on s on Com pu ter,1991(40:13207Sar m ien to R,E sh ragh ian K1I m p lem en tati on of a CORD I C P rocesso r fo r CFFT Com pu tati on in Gallium A r2 sen ide T echno logy1P roc1of the Eu ropean D esign and T est Conference P roc Eu r D es T est Conf

29、1994,Pub l by IEEE,Com p u ter Society P ress,L o s A lam ito s,CA,1994,2382448Sar m ien to R,Flix Tobajas,et a l1A CORD I C P rocesso r fo r FFT p u tati on and Its I m p lem en tati on U s2 ing Gallium A rsen ide T echno logy1IEEE T ran sacti on s on V ery L arge In tegrati on System,1998,6(1:18 3

30、09Jen chuan,sau Gee chen1A fast CORD I C algo rithm based on a novel angel reco rding schem e1ISCA S2000-IEEE In ternati onal Sym po sium on circu it and system1Geneva,Sw itzerland,2000,621624110Peter R ieder,Jrgen Go tze,Jo sef N o ssek A,et a l1Param eterizati on of O rthogonal W avelet T ran sfo

31、r m s and T heir I m p lem en tati on1IEEE T ran sacti on s on C ircu it and System-:A nalog and D igital Signal P rocess2 ing,1998(45:21722611R ao K R,Y i p P1D iscrete Co sine T ran sfo r m1N ew Yo rk:A cadem ic11990,488212Sh inich i sh iraish i,M ik i HA seyam a,H ideo K Itaji m a1A h igh ly accu

32、 rate p i pelined arch itectu re fo r a CORD I C A RM A lattice filter1ISCA S2000-IEEEin ternati onal Sym po sium on circu it and system1 Geneva,Sw itzerland,2000,36937213Jun M a,Keshab,p arh i K,et a l1Efficien t i m p lem en tati on s of P i pelined CORD I C B ased II R D igital filters u sing Fast o rthogonal u ro tati on s1IEEE tran sacti on on signal p rocessing1V o l148,N o19,Sep tem ber,2000, 2712271614L ijun Gao,Keshab,Parh i K1H ierarch ical P i p elin ing and Fo ldi