基于CORDIC算法的直角坐標與球面坐標變換電路的FPGA實現(xiàn)

陳彥來

（船舶重工集團公司723所,揚州 225001）

0 引 言

在雷達數(shù)據(jù)處理信號模擬器中,目標的初始位置、速度、加速度等信息通常是以球面坐標形式給出的,而目標位置的外推需要在直角坐標系中進行,因此需要將目標初始位置、速度、加速度等信息從球面坐標系變換到直角坐標系,也就是將初始位置、速度、加速度矢量在直角坐標系中進行分解,得到其在X軸、Y軸、Z軸上的坐標,然后按照經(jīng)典運動學(xué)公式進行外推；在得到目標下一時刻X、Y、Z坐標后,通常還要將其轉(zhuǎn)換成相應(yīng)的距離、方位角、俯仰角信息,也就是進行直角坐標系到球面坐標系的變換?，F(xiàn)場可編程門陣列（FPGA）以其高速性和靈活性在現(xiàn)今的雷達數(shù)據(jù)處理領(lǐng)域已經(jīng)得到了廣泛的應(yīng)用,但如果處理算法中需要計算超越函數(shù),例如 sinθ,cosθ,arcsinx,arccosx,xn等,通常采用查表法和泰勒級數(shù)展開法。使用有限的FPGA面積設(shè)計高精度的數(shù)據(jù)表格,特別是在需要多張數(shù)據(jù)表格的情況下,其設(shè)計有一定難度。泰勒級數(shù)展開法可以將復(fù)雜的函數(shù)分解為一系列的乘方和加減法運算,解決計算精度的問題,但乘方運算需要消耗過多的FPGA硬件資源；另外還有些超越函數(shù)的泰勒級數(shù)展開式本身就不存在（例如反三角函數(shù)等）,因此泰勒級數(shù)展開法在坐標轉(zhuǎn)換電路中也存在一定的局限性。有礙于FPGA器件面積消耗和計算精度、速度之間的矛盾,直角坐標與球面坐標變換電路不得不考慮其他實現(xiàn)方法。CORDIC算法能夠方便地計算正余弦、反正余弦、乘方、開方等運算,并且在實現(xiàn)過程中僅用到加法器和移位器,與FPGA的特點完全吻合,能夠完成直角坐標與球面坐標變換電路設(shè)計。

1 利用CORDIC算法進行坐標變換的算法原理

1.1 CORDIC算法的基本原理

CORDIC算法最初由Volder于1959年提出,其基本數(shù)學(xué)思想是通過一系列固定的、與運算基數(shù)相關(guān)的角度的不斷旋轉(zhuǎn)、累加而逼近所要旋轉(zhuǎn)的角度。如圖1所示,向量OA繞原點O逆時針旋轉(zhuǎn)θ角度后到達向量OB位置,假設(shè)A點坐標為（xi,yi）,B點坐標為（xj,yj）,則:

圖1 矢量旋轉(zhuǎn)模型

假設(shè)向量OA逆時針旋轉(zhuǎn)θ角度是由N次微旋轉(zhuǎn)所構(gòu)成的,由式（1）可知:向量OA的第n+1次微旋轉(zhuǎn)可表示為:

式中:n=0,1,…,N-1。

由式（1）、（2）,可得:

針對FPGA的結(jié)構(gòu)特點,選取θn=arctan（1/2n）,即 tanθn=1/2n。對式（3）前面的系數(shù)K取極限得:

如果忽略常系數(shù)K,式（2）可表示為:

式中:Si={1,-1},Si=1表示第n+1微旋轉(zhuǎn)方向為逆時針,Si=-1表示微旋轉(zhuǎn)方向為順時針。

根據(jù)每次微旋轉(zhuǎn)方向的判定準則,CORDIC算法有旋轉(zhuǎn)模式和矢量模式2種。旋轉(zhuǎn)模式是以角度誤差的符號作為每次微旋轉(zhuǎn)方向的判斷依據(jù),最終使角度誤差等于零或趨近于零,可用于求正余弦值,適用于球面坐標系到直角坐標系變換；矢量模式是以每次微旋轉(zhuǎn)后旋轉(zhuǎn)矢量Y軸坐標的符號作為下次微旋轉(zhuǎn)方向的判斷依據(jù),最終使旋轉(zhuǎn)矢量與X軸重合或趨近重合,可用于求極徑和極角,適用于直角坐標系到球面坐標系變換。

1.2 CORDIC算法旋轉(zhuǎn)模式計算正余弦值

假定起始向量為OA,其中A點坐標為（1,0）,經(jīng)過N次微旋轉(zhuǎn)后到達終止向量OB的位置,B點坐標為（x,y）。從起始向量到終止向量旋轉(zhuǎn)的角度為θ,則B點坐標為（cosθ,sinθ）,也就說通過矢量旋轉(zhuǎn)得到了θ角度的正余弦值。為了通過若干次的微旋轉(zhuǎn)等于或逼近旋轉(zhuǎn)角度θ,則需要按照式（6）的規(guī)則進行每次微旋轉(zhuǎn)旋轉(zhuǎn)方向的判斷。式（6）中θerr_n=θ-θn。

