CORDIC算法的FPGA与DSP实现的优劣分析

王 琦，栾铸徵

（船舶重工集团公司723所，扬州225001）

0 引 言

在雷达信息处理中，需要进行球面坐标与直角坐标的转换，目前大多是通过软件方式来实现的［1］，但随着雷达数据率的不断提升，用软件的方法越来越不能满足处理的实时性要求了，所以有必要用硬件来实时计算。

CORDIC算法可以将多种难以用硬件电路直接实现的复杂运算分解为统一、简单的移位、加迭代运算，而且结构规则，运算周期可以预测，适合于超大规模集成电路（VLSI）实现。由于CORDIC采用迭代的思想，且可以不需要乘法运算，所以特别适用于硬件实现（FPGA或专用集成电路（ASIC））。另一方面，随着DSP（数字信号处理器）芯片中乘法指令的快速实现（一条乘法指令可以在2个周期内完成对多个数据的乘法操作），以及体系上并行度的提高，使得在DSP芯片上实现CORDIC算法也成为一个可行的方案。

本文首先介绍CORDIC算法原理，然后分析了算法中旋转迭代次数、操作数位宽与精度的关系，最后分别在ALTERA公司的FPGA芯片（Stratix2系列的EP2S90）和TI公司的DSP芯片（TMS320C6455）上实现旋转模式下的CORDIC算法，并将两者的精度、时间效率、空间效率进行比较分析。

1 CORDIC算法原理与精度分析

1.1 CORDIC算法原理

1971年，Walther提出了统一的CORDIC算法［2］，引入了参数m，将CORDIC实现的3种迭代模式：三角运算、双曲运算和线性运算统一于一个表达式下，形成目前所用到的CORDIC算法最基本的数学基础。该算法的基本思想是通过一系列固定的、与运算基数相关的角度不断偏摆，以逼近所需的旋转角度，可由下列等式描述：

式中：X（n）、Y（n）和Z（n）为所期望得到的函数。

根据m＝1、－1或0，可以将上面的运算分别称为圆周旋转运算、双曲旋转运算或线形旋转运算。其中：

m＝1时，通常微转角θi＝arctan（2－i），且各微转角要满足，使结果Z（n）＝0的旋转称为旋转模式，使结果Y（n）＝0的旋转称为向量模式。当m＝1时，旋转模式的CORDIC算法的迭代公式如下：

式中：i为迭代次数；δi＝sign［Z（i）］。

1.2 精度分析

由基本原理可知，CORDIC算法所能达到的精度与所选取的旋转迭代次数和操作数位宽有关。

一方面，根据角度精度计算公式：

可知，算法的精度随着迭代次数的增加而提高。需要注意的是，为了提高精度，并不能一味地增加迭代次数，不仅仅因为迭代次数的增加会牺牲系统速度，增加硬件资源消耗，更因为数据位宽制约着有效迭代次数。输入数据用M位二进制数表示，当迭代次数超过M次时，X0，Y0右移的位数超过M位，导致移位操作无效，这样限制了有效的迭代运算次数，即限制了算法的精度。因此，在设计中，需对输入数据进行位扩展，将原始坐标和基本旋转角度均扩大2m倍，这样有效迭代次数增加了m次，基本旋转角度更加接近理论值，使算法精度提高。

另外，用来表述角度的二进制位数的有限也限制了算法的精度。在设计中，角度须用较宽的数据位来表示。比如当角度用20位有符号数表示时，每1°用十六进制表示为 （220－1）／360≈B61（十六进制），角度分辨率为360°／（220－1）≈0.000 343°，则CORDIC迭代中的第19次固定旋转角度无法分辨出来，所以对于20bit位宽角度，CORDIC最多只要进行18次迭代，该精度已能够满足一般的工程应用。

2 旋转模式下CORDIC算法的FPGA与DSP实现

对于CORDIC算法的FPGA实现，本文采用高速全流水线结构。流水线CORDIC结构虽然占用的硬件资源较多，但该结构可以提高数据的吞吐率。对于大多数数字信号处理算法来说，存在很多同一指令连续处理很长一段数据的情况，此时高吞吐率更有意义。从当前VLSI的发展趋势上来看，芯片内的门资源相对富裕，对流水线CORDIC的实现规模约束很小。

此外，流水线CORDIC不存在迭代式CORDIC的反馈回路，使得单元结构更加规则，有利于VLSI的实现。图1给出了FPGA中CORDIC算法的一般流水线结构。

图1 FPGA中CORDIC算法的一般流水线结构

利用FPGA实现流水线结构的CORDIC算法，主要利用FPGA寄存器资源较丰富的特点，在每个单元的输入和输出端分别加入寄存器，对输入输出进行锁存。并利用了2个移位器和2个加减法器，再使用不同的时钟信号作为输入信号，并采用两相门控时钟进行控制，以保证整个设计的同步性。

Stratix ii器件系列将FPGA性能推向了新的高度，该系列是业界最快、密度最高的FPGA。高性能的Stratix ii器件架构除了具有革新性的逻辑结构之外，还包括速度优化的互连结构和极高效的时钟网络，它们连接LE、TriMatrix存储块、DSP块、锁相环（PLL）和I／O单元（IOE）实现最大系统性能。Stratix ii器件包括高性能的嵌入DSP块，它能够运行在370MHz，并为DSP应用进行优化，消除了大计算量应用中的性能瓶颈，提供可预测和可靠的性能，这样既节约资源又不会损失性能。另外，还提供了灵活的可配置成不同数据宽度和延迟的软核乘法器，可大大提高数据的吞吐量。

