CORDIC 算法在正余弦函数中的应用及其FPGA 实现

2013-02-22常柯阳曾岳南覃曾攀

计算机工程与应用 2013年7期

常柯阳，曾岳南，陈平，覃曾攀

广东工业大学自动化学院，广州510006

1 引言

正余弦函数在众多工程应用的场合非常广泛，就典型的采用空间矢量控制方法的电机控制系统来说，坐标变换模块就需要正余弦函数的实时参与。而在电机控制芯片的发展方面，现场可编程逻辑器件（FPGA）[1]以其速度、灵活性、可靠性和集成度而逐渐受人瞩目。

由于计算精度与存储容量的突出矛盾[2]，在存储资源有限的FPGA 芯片中，常用的查找表方法没有优势；而CORDIC 算法，仅需通过移位与加减运算和占用少量的存储资源，因此能够方便地在硬件中实现。但该算法过程复杂，迭代次数较多，输出时延较长，占用的硬件资源较多。因此，本文提出了一种查找表与CORDIC 相结合的算法，结合两者的优势，在保证精度的前提下优化了算法的输出时延和资源消耗，并在QuartusII 7.2 开发环境下完成了算法的设计、仿真和硬件测试。

2 查找表法和传统CORDIC 算法介绍

2.1 查找表算法原理

查找表算法的原理是根据计算精度要求，先把一个周期内的正余弦函数分为若干个点，分别求出对应点的函数值，并将结果写入芯片存储器中。然后，再通过适当的运算将输入角度与存储器地址对应起来，从而查表获得结果。

用查找表[2]方法实现函数的计算，虽然没有输出时延，但其精度和表的容量是指数关系的，就势必需要大规模的ROM，这在实际应用中需要占用大量的片上资源，甚至是不可行的。

2.2 CORDIC 算法原理

坐标旋转数字计算机CORDIC（Coordinate Rotation Digital Computer）算法，是由Volder[3]于1959 年提出的，其基本思想是通过一系列与运算基数相关的角度的不断偏摆，从而逼近所需旋转的角度。在圆周模式下，其基本实现形式有两种：旋转计算模式和向量计算模式。计算正余弦函数时，需采用旋转计算模式。在文献[2]中，给出了其基本形式：

其中，xn、yn、zn是当前迭代变量；xn+1、yn+1、zn+1是下一次迭代变量；是符号函数；n是迭代次数。输入，则输出为，其中设增益因子，在n→∞时，K≈0.607 253。算法的角度覆盖范围[4]为(-99.88°～99.88°)。

3 改进型CORDIC 算法

3.1 改进型CORDIC 算法的思想

由上述算法描述可知，CORDIC 算法结构仅需要移位和加减运算，以及n-1 个旋转常量，非常方便在FPGA 中实现。但其迭代次数较多，输出时延大，占用硬件资源较多。考虑到上述因素，本文提出了一种改进型CORDIC 算法，将查找表方法与传统CORDIC 方法相结合。这样，可以利用少部分的存储资源，也能降低迭代次数，节约了硬件资源和降低输出时延。文献[4]虽然提出了这种思想，但并未给出具体的实现方法。

CORDIC 算法是一种逐次逼近的算法：以一个初始向量为出发点，按照一定的逐渐减小的角度值上下摆动，最终逼近真实值。传统的CORDIC 算法，初始向量为X轴，并依次以45°(arctan 20)、26.57°(arctan 2-1)…进行旋转。

如图1，在不考虑增益因子的情况下，待求向量d需经过2 次逆时针旋转和1 次顺时针旋转到达临近向量c。

图1 CORDIC 算法角度逼近示意图

但如果能够知道待求向量d的范围在向量b和c之间，并确切知道c的位置，就可以省略a、b和c三次旋转。对于流水线型结果来说，就可以省略几级流水线；对迭代式结构来说，就可以减少迭代次数，同时降低输出时延。正如图2 中所示，若已知向量d所代表的初始向量对应的坐标为(xi,yi)，则可以省略掉前面0～i次运算，仅需要i～n次的运算。与传统算法相比，减少了i次运算，因此能够将输出时延降低i个时钟，并降低一部分硬件资源。但同时，由于要获取初始向量d的坐标信息，相对于传统CORDIC算法，需要占用较多的存储资源，其多少取决于算法的运算次数和精度；但相对于查找表方法[4]，其占用的存储资源则要少很多。也就是说[4]，改进型CORDIC 算法就是解决了查找表算法占用存储资源大与传统CORDIC 算法输出时延大之间的矛盾；在占用有限存储资源，保证计算精度的情况下，减小了输出时延和硬件资源。