由矢量旋轉(zhuǎn)的幾何關(guān)系可知:N次微旋轉(zhuǎn)后的B點橫坐標即為 cosθ,縱坐標即為 sinθ,也即利用CORDIC算法巧妙地解決了球面坐標系到直角坐標系變換過程中正余弦值的計算問題。

1.3 CORDIC算法矢量模式計算極徑和極角

假設(shè)起始向量為OA,點A坐標為（xi,yi）,旋轉(zhuǎn)終止向量為OB,點B坐標為（xj,0）。從OA到OB的旋轉(zhuǎn)過程可以通過N次微旋轉(zhuǎn)完成,其每次微旋轉(zhuǎn)方向由式（8）、（9）決定。

若yn＞0,則:

由矢量旋轉(zhuǎn)的幾何關(guān)系可知:B點橫坐標xj為向量OA的極徑,旋轉(zhuǎn)的角度θ為向量OA的極角。由于arctan（2-n）為一系列常數(shù)值,可以離線計算,因此平面直角坐標系到球面坐標系變換過程中復(fù)雜的平方、開方、反三角函數(shù)計算可以通過CORDIC算法簡化為簡單的移位和加減運算。

1.4 CORDIC算法實現(xiàn)直角坐標與球面坐標變換

如圖2所示,假設(shè)任一點A的直角坐標為（x,y,z）,球面坐標為（R,α,β）,根據(jù)幾何關(guān)系可知:x=Rcosβcosα,y=Rcosβsinα,z=Rsinβ；依據(jù)式（6）原則,按照CORDIC算法的旋轉(zhuǎn)模式進行迭代運算 ,可以計算出 cosβ,sinα,sinβ,再進行乘法運算即可完成球面坐標到直角坐標的變換；而直角坐標到球面坐標變換分為2步進行:首先利用CORDIC算法,在XOY平面內(nèi),依據(jù)式（7）、（8）計算出OB和α；然后再次利用CORDIC算法,在ZOB平面內(nèi),依據(jù)式（7）、（8）計算出OA和β,至此完成直角坐標到球面坐標的變換。

2 基于CORDIC算法的直角坐標與球面坐標變換電路的FPGA實現(xiàn)

直角坐標與球面坐標變換分為直角坐標到球面坐標變換和球面坐標到直角坐標變換2種,下面以直角坐標到球面坐標變換為例來說明直角坐標與球面坐標變換電路的FPGA實現(xiàn)。

圖2 直角坐標和球面坐標變換

2.1 CORDIC算法的級聯(lián)實現(xiàn)

由式（8）、（9）可知,CORDIC算法的絕大部分計算為迭代運算,在FPGA中有2種實現(xiàn)方案。其一為設(shè)計一個有限狀態(tài)機,然后利用其狀態(tài)變化控制每次的迭代運算,直至完成一次坐標變換；其二為流水方式,構(gòu)造若干個不同的迭代結(jié)構(gòu),對其進行流水線操作,直至計算出結(jié)果。前者需要的FPGA資源少,但進行一次變換所需時間長,并且不能進行流水線處理,不利于系統(tǒng)的實時算法實現(xiàn)；后者對FPGA的資源要求高,但平均計算時間短,在流水的情況下,可以達到系統(tǒng)頻率,有利于系統(tǒng)的實時處理。在本文中采用流水線的處理方式,其單次迭代結(jié)構(gòu)如圖3所示。

圖3 CORDIC算法流水線處理單次迭代結(jié)構(gòu)

2.2 CORDIC算法的預(yù)處理模塊

在CORDIC算法迭代處理過程中,假設(shè)每次微旋轉(zhuǎn)均為逆時針方向,且微旋轉(zhuǎn)次數(shù)為無窮大,最大可旋轉(zhuǎn)角度為 θmax,則 θmax≈1.743 3。為了使微旋轉(zhuǎn)后的矢量落在X正半軸（或趨于X正半軸）,則被旋轉(zhuǎn)的矢量極角θ應(yīng)滿足-θmax≤θ≤θmax；同時通過大量仿真實驗發(fā)現(xiàn),當被旋轉(zhuǎn)矢量靠近Y軸時,極角θ的計算誤差較大。

在本文中,為了使旋轉(zhuǎn)矢量極角達到2π,同時減少角度計算誤差,加入了CORDIC算法的預(yù)處理模塊,處理原則為:

（1）如果被旋轉(zhuǎn)矢量在第二象限,則通過Y軸對稱將其變換到第一象限；如果被旋轉(zhuǎn)矢量在第三象限,則通過原點對稱將其變換到第一象限；如果被旋轉(zhuǎn)矢量在第四象限,則通過X軸對稱將其變換到第一象限。

