CORDIC算法

2024-06-04

CORDIC算法（通用7篇）

CORDIC算法篇1

1 CORDIC迭代算法简介

CORDIC[1,2]主要应用于直角坐标与极坐标的数值相互转换,其在特征值,快速傅里叶运算[3]的定点运算[4,5]有重要意义。CORDIC迭代算法的基本原理如图1所示:

初始向量V0逆时针旋转角度θ后得到向量V1,则V0与V1存在数学关系(1):

在实际的工程应用中,所有浮点数据都需要转化为二进制数据在计算机处理,为方便运算取每一次旋转的角度θi正切值为2的倍数,即θi=tan-1(2-i),则迭代运算式可以表示为公式(2):

其中di表示矢量旋转的方向,取-1表示朝逆时针方向旋转,取1表示朝顺时针方向旋转。很多研究已经证明,对于迭代次数大于6的CORDIC运算,基本收敛于一个常数,这样上式的运算在计算机处理中就可以用简单的加法和移位来实现了。简写迭代公式并引入角度分量可以得到公式(3):

其中i=0,1……N-1,N为最大迭代循环数;arctan(2-i)=θ(i),迭代完成后需要在X,Y上分别乘上KN。整个旋转过程可以表示为一系列与旋转角度集相关的角度不断偏摆,从而不断逼近所需旋转角度的循环迭代过程。这样CORDIC算法基本上可以实现数学运算中所需的函数运算。

2 两种模式迭代算法

CORDIC算法最初主要用于平面直角坐标系(X,Y)和极坐标系(R,θ)之间的自由坐标变换,其迭代算法有两种操作模式:旋转模式迭代[6]和向量模式迭代[7]。旋转模式为将极坐标数据转换为直角坐标数据,而向量模式则将直角坐标的数据转换为极坐标数据。

2.1 旋转模式

旋转模式下,设定初始值(X0,Y0)=(R,0),Z0=θ,dn=sign(Zn),,当N→∞时,Zn→0。经过n次迭代后的三个累加器结果

由等式(4)得到极坐标系(R,θ)到平面直角坐标(X,Y)的转换。由于迭代只支持第一象限的转换,为支持四个象限的矢量都能转换到平面直角坐标,需要将初值转换到第一象限。其原则是根据表1进行初值变换,转换到第一象限。

旋转模式迭代流程如图2:首先设置好初始值,随后更新迭代次数n,根据公式更新Xn,Yn,dn以及Zn的值,这里更新Zn的值需要查表法来计算。接着可以根据Zn的值与门限阀值比较,如果Zn小于或者等于门限阀值,则停止迭代。当然这里也可以设置迭代次数,当迭代次数达到设置的值后,强行停止迭代。完成迭代后,Xn与Yn分别乘以Kn,更新得到极坐标对应的数据。

2.2 向量模式

向量模式是将平面直角坐标的数转换为极坐标的数,在向量模式下,首先设定初始值(X0,Y0),Z0=0,,当N→∞时,Yn→0。经过n次迭代后的三个累加器结果

由此得到平面直角坐标(X,Y)到极坐标系(R,θ)的转换。向量模式算法实现流程如图3,同样为在向量模式下支持四个象限的平面直角坐标都能转换到极坐标,当X0<0,需要多重复两次i=0的迭代运算。开始迭代流程如下:首先设置好初始值,随后更新迭代次数n,根据公式更新Xn,Yn,dn以及Zn的值,同样这里更新Zn的值需要查表法来计算。与旋转模式一样在这里更新Zn的值需要查表法来计算。但与旋转模式不一样,向量模式里迭代次数是根据Yn的值与门限阀值比较,如果Yn小于或者等于门限阀值,则停止迭代。当然这里也可以设置迭代次数,当迭代次数达到设置的值后,强行停止迭代。完成迭代后,Xn与Yn分别乘以Kn,更新得到直角坐标对应的数据。

3 仿真与结论分析

在进行CORDIC定点算法仿真前,首先需要建立一个查找表如2(LUT)存储角度值θ(i)。下表以定点位宽N=14为例,在旋转模式下进行不同迭代次数仿真。

CORDIC为移位相加算法,每一次迭代需要两次移位(2-i),一次查找表(查θ(i)),三次加法(di为符号系数)。

对CORDIC算法来说,一个粗略的精度估计为:K位精度需要K次迭代[8]。图4对不同迭代结果的误差进行了对比。从仿真结果可发现,14位精度的定点运算,迭代10次到12次,运算误差都在千分之一以上。而迭代14次或者15次,误差基本都在千分之一以下,且迭代14次与15次性能大部分点重合。因此在保证CORDIC定点性能前提下,最小迭代次数可以选择与精度位数相同的次数进行迭代。

4 结束语

从算法流程可知,快速傅里叶蝶形算法中旋转因子计算中,ROM不直接存储旋转因子的值,而是存储少量的单位旋转角度值,再通过CORDIC流水线循环迭代,得到所需的旋转角度值θ;无需复数乘法器,每步运算可分解为简单的移位、相加来完成;为了保证CORDIC计算精度,需要考虑旋转因子位宽与迭代次数关系,如果迭代次数多大,影响CORDIC运算的复杂度,次数不足,则影响CORDIC运算的精度。本文仿真验证了迭代次数与位宽的关系。当然后续也可以利用门限阀值对迭代性能做进一步研究。

摘要：在实际的工程应用中,经常需要计算角度的三角函数运算,比如计算流水线型快速傅里叶变换处理器蝶形运算中的旋转因子,采用CORDIC迭代加法器,性能与直接采用乘法器相比性能损失很小,但可以大大节约数字面积。CORDIC的定点化运算中,迭代次数是算法的重要指标之一,其关系到算法的复杂度及计算误差。算法迭代次数与要求的数据精度相关,该文将实现CORDIC算法的旋转模式,利用迭代不同次数得到的值与精确值的误差进行比较来确定CORDIC算法需要进行的迭代次数。这样在节约计算量的同时,保证计算精度不受较大影响,从而在节约计算量的前提下保证CORDIC算法的性能。

