一種CORDIC算法優(yōu)化及32位浮點(diǎn)反正切函數(shù)FPGA實(shí)現(xiàn)

鮑宜鵬

（中國(guó)電子科技集團(tuán)公司第58研究所，江蘇 無錫 214035）

一種CORDIC算法優(yōu)化及32位浮點(diǎn)反正切函數(shù)FPGA實(shí)現(xiàn)

鮑宜鵬

（中國(guó)電子科技集團(tuán)公司第58研究所，江蘇 無錫 214035）

通過對(duì)反正切函數(shù)實(shí)現(xiàn)算法的研究，在傳統(tǒng)CORDIC算法的基礎(chǔ)上，提出了一種以超前進(jìn)位加法器為基本單元的迭代結(jié)構(gòu)，雙時(shí)鐘輸入，完成了反正切函數(shù)的ASIC電路設(shè)計(jì)。該算法采用TSMC 55 nm工藝，在Synopsys/syn10.12環(huán)境中綜合實(shí)現(xiàn)。該算法的關(guān)鍵路徑由原來的2.9 ns提升至1.3 ns，最高運(yùn)算頻率可以達(dá)到769 MHz，即優(yōu)化后的CORDIC算法比優(yōu)化前速率提高了2倍多。

CORDIC 算法；分層次超前進(jìn)位加法；反正切函數(shù)

1　引言

在導(dǎo)航通信、數(shù)字信號(hào)處理等許多領(lǐng)域都會(huì)大量使用反正切函數(shù)進(jìn)行必要的計(jì)算。隨著其應(yīng)用越來越廣泛，在硬件上快速簡(jiǎn)單地實(shí)現(xiàn)浮點(diǎn)反正切函數(shù)的需求越來越大。

CORDIC（Coordinate Rotation Digital Computer）［1］算法是實(shí)現(xiàn)反正切函數(shù)最常用的方法之一，它非常適合在FPGA中實(shí)現(xiàn)。近幾年，國(guó)內(nèi)外學(xué)者對(duì)該算法都作了相應(yīng)的改進(jìn)，而在優(yōu)化過程中，運(yùn)算速度和精度是影響算法優(yōu)劣的關(guān)鍵因素。正因?yàn)镃ORDIC算法的復(fù)雜性以及速度和精度尚待提高，使得該算法還有一定的改進(jìn)空間。

2　CORDIC算法原理

傳統(tǒng)的CORDIC算法在1971年由J S Walther提出了統(tǒng)一的算法形式［1］，將原來的圓周旋轉(zhuǎn)、雙曲旋轉(zhuǎn)和線性旋轉(zhuǎn)統(tǒng)一到了同一個(gè)迭代方程里。該算法分為旋轉(zhuǎn)模式和向量模式，本節(jié)主要講述圓周系統(tǒng)向量模式的基本原理。

2.1圓周系統(tǒng)原理

設(shè)有向量（XA， YA），在平面旋轉(zhuǎn)α角到（XB，YB），如圖1所示。取R為半徑，α為旋轉(zhuǎn)角，β為向量（XA， YA）離x軸的偏轉(zhuǎn)角。由極坐標(biāo)公式可得：

圖1 平面坐標(biāo)旋轉(zhuǎn)圖

轉(zhuǎn)換成矩陣形式：

將旋轉(zhuǎn)角α分解為N個(gè)遞減的旋轉(zhuǎn)角αi之和，即，其中αi≥0，δi的值取決于角度偏擺時(shí)是否逆時(shí)針偏擺。若為逆時(shí)針偏擺則為1，反之為-1。這樣，使得只與運(yùn)算基數(shù)相關(guān)的角度不斷偏擺從而逼近所需旋轉(zhuǎn)的角度α值。對(duì)于單次旋轉(zhuǎn)有：

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

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

則tanαi=2-i，那么

當(dāng)N→∞，K→0.607 253，K可以看作一個(gè)常量，其中i=0，1，2，…N-1，通常來講，K被稱為校正因子、增益因子或聚焦常數(shù)。

則式（3）可以改為：

提取K因子，式（3）可以化簡(jiǎn)為式（6）：

則（XA， YA）=（X0， Y0），（XB， YB）=K（XN，YN），所以在實(shí)際計(jì)算時(shí)可以將K當(dāng)作一個(gè)常量，直接計(jì)算式（6），到最后乘以系數(shù)K就可以了。

將式（6）再轉(zhuǎn)化為方程形式，有迭代式（7）：

在運(yùn)算中，為了確定偏擺角偏擺方向，求得δi值，需要再添加一個(gè)變量θi來確定每次旋轉(zhuǎn)過后的剩余角。將其定義為：

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

2.2向量模式

根據(jù)2.1節(jié)的圓周系統(tǒng)原理介紹，這里將討論向量模式下CORDIC算法的迭代算法。設(shè)旋轉(zhuǎn)角度初值為θ0=α，每次旋轉(zhuǎn)角度剩余角設(shè)為θi，經(jīng)過N次旋轉(zhuǎn)以后，最終θN= 0。在旋轉(zhuǎn)過程中，有：

