胡普華，趙建龍，羅炬鋒，李 強(qiáng)

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

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

胡普華1，2，趙建龍1，2，羅炬鋒1，李 強(qiáng)3

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

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

FPGA；符號(hào)預(yù)測(cè)；低功耗；二進(jìn)制兩極編碼；微旋轉(zhuǎn)角編碼

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

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

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

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

1 CORDIC算法基本原理

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

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

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

2 并行CORDIC分段符號(hào)預(yù)測(cè)研究

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

2.1 低位符號(hào)預(yù)測(cè)研究

對(duì)照（3）式可以得到

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

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

表1 符號(hào)預(yù)測(cè)實(shí)例

2.2 高位符號(hào)誤差校正

所以對(duì)于32位字長(zhǎng)的算法而言，前10次迭代誤差求解方法如下：

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

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

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

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

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

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

其中：

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

以32位字長(zhǎng)為例，旋轉(zhuǎn)方向的符號(hào)位可以分三段來(lái)預(yù)測(cè)。第一段，即1-10次旋轉(zhuǎn)；第二段，即10-16次旋轉(zhuǎn)；第三段，即16-32次旋轉(zhuǎn)。

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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

[3]吳慶達(dá)，何書(shū)專，潘紅兵，等.32位定浮點(diǎn)數(shù)正余弦函數(shù)FPGA實(shí)現(xiàn)方法[J].微電子學(xué)與計(jì)算機(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]甘露，吳國(guó)綱，徐政五，等.改進(jìn)型MVR-CORDIC算法研究[J].電子科技大學(xué)學(xué)報(bào)，2004，33（5）:489-491.

[8]談宜育，卞文兵，李元.一種基于CORDIC算法的坐標(biāo)變換電路[J].數(shù)據(jù)采集與處理，2004，16（2）:257-260.

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

[10]孔德元.針對(duì)正弦余弦計(jì)算的CORDIC算法優(yōu)化及其FPGA實(shí)現(xiàn)[D].長(zhǎng)沙：中南大學(xué)，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 稿件編號(hào)：201512300

上海市浦江人才計(jì)劃資助（14PJ1433100）

胡普華（1990—），男，湖北黃岡人，碩士。研究方向：微電子學(xué)與固體電子學(xué)。