关键词：CORDIC,定点化算法,旋转模式,向量模式

参考文献

[1]Andraka R.A Survey of Cordic Algorithms for FPGA BasedComputers[C].Proceedings of the ACM/SIGDA 6th Internation-al Symposium on Field Programmable Gate Arrays(FPGA'98),1998.

[2]耿丹.CORDIC算法研究与实现[J].论文与技术报告:2007(S1):39-40.

[3]彭清兵,李方军.基于CORDIC算法的FFT处理器设计[J].工程应用技术与实现,2011(23):208-209.

[4]孙明革,陈靖.CORDIC算法在定点DSP中的应用[J].吉林化工学院学报,2012(5):61-62.

[5]Martin Uhlmann,Keshab K P.A high-speed CORDIC algo-rithm and architecture for DSP application[J].IEEE,2005,52:1-5.

[6]Granado J,Torralba A,Chavez J,et al.Optimization ofCORDIC cells in the backward circular rotation mode[J].AEU-International Journal of Electronics and Communications,2007,61:337-340

[7]王建军,徐力,安鹏.基于CORDIC的频偏估计幅角计算算法[J].技术与方法,2014(7):77-78.

[8]梁源,王兴华.一种基于贪婪算法的CORDIC改进算法[J].电讯技术,2014(3):313-314.

CORDIC算法篇2

关键词：算法,正切余切函数,FPGA

1 CORDIC算法

C O R D I C算法是坐标旋转的方法,假设初始坐标为,旋转角度后,得到终点坐标为,如图1所示。由三角函数可知,得如下公式:

分别称为圆周旋转运算、双曲旋转运算和线性旋转运算,然后根据取值的判读方式,CORDIC算法结构可分为旋转模式和向量模式。当m取不同的值时,即可得到三种不同计算方式,并在各种计算方式下通过多次迭代,三角函数、实现乘法、除法、指数、双曲函数、开方及对数等运算。

2 Cordic算法正切余切函数的模块设计

2.1 系统设计

系统采用圆周Cordic与线性Cordic相结合的方式实现正、余切的运算,如图2所示。

2.2 算法结构及RTL综合电路(图3)

3 仿真验证

对整个Tan Ctg Calcu Sys系统模块选用了Xilinx Virtex-4的器件。各个计算模块能够较为精确地获得角度的正切余切计算结果。图4是Modelsim上的仿真波形。

图5描绘了内,从理论值与计算结果的对比曲线可知,理论值和仿真结果是非常的接近。

4 硬件实现

通过上述在综合软件上的对比分析,将子模块内部在FPGA上仿真验证。下面是子模块Verilog HDL主要代码。

参考文献

[1]孔德元.针对正弦余弦计算的CORDIC算法优化及其FPGA实现[D].中南大学硕士论文,2008.P.1-P.3.

[2]Xiaobo Hu,Ronald G.Harber,and Steven C.Bass,Expanding the Range of Convergence of the CORDIC Algorithm,IEEE Trans.on Computers,[J].vol.40,no.1,1991.Jan.P.13-P.21.

CORDIC算法篇3

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

2 CORDIC算法原理

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

(2)式经过和差化积公式变换可得(3)式为

联合(1)式和(3)式可知

提取公因式cos(ψ)后得到

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

上式中ψi和ψ的关系为。将上式分成n次迭代动作完成,则迭代的第i次为:

又根据ψi=snarctan(2-n)可得下式:

式(8)中,经过多次累乘后得到的值收敛于一个值K,

通过(6),(8),(9)可得:

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

可知当输入x=K,y=0,z=ϕ时。输出为x=cos(ϕ),y=sin(ϕ)。

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

当Zi>0时,Si=1;Zi<0时,Si=-1。

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

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

圆系统:μ=1;etai=arctan(2-i);

线性系统:μ=0;etai=2-i;

双曲系统:μ=-1;etai=a tanh(2-i);

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

3 CORDIC函数的FPGA实现[4]

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

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

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

通过表2和图1可以看到该方法成功实现了将6中函数的计算,下面我们比较计算误差:

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

4 结束语

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

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

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

参考文献

[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).

CORDIC算法篇4

数控振荡器用于产生可控的正弦波和余弦波样本。在软件无线电中, 它是决定数字下变频性能的主要因素之一。数控振荡器实现的方法目前主要有查表法和CORDIC算法。查表法耗费大量的ROM资源, 这样不仅增大了功耗, 而且增加了芯片的面积。CORDIC算法很好地解决了查表法面临的问题, 且非常适合在FPGA中实现。通过设计仿真分析了基于查表法与CORDIC算法的面积资源对比, 并详细阐述了基于流水线CORDIC算法的精度分析。

1数控振荡器设计分析

1.1算法设计

如图1所示直角坐标系, 向量A (x, y) 旋转一个角度Z得到向量B (x*, y*) , 则

x*=xcosz-ysinz,

y*=ycosz+xsinz。

利用三角关系重新整理后得:

$\begin{array}{l} x^{*} = c o s z (x - y t a n z) ‚ \\ y^{*} = c o s z (y + x t a n z) 。 \end{array}$

假设向量B是由A经过多次旋转得到的, 其中第i次旋转的角度为ϕi, 则第i次旋转的表达式为:

xi+1=cosϕi (xi-yitanϕi) ,

yi+1=cosϕi (yi+xitanϕi) 。

如果限定基本旋转角度ϕi满足 $\tan ϕ_{i} = \pm 2^{- i} (i = 0, 1, 2, \dots) ‚ ϕ = \sum_{i = 0}^{n - 1} ϕ_{i}$ , 则含有正切项的乘法可以演变为简单的二进制的移位运算, 非常利于硬件实现。由上式又可以表示为:

xi+1=ki (xi-diyi2-i) ,

yi+1=ki (yi+dixi2-i) ,

zi+1=zi-diarctan (2-i) , i=0, 1, 2, …。

式中, $k_{i} = \cos (\arctan 2^{- i}) = 1 / \sqrt{1 + 2^{- 2 i}}$ 为模校正因子, di=±1 (当逆时针旋转时di=1, 顺时针旋转时di=-1) 。zi是每次旋转之后, A与B之间的夹角。若zi>0, 说明A还需要继续逆时针旋转才能跟接近B。迭代运算不能使幅值比例因子恒为1, 为了抵消因迭代产生的比例因子的影响, 可将输入数据校正后再参与运算, 以避免在迭代运算中增加校正运算, 降低CORDIC算法的速度, 由此迭代式可简化为:

xi+1=xi-diyi2-i, yi+1=yi+dixi2-i。

上式的运算仅通过加法器及移位器就可以实现。

必须注意, CORDIC能够完成的旋转角度是有一定范围限制的, 因为arctan2-i>arctan2- (i+1) > (1/2) arctan2-i, 所以, $\sum_{i = 0}^{\infty} \arctan 2^{- i} > π / 2$ , 事实上, $\sum_{i = 0}^{\infty} \arctan 2^{- i} \approx 99.883 °$ , 也就是说, 假设从X正轴开始旋转, 通过一系列逐次见效的角度旋转后, 只要迭代的次数足够多, 就可以实现[-π/2, π/2]内任意角度的旋转。

一般考虑到流水线的技术问题, n不可能取得无穷大, 若取x0=1/An, y0=0则可以得到下式所示的数控振荡器所需要产生的标准正弦和余弦波, 对增益因子1/An不做处理。xn=cosz, yn=sinz, 式中正弦或余弦样本可以进一步表示为:

式中, fc为正弦或余弦波频率;fs为正弦或余弦波的采样频率。离散相位2πfc/fsn的产生是通过相位累加器实现的。累加器的相位间隔Δϕ=2πfc/fclk, 这通常是一个小数, 给后面的处理带来困难, 所以将2π放到2n, 即把2π用n位的二进制表示。这样就可以用整数的ϕword代替Δϕ, 且有fc=ϕword×fclk/2n, 此时, 相位间隔范围变成0≤φword≤2n-1, 并且可以通过设定ϕword的值得到想要的载波频率fc。数控振荡最高采样频率也是由累加器的式中频率决定, 且有fs=fclk。有采样定律可知, 可得到fs≤fclk/2。

1.2结构设计

基于流水线CORDIC算法数控振荡器结构如图2所示, 主要包括相位累加器、八分圆映射器以及CORDIC算法模块3个部分, 传统的CORDIC算法数控振荡器是采用的四分圆映射器。

经过MATLAB算法仿真验证, 采用八分圆映射比四分圆映射在保持整个可变频率范围内SFDR的稳定性方面更具优势, 所产生的正弦值和余弦值更精确。缺点是八分圆映射比四分圆映射复杂, 硬件实现时将消耗更多的资源。

CORDIC算法模块结构如图3所示。每一级实现的功能是根xi+1=xi-diyi2-i, yi+1=yi+dixi2-i进行一次迭代, 移位的位数等于当前的迭代级数, 加减法选择由该级中Z的最高位 (符号位) 决定, 得到下一级的X、Y和Z的值, 经过20级流水线运算后, Z值变为0, X和Y的值则为初始值z0的余弦和正弦值。每一级电路结构主要包括2个移位器和3个加 (减) 法器, 级与级之间直接相连, 不需要额外的寄存器。采用的这种流水线型实现结构, 它用n级相似的算法单元在同一个时钟周期内并行工作, 图中的3个累加器分别完成了该级中xi, yi, zi的迭代, 累加器的加/减控制信号为上一级算法单元中的di信号, 2个i位的右移寄存器完成了迭代等式中乘2-i运算, 而该级的基本旋转角度值arctan2-i可以采用直接硬连接, 省去了串行结构中的查找表单元。

ϕi的值因为参与运算的均为二进制数, 流水线结构中的移位器和加法器的位数有限, 故存在尾数舍弃带来的舍位误差。这种舍位误差是杂散的主要来源, 要提高SFDR必须设法减少舍位误差。CORDIC算法流水线级数有限带来的相位旋转误差是杂散的另一个主要来源。因为CORDIC算法的计算范围为[-π/2, π/2], 所以通常将[0, 2π]映射到[0, π/2]。映射原理:利用区间的三角关系, 改变CORDIC模块的输入参数如x0、y0, 用累加器的低位输出作为CORDIC算法模块的角度输入z0, 达到由z0输入计算sinz、cosz的目的。

八分圆的映射将计算范围缩小到[0, π/2], 最大的旋转角度为π/4, 旋转的角度接近π/4时有:

$\sum_{i = 0}^{n} \arctan 2^{i} + Δ ϕ = π / 4$ 。

2数控振荡器实现和精度分析

2.1实现

设计过程分为2个部分:

① CORDIC迭代前模块, 最终目的是输出当前相位, 主要功能是进行相位累加、截断以及按照以上的设计参数转换相位至 (-90, 90) 之间, 并给出相应的控制信号。系统采用32位的累加器, clk接外部时钟, 每来一个上升沿, 累加器以M为步进进行一次累加, 根据输出结果的高3位通过八分圆映射关系, 输出对应区域x0、y0的初始值, 同时将低29位数据赋值给z0;

② 整个CORDIC算法的迭代过程, 根据仿真结果, 系统采取了25级迭代, x0、y0迭代初始值量化为24位二进制数, 同样迭代过程中所需要的反正切角度值, 也根据角度比例对应量化为32位二进制相位参数。每一个模块 (级) 接收来自上一次迭代的Z角度值、X值、Y值, 通过判断Z的符号对X、Y、Z做移位加减操作, 其迭代的核心部分只需要3个加减法器和2个移位器。采用这样的流水线结构, 级级直接相连, 省去了中间的多位寄存器, 每一级移位长度和反正切角度值的固化, 也大大节省了实现时寄存器数量。实际工作时, 只需要26个时钟周期就可以输出第一个正、余弦值, 进而连续输出波形的离散数值。

在累加器精度为32位, 时钟频率为100 MHz, 幅度位数为18位时, 通过DC综合工具对3种方式下的面积资源进行了估计。采用大表型方式门数达到2、147、483、648, 小表型为268、435、456, 而采用CORDIC方式时仅为59、608。可见查找表不管是用大表型还是小表型, 因为ROM的使用都会占用大量的资源, 增加了芯片的面积。

2.2精度分析

提高结果的精度, 就是在进行数据的每次截位时, 都尽量的保持小数点后最多的位, 这就需要增加运算中的数据宽度或者迭代次数增加。

增加迭代的次数, 迭代次数越多, 精度越高, 但是在迭代进行到一定的程度 (主要是z0变为了0之后迭代的结果就不再改变) , 结果就不再改变了;同时迭代的精度也取决于x0、y0的精度, 也就是x0、y0位宽越大, 迭代的精度越高。

增加精度的同时, 都会增加大量的面积来实现功能, 这就需要选择一个合适的平衡点。

设计中使用的CORDIC算法是由MATLAB的浮点程序转化而来, 在浮点程序的MATLAB仿真结果和直接调用cos和sin算符的结果对比, 相差没有超过1。说明浮点程序不影响数据精度。

在将浮点的程序转化为定点之后, 因为存在每次的运算都会将数据四舍五入, 根据MATLAB的估算最终运算结果是有4个数差6, 数差5到4之间的有32 768个, 数差3到1之间的有536 870 912个, 其余全相等, 精度得到了最大的保留。

最终VHDL仿真结果与定点的MATLAB结果相比, 最大误差6的不会超过8个, 数差3到1之间的大概有231个, 这是因为在程序内部, 对负数的进位存在调整。

通过最后的输出数据与cos、sin函数的输出值相比较很接近, 得到了预期的正、余弦离散波形, 验证了基于流水线CORDIC算法的可行性以及程序本身的正确性。

3结束语

采用基于流水线CORDIC算法设计数控振荡器可以生成高精度数控振荡器而无需大容量的查找表, 节省了大量的ROM资源, 减小了面积。该设计中采用的八分圆映射结构, 在实际应用中对性能的提高有重要的促进作用。随着数字处理技术的发展, 数控振荡器越来越被广泛应用在解调电路中上变频、下变频以及调制电路 (包括PSK、MSK、FSK) 等数字处理系统中。

摘要：数控振荡器 (NCO) 的实现通常都是基于查表的方法, 为了达到高精度要求, 常常需要耗费大量的ROM资源去建立庞大的查找表。提出了一种基于坐标旋转算法 (Coordinate Rotation Digital Compute, CORDIC) 的流水线型数控振荡器的实现方法。硬件描述语言的仿真与综合结果表明, 采用这种方法设计的数控振荡器精度高、误差小、结构简单, 与基于查找表的数控振荡器相比, 更易于ASIC实现, 最后给出了该方案的仿真结果。

关键词：数控振荡器,FPGA,CORDIC算法,流水线

参考文献

[1]WALTHERJ S.A Unified Algorithmfor Elementary Functions[C].Spring Joint Computers Conference, 1971:379-385.

[2]高西全, 丁玉美, 阔永红.数字信号处理-原理、实现及应用[M].北京:电子工业出版社, 2006.

[3]赵鑫.VHDL与数字电路设计[M].北京:机械工业出版社, 2005.

[4]王诚, 吴继华.Altera FPGA/CPLD设计[M].北京:人民邮电出版社, 2005.

[5]陈泽强, 李蓬勃, 曹叶文登.基于FPGA的数控振荡器设计及其性能分析[J].山东工业大学学报, 2000, 30 (16) :584-589.

CORDIC算法篇5

1 SPWM不规则采样法分析

冲量等效的窄脉冲作用在惯性系统上，惯性系统的输出或响应是基本相同的。SPWM的产生即通过对输入正弦波进行脉宽调制，获得占空比按正弦规律来排列的脉冲序列，其脉冲宽度与正弦波幅值呈正相关，与脉冲间的间隔大小呈负相关，其调制原理如图1所示。

产生SPWM的方法有多种，本文采用一种不对称规则采样法，核心思想为选用正弦波作为调制信号，用更高频率的三角波作为载波，载波的顶点和底点作为抽样点对正弦波进行抽样，再与调制波进行比较判别，决定SPWM的脉冲宽度，局部放大如图2所示。

设调制正弦信号为Ussinωt，载波信号三角波的电压峰值为Uc，周期为Tc，每个三角波周期内的峰值顶点和底点都对正弦波进行一次采样，如t1和t2时刻对正弦波进行采样，过正弦波采样点幅值做平行于时间轴的水平线，在Ts周期内与三角波的交点为C点和H点，在时间轴上的投影分别为B和G点，BG即为SPWM的导通时间ton=Ta+Tb,SPWM的截止时间toff=Tc+ton，由图2易知：

根据三角形相似定理，ΔABC～ΔADE和ΔFGH～ΔFJI，结合式（1）推出：

式（2）中，是正弦波峰值电压与三角波峰值电压之比，称为SPWM的模，模数M越大，相应的SP-WM等效的正弦波电压越高。

令三角波频率fc与正弦波频率fs之比为载波比N，则：

式中k为采样号k=0,1,2,…,N-1。故式（2）中部分因子：

将式（5）代入式（2）可计算出Ta和Tb如下所示：

整理得，三角载波一个周期内SPWM的导通时间ton的表达式为：

由式（7）可以看出，通过确定三个参数Tc、M和N即可算出SPWM的脉宽ton，据此可知，通过产生三路互成120°的正弦调制信号和一个单通道频率数值远高于正弦调制信号的三角载波信号进行判别运算即可输出三相SPWM，本设计可采用FPGA或CPLD作为控制器件，正弦波信号通过CORDIC算法运算产生，利用其高速运算性能保证本设计的快速响应，纯数字电路计算产生的正弦调制信号和三角载波信号频谱特性好，能够有效减少输出电压的谐波含量，克服了常见SPWM发生装置的输出电压基波相位迟滞大的缺点，可实现快速控制。

2 CORDIC算法原理

传统的DDS产生正弦波一般是基于查找相位-幅值存储表实现，通过增加地址线位数提升相位精度指标，将导致存储表容量相应呈几何级数增长，多路信号的硬件资源消耗巨大。本文采用的CORDIC(Coordinate Rotation Digital Computer）改进型算法可直接计算得出正弦波形的幅值，以代替DDS中的相位幅度转换单元，释放查表法所需大量ROM空间，其基本原理如图3所示。

设初始向量V(x,y)，旋转角度θ后得到向量V′′′，坐标对应关系为：

选取每一次旋转角度的正切值为2的倍数，即θi=arctan(2-i)，体现在硬件上即用FPGA的基本移位操作实现乘法运算，因cosθ=cos(-θ)，每次旋转可表达成

式中：Ki=cos(arctan(2-i));di=±1表示向量的旋转方向，+1表示逆时针旋转；-1表示顺时针旋转；Ki的乘积为比例因子K:

由式（10）进行数学推导可知，当迭代次数足够多时，K收敛于一个常数0.607 252 935 008 881 3，可以将此因子和迭代的最后一级的结果相乘，以减少校正运算，则可得迭代式（11):

每次旋转后的剩余角度为：

所有旋转角度的总和为：

将所需产生的角度值为作Z0输入，当Zn→0时，旋转角度总和Φ→Z0，此时向量为单位向量，迭代结果即实现了三角函数数值逼近，cosθ=xn,sinθ=yn。

3 FPGA的硬件实现

CORDIC算法的FPGA硬件实现常见有两种，循环迭代结构和流水线结构，前者设计简单，占用资源少，但是N个迭代周期才能计算一次值，速度慢，后者结构较为复杂，需将每一步的迭代进行展开，插入寄存器，实现流水作业，实质上是以硬件资源换取速度，每一个时钟节拍输出一次值。本设计采用Altera公司的FPGA芯片EP2C8Q208C8N作为主控芯片，借助于Quartus ii开发平台，基于自顶向下的设计思想，分别设计出CORDIC算法和三组不对称规则比较法SPWM产生模块，相位两两相差为120°，构建顶层框图如图4所示。

具体CORDIC算法模块采用Verilog HDL硬件描述语言编写，设计了8级流水线单元，其结构如图5所示。

xi、yi的字长为8 b，最高位为符号位，因此弦函数的最大幅值为127，根据式（10）得出的比例因子K可计算出初始输入值：

Zi的字长为10 b，最高位和次高位判别象限，低8位对应于的相位，其中一、三象限里Zi的低8位与函数的相位是一一对应关系，二、四象限里Zi的低8位与函数的相位成逆序对应关系，即需要用256减去Zi的低8位值后才能与函数的相位一一对应。

所设计系统在QuartusⅡ里的运行结果如图6所示。

通过分析运行结果发现，本设计生成的SPWM迟滞极小，频率变换便捷快速。将此三相SPWM信号接入死区发生器输出六路PWM信号，再分配到FPGA的相应引脚上，便可以驱动桥式三相逆变器的三个桥臂，输出三相电源。

综合编译运行结果如图7所示，分析可知，本设计只用到2个片内锁相环，不需要乘法器和记忆体，逻辑资源占用不到10%，占用资源极少。

4 结语

CORDIC算法篇6

全球卫星导航系统 (Global Navigation Satellite System, G N S S) 现已成为航天大国的重要特征, 对G N S S的研究己在世界各国掀起热潮。例如, 美国的全球定位系统 (GPS) , 俄罗斯的格洛纳斯系统 (GLONASS) , 欧盟建立的伽利略系统 (Galileo) , 日本的准天顶卫星系统 (Quasi-Zenith Satellite System, QZSS) , 我国也建成了北斗卫星导航系统 (Compass) 。在诸多定位系统中, 各国对导航接收机的研究主要集中在信号的捕获和跟踪阶段。对于环路跟踪而言, 鉴别器设计是研究的重中之重, 找到跟踪精度高, 耗费硬件资源少的设计方案成为其追求的目标。

实现鉴相器的方法有很多种, 采用反正切函数所得到的特性曲线相对于其他方法而言线形度最佳、可鉴相的范围最广、所产生的误差也最小。因此, 在GPS载波跟踪环中选择反正切函数能够得到最好的效果。当鉴别器采用反正切函数时, 不易在硬件上实现, 所以鉴别器算法实现也是研究的热点。CORDIC算法功能较多, 可以同时实现多种函数, 它在硬件电路的实现上只用到了移位和累加, 大大节约了FFGA的资源, 使得这些算法在硬件上可以得到较好地实现, 从而可以满足设计者的要求。但是现有的CORDIC算法计算反正切时输入输出范围较小, 因此本文将原有CORDIC算法做部分改进, 扩大了鉴相器输入输出的范围。

一、鉴相器的基本原理

鉴相器 (PD) 作为跟踪环路的重要部分, 同环路滤波器 (LF) 和压控振荡器 (VCO) 共同组成相位锁定环路, 简称锁相环。锁相环能够跟踪输入信号的频率和相位, 并输出相位锁定、低抖动的其它频率信号。

设鉴相器的输入信号分别为:

那么通过求得φe (t) 就可以得到采样的中频信号的初相与载波初相的包含频率差的相位差, 进而得到修正后的载波频率。φe (t) 可以通过反正切函数进行计算:

根据锁相环模型的不同, 鉴相器还可以由乘积法, 除法等多种方法实现, 这里主要就CORDIC算法来讨论如何实现鉴相器的arctan函数。

二、CORDIC算法的基本原理

CORDIC算法 (Coordinate Rotational Digital Computer, 坐标旋转计算机) 是一种用于计算一些常用的基本运算函数和算术操作的循环迭代算法。其基本思想是用一系列与运算基数相关的角度的不断偏摆从而逼近所需旋转的角度, 从广义上讲它是一个数值计算逼近的方法, 由于这些固定的角度与计算基数有关, 运算只有移位和加减法。最初的CORDIC算法是计算平面直角坐标系和极坐标系之间进行自由坐标变换的乘法器。后经J.SWalther推广, 将圆周, 线性和双曲线都整合起来, 为FPGA完成多种超越代数函数的运算奠定了基础。CORDIC算法原理如图1所示:

将上式转为矩阵形式可得

θn+1表示经过n次迭代后剩余未旋转角度, 则可得CORDIC算法方程组 (忽略常数增益k) :

该式需要注意的是在迭代计算完之后Xn+1和Yn+1, 需要再乘上系数k=0.60725才是正确的结果。

三、CORDIC算法的改进部分

假设Z0=0, 则Zn+1的取值范围为

将分布在第二象限和第三象限的输入数据 (x, y) , 转换为现有CORDIC算法能够计算的第一象限和第四象限数据 (x0, y0) , 转换公式如下:

并且实时发出信号flag给相位转换模块, 以便确定该Zn+1属于哪一象限。

接收象限转换模块发送的flag标志位, 确定输入数据 (x, y) 处在哪一象限, 同时接收现有CORDIC算法模块的输出Zn+1, 根据Zn+1和flag—起来确定输出四象限反正切值φ四象限:

四、改进后CORDIC算法FPGA实现

本文以迭代CORDIC算法的FPGA实现方式为例说明改进后的CORDIC算法如何实现, 迭代算法流图如下所示:

其中, 浮点数转定点数的扩大倍数直接影响最终相位的精度。对改进部分的代码实现说明如下:

象限转换:将原坐标数据 (x, y) 转为可以直接进行计算的第一象限和第四象限坐标 (x0, y0) , verilog HDL部分实现代码如下所示:

相位转换:最后将经过移位和累加后的数据Zn+1进行±180°补偿, 确定最终实际的相位差φ四象限, verilog HDL部分实现代码如下:

结束语

本文提出了一种基于CORDIC算法的数字鉴相器的实现方法, 该算法结构简单、硬件实现较易, 针对现有CORDIC算法中反正切函数的输入输出范围小的弊端, 改进CORDIC算法, 增加了象限转换和相位转换功能, 使鉴相器输入输出的范围扩大至四个象限。

参考文献

[1]谢钢.GPS原理与接收机设计[M].电子工业出版社, 2009, 7.

[2]李超.GPS接收机跟踪环路的改进设计及FPGA实现[D].大连理工大学, 2013, 5.

[3]姜华, 毛志刚, 谢憬.基于CORDIC算法的GPS载波跟踪环鉴相器的设计[J], 2007, 8.

[4]郑立岗, 吕幼新, 向敬成, 等.一种基于CORDIC算法的数字鉴频方法[J].信号处理, 2003, 19 (1) .

[5]陈石平, 李全, 莫丽兰, 等.基于C0RDIC的反双曲正切函数的FPGA实现[J].计算机工程与科学, 2009, 31 (05) :150-152.

CORDIC算法篇7

关键词：FFT,CORDIC算法,MODELSIM仿真,FPGA

快速傅里叶变换是DSP的核心技术之一,作为时域和频域转换的基本运算,是数字谱分析的必要前提,在雷达、观测、跟踪、高速图像处理、保密无线通信和数字通信等领域有广泛应用。FPGA(现场可编程门阵列)内部含有大量逻辑单元和高速RAM模块,使FFT算法可以灵活快速地实现,并具有很高的性能。针对快速信号处理的要求及FPGA器件的特点,提出了一种基于CORDIC算法的基二流水线结构的FFT处理器设计方法。

1 基二FFT算法原理分析

设序列长度是为N=2M,M为正整数。如此可以将序列x(n)分解成两组,偶数项为一组,奇数项为一组,可以得到两个N/2点的子序列,即:x1(r)=x(2r),x2(r)=x(2r+1),r=0,1,…,N/2-1;相应地将DFT运算分为两组[1]。

$\begin{array}{l} X (Κ) = D F Τ [x (n)] = \sum_{n = 0}^{Ν - 1} x (n) W_{Ν}^{k n} = \\ \sum_{n = 0 偶数}^{Ν - 1} x (n) W_{Ν}^{k n} + \sum_{n = 0 奇数}^{Ν - 1} x (n) W_{Ν}^{k n} = \\ \sum_{r = 0}^{Ν / 2 - 1} x (2 r) W_{Ν}^{2 k r} + \sum_{r = 0}^{Ν / 2 - 1} x (2 r + 1) W_{Ν}^{k (2 r + 1)} = \\ \sum_{r = 0}^{Ν / 2 - 1} x_{1} (r) W_{Ν / 2}^{k r} + W_{Ν}^{k} \sum_{r = 0}^{Ν / 2 - 1} x_{2} (r) W_{Ν / 2}^{k r} = \\ X_{1} (Κ)_{Ν / 2} + W_{Ν}^{k} X_{2} (Κ)_{Ν / 2} \end{array} (1)$

利用W $_{Ν}^{Κ}$ 的特性,式(1)可以写成

${\begin{cases} X (Κ) = X_{1} (Κ) + W_{Ν}^{k} X_{2} (Κ) \\ X (Κ + \frac{Ν}{2}) = X_{1} (Κ) - W_{Ν}^{k} X_{2} (Κ) \end{cases} ‚ Κ = 0, 1, \dots, \frac{Ν}{2} - 1 (2)$

继续照上式将序列分解,直到最后是二点的DFT为止。8点FFT蝶形图如图1所示。

2 基二FFT的FPGA实现

在FPGA上实现流水线型FFT处理器,其主要结构模块包括:输入的乒乓RAM模块、蝶形运算模块、旋转因子乘法模块(本文用CORDIC算法实现)、倒序输出模块、旋

转相角(φ)ROM,还有信号流程控制模块和地址产生器模块。具体如图2所示。

2.1 RAM的乒乓读取

为了使输入数据无等待周期,采取了乒乓操作。这种结构是将输入数据流不断写入存储深度为2N的存储单元,用RAM写地址值的最高位来区分低、高存储部分,数据首先输入的低位存储区,当低N个存储单元存储满之后,数据开始存入高N个存储单元,同时开始读取低N个存储单元的数据,由于读写频率相同,低存储单元的数据读完后高存储单元已经写满,此时则开始将数据写入低存储单元,读出高存储单元。如此循环往复,一旦RAM存满最初N个数据后,RAM就可以不间断的输出按要求分组的N个数据点。

由于FFT的蝶形运算特性,要求最终输出结果是顺序输出,即:RAM的读地址应该是其同步写地址的低N-1位二进制码的求逆。如此即可将按正常次序存入RAM的数据进行逆序输出。其中RAM写地址和RAM读地址均由地址产生单元产生,而要保证RAM读、写同步速,在进行求逆时不能有延时,因此对求逆运算要采用组合逻辑电路或者是函数运算来实现。

2.2 蝶形运算的实现

由于读入蝶形单元的数据是串行输入的,而蝶形单元涉及到前后不同地址的数据的加减运算,因此必须对先前输出的数据进行寄存,利用两个选择控制信号对输入数据进行运算控制,如图3所示[2]。

在选择器控制信号sel0的控制下选择对输入数据或输入数据与寄存器输出相加的结果进行寄存。当sel0为高电平时选择对输入数据进行寄存,低电平时对输入数据与寄存器输出的数据相加结果进行寄存。sel1信号控制对寄存器输出数据或寄存器与输入数据之差进行输出。移位寄存器深度可表示为2m-1,m为蝶形运算所在的级数。每级蝶形运算都有sel0、sel1两个控制信号,所有控制信号由控制单元产生。sel1信号为sel0取反后的信号,其频率为主控制时钟的2m分频,m为该蝶形所在的级数。每级蝶形运算输出即送往下一级蝶形运算,在输入下一级之前需与旋转因子W $_{Ν}^{k n}$ 进行相乘。

2.3 利用 CORDIC算法实现旋转因子乘法器

旋转因子的获取有两种方法:一种是将先所需要的旋转因子计算预先存储在ROM中,再通过ROM寻址获取后和相应的数据相乘。本文采用的是实时计算的方法,即将需要旋转的角度值预先存储在ROM中,通过ROM寻址将需要旋转的角度送入CORDIC计算器,直接计算出数据与cosφ和sinφ乘积值。实时计算的方法对计算点数不多的FFT,具有很大的灵活性,也可以节省存储空间。

CORDIC算法的原理如式(3)所示[3,4]:

${\begin{cases} x_{i + 1} = x_{i} - y_{i} d_{i} 2^{- i} \\ y_{i + 1} = y_{i} + x_{i} d_{i} 2^{- i} \\ z_{i + 1} = z_{i} - d_{i} \arctan^{- 1} 2^{- i} \end{cases} (3)$

$d_{i} = {\begin{cases} + 1 ‚ z_{i} > 0 \\ - 1 ‚ z_{i} < 0 \end{cases} (4)$

CORDIC算法的流水线实现流程如图4所示。

式(3)中(x0,y0)为旋转向量点的坐标值,经过逐步迭代移位相加运算后可以得到式(5)

${\begin{cases} x_{n} = A_{n} (x_{0} c o s z_{0} - y_{0} s i n z_{0}) \\ y_{n} = A_{n} (y_{0} c o s z_{0} + x_{0} s i n z_{0}) \\ z_{0} = 0 \\ A_{n} = \prod_{i = 0}^{n - 1} \sqrt{1 + 2^{- 2 i}} \end{cases} (5)$

当旋转向量和x轴重合时,即y0=0时,其最终结果可表示为

${\begin{cases} x_{n} = A_{n} \cdot x_{0} c o s z_{0} = A_{n} \cdot x_{0} \cos φ \\ y_{n} = A_{n} \cdot x_{0} s i n z_{0} = A_{n} \cdot x_{0} \sin φ \end{cases} (6)$

如此可以得到参数W $_{Ν}^{k n}$ 的实部和虚部。式(6)中An表示增益系数,其极限值为1.647,即一次旋转乘法完成后最终结果比预期的要大1.647倍,考虑到数据位的溢出,在运算初始过程中需将初始值x0进行右移1位处理,即将x0初始值缩小2倍。z0值为存储旋转相位角ROM的输出值φ,在不用乘旋转因子时ROM输出数据为φ=0。旋转结果xn为实部值,-yn为虚部值。其中只有第一级输入是全实数输入,以后每级的输入包含实部和虚部两部分,实部和虚部要分别进行旋转相乘和分别进行移位寄存处理,即每级中需包含两个运算单元,分别同步处理实部和虚部数据。得到旋转输出结果后将实部旋转后的实部和虚部旋转后的虚部相加得到新的实部数据作为下一级的实部输入,实部旋转后的虚部与虚部旋转后的实部相加得到新的虚部数据作为下级输入的虚部。

CORDIC算法所能获得的最大旋转角度为[5]: $φ = \lim_{n \to \infty} \sum_{i = 0}^{n} \arctan 2^{- i} \approx 99 °$ ,故设定旋转区间为[0,π/2],要求对ROM输出的相位角进行预判,之后利用三角函数的性质将第一区间外的相角转换到第一区间内进行运算以实现全相位的运算,如表1所示。

2.4 地址产生单元与ROM存储设计

地址产生单元主要用来产生RAM的读、写地址和旋转相角ROM的读地址。主要是根据时钟的步速(串行数据的输入步速)产生RAM的写地址,并按照求逆的要求将写地址的低N-1位二进制数按位序求逆产生对应RAM读地址。按照写地址的最高位是1还是0判定读地址的最高位是0还是1,保证其进行乒乓读取。ROM读地址的产生与RAM读地址的产生同步同时产生,但不用求逆,即与RAM写地址的低N-1位完全相同,并以N点为周期进行循环产生。

由于ROM地址产生器产生的地址是与RAM写地址的低位N-1值相等的,即数据开始串行输入蝶形单元的顺序值。而经过蝶形单元运算后产生了数据延迟,等到N个数据完全移出一级蝶形单元时,ROM的地址值已经重新开始计数,由此产生了ROM的循环寻址,即:将相角数据φ预先存入ROM时要考虑延迟后的寻址,ROM地址重新归零后对应的存储单元要存放的数据是对应延迟输出的几个相角值。如此就像循环右移一样,将本应该存储地址末尾的内容拿到存储地址的前几个地址,如图5所示。

2.5 控制信号与数据对准

在每级蝶形单元的交叉运算中都需要控制信号sel0,sel1,总计需要2M个控制时钟,M为基二运算过程中的蝶形运算中所需的级数。从数据开始输入的同时开始计数、分频,由于每级不同的延迟,数据从第m级输入到输出由于中间有移位寄存器的延迟作用会对数据的输出造成延迟,延迟量可以表述为2m-1,其中2m-1为移位寄存器的深度,读入数据过程中本身就有一个数据延迟,因此第m级的数据输出相对于开始输入蝶形单元的数据总延迟量可以表述为1+2+…+2m-1+2m。而控制数据输出的sel1信号不断经过时钟的2的整数次幂得到的,此时会产生各级输出数据(下级的输入)与下级蝶形运算控制信号的上升沿未能对准的情况,因此需要将各级数据在输出过程中进行不同单位的延迟(增加寄存次数)以保证蝶形单元的输出数据与下级蝶形单元的选择器控制时钟对齐,只有输入数据与蝶形单元的控制时钟的上升沿对准,才能保证数据进行正确的寄存和运算。

在蝶形运算过程中,由于是控制时钟的关系,按照二进制码逆序输入的数据最终在FFT处理器输出是十进制的逆序,即先输出的是第N个数据,最后才输出第一位数据。要得到正确的顺序输出在最后一级蝶形运算后需要进行倒序处理,同样为保证输出的连续性也采取了乒乓操作,只是此时有实、虚两部分数据,存储空间要比输入时的RAM大一倍。

3 仿真与验证

利用MATLAB产生的数据作为FFT的输入激励。设计输入信号为100 kHz与300 kHz的叠加,采样频率为1 MHz,FFT点数定为32,将采样值转换成二进制数据,并写入txt文件,如下文所示:

在testbench中利用verilog语言的系统函数MYM-readmemb将txt文件中的二进制数据读入存储数组datamem,在采样时钟的控制下,将datamem中数据串行读入FFT处理器,作为输入激励,如下文所示:

MYMreadmemb(″binarydata.txt″,datamem)

利用verilog系统函数MYMfdisplay将FFT处理器输出的实部和虚部数据写入txt文件,方便利用MATLAB读取分析。部分代码如下:

利用MATLAB绘图对比分析结果如图6所示。

对比分析可以证实该设计基本满足了FFT对频谱分析的要求。其幅度值不等是因为在硬件设计中采用了防止溢出的限幅措施。

4 总结

主要讨论了基二FFT在FPGA上的实现方法,结合CORDIC算法,在FPGA芯片上实现了FFT处理器,解决了设计过程中的乒乓读取,CORDIC旋转运算,ROM存储,数据与控制时钟的对准等问题。并进行了MODELSIM和MATLAB的联合仿真,仿真结果表明该设计满足了FFT处理的处理要求。在10 MHz采样率的情况下完成32点的FFT运算需要14.45 μs,满足实时处理的要求,并且具有可以继续扩展到更高的点数,具有推广价值。下一步将考虑更为节约资源的方法,使其用于具体的装备中。

参考文献

[1]俞卞章.数字信号处理[M].2版.西安:西北工业大学出版社,2002.

[2]高亚军.基于FPGA的数字信号处理[M].北京:电子工业出版社,2012.

[3]UWE M.Digital signal processing with field programmable gate arrays[M].刘凌,译.北京:清华大学出版社,2003.

[4]刘福奇,刘波.Verilog HDL应用程序设计[M].北京:电子工业出版社,2009.

【CORDIC算法】推荐阅读：

扩展算法07-16

蝶形算法07-18

区间算法07-18

搜索算法07-19

矩阵算法05-13

回归算法05-15