摘 要：CORDIC的运算速度问题是研究的热点。为了解决CORDIC运算速度慢的问题，采用跳过零点思想，跳过输入相位值中为0的位，有效的减少了迭代次数。利用ISE仿真技术多次仿真综合。验证出改进型的CORDIC算法，在保证算法的运算精度基础上，明显地改善了CORDIC的运算速度，尤其针对于一些特殊的旋转角度，利用极少的旋转就达到结果。最终利用FPGA实现改进后CORDIC算法。
关键词：CORDIC算法; Zero-skipping; ISE； 旋转角度
中图分类号：TN911-34 文献标识码：A 文章编号：1004-373X(2011)24-0165-03
Research and Implementation of Modified CORDIC Algorithm
CHEN Jing
(Fujian University of Technology, Fuzhou 350108, China)
Abstract： With the rapid development of VLSI technology, CORDIC algorithm is widely used. A method of jumping over "0" in the input phase values is adopted to reduce the iterations effectively in this paper. The modified CORDIC algorithm was simulated with ISE simulation technology for several times. The results show that the operational speed of the modified CORDIC algorithm is obviously improved on the premise of ensuring the operational accuracy of the algorithm. The CORDIC algorithm was implemented with FPGA.
Keywords： CORDIC algorithm; Zero-skipping technology; ISE technology; rotation angle
0 引 言
CORDIC算法是一种逐渐逼近的数学方法，利用不断偏摆来逼近所需要的旋转角度。传统CORDIC算法中，每次迭代方向都必须根据上一次迭代的结果确定，也就是说每次迭代必须在上一次迭代完成以后进行，因而影响了运算速度。因此如何改进CORDIC，提高它的运算速度成为研究的重点，主要改进的思想有以下几种：一是对旋转角度进行编码来提高CORDIC的运算速度。这种方法的缺点就是要事先根据前几次运算结果来计算后几次的旋转方向，这样做的缺点就是增加了对于旋转角度的运算。二是利用Zero-skipping技术［1］跳过不必要的旋转。跳过输入相位值中为0的位对应的旋转，这样做的优点可以用一个简单的控制信号直接减少迭代次数，并且只有正向旋转［2］，从而简化旋转的方式。对于特殊角度，例如π/4，通过很少次数的旋转就已经达到该角度，即可不再进行后面的旋转［3］。这样做的优点在于原理简单，能够很快地判断是否需要再进行不必要的旋转。因此本文根据第二种思想，改进了CORDIC的算法，并利用ISE仿真综合软件验证了以上思想的实现。
1 CORDIC的基本原理
CORDIC是矢量旋转的一种迭代方法，通过一系列固定的与运算基数相关的角度不断偏摆以逼近所需要的旋转角度［4］。它的基本原理［5］如下：
初始向量V(x,y)旋转角度θ以后得到向量V′(x′,y′)：x′=xcos θ－ysin θ
y′=ycos θ+xsin θ
（1）改为：x′=cos θ(x－ytan θ)
y′=cos θ(y+xtan θ)
(2) 在硬件实现上，使θi=arctan(2－i)从而就可以将上式改进成为：xi+1=Ki(xi－yidi•2－i)
yi+1=Ki(yi+xidi•2－i)
(3)式中：Ki=cos(arctan(2－i))；di取±1，其中+1为正旋转，而-1为负旋转。Ki的乘积为比例因子K：K=∏n－1i=0Ki=∏n－1i=011+2－2i
（4） 对于N次的旋转K为常数，因此可以预先算出K，然后再进行校正。
2 CORDIC的改进
为了加快CORDIC的运算速度，该方法采用Zero-skipping技术。Zero-skipping技术的主要思想是可以跳过不必要的旋转。在每个级的计算之后加入判断，是否进入下一级的计算或是补偿输出。由此将传统的CORDIC结构改进成如图1所示的流程图。
图1 每级电路结构图图中分为3个部分，其中X，Y，PHASE的计算部分都是由移位和加减构成的。而本文中的不同就是每个部分完成本级的计算之后由一个控制信号来确定是否将该级的结果传到下一级，进行进一步的计算，还是直接终止计算，将结果传到输出端口选择器进行模校正和最后的输出。
另外本文利用剩余角度的大小作为控制信号，一旦剩余角度等于0，那么就直接停止运算，跳出旋转，得到最后的结果。所以在每一个级都会利用一个比较器将该级的剩余角度Zw的结果与0进行比较作为控制信号，如果某个级别的dn=0;那么就要结束运算。例如θ=π/4，可以通过i=0的1次迭代就可以完成。
模校正问题由于：K=∏n－1i=0Ki=∏n－1i=011+2－2i
（1）可以知道当跳过旋转时，就会使得K的值不准确。因此应该进行K的补偿。但是，一旦CORDIC的级数确定，那么就可以根据式（1）事先确定不同级数下K的值。所以本文在最后的输出之前会进行模的补偿。
3 具体实现
根据以上的流程图并以三级的CORDIC算法为例，部分程序如：
(1) 部分主程序：
always @ (posedge clk)
/*整个模块设置一个时钟，为防止冒险现象*/
begin
x0=xw0;
/*作为输入的连接端口*/
y0=yw0;
z0=zw0;
end
always @ (posedge clk or control2)
begin
if (control1==0)
/*一旦某级的控制信号使能，那么就终止此信号向下传递，而xout1=xw1;是直接输出到输出端口选择器，经其校正后输出*/
else x1=xw1;
if (control1==0)
yout1=yw1;
else y1=yw1;
if (control1==0)
zout1=zw1;
else z1=zw1;
end
(2) 输出端口选择器
当控制信号作用时，停止旋转后就要将该级的结果输出，输出前要进行对应的模校正。以三级为例输出端口的部分程序如下：
input ［15:0］ x1,x2,x3;
/*不同级的加法输出值*/
output ［15:0］ out;
reg ［15:0］ out;
input con1,con2;
always @ (con1 or con2 or a or b or c)
begin
if (con1==0)
/*通过con信号最后的选择其输出*/
out=a*（1/2）; /*第一级就输出要对应的补偿它的K值，K=1/1+22i－1*/
else if (con2==0) out=b*1/3；
/*同上*/
elseout=c;
/*没有中途终止输出就用最后一级的输出作为最后结果*/
end
本文利用Xilinx-ise软件仿真，以三级为例，综合出的结构图如图2所示。
图2中综合以后模块输入xin,yin,clk,phasein，输出端口为：xout,yout,phaseout,clk。分别代表向量的x，y坐标，以及其角度。clk代表输入时钟。并且通过内部结构图，可以看到它含有各个级别的加法器，在phaseout每一级的加法器之间加入了比较模块，生成每一级的控制信号。
本文中节约时间最重要的就是：经过控制信号使得需要的加法器置0来缩短时间在硬件实现中无法像软件设计语言那样轻易地实现跳过不必要的部分，所以只能通过提前置0来缩短程序的时间。
4 实验结果
本文用16位精度的CORDIC算法为例，采用Virtex-4型号XC4VFX12的芯片将其实现。改进前后的CORDIC算法结果列表如图3和表1所示。
从表1可以看到，虽然加入了控制信号，但是并不影响最后的精度。另外本文将改进的CORDIC算法应用到DDS频率合成器中，选用Xilinx公司的改进前后运算速度以及占有硬件资源比较如表2所示。
从表2可看出，改进后DDS的运算速度变快了。但是却由于添加了额外的控制部分由此占用了许多资源，这也是本方法的缺点之一，也是在今后的研究中要致力于改进的地方。
5 结 语
本文根据跳过不必要的旋转的思想，改进了流水线CORDIC。它能够明显地改进CORDIC算法的运算速度，并且不影响算法原来的运算精度。缺点是由于在不同级之间加入了比较器作为跳过旋转的控制信号，增加了硬件的复杂性，因此为了提高CORDIC算法的运算速度，牺牲了硬件的开销。这个也是本方法的缺点。鉴于以上的缺点，今后的工作方向可以从节约硬件开销方面入手。
参 考 文 献
［1］ 李滔,韩月秋.基于流水线CORDIC算法的三角函数发生器 [J ].电子技术应用,1999(6):52-53.
［2］ KHARRAT M W, LOULOU M, MASMOUD N, et al. A new method to implement CORDIC algorithm [C ]// Proceedings of IEEE International Conference on Electronic, Circuit and Systems. [S. l. ]: IEEE, 2001: 715-718.
［3］ LEE J A, LANG T. Constant-factor redundant CORDIC for angle calculation and rotation [J ]. IEEE Trans. on Computers, 1992, 41 (8): 1016-1025.
［4］ 宋丹.CORDIC算法在DDS中的应用 [D ].成都：电子科技大学,2007.
［5］ LIN Chun-Fu, CHEN S G. A CORDIC algorithm with fast rotation prediction and small iteration number [C ]// Proceedings of the 1998 IEEE International Symposium on Circuits and Systems. Monterey, CA , USA: IEEE 1998, 5: 229-232.
［6］ 杨宇,毛志刚,来逢昌.一种改进的流水线CORDIC算法结构［J］.微处理机,2006(4):10-14.
［7］ 周柱,张炜.基于CORDIC算法的优化的直接数字频率合成器 [D ].长沙：国防科技大学，2005.
［8］ RODRIGUES M R D, ZURAWSKI J H P, GOSLING J B. Hardware evaluation of mathematical functions [J ]. IEEE Proceedings of Computers and Digital Techniques, 1981, 128 (4): 155-164.
［9］ GOLDBERG B G. Digital techniques in frequency synthesis [M ]. [S. l. ]: McGraw-Hill, 1996.
作者简介: 陈 婧 女，1983年出生，福建福州人，硕士研究生，助教。研究方向为智能化信息处理与控制。