這樣的模式就是旋轉(zhuǎn)模式。根據(jù)2.1節(jié)和式（7），可知CORDIC迭代式為：

假設(shè)將輸入向量通過一個(gè)特定的角將Y角變?yōu)?，且旋轉(zhuǎn)的方向取決于Y的符號(hào)，則當(dāng)旋轉(zhuǎn)N次后，式（10）變?yōu)椋?/p>

式（11）即為CORDIC算法的反正切函數(shù)的基本迭代結(jié)構(gòu)。其中P為旋轉(zhuǎn)增益，P≈1.646 76。在硬件中實(shí)現(xiàn)該結(jié)構(gòu)時(shí)，對(duì)于給定的X0和Y0，只需要設(shè)置Z0=0，就可以計(jì)算出反正切函數(shù)的值了。

3　CORDIC算法的優(yōu)化

3.1傳統(tǒng)的CORDIC迭代結(jié)構(gòu)

實(shí)現(xiàn)CORDIC算法的硬件架構(gòu)有多種不同的設(shè)計(jì)方法，理想的CORDIC算法硬件架構(gòu)是運(yùn)行速度和資源面積的折中，目前主要有兩種方式。一種是流水線結(jié)構(gòu)實(shí)現(xiàn)方法，由多個(gè)單元組成，除第一次計(jì)算比較耗時(shí)外，可在每次輸入進(jìn)程的同時(shí)輸出數(shù)據(jù)，極大提高了數(shù)據(jù)吞吐量，相對(duì)運(yùn)算速度提高了很多。但其硬件資源花銷較大，流水線級(jí)數(shù)越高，硬件資源需成倍增長(zhǎng)。另一種是迭代結(jié)構(gòu)實(shí)現(xiàn)方法，由單個(gè)迭代單元經(jīng)過N次迭代完成運(yùn)算，硬件資源消耗少，但每次迭代的時(shí)鐘延遲比流水線結(jié)構(gòu)長(zhǎng)。本文采用迭代結(jié)構(gòu)，在較少資源的情況下，實(shí)現(xiàn)運(yùn)行速度最大化。）

傳統(tǒng)的CORDIC迭代算法是一種反饋結(jié)構(gòu)，通過迭代運(yùn)算單元實(shí)現(xiàn)，其經(jīng)典的硬件實(shí)現(xiàn)方式［3］如圖2所示。它主要由控制單元、選擇器、移位寄存器、ROM以及若干加法器構(gòu)成。在時(shí)鐘信號(hào)的驅(qū)動(dòng)下，將本級(jí)輸出反饋回輸入，直到迭代完畢，最終計(jì)算出結(jié)果。在節(jié)省硬件資源的前提下追求較高運(yùn)算速度，只能通過進(jìn)一步優(yōu)化迭代結(jié)構(gòu)中的加法器或者針對(duì)CORDIC算法內(nèi)部進(jìn)一步優(yōu)化來達(dá)到所需目標(biāo)。

圖2　經(jīng)典迭代結(jié)構(gòu)

3.2分層次流水線超前進(jìn)位加法的實(shí)現(xiàn)

雖然隨著半導(dǎo)體技術(shù)的發(fā)展，芯片的集成度越來越高，面積越來越小，性能也要求越來越高，這些都離不開單個(gè)IP模塊功能的優(yōu)化，以及對(duì)硬件電路的改進(jìn)。運(yùn)算速度是其性能的關(guān)鍵之一。采用分層流水線超前進(jìn)位方式正好能提高CORDIC迭代結(jié)構(gòu)的速度。

對(duì)于純組合的全加器結(jié)構(gòu)，其硬件開銷小，進(jìn)位方式邏輯清楚，電路簡(jiǎn)單，每個(gè)全加器都有延時(shí)存在，下一個(gè)全加器的進(jìn)位依賴于上一個(gè)全加器的進(jìn)位輸出，導(dǎo)致延時(shí)較大。目前多數(shù)加法器都作了相應(yīng)的改進(jìn)，比如采用超前進(jìn)位加法器，使其延時(shí)大大降低。本文也不例外，但即使采用超前進(jìn)位加法器，加法運(yùn)算依然在CORDIC算法中占用了大量的時(shí)序，因此需要對(duì)超前進(jìn)位加法器作相應(yīng)改進(jìn)以提高其時(shí)序。這里主要采用流水結(jié)構(gòu)來提高加法器的吞吐量，如圖3所示。

