高速高精度固定角度旋轉(zhuǎn)CORDIC算法的設(shè)計與實現(xiàn)

張朝柱，韓吉南，燕慧智

(哈爾濱工程大學(xué)，黑龍江哈爾濱150001)

?

高速高精度固定角度旋轉(zhuǎn)CORDIC算法的設(shè)計與實現(xiàn)

張朝柱，韓吉南，燕慧智

(哈爾濱工程大學(xué)，黑龍江哈爾濱150001)

摘要:固定角度旋轉(zhuǎn)的CORDIC(Coordinate Rotation Digital Computer)算法已經(jīng)廣泛的應(yīng)用于高速數(shù)字信號處理、圖像處理、機器人學(xué)等領(lǐng)域．針對固定角度旋轉(zhuǎn)CORDIC算法在相位旋轉(zhuǎn)過程中，存在數(shù)據(jù)吞吐率較高、占用硬件資源較多且資源消耗量大等缺點，提出了利用混合CORDIC算法，將角度旋轉(zhuǎn)分為單向角度旋轉(zhuǎn)和一次角度估計旋轉(zhuǎn)兩部分．本文根據(jù)欠阻尼理論，將固定角度旋轉(zhuǎn)采用單向旋轉(zhuǎn)CORDIC算法實現(xiàn)，減少了流水線的級數(shù)和迭代符號位的判決，然后通過對角度估計旋轉(zhuǎn)的二進制表示，修正常數(shù)因子，再根據(jù)角度映射關(guān)系進行相關(guān)處理，完成高速高精度坐標旋轉(zhuǎn)．最后在硬件平臺上進行了仿真實驗．實驗結(jié)果表明，在誤差范圍一定的前提下，混合算法進一步的減少了迭代次數(shù)，并且資源消耗較低，提高了數(shù)據(jù)吞吐率．

關(guān)鍵詞:坐標旋轉(zhuǎn)數(shù)字算法;固定角度旋轉(zhuǎn);流水線結(jié)構(gòu);現(xiàn)場可編程門陣列

1　引言

Volder提出的坐標旋轉(zhuǎn)數(shù)字計算方法(CORDIC)以其運算及硬件結(jié)構(gòu)簡單和多能性而倍受關(guān)注，并已廣泛應(yīng)用于信號處理領(lǐng)域．針對其實現(xiàn)的硬件結(jié)構(gòu)，國內(nèi)外學(xué)者也進行了大量研究［1～4］．在近期的研究工作中，乘法器的設(shè)計與實現(xiàn)成為了其在數(shù)字信號處理領(lǐng)域的一個新熱點［5～8］．但是對于固定相位旋轉(zhuǎn)的設(shè)計與實現(xiàn)的研究較少．

固定旋轉(zhuǎn)角度的CORDIC算法已經(jīng)廣泛的應(yīng)用在高速數(shù)字信號處理、機器人學(xué)、動畫片等領(lǐng)域．在高速數(shù)字信號處理領(lǐng)域，數(shù)字控制振蕩器NCO(Numerical Controlled Oscillator)，是數(shù)字下變頻的重要組成部分．機器人的平行移動通過小角度的旋轉(zhuǎn)，從而完成坐標值的連續(xù)疊加［6］．計算機圖形中關(guān)鍵幀的插入可以采用固定旋轉(zhuǎn)角度的CORDIC旋轉(zhuǎn)［8］．

為了解決CORDIC算法中由于迭代次數(shù)較多，從而處理時間增加的問題，目前國內(nèi)外一些學(xué)者致力于減少算法的延時．文獻［9］提出了一種基于控制理論的任意角度旋轉(zhuǎn)方法，但是以迭代次數(shù)的增加為代價．在文獻［10，11］中，由于每一次迭代會產(chǎn)生更多的位數(shù)，高進制數(shù)的CORDIC算法減少了迭代次數(shù)，然而Sn的判定增加了循環(huán)迭代的時間．文獻［12］提出了預(yù)測旋轉(zhuǎn)方向，并針對誤差進行分析和消除，具有速度快等優(yōu)點，但是并沒有給出使用各種硬件結(jié)構(gòu)實現(xiàn)此種算法的效果，更沒有將實驗結(jié)果進行比對．文獻［13］提出了基于相位旋轉(zhuǎn)估計的改進混合式CORDIC算法，提高了輸出數(shù)據(jù)精度，但是迭代次數(shù)依然較多，并且硬件資源的一半以上完成的是移位寄存器的操作．

