基于FPGA的CORDIC算法的改进及实现

摘  要： 介绍了CORDIC算法的基本原理,分析了其具体计算方法。针对利用CORDIC流水线实现FFT蝶形运算耗费资源多的问题，依据CORDIC计算迭代系数的方法改进了CORDIC流水线的结构形式，使其适应FFT算法。选用 ALTERA 公司CycloneII系列的EP2C35F672C6 来实现整个FFT 处理器，并对设计进行了时序仿真和硬件仿真。通过比较，计算结果与设计基本一致。
关键词： CORDIC；FFT；Cyclone II；流水线
   　坐标旋转计算机CORDIC(The Coordinate Rotational Digital Computer)算法是一种用于计算一些常用的基本运算函数和算术操作的循环迭代算法。其基本思想是用一系列与运算基数相关的角度的不断偏摆来逼近所需旋转的角度,从广义上讲它是一个数值型计算逼近的方法。由于这些固定的角度与计算基数有关，运算只有移位和加/减。若用传统的乘、除等计算方法,需要占用大量的硬件资源，甚至算法是难以实现的，这样就不能满足设计者的要求。CORDIC算法正是由此产生的，它仅在硬件电路上用到了移位和加/减，大大节约了硬件资源,使得这些算法在硬件上可以得到较好地实现,从而满足设计者的要求。根据它的迭代原理，CORDIC单元可以用流水线结构表示，使向量旋转并行处理，大大加快了蝶形运算的速度[1]。但是CORDIC运算单元的多级迭代也占用了大量的芯片资源，尤其是在使用多个蝶形进行FFT处理时，使用的资源是非常巨大的，为了尽量降低资源占用，对CORDIC流水线进行了结构上的改进。
1 CORDIC算法原理
     1959年，VOLDER开发了一类计算三角函数、双曲函数的算法，其中包括指数和对数运算。此算法的基本思想是用一系列固定的与运算基数相关的角度不断偏摆从而逼近所需的角度。从广义上讲它是提供一个数值计算的逼近方法。由于这些固定的角度只与计算基数有关，运算只有移位和加减。CORDIC算法虽然可以实现很多基本函数，但一开始并没有引起人们很大的注意，只是CAGGETT用它来实现二进制和十进制的转换。整个60年代没什么进展，直到1971年WALTHER提出统一的CORDIC算法，加上VLSI技术的不断发展，CORDIC算法才越来越受到人们的重视，并展示出广泛的应用前景[2]。CORDIC算法已被广泛用作现代信号处理各种算法实现中的运算单元，诸如离散傅里叶变换、矩阵的分解、矩阵特征值的求解、场分解、线性预测参数的求解等。
     如图1所示，一对直角坐标轴顺时针旋转角度A（点M相对于坐标轴逆时针旋转），点M的坐标从(x0，y0)变为(x，y)[3-6]。
   
   
     
     为了满足FFT在速度上的要求，CORDIC可以设计成流水线的形式。将需要旋转的角度加到Z0数据通道，通过Z1与固定角度相加减产生所取的值。需要旋转的(x0，y0)向量在各级迭代中旋转方向。Zn通过多次迭代，趋近于零，向量旋转到相应角度。如果在FFT的蝶形单元中用CORDIC代替复乘单元，只需要将数据的实部和虚部分别加到x0和y0通道，将复乘系数作为角度从Z0处输入，达到了乘以的目的。实际应用中将FFT使用的角度值存储在ROM中，由地址发生器控制，在计算时将相应的旋转角度读入CORDIC中即可。使用CORDIC算法可以方便快捷地计算FFT蝶形，但是由于迭代次数多，导致耗费资源也比较多。
     将CORDIC流水线形式进行改进，如图3所示，需要旋转的向量的实部和虚部分别加到X0和Y0数据通道上，系数输入到D触发器中与向量保持同步，用来控制向量在各级迭代中旋转的方向。向量经多次迭代旋转到相应角度[7-8]。
   
   3 CORDIC的旋转系数
     按照改进后CORDIC的结构，需要事先求出CORDIC的旋转系数。根据CORDIC 算法的迭代原理以及此结构的具体情况，使用 MATLAB 语言编写程序求出各级旋转系数，存在ROM中。时序仿真结果如图4所示。