本文所計(jì)算的數(shù)據(jù)為32位單精度浮點(diǎn)數(shù)，采用IEEE-754標(biāo)準(zhǔn)數(shù)據(jù)格式，先將浮點(diǎn)數(shù)轉(zhuǎn)化為定點(diǎn)數(shù)，對(duì)輸入數(shù)據(jù)進(jìn)行選擇。然后對(duì)整個(gè)運(yùn)算單元進(jìn)行優(yōu)化，將加法結(jié)構(gòu)分為四層流水線的加法結(jié)構(gòu)，每一層次的延時(shí)接近相等。第一層為P-G單元層，將32位定點(diǎn)數(shù)分為8組四位超前進(jìn)位加法器并行執(zhí)行，設(shè)A和B分別為加數(shù)與被加數(shù)，則第一層次需要計(jì)算組內(nèi)的P和G（P = AB，G= A&B），然后計(jì)算每組之間的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］））），并初始進(jìn)位C0鎖存。第二層鎖存上一層次的P、G以及C0，計(jì)算每組之間的進(jìn)位C3、C7、C11，并在假設(shè)C15為0和1的情況下分別計(jì)算C19、C23、C27。第三層為鎖存上一層次的P、G以及C0，計(jì)算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］）））。第四層計(jì)算出C15的取值，根據(jù)C15的取值，計(jì)算出所有進(jìn)位，進(jìn)而計(jì)算出和以及進(jìn)位。

圖3　流水線超前進(jìn)位加法的CORDIC實(shí)現(xiàn)

該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）

）；

采用雙時(shí)鐘技術(shù)，用在超前進(jìn)位加法器的時(shí)鐘頻率是前置處理單元和后置處理單元的4倍，該迭代結(jié)構(gòu)一共迭代26次，用了27個(gè)時(shí)鐘周期，加法器流水線為4層。在工藝為TSMC 55 nm的條件下，該算法的關(guān)鍵路徑由原先的2.9 ns提升至1.3 ns，可以達(dá)到769 MHz。也就是說優(yōu)化后的CORDIC算法比優(yōu)化前速率提高了2倍多。

3.3CORDIC算法的實(shí)現(xiàn)及仿真綜合

CORDIC前置單元根據(jù)IEEE-754數(shù)據(jù)格式［4］，將32位的浮點(diǎn)數(shù)據(jù)轉(zhuǎn)換為32位定點(diǎn)數(shù)據(jù)，以便在內(nèi)核中移位和加減法運(yùn)算。在前置單元對(duì)輸入數(shù)據(jù)進(jìn)行選擇，將選擇的值送入核心邏輯。后置處理單元，主要對(duì)角度的象限進(jìn)行判斷，以選擇正確的角度輸出，其邏輯如下：

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；

整個(gè)硬件模塊采用Verilog HDL語言進(jìn)行描述，雙時(shí)鐘輸入，4級(jí)的分層次超前進(jìn)位加法器，角度以及計(jì)算結(jié)果均采用32位IEEE-754數(shù)據(jù)格式表示，每次計(jì)算需要花費(fèi)26個(gè)周期完成。在cds/incisiv102環(huán)境下，調(diào)用NC_SIM，選取xi=36'h376cf5d0（cos30°），yi =36'h020000000（sin30°）時(shí)的計(jì)算結(jié)果（見圖4）。在圖4的仿真波形中，超前進(jìn)位加法器有自己的時(shí)鐘和復(fù)位信號(hào)，i信號(hào)為迭代次數(shù)，ovld 為輸出角度有效信號(hào)， xi_pre、yi_pre、zi_pre分別表示輸入的初值，xo_post、yo_post、zo_post表示1個(gè)運(yùn)算周期結(jié)束時(shí)的輸出值，一次迭代過程用了26個(gè)周期，用時(shí)55 ns。

圖4　輸入角度為cos30°、sin30°時(shí)的仿真結(jié)果圖

表1為理想值與實(shí)際計(jì)算結(jié)果的比較。由表1可以看出，計(jì)算結(jié)果的IEEE-754定點(diǎn)數(shù)據(jù)能夠保證6位有效數(shù)字無誤差，即精度可以達(dá)到1/100 000度，滿足一般應(yīng)用需求。

表1　理想值與實(shí)際計(jì)算結(jié)果比較

4　總結(jié)

本文提出了一種以流水的分層次超前進(jìn)位加法器為基本單元的迭代結(jié)構(gòu)算法，采用雙時(shí)鐘輸入，完成了該算法的綜合及仿真設(shè)計(jì)，充分體現(xiàn)了硬件實(shí)現(xiàn)的優(yōu)越性。該算法比CORDIC純流水線結(jié)構(gòu)節(jié)省了很多資源，比傳統(tǒng)迭代算法提高了頻率，滿足在一定的工藝條件下對(duì)時(shí)鐘頻率的要求，在一定程度上彌補(bǔ)了CORDIC算法迭代結(jié)構(gòu)和流水線結(jié)構(gòu)在速度與資源消耗之間的不足。

［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］ 陳石平，李全，付細(xì)華，段結(jié)海. 32位浮點(diǎn)正余弦函數(shù)的FPGA實(shí)現(xiàn)［J］. 微計(jì)算機(jī)信息，2012， 29（8）：111-114.

［4］ 高延濱，闕興，濤彭浩. 單浮點(diǎn)cordic算法的FPGA實(shí)現(xiàn)及其在導(dǎo)航算法中的應(yīng)用［J］. 導(dǎo)航與控制，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

TN402

A

1681-1070（2015）03-0022-04

鮑宜鵬（1985—），男，江蘇人，碩士研究生，研究方向?yàn)镾OC 設(shè)計(jì)方法學(xué)。

2014-11-10