2　傳統(tǒng)CORDIC算法

1959年，Voder提出CORDIC算法，1971年Walther統(tǒng)一了該算法的形式，Meyer-base第一次利用FPGA實現(xiàn)了該算法［14］．其基本思想是從起始點(xi，yi)按照一定的相位不斷進行矢量旋轉(zhuǎn)，逐步逼近最終點(xj，yj)．其向量旋轉(zhuǎn)示意圖如圖1所示．

根據(jù)極坐標知識和圖1易得:

從起始位置到終點位置的旋轉(zhuǎn)過程可以通過多步來實現(xiàn)，每步只旋轉(zhuǎn)一定相位，則:

把cosθn提取出來，式(2)可重寫為:

cosθn可以通過在最終結(jié)果上乘一個已知的常數(shù)K來加以消除．例如，當(dāng)?shù)螖?shù)P =16時，且|θ|≤π/4，有:

所以，在相位旋轉(zhuǎn)過程中，cosθn項可以不予考慮，最后得到旋轉(zhuǎn)迭代公式為:

引入?yún)?shù)z，用來判斷迭代何時結(jié)束，zn +1= zn－θn，z0=θ．這樣當(dāng)zn＜θ時，Sn=－1;當(dāng)znθ時，Sn= + 1．如果(xi，yi) = (x0，y0) = (K，0)，(xn，yn)第P次迭代將收斂于(cosθ，sinθ)．CORDIC算法的收斂性滿足收斂定理［15］．對傳統(tǒng)CORDIC算法的計算精度進行全面的分析后，得到CORDIC算法的迭代次數(shù)P和相位精度Δθmin之間的關(guān)系式:

式中，Δθmin=2π/2N，N為輸入相位數(shù)據(jù)bit寬度．

3　單向固定角度旋轉(zhuǎn)CORDIC算法

3.1單向旋轉(zhuǎn)CORDIC算法

根據(jù)傳統(tǒng)的CORDIC算法，迭代P次后的剩余角度值為:

由于arctan(2－n)為n的單調(diào)遞減函數(shù)，本文用比較典型的二階控制系統(tǒng)作為理論模型來討論CORDIC算法的收斂方式．一個典型的二階控制系統(tǒng)的傳遞函數(shù)設(shè)為，其閉環(huán)的階躍信號響應(yīng)為:

圖2給出了傳統(tǒng)的CORDIC算法與單向旋轉(zhuǎn)CORDIC算法的角度收斂曲線圖，初始相位為23.345°．圖3和圖4給出了單向旋轉(zhuǎn)CORDIC算法中不同的旋轉(zhuǎn)角度所需迭代次數(shù)的仿真圖，相位的位數(shù)16位，角度從0.00699°～90°，樣本數(shù)為899721．

由仿真結(jié)果可知，與傳統(tǒng)的基于流水線結(jié)構(gòu)的CORDIC算法相比，平均迭代次數(shù)減少了29.41％．

3.2一次角度估計的單向旋轉(zhuǎn)CORDIC算法

假設(shè)CORDIC算法的輸入相位長度為N，迭代次數(shù)為P，則旋轉(zhuǎn)相位θ可表示為:

式中，Sn=±1．

隨著旋轉(zhuǎn)系數(shù)n的增加，arctan(2－n)逼近2－n，根據(jù)文獻［12］，當(dāng)nm =「(N－log23) /3?，滿足arctan (2－n)≈2－n．通過式(7)可知CORDIC算法的迭代次數(shù)為PN－2，取P = N－2．式(10)可重新表示為:

此時，實際剩余相位為zm +2，按照傳統(tǒng)CORDIC算法的理論，zm +2≈∑θn，由此得zm +2＜2－m－1．在第m + 3次旋轉(zhuǎn)時，引入新的旋轉(zhuǎn)相位m +2=m +2，m +2是zm +2的絕對值珓θm +2＜2－m－1．為了防止旋轉(zhuǎn)角度超過(－π/2，π/2)，此算法做了如下判斷:，其中當(dāng)zm +2＜0時，m +2=－1;當(dāng)zm +20時m +2= + 1．帶入式(3)可得:

本次旋轉(zhuǎn)完之后，剩余相位為0，過程結(jié)束．N位輸入相位經(jīng)過m +2次迭代得到一個N位2進制數(shù)W，即此時的剩余相位zm +2．而也由N位2進制數(shù)表示為:

式中，Ai= 1或0;當(dāng)W［N－1］= 0時，Ai= W［i］，當(dāng)W ［N－1］=1時，Ai為W的每一位值取反最后加一．

由相位實際值和它的N位二進制表示值的比例關(guān)系，可得:

式中，Bi=1或0．

聯(lián)立式(13)和式(17)得:

由上可看出，一次相位估計CORDIC算法將傳統(tǒng)的旋轉(zhuǎn)相位集{ arctan20，arctan2－1，…arctan2－m－1，…，arctan2－P}簡化為{ arctan20，arctan2－1，…，arctan2－m－1，珓m +2}．雖然增加一次移位加法運算，但是與傳統(tǒng)的CORDIC算法相比，減少了N－m－3次旋轉(zhuǎn)．

最后，隨著流水線級數(shù)的減少，常數(shù)系數(shù)K需要重新規(guī)定，即:

此時把初始值設(shè)為: (x0，y0) = (，0)，按照上述過程，最后(xm +3，ym +3)將收斂為(cosθ，sinθ)．由于是固定角度旋轉(zhuǎn)，所以^K值可以根據(jù)所要旋轉(zhuǎn)的角度值預(yù)先計算出迭代次數(shù)和每一級的旋轉(zhuǎn)角度值．圖5和圖6給出了基于旋轉(zhuǎn)相位估計的單向旋轉(zhuǎn)CORDIC算法中，不同的旋轉(zhuǎn)角度與迭代次數(shù)的仿真圖，相位的有效位數(shù)14位，角度從0.00699°～90°，樣本數(shù)為899931．

由仿真結(jié)果可知，迭代次數(shù)同樣近似服從高斯分布，與傳統(tǒng)的基于流水線結(jié)構(gòu)的CORDIC算法相比，平均迭代次數(shù)至少減少了75.82％．

4　固定角度旋轉(zhuǎn)的硬件設(shè)計與實現(xiàn)

本文實現(xiàn)高速高精度固定角度的CORDIC算法的硬件結(jié)構(gòu)圖如圖7所示．表1為固定角度旋轉(zhuǎn)CORDIC算法輸出端的象限映射表．

圖8～圖10分別給出了三種CORDIC算法的硬件結(jié)構(gòu)，表2對三種算法的硬件結(jié)構(gòu)進行了對比．基于相位估計的單向旋轉(zhuǎn)CORDIC算法采用高效流水線結(jié)構(gòu)，需要3次單向相位旋轉(zhuǎn)，1次估計相位旋轉(zhuǎn)．在高速高精度的數(shù)控振蕩器模塊中，設(shè)定每次固定旋轉(zhuǎn)角度為23.345°，可知單向旋轉(zhuǎn)次數(shù)為三次，通過3.2節(jié)的計算可知=2－8+2－9+ 2－10，最后一級流水線單元只需3個加減法器、6個移位寄存器和一個相位系數(shù)存儲器，且無需旋轉(zhuǎn)方向判定．

表1　固定角度旋轉(zhuǎn)CORDIC算法輸出端的象限映射表

表2　硬件結(jié)構(gòu)比較

5　系統(tǒng)仿真與驗證