（2）如果被旋轉(zhuǎn)矢量變換后θ＞0.25π,則把變換后旋轉(zhuǎn)矢量關(guān)于Y=X的對稱矢量作為最終的旋轉(zhuǎn)矢量。由于在對被旋轉(zhuǎn)矢量進行微旋轉(zhuǎn)前進行了對稱變換,必然會影響到極角的計算結(jié)果,在CORDIC流水計算完成后需要對極角的計算結(jié)果進行修正；而對于極徑而言,不會隨對稱變換而發(fā)生變化,因而CORDIC算法計算出的值即為其真實值。考慮原則（1）、（2）以及極角計算結(jié)果的修正,CORDIC算法預(yù)處理模塊計算規(guī)則和后處理極角修正規(guī)則如表1所示。

2.3 CORDIC算法的后處理模塊

利用CORDIC算法實現(xiàn)直角坐標到球面坐標變換的后處理模塊主要是實現(xiàn)極角修正和極徑縮放（乘以式（3）中的常數(shù)K）。其中極角的修正規(guī)律見表1的最后一列；極徑縮放通過乘以一個固定的因子來實現(xiàn),可以利用FPGA的DSP IP核來實現(xiàn),在此不再論述。

2.4 直角坐標到球面坐標變換電路的FPGA實現(xiàn)

根據(jù)前面所述,直角坐標到球面坐標變換分為兩部分:其一為在XOY平面利用CORDIC算法計算OB和 α；其二為在ZOB平面內(nèi),再次利用CORDIC算法計算OA和β,其FPGA電路模塊劃分如圖4所示。

圖4 直角坐標到球面坐標變換電路的FPGA實現(xiàn)模塊劃分

其中x0、y0為原始矢量的直角坐標,x1、y1為進行坐標對稱變換后的直角坐標,θ17為CORDIC算法計算出的極角,θ為其修正值。

在圖4中,clk為時鐘信號,xyz_inen為輸入使能信號,qiumianzuobiao_outen為輸出使能信號,xin、yin、zin 為直角坐標輸入 ,jijing、fangweijiao、yangjiao為球面坐標輸出。inst1完成直角坐標輸入信號的鎖存,inst2完成在XOY平面的變換,inst6完成ZOB平面的變換；inst4形成輸出使能信號,inst3,inst5完成數(shù)據(jù)同步。

3 試驗結(jié)果

本文利用Altera公司的QuartusⅡ7.2軟件,采用VHDL硬件描述語言對直角坐標到球面坐標變換電路模塊進行了功能描述和時序仿真,待仿真結(jié)果正確后綜合出電路網(wǎng)表,最后下載到Altera公司生產(chǎn)的StratixⅡ器件EP2S90F1020I4中進行了試驗驗證。圖5為時序仿真波形,其中系統(tǒng)時鐘clk為40 MHz；xin為xin_0=-500,每個時鐘周期增加100的等差數(shù)列；yin為yin_0=200,每個時鐘周期遞減50的等差數(shù)列；zin為zin_0=50,每個時鐘周期增加10的等差數(shù)列。

圖5 直角坐標到球面坐標變換電路時序仿真波形

圖6為通過QuartusⅡ自帶的在線邏輯分析儀SignalTapⅡ采集到的波形。

圖6 直角坐標到球面坐標變換電路實際信號波形

4 結(jié)束語

本文研究了CORDIC算法的基本原理,提出了利用CORDIC算法實現(xiàn)直角坐標與球面坐標變換電路的方案,并且進行了仿真試驗驗證。

試驗結(jié)果表明,利用CORDIC算法實現(xiàn)直角坐標與球面坐標變換電路具有較高的運算速度和運算精度,并且在FPGA實現(xiàn)過程中利用資源少,具有較高的使用價值。由此可見,本文所提出的利用CORDIC算法實現(xiàn)直角坐標與球面坐標變換電路的方案是切實可行的,其具有一定的理論和工程應(yīng)用價值。

[1] 季中恒,宋博.CORDIC算法及其硬件實現(xiàn)[J].彈劍與制導(dǎo)學(xué)報,2005,25（3）:609-610.

[2] 王智霞,王廣生.CORDIC算法在FPGA中的實現(xiàn)[J].微處理機,2007,2（1）:4-7.

[3] VOLDER J E.The CORDIC trigonometric comphting technique[J].IRE Transactions on Electronic Computers,1959,8（9）:330-334.

[4] 楊宏,李國輝,劉立新.基于FPGA的CORDIC算法的實現(xiàn)[J].西安郵電學(xué)院學(xué)報,2008,13（1）,75-77.

[5] 王誠,吳繼華,范麗珍,等.Altera FPGA/CPLD設(shè)計[M].北京:人民郵電出版社,2005.