CORDIC算法在FPGA中的实现

1、微处理机M I CROPROCESS ORS大规模集成电路设计、制造与应用C ORD I C 算法在FPG A 中的实现王智霞,王广生(北京工业大学电控学院,北京100022摘要:CORD I C 算法是在许多角度计算方面有着广泛应用的经典算法,通过考虑FPG A 的结构、精度局限和速度要求,采用流水线技术(p i peline ,在FPG A 上用CORD I C 算法实现了对于大吞吐量数据的向量倾角的计算,并对实际应用中内部步骤寄存器精度的选取给出了较为详细的方法。关键词:坐标旋转数字计算;FPG A;流水线中图分类号:T N4文献标识码:B 文章编号:1002-2279(200701-0

2、004-04FP GA B a sed R ea li za ti o n o f CO RD I C A l go rithmWANG Zhi -xia,WANG Guang -sheng(B eijing university of technology,B eijing 100022,China Abstract:CORD I C algorithm is a classic algorith m with many app licati ons .Considering the archi 2tecture,p recisi on and s peed of FPG A ,the p

3、i peline technol ogy is used in computing large number of vect or angle values .This article p r ovides the way of confir m the wide of inner p r ocessing register .Key words:CORD I C;FPG A;Pi peline1引言FPG A 以其灵活性和使用方便在现今的数字领 域已经得到了广泛的应用。但FPG A 实现数字系统也有其自身的局限性,其一是器件资源的门阵列规模的限制,其二是单元延迟限制,所以,这就需要设计者充分

4、考虑器件的实际工作能力。角度的旋转计算在数字领域尤其是数字通信领域是一种应用非常广泛的计算,如果用传统的除法器、乘法器等计算方法,需要占用大量的FPG A 资源,这样就不能满足设计者的要求,需要设计者考虑其他的算法实现这种类型的计算。CORD I C 算法在硬件电路的实现上只用到了加法器和移位器,这样就大大节约了FPG A 的资源,从而可以满足设计者的要求。2CORD I C 算法简介CORD I C (Coordinate Rotati on D igital Computer , 又名:坐标旋转数字计算,是J.Voider 等人于1959年在设计美国航空导航控制系统的过程中提出来的一种算法

5、。下面就简要地介绍一下CORD I C 算法的基本数学思想。如图1所示,向量逆时针旋转度角得到向量OB ,这个关系可以用矩阵表示如式11:X j Y j=cos -sin sincos X i Y i=cos1-tan tan1X i Y j(1图1向量旋转坐标图如果假设是由n 个n 角度叠加而成的,那么根据式(1得出每一步的叠加操作需要按照式(2行X n +1Y n +1=cos n1-tan ntan n 1X n Y n(2利用式2经过n 步叠加可以表示由向量旋转到向量OB ,如下表示:X j Y j =cos 0cos 1.cos n1-tan 0tan 01.1-tan n tan

6、n 1X i Y i(3作者简介:王智霞(1980-,女,北京人,硕士研究生,主研方向:嵌入式系统设计与实现,大规模集成电路系统设计,数字通信。收稿日期:2005-02-23第1期2007年2月No .1Feb .,2007王智霞等:CORD I C 算法在FPG A 中的实现由于计算机进行计算采用二进制形式,所以我们选取n =arctan (12n ,这样选取n 方便了tan n 的计算,即tan n =S n 2-n,式3前面的cos n 可以取累乘的极限即:K =n =0cos n =n =0cosarctan (12n 0.607253如果我们在设计的系统中提前计算K,那么当抛开K 不

7、算时,式(2就可以表示成式(41: X n +1Y n +1=1-Sn 2-nS n 2-n1X n Y n =m i =0S i i (S i =-1,1(4至此,我们可以得出结论,由向量OA ,在先计算K 的情况下,我们可以由式4逐步的计算旋转角度后得出向量OB 。计算的精度由n 的大小决定,式(4中的S n 由每一步的具体情况而定。3CORD I C 算法的应用利用CORD I C 算法可以进行许多运算,比如计算角度正弦、角度余弦、复数的乘法、向量的角度和模的运算等等。下面就介绍两种CORD I C 算法的实际应用实例:(1已知:角度,求:cos ?这个问题我们可以转换为利用CORD I

8、 C 这种向量旋转的思想进行解析,建模如下(见图2: 图2向量旋转坐标图起始向量OA 为X i ,Y i ,i =1,0,0终止向量为X j ,Y j ,j =cos ,sin ,由OA 经过n 步旋转到OB ,即可以得到cos设:Zn 表示经过n 步旋转后,得到的结果与的差值,即:Z n =-ni =0i ,通过这样的假设,就可以得到:S n =1Zn 0-1Z n =0X (n +1=X (n -Y (n 2-nY (n +1=Y (n +X (n 2-nZ (n +1=Z (n -arctan (2-nE LSEX (n +1=X (n +Y (n 2-n Y (n +1=Y (n -X

9、 (n 2-nZ (n +1=Z (n +arctan (2-n(2已知:点A (X i ,Yi ,求:向量在坐标系中的倾角?这个问题我们可以转换为利用CORD I C 这种向量旋转的思想进行解析,建模如下(见图3:图3坐标系旋转图如图3所示,为了方便对角度的计算,我们旋转了一下坐标轴,可以推断出起始向量OA 为X i ,Y i ,Z i =X i ,Y i ,0终止向量OB 为X j ,Y j ,Z j =R,0,-设Z n =n =0n ,就可以得到:S n =1Y n 0-1Y n 0(6将式(4和式(6结合,就可以得到它的逻辑表述:I F Y (n =0X (n +1=X (n -Y

10、(n 2-n Y (n +1=Y (n +X (n 2-nZ (n +1=Z (n -arctan (2-nE LSEX (n +1=X (n +Y (n 2-n Y (n +1=Y (n -X (n 2-nZ (n +1=Z (n +arctan (2-n4CORD I C 的FPG A 实现下面就上述的第二种应用实例,描述一下用veril og 语言实现CORD I C 算法的具体步骤和实现方法。(1系统要求接口类型和精度1输入X Y 的精度为(11,10,T :10位整数、无小数位的有符号数。2输出角度为Z,Z 为弧度值的前的系数,精度为(8,1,T :6位小数、1位整数的有符号数,它5

11、1期微处理机的范围是(-1,1。3系统的接口,见表1,其中clk 为80MHz表1cordic 模块的接口表接口名称长度类型clk 1I N rst 1I N enin 1I N xin 11I N yin 11I N okout 1OUT zout8OUT(2计算中间寄存器宽度的选取分析系统要求的输入X 和Y 的精度和输出的Z的精度进行比较,可以分析出,输出和输入的精度不对称,即:Z 的精度为(8,1,T 对应的最小可以表示的角度为2.8125X Y 的精度为(11,10,T ,对应的可以表示的最小的角度为:45-arctan (10221023=0.028017可见,输入和输出误差的允许值

12、相差非常远,这样就得到了两种精度的分析。1如果允许输出的角度Z 的最后一位不准确,那么可以以2.8125为精度进行分析,分析如下:假设计算中用到的角度精度为(9,0,T ,即:8位小数,1位符号位的值,这个值与z 值相同,都表示弧度值的前的系数,小数位的最高位表示1/4(45度,所以它能表示的最小角度为0.3515625度。根据上述假设,arctan (2-n可以表示为下表2:表2arctan2-n 值实际值取值计算值误差arctan 1/226.5650500000000100110026.718750000000.1537arctan 1/414.036240000000001010001

13、4.062500000000.02626arctan 1/87.125020000000000101007.0312*.09377arctan 1/163.57633000000000001010 3.515624500000.060706arctan 1/321.789910000000000001011.757812500000.032097误差合计0.366533从表2中我们不难看出,由于arctan (2-n用精度为(9,0,T 表示,有部分的误差,误差的最大合计为0.366533度,这样可以得出如下结论:用(9,0,T 表示中间计算的角度寄存器的精度,运行5步叠加结果的最大误差为:0

14、.366533(前者的误差+1.78991(后者的误差=2.156443度上述计算出的最大误差为2.156度,小于2.8125度,符合z 的精度范围,计算结果只会在最后一位上与z 的真实结果有出入,误差在允许范围之内。2如果不允许输出角度Z 有任何的偏差,6位小数位必须全部准确,那么需要用0.028017精度进行计算,分析方法同上,最后得出的选取中间计算角度的精度是(15,0,T ,即:14位小数,1位符号位的值,这个值与z 值相同,都表示弧度值的前系数,小数位的最高位表示1/4(45度,需要进行12步计算,这个过程要比第一个过程需要增加数倍的资源,而且速度会明显变慢。根据综合后的经验得知9位

15、加法器的延迟时间大约为3ns,而16位加法器的延迟时间大约为5ns,系统输入的clk 为80MHz,周期为1/80MHz =12.5ns,16位加法器(X n Y n 的计算的延迟时间可以满足clk 的速度,所以考虑到运算速度的要求,使用第一种精度和步数选取结果,即:Z n 的精度为(9,0,T ,5步迭代运算。(3 一个计算过程的处理一个计算过程的实现步骤如图4所示。图4计算过程步骤图1由于系统要求输入点A (X,Y 的范围为4个象限,而文章的二.2中讲述的方法只是针对象限的,所以我们需要在开始的计算前判断点A (X,Y 所在的象限,并将它转换到象限;另外,由于我们是判断Y (n 正负来确定

16、S (n 的正负,角度小于45的角,角度的变化对于Y 值的影响比较明显,所以如果所求向量角度在4590度的范围内,需要先将X 和Y 互换,转换到045度的范围内进行计算,这样可以减少误差。下面介绍一个具体的例子,说明一下具体的变换过程:如图5已知点A 在第三象限,经过变换后变换到第一象限变成(-X,-Y ,经过判断-X -Y,以45度为对称轴进行对称操作得到最终的变换结果(X ,Y 为(-Y,-X 。2对于得到的向量进行5步的迭代过程:每一步的迭代过程需要对X (n 和Y (n 进行除法操作,下面详细说明一下带符号数的除2的倍数操作。X =b1b2b3b4b5bn (b1代表符号位X /2m=

17、b1b1b1(共M 个b2b3b n -m +1例如:实现运算-56/4=-14-56=1111100100062007年王智霞等:CORD I C算法在FPG A中的实现-56/4=1111110010=-143这步与第一步形成了对应的关系,如图5所示,这一步的作用是将在第一象限计算出来的角度转换成,步骤正好与步骤一中的相反。图5象限转换图示首先,判断第一步是否进行了以45度角分界线为轴进行的对称操作,如果进行了,则将角度转换为2-;其次,判断第一步判断的点(X,Y在第三象限,所以最后的结果=-2-。(4由于这种角度运算多数应用在通讯领域的FPG A设计中,通讯领域要求计算的数据吞吐量非常大

18、,所以在这里引入了流水线技术进行数据的处理。上述已经说明,完成一个完整的运算需要7个子操作过程。所以我们就设计了7重叠的一个流水线,如图6所示。第一个clk上升沿时,数据1进行预先步骤处理,第二个clk 上升沿时第二个数据进行预先处理,同时数据1进行第一步处理,到第七个clk时一共同时处理7个数据,但是这7个数据在不同的步骤状态下。这样就可以实现如果大数据量需要计算时,一个clk最多可以同时处理7个数据,大大提高了数据的吞吐能力。图6流水线示意图5总结经过综合工具I SE的综合后得出:最大延时为6.50ns时占用资源为4500。延时和占用资源符合系统要求,此模块可以良好地运行。FPG A有着规

19、整的内部逻辑阵列和丰富的连线资源,特别适合于数字信号处理任务,相对于串行运算为主导的通用DSP芯片来说,其并行性和可扩展性更好。但长期以来,FPG A一直被用于系统逻辑或时序控制上,很少有信号处理和数字通信方面的应用,其原因主要是因为在FPG A中缺乏实现一些象CORD I C这样的,可以通过数字电路完成数学运算的有效结构。现在这个问题正逐步得到解决,使FPG A在数字信号处理方面有了长足的发展,也使CORD I C这种经典算法得到更广泛的应用。参考文献:1R ichard Herveille.Cordic Core Specificati onE B/OL.htt p:/.2李波.80位嵌入式超越函数运算器的设计J/OL.计算机工程与科学,2004(12:52-57.3夏宇闻.复杂数字电路与系统的veril og HDL设计技术(第一版M.北京:北京航空航天大学出版社,1998-08.(上接第3页5结束语多核、多线程处理器技术具有普通单核、单线程处理器所未有的性能优势,目前已成为提高处理器性能的主要途径,同时,多核、多线程处理器也为很多的应用领域提供了新的解决方案。发挥出多核处理器硬件的优势,需要从编译器技术,操作系统及其它系统软件的架构上来加以发掘。这个全新的领域为我国发展系统软件带来了机遇和挑战。如何面对这