高速低功耗CORDIC算法的研究與實現(xiàn)

胡普華，趙建龍，羅炬鋒，李 強

（1.中國科學院上海微系統(tǒng)與信息技術研究所 傳感技術聯(lián)合國家重點實驗室，上海200050；2.上?？萍即髮W 上海200120；3.上海物聯(lián)網(wǎng)中心 上海201800）

高速低功耗CORDIC算法的研究與實現(xiàn)

胡普華1，2，趙建龍1，2，羅炬鋒1，李 強3

（1.中國科學院上海微系統(tǒng)與信息技術研究所 傳感技術聯(lián)合國家重點實驗室，上海200050；2.上?？萍即髮W 上海200120；3.上海物聯(lián)網(wǎng)中心 上海201800）

針對傳統(tǒng)CORDIC算法流水線結(jié)構(gòu)的迭代次數(shù)過多，運算速度不夠快，消耗硬件資源較多的缺點，改進了一種基于旋轉(zhuǎn)模式并行運算的CORDIC算法。該算法采用二進制兩極編碼和微旋轉(zhuǎn)角編碼進行低位符號預測和高符號位預測，并且在高符號位預測過程中，對誤差進行了校正。在FPGA實現(xiàn)中，采取三段式實現(xiàn)方法，與傳統(tǒng)方法相比，有效地減少計算的級數(shù)和降低硬件資源的功耗，達到了高速低功耗的要求。

FPGA；符號預測；低功耗；二進制兩極編碼；微旋轉(zhuǎn)角編碼

通信設備之間的頻率偏差和終端移動引起的多普勒頻移，使得載波頻率與本地晶振之間存在較大的頻率偏移[1]。頻偏會引起無線通信性能惡化，因此需要做頻偏估計和糾正。而數(shù)字通信中的頻偏估計和糾正不可避免的用到三角函數(shù)[2]。在硬件設計中實現(xiàn)三角函數(shù)的運算，常用的方法有3種[3]：查找表法、級數(shù)展開法、CORDIC算法。其中查找表法占有資源少，但是精度不夠高；級數(shù)展開法使用了泰勒公式展開，運算復雜度比較高；CORDIC算法運算速度快，對資源需求比較靈活。

CORDIC算法是J.Volder[4]等人在美國航空控制系統(tǒng)中提出的，它是一種用于計算常用基本運算函數(shù)和算術操作循環(huán)迭代的算法。傳統(tǒng)的CORDIC算法根據(jù)不同的旋轉(zhuǎn)軌跡分成線性系統(tǒng)，雙曲線系統(tǒng)，圓周系統(tǒng)。

國內(nèi)外對CORDIC算法進行深入的研究。法國Christophe Mazenc[5]提出了計算反正弦和反余弦的CORDIC結(jié)構(gòu)；Tso-Bing Juang[6]提出了一種低延遲角重編碼方法來應用于高位寬并行CORDIC算法。電子科技大學的甘露[7]、南京大學談宜育[8]以及西北工業(yè)大學丘偉[9]等，針對CORDIC算法的實現(xiàn)和應用提出了改進方案，在不同程度上提高了傳統(tǒng)算法的速度和效率。CORDIC算法的研究趨勢是高精度，高進制，低功耗，高吞吐率。傳統(tǒng)算法要實現(xiàn)高精度和高進制，就不得不增加迭代次數(shù)，使用更多的流水線結(jié)構(gòu)。然而，這種方法勢必導致消耗更多的硬件資源，增加功耗。

針對上述分析，文中提出一種改進型并行CORDIC算法，能夠有效的減少迭代次數(shù)，在保證精度的前提下，降低功耗，使得算法效率更高。

1 CORDIC算法基本原理

根據(jù)（1）式的迭代關系，在硬件上，采用流水線結(jié)構(gòu)來實現(xiàn)三角函數(shù)的運算[10]。通過寄存器、移位器、加減器的協(xié)同運作來實現(xiàn)三角函數(shù)的計算。如圖1所示，每一級CORDIC迭代運算都使用單獨的一套運算單元，它的運算速度非?？?，流水線使用占滿之后，每個時鐘周期就會運算得出一組結(jié)果，使得高速實時處理數(shù)據(jù)得以實現(xiàn)。移位的位數(shù)等于當前的迭代級數(shù)，加減法選擇由該級中Z的最高（符號位）決定，得到下一級的x，y，Z的值。經(jīng)過N級流水線運算后，Z的值變?yōu)?，x，y的值則為cosZ0、sinZ0。每一級電路結(jié)構(gòu)包含有3個加減法器，2個移位器，每級電路之間直接相連，不需要額外的寄存器。

圖1 傳統(tǒng)CORDIC算法流水結(jié)構(gòu)圖

傳統(tǒng)CORDIC算法通過移位寄存器和加減法器將復雜的三角函數(shù)運算大大簡化，但是該算法處理的字長有多少位，就需要多少級迭代流水線結(jié)構(gòu)。對于32位或者64位字節(jié)而言，需要32次或者64次迭代運算，所消耗的硬件資源較大。

