基于CORDIC算法的模值計算及優(yōu)化設(shè)計基于CORDIC算法的模值計算及優(yōu)化設(shè)計

劉 恒，鐘 俊，劉 輝

(安徽職業(yè)技術(shù)學(xué)院 安徽合肥 230011)

在數(shù)字信號處理等領(lǐng)域常常需要求解三角函數(shù)值以及模值。CORDIC算法是實現(xiàn)上述求解過程的最常用的方法。從本質(zhì)上說，CORDIC算法使用了一種數(shù)學(xué)計算的逐次逼近法[1]。算法的基本運算單元只包含移位器和加法器[2]。因此它的操作簡單，執(zhí)行效率高。FPGA器件集成度高，速度快，是實現(xiàn)CORDIC算法的首選方式[3]。本文深入研究了CORDIC算法的基本原理，提出了運算單元的優(yōu)化方法及硬件實現(xiàn)結(jié)構(gòu)，并進行了Modelsim仿真。

1 CORDIC算法的基本原理

向量OA在單位圓上，輻角為α，如圖1所示。

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

A點坐標可寫成三角函數(shù)形式：

(1)

將向量OA按照逆時針方向旋轉(zhuǎn)角度θ至向量OB，OB輻角為α+θ，

B點坐標可寫成三角函數(shù)形式:

(2)

θ是本次旋轉(zhuǎn)的目標旋轉(zhuǎn)角度。將式 (2) 按照三角函數(shù)公式展開：

(3)

將式 (1 ) 代入式 (3) 可得：

(4)

兩個表達式提取公因子 cosθ, 式 (4) 可變形

(5)

式 (5) 表明，cosθ對目標向量OB輻角沒有影響，只是縮短了模長。 如果去除cosθ, 這種旋轉(zhuǎn)稱為偽旋轉(zhuǎn)，如圖 2所示。由偽旋轉(zhuǎn)得到的OC是在OA基礎(chǔ)上先旋轉(zhuǎn)θ角再伸長1/cosθ。向量OA⊥AC。C點坐標可寫為：

(6)

圖2 變換后的矢量旋轉(zhuǎn)圖

比較上面兩個表達式，旋轉(zhuǎn)的角度不變，模值在原來基礎(chǔ)上增大了1/cosθ。為了得到真實旋轉(zhuǎn)的結(jié)果，可將偽旋轉(zhuǎn)的輸出乘相應(yīng)的因子進行修正。

對于任意角度θ的偽旋轉(zhuǎn)，可將θ拆分為一系列的特定角度的和，即：

(7)

由此可將一次旋轉(zhuǎn)變成多次旋轉(zhuǎn)。由式(6)可知，經(jīng)過第i+1次旋轉(zhuǎn)可得:

(8)

考慮到FPGA硬件實現(xiàn)過程，可以取特殊角度：

θi=tan-1(di2-i)

(9)

其中di∈{-1,1}，根據(jù)式(9)，式(8)可變形為：

(10)

根據(jù)式(10)可知，每次偽旋轉(zhuǎn)的具體操作過程只包括加法、減法和移位運算。di的值由剩余旋轉(zhuǎn)角度決定，假設(shè)剩余旋轉(zhuǎn)角度為z，表達式為：

zi+1=zi-ditan-12-i

(11)

z初始化為θ，即z0=θ。每次迭代，對zi加或者減特定角度tan-12-i，最終使z的值為0 ，加減由di決定，即：

(12)

逆時針方向旋轉(zhuǎn)，di記為+1，順時針方向旋轉(zhuǎn)，di記為-1。在迭代過程中分解為θi。剩余的角度zi隨著迭代進行將收斂于零。CORDIC算法迭代的完整過程如下：

(13)

CORDIC算法可用于計算向量的模值。假設(shè)向量初始值為(x0,y0),在多次迭代之后，如果yn趨于零，則：

(14)

(15)

(16)

如果迭代總次數(shù)n確定，則k(n)可預(yù)先計算得到，視為已知。計算表達式(15)可以得到向量模值[4]。

2 算法優(yōu)化

2.1 算法的局限性

CORDIC算法是將運算單元的運算結(jié)果反饋回輸入端。運算單元包含控制單元、MUX、移位寄存器、只讀存儲器以及加法器[5]。隨著時鐘脈沖信號的推進，把當前輸出傳回到輸入端，經(jīng)過多次計算，得到最終結(jié)果。無論串行還是并行實現(xiàn)方式，都離不開上述CORDIC運算單元。

2.2 優(yōu)化過程

之前廣泛采用的優(yōu)化策略主要體現(xiàn)在模校正和角度收斂范圍等方面，這些優(yōu)化并沒有改變CORDIC運算單元。本文采用新的優(yōu)化思路，將CORDIC算法兩級運算表達式展開。原先的兩級迭代合并為一級，其中di與di-1由上一次迭代產(chǎn)生。通過直接建立xi+1,yi+1與xi-1,yi-1之間的聯(lián)系，可以減少單元結(jié)構(gòu)，從根本上優(yōu)化傳統(tǒng)的CORDIC運算單元。

