一种CORDIC算法优化及32位浮点反正切函数FPGA实现

2015-10-19鲍宜鹏

电子与封装 2015年3期

关键词：加法器浮点时钟

鲍宜鹏

（中国电子科技集团公司第58研究所，江苏无锡 214035）

一种CORDIC算法优化及32位浮点反正切函数FPGA实现

鲍宜鹏

（中国电子科技集团公司第58研究所，江苏无锡 214035）

通过对反正切函数实现算法的研究，在传统CORDIC算法的基础上，提出了一种以超前进位加法器为基本单元的迭代结构，双时钟输入，完成了反正切函数的ASIC电路设计。该算法采用TSMC 55 nm工艺，在Synopsys/syn10.12环境中综合实现。该算法的关键路径由原来的2.9 ns提升至1.3 ns，最高运算频率可以达到769 MHz，即优化后的CORDIC算法比优化前速率提高了2倍多。

CORDIC 算法；分层次超前进位加法；反正切函数

1　引言

在导航通信、数字信号处理等许多领域都会大量使用反正切函数进行必要的计算。随着其应用越来越广泛，在硬件上快速简单地实现浮点反正切函数的需求越来越大。

CORDIC（Coordinate Rotation Digital Computer）［1］算法是实现反正切函数最常用的方法之一，它非常适合在FPGA中实现。近几年，国内外学者对该算法都作了相应的改进，而在优化过程中，运算速度和精度是影响算法优劣的关键因素。正因为CORDIC算法的复杂性以及速度和精度尚待提高，使得该算法还有一定的改进空间。

2　CORDIC算法原理

传统的CORDIC算法在1971年由J S Walther提出了统一的算法形式［1］，将原来的圆周旋转、双曲旋转和线性旋转统一到了同一个迭代方程里。该算法分为旋转模式和向量模式，本节主要讲述圆周系统向量模式的基本原理。

2.1圆周系统原理

设有向量（XA， YA），在平面旋转α角到（XB，YB），如图1所示。取R为半径，α为旋转角，β为向量（XA， YA）离x轴的偏转角。由极坐标公式可得：

图1 平面坐标旋转图

转换成矩阵形式：

将旋转角α分解为N个递减的旋转角αi之和，即，其中αi≥0，δi的值取决于角度偏摆时是否逆时针偏摆。若为逆时针偏摆则为1，反之为-1。这样，使得只与运算基数相关的角度不断偏摆从而逼近所需旋转的角度α值。对于单次旋转有：

其中（XA， YA）=（X0， Y0），（XB， YB）=（XN， YN）。

令αi=tan-1（2-i），

则tanαi=2-i，那么

当N→∞，K→0.607 253，K可以看作一个常量，其中i=0，1，2，…N-1，通常来讲，K被称为校正因子、增益因子或聚焦常数。

则式（3）可以改为：

提取K因子，式（3）可以化简为式（6）：

则（XA， YA）=（X0， Y0），（XB， YB）=K（XN，YN），所以在实际计算时可以将K当作一个常量，直接计算式（6），到最后乘以系数K就可以了。

将式（6）再转化为方程形式，有迭代式（7）：

在运算中，为了确定偏摆角偏摆方向，求得δi值，需要再添加一个变量θi来确定每次旋转过后的剩余角。将其定义为：

θi+1=θi-δitan-1（2-i），i=0，1，2，…N-1 （8）

2.2向量模式

根据2.1节的圆周系统原理介绍，这里将讨论向量模式下CORDIC算法的迭代算法。设旋转角度初值为θ0=α，每次旋转角度剩余角设为θi，经过N次旋转以后，最终θN= 0。在旋转过程中，有：

这样的模式就是旋转模式。根据2.1节和式（7），可知CORDIC迭代式为：

假设将输入向量通过一个特定的角将Y角变为0，且旋转的方向取决于Y的符号，则当旋转N次后，式（10）变为：

式（11）即为CORDIC算法的反正切函数的基本迭代结构。其中P为旋转增益，P≈1.646 76。在硬件中实现该结构时，对于给定的X0和Y0，只需要设置Z0=0，就可以计算出反正切函数的值了。

3　CORDIC算法的优化

3.1传统的CORDIC迭代结构

