高速低功耗CORDIC算法的研究与实现

胡普华，赵建龙，罗炬锋，李 强

（1.中国科学院上海微系统与信息技术研究所 传感技术联合国家重点实验室，上海200050；2.上海科技大学 上海200120；3.上海物联网中心 上海201800）

高速低功耗CORDIC算法的研究与实现

胡普华1，2，赵建龙1，2，罗炬锋1，李 强3

（1.中国科学院上海微系统与信息技术研究所 传感技术联合国家重点实验室，上海200050；2.上海科技大学 上海200120；3.上海物联网中心 上海201800）

针对传统CORDIC算法流水线结构的迭代次数过多，运算速度不够快，消耗硬件资源较多的缺点，改进了一种基于旋转模式并行运算的CORDIC算法。该算法采用二进制两极编码和微旋转角编码进行低位符号预测和高符号位预测，并且在高符号位预测过程中，对误差进行了校正。在FPGA实现中，采取三段式实现方法，与传统方法相比，有效地减少计算的级数和降低硬件资源的功耗，达到了高速低功耗的要求。

FPGA；符号预测；低功耗；二进制两极编码；微旋转角编码

通信设备之间的频率偏差和终端移动引起的多普勒频移，使得载波频率与本地晶振之间存在较大的频率偏移[1]。频偏会引起无线通信性能恶化，因此需要做频偏估计和纠正。而数字通信中的频偏估计和纠正不可避免的用到三角函数[2]。在硬件设计中实现三角函数的运算，常用的方法有3种[3]：查找表法、级数展开法、CORDIC算法。其中查找表法占有资源少，但是精度不够高；级数展开法使用了泰勒公式展开，运算复杂度比较高；CORDIC算法运算速度快，对资源需求比较灵活。

CORDIC算法是J.Volder[4]等人在美国航空控制系统中提出的，它是一种用于计算常用基本运算函数和算术操作循环迭代的算法。传统的CORDIC算法根据不同的旋转轨迹分成线性系统，双曲线系统，圆周系统。

国内外对CORDIC算法进行深入的研究。法国Christophe Mazenc[5]提出了计算反正弦和反余弦的CORDIC结构；Tso-Bing Juang[6]提出了一种低延迟角重编码方法来应用于高位宽并行CORDIC算法。电子科技大学的甘露[7]、南京大学谈宜育[8]以及西北工业大学丘伟[9]等，针对CORDIC算法的实现和应用提出了改进方案，在不同程度上提高了传统算法的速度和效率。CORDIC算法的研究趋势是高精度，高进制，低功耗，高吞吐率。传统算法要实现高精度和高进制，就不得不增加迭代次数，使用更多的流水线结构。然而，这种方法势必导致消耗更多的硬件资源，增加功耗。

针对上述分析，文中提出一种改进型并行CORDIC算法，能够有效的减少迭代次数，在保证精度的前提下，降低功耗，使得算法效率更高。

1 CORDIC算法基本原理

根据（1）式的迭代关系，在硬件上，采用流水线结构来实现三角函数的运算[10]。通过寄存器、移位器、加减器的协同运作来实现三角函数的计算。如图1所示，每一级CORDIC迭代运算都使用单独的一套运算单元，它的运算速度非常快，流水线使用占满之后，每个时钟周期就会运算得出一组结果，使得高速实时处理数据得以实现。移位的位数等于当前的迭代级数，加减法选择由该级中Z的最高（符号位）决定，得到下一级的x，y，Z的值。经过N级流水线运算后，Z的值变为0，x，y的值则为cosZ0、sinZ0。每一级电路结构包含有3个加减法器，2个移位器，每级电路之间直接相连，不需要额外的寄存器。

图1 传统CORDIC算法流水结构图

传统CORDIC算法通过移位寄存器和加减法器将复杂的三角函数运算大大简化，但是该算法处理的字长有多少位，就需要多少级迭代流水线结构。对于32位或者64位字节而言，需要32次或者64次迭代运算，所消耗的硬件资源较大。

2 并行CORDIC分段符号预测研究

传统CORDIC算法是一个顺序执行迭代运算且线性收敛的算法。因此，对于N字节长度的数据，需要迭代运算N次，而且必须等待第i-1次迭代运算结束过后，第i次运算才能够执行。正是这些特性限制了算法的运算速度。因此，提高CORDIC算法的运算速度，可以在两个方面着手：1）减少迭代次数；2）降低单个迭代运算消耗的时间。

2.1 低位符号预测研究

对照（3）式可以得到

则第1到第N位的转换规则为下列规则（a）来运行。

例如，对12位的初始输入角度为π/6所对应的旋转方向如表1所示。

表1 符号预测实例

2.2 高位符号误差校正

所以对于32位字长的算法而言，前10次迭代误差求解方法如下：

表2 N=32时，MAR转换表格

下面，将误差并入高位ZH中。新校正的高位如（6）式所示：

采用上述方法，就可以将每次迭代运算的方向d的值直接求解出来，节省了资源和时间。

3 优化算法的FPGA实现

在符号位预测中，分两步骤将旋转迭代的符号预测出来，节省了预判符号所消耗的时间，同时也提高了效率。在高位符号预测中，在2.2节的基础上可以更进一步减少迭代次数，综合（1）式，第i次迭代结果带入第i+2次中，得到（7）式。

如此循环代入，可以得到k项和第n项的关系式（8）。

其中：

其中i，j，i1，i2…i2t都是属于k到n之间的整数。其中i＜j, i1＜i2＜…＜i2t。

以32位字长为例，旋转方向的符号位可以分三段来预测。第一段，即1-10次旋转；第二段，即10-16次旋转；第三段，即16-32次旋转。