本文根據(jù)圖8～圖10所示硬件結(jié)構(gòu)，在不同相位寬度的條件下，將本文算法與現(xiàn)有的CORDIC算法進行資源使用量，旋轉(zhuǎn)相位后的相位誤差、坐標位置誤差進行比較．硬件描述語言采用Verilog語言，基于EP2C8Q208C8芯片和QuartusⅡ軟件平臺搭建模塊進行系統(tǒng)級仿真．

設(shè)定每次固定旋轉(zhuǎn)角度為23．345°．將本文所提出的CORDIC算法與其他幾種算法的使用資源進行對比，如圖11、12所示．通過圖11、12可知，各種算法的資源使用量都是隨著相位寬度的增加而增加;在相同的相位寬度下與其他幾種CORDIC算法相比，相位估計的單向旋轉(zhuǎn)CORDIC算法資源消耗量最少．

將文所提出的CORDIC算法與其他幾種算法的固定角度旋轉(zhuǎn)理論值與實際值進行比較，誤差統(tǒng)計結(jié)果如表3所示．通過比較可知，在相同的數(shù)據(jù)寬度下，相位估計的單向旋轉(zhuǎn)CORDIC算法輸出的坐標位置誤差最大．但是隨著數(shù)據(jù)寬度的增加它的誤差范圍將被縮小，當(dāng)數(shù)據(jù)寬度增加到18以上時，坐標位置誤差將被控制在(－6×10－4，6×10－4)內(nèi)，說明本文的所提出的算法在減少迭代次數(shù)的基礎(chǔ)上，保證了輸出正余弦數(shù)據(jù)的精度．

6　結(jié)束語

針對固定角度旋轉(zhuǎn)CORDIC算法在相位旋轉(zhuǎn)過程中，存在數(shù)據(jù)吞吐率較高、占用硬件資源多且資源消耗量大等缺點，提出了利用混合CORDIC算法．將本文算法與現(xiàn)有的CORDIC算法進行資源使用量、旋轉(zhuǎn)相位后的相位誤差、坐標位置誤差進行比較，實驗數(shù)據(jù)表明，當(dāng)數(shù)據(jù)寬度增加到18位以上時，該算法將誤差控制在(－6× 10－4，6×10－4)，迭代次數(shù)、邏輯資源使用量以及寄存器資源使用量較現(xiàn)有的算法有了較為明顯的減少．

表3　坐標位置誤差值比較

參考文獻

［1］Pramod Kumar Meher，SangYoon Park．CORDIC designs for fixed angle of rotation［J］．IEEE transactions on very large scale integration(VLSI) systems，2013，21(2) : 217 －227．

［2］Shen-Fu Hsiao，Yu-Hen Hu，Tso-Bing Juang．A memoryefficient and high-speed sine/cosine generator based on parallel CORDIC rotations［J］．IEEE signal processing letters，2004，11(2) : 152－155．

［3］C-S Wu，A-Y Wu，C-H Lin．A high-performance/low-latency vector rotational CORDIC architecture based on extended elementary angle set and trellis-based searching schemes［J］．IEEE Trans Circuits Syst II，Analog Digit．Signal Process，2003，50(9) : 589－601．

［4］T-B Juang，S-F Hsiao，M-Y Tsai．Para-CORDIC: Parallel cordic rotation algorithm［J］．IEEE Trans Circuits Syst I，Reg Papers，2004，51(8) : 1515－1524．

［5］Zhang G，Chen，F(xiàn) Parallel FFT with CORDIC for ultra wide band［A］．In Proc of 15th IEEE International Symposium on Personal，Indoor and Mobile Radio Communications［C］．Barcelona: IEEE，2004．1173－1177．

［6］P K Meher，J K Satapathy，G Panda．Efficient systolic solution for a new prime factor discrete Hartley transform algorithm［J］．IEE Proc Circuits，Devices Syst，1993，140(2) : 135－139．