实现CORDIC算法的硬件架构有多种不同的设计方法，理想的CORDIC算法硬件架构是运行速度和资源面积的折中，目前主要有两种方式。一种是流水线结构实现方法，由多个单元组成，除第一次计算比较耗时外，可在每次输入进程的同时输出数据，极大提高了数据吞吐量，相对运算速度提高了很多。但其硬件资源花销较大，流水线级数越高，硬件资源需成倍增长。另一种是迭代结构实现方法，由单个迭代单元经过N次迭代完成运算，硬件资源消耗少，但每次迭代的时钟延迟比流水线结构长。本文采用迭代结构，在较少资源的情况下，实现运行速度最大化。）

传统的CORDIC迭代算法是一种反馈结构，通过迭代运算单元实现，其经典的硬件实现方式［3］如图2所示。它主要由控制单元、选择器、移位寄存器、ROM以及若干加法器构成。在时钟信号的驱动下，将本级输出反馈回输入，直到迭代完毕，最终计算出结果。在节省硬件资源的前提下追求较高运算速度，只能通过进一步优化迭代结构中的加法器或者针对CORDIC算法内部进一步优化来达到所需目标。

图2　经典迭代结构

3.2分层次流水线超前进位加法的实现

虽然随着半导体技术的发展，芯片的集成度越来越高，面积越来越小，性能也要求越来越高，这些都离不开单个IP模块功能的优化，以及对硬件电路的改进。运算速度是其性能的关键之一。采用分层流水线超前进位方式正好能提高CORDIC迭代结构的速度。

对于纯组合的全加器结构，其硬件开销小，进位方式逻辑清楚，电路简单，每个全加器都有延时存在，下一个全加器的进位依赖于上一个全加器的进位输出，导致延时较大。目前多数加法器都作了相应的改进，比如采用超前进位加法器，使其延时大大降低。本文也不例外，但即使采用超前进位加法器，加法运算依然在CORDIC算法中占用了大量的时序，因此需要对超前进位加法器作相应改进以提高其时序。这里主要采用流水结构来提高加法器的吞吐量，如图3所示。

本文所计算的数据为32位单精度浮点数，采用IEEE-754标准数据格式，先将浮点数转化为定点数，对输入数据进行选择。然后对整个运算单元进行优化，将加法结构分为四层流水线的加法结构，每一层次的延时接近相等。第一层为P-G单元层，将32位定点数分为8组四位超前进位加法器并行执行，设A和B分别为加数与被加数，则第一层次需要计算组内的P和G（P = AB，G= A&B），然后计算每组之间的PP和GG（PP ［N］= &P［N+3：0］，GG［N］=G［N+3］ |（P［N+3］&（G［N+2］ | P［N+2］&（G［N+1］| P［N+1］ & G［N］））），并初始进位C0锁存。第二层锁存上一层次的P、G以及C0，计算每组之间的进位C3、C7、C11，并在假设C15为0和1的情况下分别计算C19、C23、C27。第三层为锁存上一层次的P、G以及C0，计算PPP，GGG（PPP［N］ = &P［N+3：0］，GGG［N］=GG［N+3］ |（PP［N+3］&（G［GN+2］| PP［N+2］&（GG［N+1］ | PP［N+1］ & GG［N］）））。第四层计算出C15的取值，根据C15的取值，计算出所有进位，进而计算出和以及进位。

图3　流水线超前进位加法的CORDIC实现

该CORDIC算法用VHDL语言描述，核心逻辑如下：

assign yn = yi［31］ == 0 ？ b_in ：｛～b_in［31］，～b_ in［30：0］+1'b1｝；

assign xn = yi［31］ == 0 ？｛～a_in［31］，～a_in［30：0］+1｝： a_in；

assign zn = yi［31］ == 0 ？ atan_i ：｛～atan_i［31］，～atan_ i［30：0］+1'b1｝；

cadder_top cadder_x（

.clk（clk_add），

.rst（rst_add），

.a（xi），

.b（yn），

.c0_1（1'b0），

.s（xo_core），

.cout（cout_x）

）；

cadder_top cadder_y（

.clk（clk_add），

.rst（rst_add），

.a（yi），

.b（xn），

.c0_1（1'b0），

.s（yo_core），

.cout（cout_y）

）；

cadder_top cadder_z（

.clk（clk_add），

.rst（rst_add），

.a（zi），

.b（zn），

