基于FPGA的一种改进型三角超越函数CORDIC实现方式
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于FPGA的一种改进型三角超越函数CORDIC实现方式范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘要】CORDIC算法将复杂的算术运算转化为简单的加法和移位操作，然后逐步逼近结果。这种方法很好地兼顾了精度、速度，非常适合三角超越函数的硬件实现，但同时也带来硬件资源占用增加的问题。如何尽可能减少CORDIC算法带来的硬件资源占用增加，是利用CORDIC算法实现三角超越函数的关键。本文提出一种改进型三角超越函数CORDIC硬件实现方案，该方案中CORDIC算法IP核利用VHDL语言进行编写，IP核在Modelsim 6.5g上通过功能仿真，并且在XUPV5-LX110T FPGA开发板上通过硬件测试，实验结果表明改进的方案可以有效减少CORDIC算法带来的硬件资源占用增加。
【关键词】CORDIC；三角超越函数；VHDL；FPGA
An Improved CORDIC Implementation of Trigonometric Transcendental Functions Based on FPGA
Chen Bingcheng
（Foshan Synwit Technology Co.，Ltd.，Foshan 528000，China）
Abstract：By converting complex arithmetic into simple operations such as adding and shift then gradually approach the exact result，CORDIC algorithm keeps balance between precision and speed，which is very suitable for trigonometric transcendental functions hardware implementation and causes problem of hardware resource consumption increase，however.How to minimize the hardware resource consumption increase the CORDIC algorithm causes as much as possible is the key of trigonometric transcendental functions implementation using CORDIC algorithm.This paper presents an improved program of CORDIC hardware implementation of trigonometric transcendental functions.The IP core of CORDIC algorithm is coded through VHDL，simulated in Modelsim 6.5g software and successfully tested on XUPV5-LX110T FPGA development board.The experimental results show that the improved program could efficiently minimize the hardware resource consumption increase the CORDIC algorithm causes.
Keywords：CORDIC；trigonometric transcendental functions；VHDL；FPGA
1.引言
现代数字信号处理的一个主要发展趋势是，算法结构日趋复杂，计算量大，实时性要求高，且包含大量三角函数、开方等复杂超越函数计算[1]。但是MAC单元并不适合类函数的运算。而CORDIC算法可以将多种难以用硬件电路直接实现的复杂运算分解为统一的简单移位、加迭代运算，而且结构规则、运算周期可以预测，适合于VLSI实现[2]。许多数字信号处理算法，如DXT、FFT、复数滤波器、格型滤波器、基于Givens旋转的QR分解、奇异值/特征值分解、最小二乘求解及线性系统求解等，都很容易用圆周旋转或双曲旋转来描述其基本操作，因此都可以用CORDIC算法得到很好的实现。以CORDIC为核心的fpga应用日益受到人们的重视。
2.CORDIC算法原理
CORDIC是用于计算广义矢量旋转的一种迭代方法，由J.D.Volder于1959年提出[3]的，主要用于三角函数、双曲函数、指数和对数的运算。该算法使得矢量的旋转和定向运算不需要三角函数及乘法、开方、反三角函数等复杂的运算，仅需要进行加减和移位即可。1971年，Walther提出了统一的CORDIC算法[4]，引入了参数m将CORDIC实现的3种迭代模式：三角运算、双曲运算和线性运算统一于一个表达式下，形成目前所用到的CORDIC算法最基本的数学基础。该算法的基本思想是通过一系列固定的、与运算基数相关的角度不断偏摆以逼近所需的旋转角度，可由下列等式进行描述：
（1）
（2）
根据m=1、-1或0，分别称为圆周旋转运算、双曲旋转运算或线形旋转运算。其中：
（3）
使结果Z（n）=0的旋转成为旋转模式（rotation mode），使结果y（n）=0的旋转称为向量模式（vector mode）。为了能达到所要求的结果，各旋转角要满足下列条件：
（4）
（5）
其中，=0或1，和为非负整数值。
最通常的微转角选择方法为：
当m=1，；当m=-1时，；当m=0时，。
此时每一级迭代运算可以简化为：
（6）
（7）
（8）
可以仅由加法、减法和移位来实现，本级的微转角旋转方向由上一级运算结果和所处的旋转模式决定。
在所有级旋转之后需执行一次模校正运算，即乘以模校正因子，一旦如上旋转一系列微转角之后，无论每个微转角的方向如何，对于确定的m值，当n趋向于无穷大时，模校正因子趋近于一个极限值Km。因为CORDIC算法本身是一种逐位逼近算法，所以一般不论旋转级数n为多少，都直接应用其极限的二进制码作为模校正因子。
对于不同的m值、工作模式和初始值，可以产生不同的结果，如表1所示。
3.CORDIC算法的FPGA实现结构
有很多途径可以实现一个CORDIC处理器，理想的结构依赖于实际应用中的速度与资源的折中考虑。下面介绍两种比较常见的CORDIC处理器实现结构：迭代结构的CORDIC处理器和流水线结构的CORDIC处理器[5]。
3.1 迭代结构的CORDIC处理器
将CORDIC算法的三个公式（公式6、公式7和公式8）复制到硬件描述上，就可以简单地实现迭代的CORDIC结构，如图1所示。根据CORDIC旋转器工作于“旋转”模式还是“向量”模式，来决策变量di由y或者z寄存器控制。在实际工作时，初始化指由多路选择器加载到x、y、z寄存器，然后在接下去的n个时钟周期内，寄存器内的值通过移位寄存器输入到加/减法器，其输出又返回输入到寄存器。移位寄存器在每一步的迭代中都会修改，以获得本次迭代的正确移位次数。同时ROM（Lookup Table）地址也会在每一步迭代中递增，以将正确的单元角度值输入到z加减法器。最后一次迭代，计算结果就可以直接从加/减法器的输出得到。
以上迭代结构也称为串并结构，串并结构的移位寄存器不能很好的应用于FPGA，因为这个结构需要比较大的扇入能力[6]。如果用FPGA实现，可能会造成比较大的延时，处理速度上不去（下一次的迭代需要上一次迭代完成后才能继续进行，造成时间的很大浪费），并且输出结果由迭代次数决定，如图1所示。
3.2 流水线结构的CORDIC处理器
上面讨论的基于迭代结构的处理器可以进行展开，因此n个处理单元的每一个都可以同时并行处理一个相同的迭代运算。图2为展开的CORDIC处理器。首先，这些移位寄存器各自有不同的固定的移位次数，其次，角度累加器原本需要查找的角度值被拆分，作为角度累加器链中每个加法器的一个常量输入。这些常量可以用硬件连线来代替存储空间。整个CORDIC处理器被精简成一个内部互连的加/减法器阵列。这时候电路上成为组合逻辑，在FPGA中实现的时候，电路的延迟比较大，可以在每个加/减法器后插入寄存器，构成流水结构，这个可以提高系统工作速度。
4.CORDIC算法硬件资源改进分析
由图1和图2可知，当迭代N次时，利用迭代方式CORDIC结构实现只需要1个单位的硬件资源，但需要N个单位的处理时间；而利用流水线方式CORDIC结构实现则只需要1个单位的处理时间，但需要N个单位的硬件资源。迭代方式CORDIC结构具有串行结构节省硬件资源的优点，而流水线方式CORDIC结构具有并行结构节省处理时间的优点，如何利用好两者的优势找到硬件资源（面积）和处理时间（速度）的最好平衡点，是实际应用中使用硬件实现CORDIC算法的关键。
目前最常用的CORDIC硬件实现方式为流水线CORDIC结构，前面说过流水线CORDIC结构可以大大减少迭代处理时间，但同时会增大硬件资源。本文提出的改进实现方法就是在流水线CORDIC实现方式基础上作出的硬件资源优化，这样就能够实现既具有迭代实现方式节省硬件资源的优点，又具有流水线实现方式节省处理时间的优点，找到硬件资源（面积）和处理时间（速度）的平衡点。
通常硬件实现N级流水线CORDIC结构时，会按公式6、公式7和公式8定义N个N位的变量，对于公式6就要定义N个N位的X寄存器，即X0[N-1]、X1[N-1]、X2[N-1]…XN-1[N-1]，有时为了其他应用需要，会把寄存器定义为多1位或2位，如加1位最高位作为符号位和加1位用于防止数据溢出。同理对于公式7就要定义N个N位的Y寄存器，即Y0[N-1]、Y1[N-1]、Y2[N-1]…YN-1[N-1]。很明显N值越大，需要定义的寄存器就越多，寄存器的位数也越大，同时，在进行运算时需要更多的中间寄存器，以上的因素都会造成硬件资源占用的显著增加，而且流水线级数越大，迭代次数越多，这个资源增加的情况就越为明显。如果能够在寄存器定义上进行改进，将会大大减少硬件资源的占用。我们可以在寄存器上作以下的改进：定义一个迭代循环计数器REG_J，如需要迭代16次，REG_J计数器定义为REG_J[3：0]，可以表示从0到15的迭代。对于X迭代，定义寄存器AX[15：0]、BX[15：0]、CX[15：0]和DX[15：0]，当REG_J[3]为1时（即REG_J=“1xxx”），X值右移8位，然后存到寄存器AX；当REG_J[2]为1时（即REG_J=“x1xx”），X值右移4位，然后存到寄存器BX；当REG_J[1]为1时（即REG_J=“xx1x”），X值右移2位，然后存到寄存器CX；当REG_J[0]为1时（即REG_J=“xxx1”），X值右移1位，然后寄存到寄存器DX。REG_J每一位上的数字从0变为1都会产生对应位置的移位，然后16次迭代的迭代值只需要AX，BX，CX和DX寄存器进行保存，如REG_J为“1111”时，X值先右移8位存到AX，AX再移位4位存到BX，BX再右移2位存到CX，最后CX再右移1位存到DX，DX值进行公式运算，对于REG_J为其他值时也可以作相应的移位处理。同理对于Y的迭代，也可以做相同的处理，经过这样处理后寄存器资源将大大减少，实际使用的硬件资源也会减少。
图3为改进型cordic算法实现正余弦三角超越函数的仿真波形图，此时mode_in为0，表示当前处于计算sin/cos三角函数模式，输入角度为1Q14格式（即1位有效整数位，14位有效小数位，14次迭代）。当输入角度angle_in为0xaaa，即0.167π（0xaaa/214=0.167π，即30°）时，计算得到cos值为0x376C，即0.866（0x376C/214=0.866），sin值为0x2003，即0.500（0x2003/214=0.500）。同理输入角度angle_in为0x1000和0x1555即45°和60°时，计算得到cos值和sin值分别为0x2d44（即0.707）、0x2d3f（即0.707）和0x2003（即0.500）、0x376C（即0.866）。计算1次sin/cos值占用16个时钟周期，与14级流水线CORDIC结构占用时钟周期相当，运算精确度达到3位有效小数位。其他象限的sin/cos运算与第一象限类似，这里不再详述。
图4为改进型CORDIC算法实现反正切超越函数的仿真波形图，此时mode_in为1，表示当前处于计算arctan三角函数模式，输入输出为1Q14格式。当输入x_in为0x400，y_in为0x400，arctan（y_in/x_in）=0x1003，即0.250π（0x1003/214=0.250π，即45度）。当输入为x_in为0x400，y_in为0x200，arctan（y_in/x_in）=0x975，即0.148π（0x975/214=0.148π，即26.6度）。当输入x_in为0x400，y_in为0x800，arctan（y_in/x_in）=0x1691，即0.353π（0x1691/214=0.353π，即63.47度）。计算1次arctan值占用16个时钟周期，与14级流水线CORDIC结构占用时钟周期相当，运算精确度达到3位有效小数位。
图5为14级流水线CORDIC结构计算sin/cos时，在XC5V-LX110T FPGA上综合布线硬件资源报告。由图可知，14级流水线CORDIC结构计算sin/cos，总的硬件资源占用门数约为15571逻辑门。
图6为改进型CORDIC算法计算sin/cos及arctan（14级迭代）时，在XC5V-LX110T FPGA上综合布线硬件资源报告。由图可知，改进型CORDIC算法计算sincos及arctan（14级迭代），总的硬件资源占用门数约为4585逻辑门，比起用14级流水线CORDIC只计算sin/cos时使用的逻辑门还要少10000门以上，硬件资源占用大大减少，并且运算精度和运算的时间相当，都是3位有效小数位和16个时钟周期。
6.结语
目前改进型CORDIC算法已经在XUPV5-LX110T FPGA开发板上通过硬件测试，并且将应用于运动控制及滤波运算处理等领域。实践证明，改进型CORDIC算法可以有效减少CORDIC算法计算三角超越函数时带来的硬件资源占用增加。
参考文献
[1]田耘，徐文波，张延伟，等.无线通信FPGA设计[M].北京：电子工业出版社，2008.
[2]Andraka.A survey of CORDIC algorithms for FPGA based computers[A].1998：191-200.
[3]Volder.The CORDIC trigonometric computing technique[J].IRE Trans，1959：334-334.
[4]Walther.J.S.A unified algorithm for elementary functions[J].Spring Joint Computer Conf，1971：379-385.
[5]王钿，卓兴旺.基于Verilog HDL的数字系统应用设计（第2版）[M].北京：国防工业出版社，2007.
[6]刘凌，贝耶尔（U.Meyer-Baese）.数字信号处理的FPGA实现（第3版）[M].北京：清华大学出版社，2011.
作者简介：陈炳成（1983―），硕士，现供职于佛山华芯微特科技有限公司，主要研究方向：嵌入式系统新技术及SoC芯片设计技术。