(17)

從表達式來看，原來的兩級迭代，需要兩級移位運算和兩級加法運算，優(yōu)化以后，需要一級移位運算和兩級加法運算，這樣可以一定程度上減少迭代的總時間，提高運算效率。優(yōu)化后的算法一共迭代n/2次，F(xiàn)PGA關(guān)鍵路徑由原先的3.1 ns 提升至2.3 ns，優(yōu)化后的CORDIC 算法數(shù)據(jù)吞吐量增加了20%。

3 硬件實現(xiàn)

速度與功耗是影響FPGA性能的兩個重要方面，在CORDIC算法的實現(xiàn)過程中，必須同時考慮上述兩個方面。有兩種方式可以實現(xiàn)CORDIC算法。方式一：流水線結(jié)構(gòu)。采用這種結(jié)構(gòu)每個時鐘周期可以產(chǎn)生一個輸出結(jié)果。具體的實現(xiàn)過程是用n個單元完成算法的n次迭代。采用流水線結(jié)構(gòu)多個單元可以同時進行移位和加法運算，很大程度上增加了數(shù)據(jù)處理效率，運算速度較其他方式快很多。 流水線結(jié)構(gòu)占據(jù)的芯片面積大，硬件功耗會隨著流水線級數(shù)增加而線性增加。方式二：迭代結(jié)構(gòu)[6]。一個CORDIC運算單元(如圖3)重復(fù)使用n次，實現(xiàn)算法的n次迭代。這種實現(xiàn)方式占據(jù)的芯片面積小，但相比流水線結(jié)構(gòu)，系統(tǒng)的數(shù)據(jù)處理效率低很多。本文采用迭代結(jié)構(gòu)，在滿足低功耗的要求同時，提升運算速度。傳統(tǒng)的兩級運算結(jié)構(gòu)在優(yōu)化之后，變?yōu)橐患壗Y(jié)構(gòu)，如圖4所示，以此作為迭代結(jié)構(gòu)的基本運算單元。

圖3 CORDIC基本運算單元

圖4 優(yōu)化之后的兩級運算單元

4 仿真結(jié)果

采用ModelSim-Altera 10.0軟件進行仿真，時鐘頻率50 M。用Verilog語言建模并仿真測試。在實現(xiàn)算法的過程中采用流水線運算結(jié)構(gòu)，可以在很大程度上提高算法的執(zhí)行效率，其中單次迭代采用優(yōu)化后的運算單元。

CORDIC算法計算獲得的正余弦函數(shù)波形圖如圖5所示。

圖5 正余弦波形圖

用CORDIC算法計算向量(123,456)的模值，理論模值為472.3。迭代部分代碼如下。

if((y_out0*Precision<=y_out)||(y_out0*Precision<=-y_out))

begin

if(～ y_out[31])

begin

x_out_next<= x_out + (y_out >>> i);

y_out_next<= y_out - (x_out >>> i);

end

else

begin

x_out_next<= x_out - (y_out >>> i);

y_out_next<= y_out + (x_out >>> i);

end

end

else

begin

x_out<=x_out;

y_out<= y_out;

i <= i;

end

其中Precision為預(yù)設(shè)的計算精度。經(jīng)過有限次迭代，輸出向量模值473，如圖6所示。采用優(yōu)化后的CORDIC算法計算模值，如圖7所示。

圖6 CORDIC算法計算模值

圖7 優(yōu)化后的 CORDIC算法計算模值

在精度0.001條件下，采用兩種不同方法對多組數(shù)據(jù)進行計算,比較需要時鐘周期個數(shù)，如表1。在同樣迭代次數(shù)(5次)情況下，對計算結(jié)果進行比較，如表2。

表1 優(yōu)化前后計算速度比較向量時鐘周期數(shù)優(yōu)化前優(yōu)化后(535,897)95(932,384)53(626,433)95(832,795)95(028,841)95表2 優(yōu)化前后精度比較向量向量模值計算結(jié)果優(yōu)化前優(yōu)化后 (535,897)1044.410341044(932,384)1008.010071009(626,433)761.2 753 762(832,795)1150.811441151(028,841)841.5 832 842(971,693)1192.911801193

可見，采用優(yōu)化后的CORDIC算法不僅計算速度快，而且計算精度高。

5 結(jié)束語

本文對CORDIC算法進行優(yōu)化改進，硬件采用并行結(jié)構(gòu)實現(xiàn)算法，可以很大程度上提高算法的數(shù)據(jù)處理速度。在不影響計算精度前提下，優(yōu)化后的算法可以明顯減少運算時間，具有很好的使用價值。實驗結(jié)果表明算法優(yōu)化后相比較于優(yōu)化之前，運算時間減少了40%左右，優(yōu)化后的算法具有很好的實際意義。