.c0_1（1'b0），

.s（zo_core），

.cout（cout_z）

）；

采用双时钟技术，用在超前进位加法器的时钟频率是前置处理单元和后置处理单元的4倍，该迭代结构一共迭代26次，用了27个时钟周期，加法器流水线为4层。在工艺为TSMC 55 nm的条件下，该算法的关键路径由原先的2.9 ns提升至1.3 ns，可以达到769 MHz。也就是说优化后的CORDIC算法比优化前速率提高了2倍多。

3.3CORDIC算法的实现及仿真综合

CORDIC前置单元根据IEEE-754数据格式［4］，将32位的浮点数据转换为32位定点数据，以便在内核中移位和加减法运算。在前置单元对输入数据进行选择，将选择的值送入核心逻辑。后置处理单元，主要对角度的象限进行判断，以选择正确的角度输出，其逻辑如下：

angle_sign =｛yi_pre［31］，xi_pre［31］｝；

assign angle_0 = 32'h8000_0000-zo_post；//180-zo assign angle_1 = zo_post+32'h8000_0000；//z0+180 assign angle_2 = 32'h8000_0000-zo_post；//zo+270 assign angle_i =（angle_sign ==2'b00）？zo_post：

（a n g l e_s i g n==2'b 0 1）？a n g l e_0：（a n g l e_ sign==2'b11）？angle_1：angle_2；

整个硬件模块采用Verilog HDL语言进行描述，双时钟输入，4级的分层次超前进位加法器，角度以及计算结果均采用32位IEEE-754数据格式表示，每次计算需要花费26个周期完成。在cds/incisiv102环境下，调用NC_SIM，选取xi=36'h376cf5d0（cos30°），yi =36'h020000000（sin30°）时的计算结果（见图4）。在图4的仿真波形中，超前进位加法器有自己的时钟和复位信号，i信号为迭代次数，ovld 为输出角度有效信号， xi_pre、yi_pre、zi_pre分别表示输入的初值，xo_post、yo_post、zo_post表示1个运算周期结束时的输出值，一次迭代过程用了26个周期，用时55 ns。

图4　输入角度为cos30°、sin30°时的仿真结果图

表1为理想值与实际计算结果的比较。由表1可以看出，计算结果的IEEE-754定点数据能够保证6位有效数字无误差，即精度可以达到1/100 000度，满足一般应用需求。

表1　理想值与实际计算结果比较

4　总结

本文提出了一种以流水的分层次超前进位加法器为基本单元的迭代结构算法，采用双时钟输入，完成了该算法的综合及仿真设计，充分体现了硬件实现的优越性。该算法比CORDIC纯流水线结构节省了很多资源，比传统迭代算法提高了频率，满足在一定的工艺条件下对时钟频率的要求，在一定程度上弥补了CORDIC算法迭代结构和流水线结构在速度与资源消耗之间的不足。

［1］ VOLDER J E. The CORDIC trigonometric computing technique ［J］. IRE Trans. Electronic Computers， 1959. EC-8（3）：330-334.

［2］ WALTHER J s. A unified algorithm for elementary functions ［C］. spring Joint computer conf. New York， NY，USA. 1971. 379-385.

［3］陈石平，李全，付细华，段结海. 32位浮点正余弦函数的FPGA实现［J］. 微计算机信息，2012， 29（8）：111-114.

［4］高延滨，阙兴，涛彭浩. 单浮点cordic算法的FPGA实现及其在导航算法中的应用［J］. 导航与控制，2010， 2：8-9.

One Improved CORDIC Algorithm of Calculating 32 bit Floating the Arctangent Functions with FPGA

BAO Yipeng
（China Electronics Technology Group Corporation No.58 Research Institute， Wuxi 214035， China）

Through the study of algorithms implements of the arctangent function， proposed a hierarchical carry lookahead adder structure as the basic unit of iterations basing on traditional CORDIC algorithms，double clock input， completed the ASIC circuit design of the arctangent function. The algorithm applied TSMC 55 nm process and achieved a comprehensive in Synopsys/syn 10.12 environment. The key way of the algorithm was reduced from 2.9 ns to 1.3 ns， the highest operation frequency is able to reach 769 MHz，the speed of the whole system was twice more than the original design.

CORDIC algorithm； hierarchical lookahead adder； cosine-sine functions