基于FPGA的CORDIC算法的分析和实现

摘要：该文分析了CORDIC算法为作为硬件实现基本的运算的方法，实现了开方、正弦、余弦、乘法、除法、正切、反正切，和一些双曲函数的实现。提供了一种基于流线设计的CORDIC算法的实现，在每层流水线上都可实现6种计算，共用一个加法器。减少了硬件内部资源的使用。通过是实现的结果可以看到计算结果在水线级数STAGE+3 个CLK信号后实现了连续的实时计算结果。

关键词：CORDIC；流水线设计；共用；基本运算

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）04-0841-03

The Analysis and Implementation of CORDIC Algorithm Based on FPGA

LIU Wei-liang

（Chongqing University of Posts and Telecommunications， Chongqing 400065， China）

Abstract： This paper analyzed the CORDIC algorithm for hardware implementation of basic operation method， realized the root， sine， cosine， multiplication， division， tangent， inverse tangent， and some hyperbolic function. Provide a method based on pipeline design CORDIC algorithm， each line can be realized 6 kinds of calculation， sharing one adder. Reducing the hardware resource use. Is to achieve the results you can see through calculation results in line series STAGE+3 CLK signal after achieving a continuous real-time calculation results.

Key words： CORDIC； pipeline design； share； basic operations

1 概述

随着现代数字电路中工作频率的不断提高，计算结果要求随时按工作要求实时计算，然而在实际工作中软件语言实现的算法实时性不高，在硬件中计算数据只有加法和位移的操作。因此一种需要资源耗费小，实时性高的算法来实现工作中的基本运算。该文首先分析了CORDIC算法的基本原理，然后分别研究了几种基本运算的实现方法，几种运算的共用，最后进行了仿真和实现结果的分析。

2 CORDIC算法原理

CORDIC[1]是基于坐标旋转的数字计算方法，通过加法，位移和查找表的计算实现开方、正弦、余弦、乘法、除法、正切、反正切，和一些双曲函数。下式用极坐标分别表示了一个直角坐标系中的一个模长为[r]，相角为[ϕ]的向量，和此向量旋转[ψ]角后的另一个向量。

[x0=rcos（ϕ）y0=rsin（ϕ）] （1）

[x1=rcos（ϕ+ψ）y1=rsin（ϕ+ψ）] （2）

（2）式经过和差化积公式变换可得（3）式为

[x1=rcos（ϕ）cos（ψ）-rsin（ϕ）sin（ψ）y1=rsin（ϕ）cos（ψ）+rcos（ϕ）sin（ψ）] （3）

联合（1）式和（3）式可知

[x1y1=cos（ψ）-sin（ψ）sin（ψ）cos（ψ）x0y0] （4）

提取公因式[cos（ψ）]后得到

[x1y1=cos（ψ）1-tan（ψ）tan（ψ）1x0y0] （5）

现在假定旋转的角度[ψ]是经过多次旋转得到的，每次旋转的角度为[ψi]=[snarctan（2-n）]（n= 0，1，2，……），[sn]={-1，+1}经过这样的假设后[tan（ψ）]变换为2-n，可见经过这样的变换之后乘法运算就变成为位移操作。则（5）式可以变换下式：

[x1y1=（i=0ncos（ψi）1-tan（ψi）tan（ψi）1）x0y0] （6）

上式中[ψi]和[ψ]的关系为[ψ]=[i=0nψi]。将上式分成n次迭代动作完成，则迭代的第i次为：

[xi+1yi+1=cos（ψi）1-tan（ψi）tan（ψi）1xiyi] （7）

又根据[ψi]=[snarctan（2-n）] 可得下式：[xi+1yi+1=cos（ψi）1-si（1/2）isi（1/2）i1xiyi] （8）

式（8）中cos（[ψi]）=cos（arctan（2-i））= [11+2-2i]，经过多次累乘后得到的值收敛于一个值K，

[K=11+2-2i=0.607253] （9）

通过（6），（8），（9）可得：[x1y1=K（i=0n1-sn（2-i）sn（2-i）1）x0y0] （10）

经过足够多的迭代后可知原向量变为旋转后的向量假设Z为旋转角度，则最后输出为：

[xyz=（1/K）（xcos（ψ）-ysin（ψ））（1/K）（ycos（ψ）+xsin（ψ））0] （11）

可知当输入x=K，y=0，z=[ϕ]时。输出为x=[cos（ϕ）]，y=[sin（ϕ）]。

可知只要选取适当的方法可以使Z经过迭代足够次数后趋近到0。故选取下面的方法：

[Zi+1=Zi-Siarctan（2-i）] （12）

当[Zi]>0时，[Si]=1；[Zi]<0时，[Si]= -1。

可见此方法中旋转的是Z角，逐渐改变x，y。另一种结构是逐渐旋转y。改变x，z。可得到另一组结果：

[x=Xy=Yz=0] => [x=X2+Y2y=0z=arctan（Y/X）] （13）

通过以上的分析方法可以在线性系统和双曲系统中建立相关旋转。通过观察相互之间的关系可建立如下的通用方程[2]

[xi+1=xi-μδi（2-iyi）yi+1=yi+δi（2-ixi）zi+1=zi-δietai] （14）

圆系统：[μ]=1；[etai=arctan（2-i）]；

线性系统：[μ=0]；[etai=2-i]；

双曲系统：[μ=-1]；[etai=atanh（2-i）]；

其中输入输出关系可建立表1[3]。

式子（14）表明计算中一个迭代过程只需3次加法，2次位移，和一次查找表。这样解算在FPGA中实现是可行的，而且节省了乘法器的使用，在每次迭代的过程中可以共用一个加法器来实现6种函数的计算，减少硬件资源的的消耗。所有的迭代过程可以通过流线设计连接，可以大量节省计算的时间。单级水线结构如下图所示：

图1中Fun_mode控制选择函数系统为圆系统，线性系统和双曲系统，Rot_vec控制选择旋转坐标为极坐标和直角坐标。

本设计采用alter公司FPGA芯片，使用verilog HDL语言实现电路描述，在Quartus ii 9.0 上编译仿真。

[＼&Sin＼&Cos＼&[x2+y2]＼&Atan＼&Mul＼&Div＼&Sinh＼&Cosh＼&[x2-y2]＼&atanh＼&计算＼&0.7081＼&0.7081＼&587.82＼&0.54＼&250＼&0.6015＼&0.2608＼&1.0336＼&400.89＼&0.6948＼&理论＼&0.7071＼&0.7071＼&583.0952＼&0.5404＼&256＼&0.6＼&0.2582＼&1.0328＼&400＼&0.6931＼&]

仿真结果表明在误差允许范围内，该方案可行。

4 结束语

此算法经过修改后，成功应用在卫星信号的跟踪模块中实现了信号相位的精确计算，并且该算法具有一定的通用性，在共用一个加法器的情况下，成功的设计出了上述几种函数的计算方法，设计中采用流水线设计方法，在水线级数stage+3clk 个时钟后可连续输出计算结果，并且可以实现不同的函数。

参考文献：

[1] 杨宏，李国辉，刘立新.基于FPGA的CORDIC算法的实现[J].西安邮电学院学报，2008（1）.

[2] Xiaobo Hu.Expanding the Range of Convergence of the CORDIC Algorithm[J].IEEE TRANSACTIONS ON COMPUTERS，1991，40（1）.

[3] 耿丹.CORDIC算法的研究与实现[J].遥测遥控，2007（S1）.

[4] 王金明.数字系统设计与Verilog HDL[M].北京：电子工业出版社，2010.