第一段，如图2左侧所示。将输入的角度Z0采用二进制弧度来表示。依据（4）式可以得出至的值。将x=k，y=0输入系统中，采用迭代方式获得到x10，y10的值，并作为第二段的初始输入值。

第二段，如图2右侧所示。依据（6）式，获得校正过后的d11至d32的值，并只将d11至d16输入系统中采取迭代方式获得x16，y16的值。

第三段，如图4所示。依据（9）式，将剩下的d17至d32合并成一项，完成最后一次迭代关系，直接求出xn=cosθ，yn=sinθ的值。

综上，只在第一段和第二段进行了旋转符号判断。此外，迭代的次数只有17次，相比传统算法减少了15次。

图2 N=32第一段和第二段旋转迭代原理图

图3 第一段及第二段R（i）原理图

图4 第三段求解结构图

在Xilinx系列的Zynq-7000开发板上实现32位字长的并行改进版CORDIC算法。分三段实现该算法。统计出来的数据如下表。相较于传统算法而言，改进的算法对组合逻辑资源的占用仅为传统算法的86.74%，寄存器的使用个数仅为传统算法的41.42%，迭代次数仅为传统算法的53.13%。

表3 改进算法和传统算法比较

4 结 论

文中讨论了旋转模式下的CORDIC算法的符号预测机制。采用了高符号位和低符号位预测，在硬件实现中，提出了三段式实现方法。通过实验验证，该算法减少了资源的使用，降低了功耗。同时，减少的迭代次数，使得运算速度更加快速。符合低功耗，高速度芯片应用场景。

[1]袁彦春.OFDM频偏估计算法研究[D].重庆：西南交通大学，2014.

[2]李凯.OFDM系统中同步算法的研究[D].上海：复旦大学，2012.

[3]吴庆达，何书专，潘红兵，等.32位定浮点数正余弦函数FPGA实现方法[J].微电子学与计算机，2012，29（1）：113-116.

[4]Volder J E.The cordic trigonometric computing technique[C] //IRE Transactions on electronic computers.1959:330-334.

[5]Mazenc C，Merrheim X，Muller J M.Computing functions arccos and arcsin using CORDIC[J].IEEE Transactions on Computers，1993，42（1）:118-122.

[6]Juang T B.Low latency angle recoding methods for the higher bit-width parallel CORDIC rotator implementations[J]. Circuits&Systems II Express Briefs IEEE Transactions on，2008，55（11）:1139-1143.

[7]甘露，吴国纲，徐政五，等.改进型MVR-CORDIC算法研究[J].电子科技大学学报，2004，33（5）:489-491.

[8]谈宜育，卞文兵，李元.一种基于CORDIC算法的坐标变换电路[J].数据采集与处理，2004，16（2）:257-260.

[9]邱伟，刘诗斌.基于CORDIC的一种参数化小波变换及其实现[J].网络新媒体技术，2006，27（3）:268-271.

[10]孔德元.针对正弦余弦计算的CORDIC算法优化及其FPGA实现[D].长沙：中南大学，2008.

[11]Juang T B，Hsiao S F，Tsai M Y.Para-CORDIC:parallel CORDIC rotation algorithm[J].Circuits&Systems I Regular Papers IEEE Transactions on，2004，51（8）:1515-1524.

[12]Hsiao S F，Hu Y H，Juang T B.A memory-efficient and high-speed sine/cosine generator based on parallel CORDIC rotations[J].Signal Processing Letters IEEE，2004，11（2）: 152-155.

[13]Ross D M，Miller S，Sima M，et al.Exploration of sign precomputation-based CORDIC in reconfigurable systems[C]// Circuits，Systems and Computers，1977.Conference Record. 1977 11th Asilomar Conference on.2011:2186-2191.

[14]Angarita F，Canet M J，Sansaloni T，et al.Efficient mapping of CORDIC algorithm for OFDM-based WLAN[J].Journal of Signal Processing Systems，2008，52（2）:181-191.

[15]Juang T B.Area/Delay Efficient Recoding Methods for Parallel CORDIC Rotations[C]//Circuits and Systems，2006. APCCAS 2006.IEEE Asia Pacific Conference on.IEEE，2006:1539-1542.

Research and implementation of the high-speed and low-power dissipation CORDIC algorithm

HU Pu-hua1，2，ZHAO Jian-long1，2，LUO Ju-feng1，LI Qiang3
（1.Shanghai Institute of Microsystem and Information Technology，State Key Laboratory of Transducer Technology，Chinese Academy of Science，Shanghai 201800，China；2.Shanghai Tech University，Shanghai 200120，China；3.Shanghai Center for internet of Things，Shanghai 201800，China）

In this paper，a new parallel coordinate rotation digital computer（CORDIC）rotation algorithm in circular is proposed.The rotation number of conventional CORDIC algorithm is too large and the conventional algorithm is not efficiency. In order to improve the CORDIC algorithm，we use the binary-to-bipolar recoding（BBR）and microrotation angle recoding（MAR）to predict the lower part and higher part of the direction of rotation.Compared to conventional CORDIC algorithm，the proposed method needs fewer iterations and less hardware resources and operates faster.The lower sign precomputation and higher sign precomputation is processed respectively and error correction is done during the high sign bit prediction.The three-phase implementation method is applied on FPGA，which can reduce the operation series and power consumption effectively and meets the requirement of high-speed and low-power dissipation.

FPGA；sign precomputation；low-power dissipation；Binary-to-Bipolar Recoding（BBR）；Microrotation Angle Recoding（MAR）

TN911.7

A

1674－6236（2016）24-0144-04

2015-12-29 稿件编号：201512300

上海市浦江人才计划资助（14PJ1433100）

胡普华（1990—），男，湖北黄冈人，硕士。研究方向：微电子学与固体电子学。