［7］張曉彤，辛茹，王沁，李涵．基于改進混合式CORDIC算法的直接數(shù)字頻率合成器設(shè)計［J］．電子學(xué)報，2008，36 (6) : 1144－1148．Zhang Xiao-tong，et al．Design of direct digital frequency synthesizer based on improved hybrid CORDIC algorithm ［J］．Acta Electronica Sinica，2008，36(6) : 1144－1148．(in Chinese)

［8］T Lang，E Antelo．High-throughput CORDIC-based geometry operations for 3D computer graphics［J］．IEEE Trans．Computer，2005，54(3) : 347－361．

［9］S Wang，E E Swartzlander，Jr．Critically damped CORDIC algorithm［A］．The 37th Midwest Symp Circuits and Systems［C］．Lafayette，LA: IEEE，1994．236－239．

［10］Kaushik B，Rakesh B．Architectural design and FPGA implementation of radix-4 CORDIC processor［J］．Microprocessors and Microsystems，2010，34(2－4) : 96－101．

［11］E Antelo，J Villalba，J D Bruguera，E L Zapata．High performance rotation architectures based on the radix-4 CORDIC algorithm［J］．IEEE Trans Computers，1997，46 (8) : 855－870．

［12］Wang S，Piuri V，et al．Hybrid CORDIC algorithms［J］．IEEE Transaction on Computers，1997，46 (11) : 1202 －1207．

［13］Chaozhu Zhang，Jinan Han，Ke Li．Design and implementation of hybrid CORDIC algorithm based on phase rotation estimation for NCO［J/OL］．The Scientific World Journal，http: / /www．hindawi．com /journals/tswj/2014/ 897381，2014-7-7．

［14］J Volder．The CORDIC trigonometric computing technique［J］．IRE Trans on Electronic Computers，1959，8: 330－334．

［15］J Walther．A unified algorithm for elementary functions ［A］．Joint Computer Conference［C］．Atlantic: Spring，1971．379－385．

張朝柱男，1970年生于遼寧省大連市，博士生導(dǎo)師，研究方向為信號處理在雷達、通信中的應(yīng)用研究;雷達對抗技術(shù)研究．

E-mail: zhangchaozhu@ hrbeu．edu．cn

韓吉南(通信作者)男，1988年生于黑龍江省牡丹江市，男，博士研究生，研究方向為導(dǎo)航衛(wèi)星信號處理算法．

E-mail: hanjinanbuaa@163．com

Design and Implementation of CORDIC Algorithm for High Speed and Precision Fixed Angle of Rotation

ZHANG Chao-zhu，HAN Ji-nan，YAN Hui-zhi
(School of Information and Communication Engineering，Harbin Engineering University，Harbin，Heilongjiang 150001，China)

Abstract:Coordinate Rotation Digital Computer (CORDIC) algorithm for fixed angle of rotation has been widely applied in many fields，including digital signal processing，image processing and robotics．CORDIC algorithm，based on fixed angle of rotation，has an advantage of high data throughput，but it takes up much more hardware resources．To remedy these problems，a hybrid CORDIC algorithm is proposed in this paper，which separates the angle rotation into two steps，unidirectional angle rotations and angle estimation ones．According to the under-damping theory，the unidirectional phase rotations are employed to realize the fixed angle of rotation，which reduces the stage of pipeline and judgment of sign bit．Through the binary representation，the constant factor will be fixed．According to the phase mapping relationship，the high speed and precision fixed angle of rotation is completed．Finally the hybrid algorithm is implemented on a hardware platform and the experimental results show that it can further reduce the number of iterations and resource consumption and obtain high though-put rate．

Key words:CORDIC (Coordinate Rotation Digital Computer) ; fixed angle rotation; pipeline architecture; FPGA (Field-Programmable Gate Array)

作者簡介

基金項目:國家自然科學(xué)基金(No．61172159)

收稿日期:2014-08-29;修回日期: 2015-05-11;責(zé)任編輯:馬蘭英

DOI:電子學(xué)報URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．033

中圖分類號:TN713.7; TN431.2

文獻標識碼:A

文章編號:0372-2112 (2016) 02-0485-06