2 并行CORDIC分段符號預測研究

傳統(tǒng)CORDIC算法是一個順序執(zhí)行迭代運算且線性收斂的算法。因此，對于N字節(jié)長度的數(shù)據(jù)，需要迭代運算N次，而且必須等待第i-1次迭代運算結(jié)束過后，第i次運算才能夠執(zhí)行。正是這些特性限制了算法的運算速度。因此，提高CORDIC算法的運算速度，可以在兩個方面著手：1）減少迭代次數(shù)；2）降低單個迭代運算消耗的時間。

2.1 低位符號預測研究

對照（3）式可以得到

則第1到第N位的轉(zhuǎn)換規(guī)則為下列規(guī)則（a）來運行。

例如，對12位的初始輸入角度為π/6所對應的旋轉(zhuǎn)方向如表1所示。

表1 符號預測實例

2.2 高位符號誤差校正

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

表2 N=32時，MAR轉(zhuǎn)換表格

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

采用上述方法，就可以將每次迭代運算的方向d的值直接求解出來，節(jié)省了資源和時間。

3 優(yōu)化算法的FPGA實現(xiàn)

在符號位預測中，分兩步驟將旋轉(zhuǎn)迭代的符號預測出來，節(jié)省了預判符號所消耗的時間，同時也提高了效率。在高位符號預測中，在2.2節(jié)的基礎上可以更進一步減少迭代次數(shù)，綜合（1）式，第i次迭代結(jié)果帶入第i+2次中，得到（7）式。

如此循環(huán)代入，可以得到k項和第n項的關系式（8）。

其中：

其中i，j，i1，i2…i2t都是屬于k到n之間的整數(shù)。其中i＜j, i1＜i2＜…＜i2t。

以32位字長為例，旋轉(zhuǎn)方向的符號位可以分三段來預測。第一段，即1-10次旋轉(zhuǎn)；第二段，即10-16次旋轉(zhuǎn)；第三段，即16-32次旋轉(zhuǎn)。

第一段，如圖2左側(cè)所示。將輸入的角度Z0采用二進制弧度來表示。依據(jù)（4）式可以得出至的值。將x=k，y=0輸入系統(tǒng)中，采用迭代方式獲得到x10，y10的值，并作為第二段的初始輸入值。

第二段，如圖2右側(cè)所示。依據(jù)（6）式，獲得校正過后的d11至d32的值，并只將d11至d16輸入系統(tǒng)中采取迭代方式獲得x16，y16的值。

第三段，如圖4所示。依據(jù)（9）式，將剩下的d17至d32合并成一項，完成最后一次迭代關系，直接求出xn=cosθ，yn=sinθ的值。

綜上，只在第一段和第二段進行了旋轉(zhuǎn)符號判斷。此外，迭代的次數(shù)只有17次，相比傳統(tǒng)算法減少了15次。

圖2 N=32第一段和第二段旋轉(zhuǎn)迭代原理圖

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

圖4 第三段求解結(jié)構(gòu)圖

在Xilinx系列的Zynq-7000開發(fā)板上實現(xiàn)32位字長的并行改進版CORDIC算法。分三段實現(xiàn)該算法。統(tǒng)計出來的數(shù)據(jù)如下表。相較于傳統(tǒng)算法而言，改進的算法對組合邏輯資源的占用僅為傳統(tǒng)算法的86.74%，寄存器的使用個數(shù)僅為傳統(tǒng)算法的41.42%，迭代次數(shù)僅為傳統(tǒng)算法的53.13%。

表3 改進算法和傳統(tǒng)算法比較

4 結(jié) 論

文中討論了旋轉(zhuǎn)模式下的CORDIC算法的符號預測機制。采用了高符號位和低符號位預測，在硬件實現(xiàn)中，提出了三段式實現(xiàn)方法。通過實驗驗證，該算法減少了資源的使用，降低了功耗。同時，減少的迭代次數(shù)，使得運算速度更加快速。符合低功耗，高速度芯片應用場景。

[1]袁彥春.OFDM頻偏估計算法研究[D].重慶：西南交通大學，2014.

[2]李凱.OFDM系統(tǒng)中同步算法的研究[D].上海：復旦大學，2012.

[3]吳慶達，何書專，潘紅兵，等.32位定浮點數(shù)正余弦函數(shù)FPGA實現(xiàn)方法[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].數(shù)據(jù)采集與處理，2004，16（2）:257-260.

[9]邱偉，劉詩斌.基于CORDIC的一種參數(shù)化小波變換及其實現(xiàn)[J].網(wǎng)絡新媒體技術，2006，27（3）:268-271.

[10]孔德元.針對正弦余弦計算的CORDIC算法優(yōu)化及其FPGA實現(xiàn)[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—），男，湖北黃岡人，碩士。研究方向：微電子學與固體電子學。