劉 恒，鐘 俊，劉 輝

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

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

1 CORDIC算法的基本原理

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

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

A點(diǎn)坐標(biāo)可寫成三角函數(shù)形式：

(1)

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

B點(diǎn)坐標(biāo)可寫成三角函數(shù)形式:

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

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

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

(7)

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

(8)

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

θi=tan-1(di2-i)

(9)

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

(10)

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

zi+1=zi-ditan-12-i

(11)

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

(12)

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

(13)

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

(14)

(15)

(16)

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

2 算法優(yōu)化

2.1 算法的局限性

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

2.2 優(yōu)化過程

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

(17)

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

3 硬件實(shí)現(xiàn)

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

圖3 CORDIC基本運(yùn)算單元

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

4 仿真結(jié)果

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

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

圖5 正余弦波形圖

用CORDIC算法計(jì)算向量(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ì)算精度。經(jīng)過有限次迭代，輸出向量模值473，如圖6所示。采用優(yōu)化后的CORDIC算法計(jì)算模值，如圖7所示。

圖6 CORDIC算法計(jì)算模值

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

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

表1 優(yōu)化前后計(jì)算速度比較向量時(shí)鐘周期數(shù)優(yōu)化前優(yōu)化后(535,897)95(932,384)53(626,433)95(832,795)95(028,841)95表2 優(yōu)化前后精度比較向量向量模值計(jì)算結(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算法不僅計(jì)算速度快，而且計(jì)算精度高。

5 結(jié)束語(yǔ)

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