本文在Altera公司的Quartus ii7.2软件环境下采用自顶向下的方法，使用VHDL语言设计了图1所示流水线结构的旋转模式下的CORDIC算法，并在Stratix ii EP2S90F1020I4芯片上进行了验证。DSP芯片作为软件可编程器件，具有通用微处理器方便灵活的特点。DSP中实现旋转模式下的CORDIC算法，是一个软件流程，流程图如图2所示。

TMS320C6000系列是美国TI公司推出的高性能DSP芯片，其最主要特点是在体系结构上采用了超长指令字（VLIW），每个周期能执行8条32位指令，通过指令间的并行来获取更高的性能。并行的系统结构是该系列DSP高性能的体现，使之在性能上完全超越了其他传统的DSP。另外，其内核CPU由2个寄存器组A和B组成，具有8个（2个乘法器和6个ALU）32位字长的功能单元。

本文所用的TMS320C6455是定点DSP，最高主频达1.0GHz，峰值处理能力达8 000MIPS，非常适合于实时信号处理。在TI公司的CCS3.3软件开发环境下，使用C语言和汇编语言混合编程，并结合C64系列DSP的多级流水线、高并行性（SIMD）和片内存储器的特点，实现了图2所示的CORDIC算法。

图2 DSP中旋转模式下的CORDIC算法实现软件流程

3 CORDIC算法在FPGA和DSP中实现性能比较

本文分别在FPGA（Stratix ii EP2S90F1020I4）芯片和DSP（TMS320C6455）芯片上实现旋转模式下的CORDIC算法。现分别从数值精度、时间效率和空间效率角度对二者的优劣进行比较。数值精度可用误差来衡量，时间效率可以用周期数或程序执行时间来衡量，而空间效率主要指算法所消耗的存储空间以及寄存器个数。

仿真在以下条件下进行：输入输出数据位宽为16bit，中间数据位宽为20bit（即位扩展4bit），角度位宽为20bit，迭代次数16次。

表1给出了在上述仿真条件下FPGA和DSP实现极坐标与直角坐标转换仿真结果的精度比较。

从表1可看出，相同仿真条件下，FPGA计算结果与真值间的误差在0.008 2%左右，可满足大部分工程应用对精度的要求；而DSP的计算结果与真值间的误差仅为0.000 9%，该误差可忽略，DSP精度比FPGA高1个数量级。

FPGA的最高工作频率Fmax跟数据位宽和迭代次数有关，而DSP工作频率设定为1.0GHz，即其1个指令周期为1ns。表2给出了FPGA与DSP 的时间效率的比较。

表1 FPGA和DSP实现（R，θ）→（x，y）转换的仿真结果精度比较

表2 FPGA与DSP的时间效率的比较

从表2可看出，在FPGA中，周期数只跟迭代次数有关，但最高时钟频率跟数据位宽与迭代次数均有关。DSP中，周期数主要与迭代次数有关。相同条件下，FPGA速度远远快于DSP，且随着数据位宽的增加和迭代次数的增加，两者的执行时间均相应增加。

对于资源的消耗，FPGA主要是消耗算术逻辑单元和寄存器，DSP则是指占用芯片内部随机存储器的大小。表3给出了FPGA与DSP空间效率的比较。

表3 FPGA与DSP空间效率的比较

从表3可看出，随着数据位宽和迭代次数的增加，FPGA消耗的硬件资源相应增加，而DSP所消耗的内存资源相对变化不大。

对于旋转模式下的CORDIC算法在FPGA和DSP中的实现，通过两者数值精度、时间效率和空间效率的比较，可以得到以下结论：相同仿真条件下，DSP数值精度比FPGA高，而FPGA速度远远快于DSP，且消耗更少的硬件资源，但DSP设计更灵活，可移植性更强，通用性更好。

4 结束语

本文在现有的CORDIC算法的基础上分析了算法中旋转迭代次数、操作数位宽与精度的关系，并分别在FPGA芯片和DSP芯片上采用全流水式、高并行化结构进行设计，提高了数据吞吐率，加快了数据处理速度，通过选取合适的位宽和迭代次数，使计算精度得到提高。仿真结果对比表明，相同条件下，FPGA相比DSP速度更快，消耗硬件资源更少，而DSP拥有更高的数值精度和灵活性。

［1］刘翠海，王文清，袁满.一种支持雷达P显仿真的实时坐标变换策略［J］.系统仿真学报，2012，14（9）：17－22.

［2］Walther J.A unified algorithm for elementary functions［A］.Spring Joint Computer Conference［C］.New York，1971：379－385.

［3］季中恒，宋博.CORDIC算法及其硬件实现［J］.弹箭与制导学报，2005，25（3）：609－612.

［4］李滔.流水线CORDIC算法及其应用研究［D］.北京：北京理工大学，1999.

［5］吴继 华，王诚.Altera FPGA／CPLD 设计（高级篇）［M］.北京：人民邮电出版社，2005.