图2 改进型CORDIC 算法结构图

3.2 改进型CORDIC 算法的FPGA 实现

算法实现结构主要分为三个模块：预处理模块、初始向量查找表模块和算法主体及后处理模块。

整个设计过程是在QuartusII 7.2 环境下实现，采用VHDL 语言与.bdf 原理图编写；设计文件内所有数据均采用Q14 格式；而函数floor()表示向负无穷舍入，round()表示向最接近的整数舍入。各模块的作用如下所述。

3.2.1 预处理模块

主要作用：扩展输入角度范围，并获得初始向量查找表地址和剩余需旋转角度。

上文中提到CORDIC 算法的输入角度覆盖范围为(-99.88°～99.88°)，所以在计算前，需将输入角度范围扩大为[0 ～2π)。这里对输入角度theta取其对的标么值，如表1 所示。

表1 输入角度数据格式

扩展处理方法的伪码如图3。图中，theta_m为处理后的输出角度数据，其范围为；verf为theta的象限状态值，用于主体算法完成后的后处理；addra为余弦查找表地址，范围为[0 ～255]；addrb为正弦查找表地址，范围为[0 ～254]。

设计中，初始向量正余弦查找表由一块ROM 存储，地址范围为[0 ～255]，存储数据为故。在硬件实现时，仅需将theta_m右移6 位，而；仍需旋转的角度z=theta_m-(addra+1)×26。

3.2.2 初始向量查找表模块

模块功能：根据输入地址查找相应的正余弦值。

利用宏功能模块生成两输入两输出的ROM 模块，其容量为16 bit×256 word。相邻两地址所代表的角度差的标么值的Q格式为

3.2.3 算法主体及后处理模块

模块功能：计算输入角度theta_m的正余弦值，并根据输入象限状态verf对输出结果进行调整，最终得到初始输入角度theta的正余弦值。

流水线级数的确定：角度旋转常量如表2。

表2 角度常量θi=round(arctan(2-i)×214)

故按照传统的CORDIC 算法需要15 级流水线。而由于，故采用改进型算法后，仅需8 级流水线，即在初始向量的基础上摆动8 次就可逼近待求向量。由2.2 节可知，调整因子，文中忽略不计。

后处理部分，是根据verf 进行角度theta 的象限判定，并据此修改输出结果。

将上述三部分连接，即可得到改进型CORDIC 算法（图4）。

图4 改进型CORDIC 算法的基本单元

4 仿真结果

在QuartusII 7.2 开发环境下对上述设计文件进行仿真。图5 给出了传统算法与改进后算法的仿真结果，其中，输入角度theta是利用Matlab 软件计算得到的：

Theta涵盖了[0 ～2π)范围。传统算法的输出结果较改进后算法延迟了7 个时钟。

图5 传统与改进型CORDIC 算法仿真结果对比图

将两种算法的仿真数据与Matlab 计算数据作对比，可得[0 ～2π)输入范围内的误差曲线，如图6 所示，其中，叉号和圆圈曲线分别为余弦误差和正弦误差曲线。从图中可以看出，两种算法的误差均在10-4数量级内，改进后算法误差绝对值的最大值0.000 3较改进前0.000 4降低了约25%。

5 实验结果

将上述算法编译下载至Altera 公司CycloneII EP2C70F896C6 芯片。图7 为编译后芯片资源消耗的报告，编译工具为QuartusII 7.2 自带的；表3 将两份报告进行了对比。

图8 显示了使用嵌入式逻辑分析仪对算法进行硬件测试的结果，系统时钟为50 MHz，与仿真结果一致。

6 结论

将查找表算法结构和传统CORDIC 算法结构相结合，提出了一种计算正余弦函数的改进型的CORDIC 算法，并完成了该算法的仿真设计和FPGA 实现。其结果表明本文算法占用的存储资源比查找表算法少，硬件资源比传统CORDIC 算法少，但与传统CORDIC 算法相比，却实现了同等数量级的计算精度，并减低了将近一半的输出时延。将仿真和硬件测试结果与Matlab 计算结果进行了对比，验证了算法的正确性。如果需要更高的计算精度，可以增加算法中计算数据的位宽；而且，精度越高，数据位宽越大，改进后的算法在资源利用方面的优势就越明显。