王亞春, 蔡德林, 張夢龍, 王俊

(①安徽大學電子科學與技術學院,安徽 合肥 230039;②中國電子科技集團第 38研究所,安徽 合肥 200031)

0 引言

坐標旋轉(zhuǎn)計算機(CORDIC,Coordinate Rotational Digital Computer)算法是 Volder于 1959年在美國航空控制系統(tǒng)的設計中提出來的,它是一種用于計算運算函數(shù)的循環(huán)迭代算法。其基本思想是用一系列與運算基數(shù)相關的角度的不斷偏擺,從而逼近所需旋轉(zhuǎn)的角度,從廣義上講它是一個數(shù)值計算逼近的方法。這些固定的角度與計算基數(shù)有關,運算只有移位和加減,可通過該算法不同的實現(xiàn)模式(如圓周模式、雙曲線模式、線性模式等)來計算的函數(shù)包括乘、除、平方根、正余弦、反正切以及指數(shù)運算等。1971年,J.S Walther提出了統(tǒng)一的CORDIC算法形式,把圓周旋轉(zhuǎn)、雙曲旋轉(zhuǎn)和直線旋轉(zhuǎn)統(tǒng)一到同一個CORDIC迭代方程中,為同一硬件實現(xiàn)多功能運算奠定了基礎。在傳統(tǒng)的硬件算法設計中,乘、除等基本數(shù)學函數(shù)運算是一種既耗時又占用面積大的運算,CORDIC算法正是為解決這種問題而產(chǎn)生的,它從算法本身入手,將復雜的算法分解成一些在硬件中容易實現(xiàn)的基本運算,如加法、移位等,從而使得這些算法在硬件上可以得到較好的實現(xiàn)。

1 CORDIC算法的基本原理

以基于圓周模式的 CORDIC算法實現(xiàn)為例,介紹CORDIC算法的基本原理[1]。假設平面直角坐標系里有一向量：a(xi,yi)=a(r cosα,r sinα),現(xiàn)將其旋轉(zhuǎn) θ角得到新向量：b(xj,yj)=b(r cos(α+θ),r sin(α+θ)),如圖 1所示,則有：

圖 1 CORDIC算法旋轉(zhuǎn)示意

寫成矩陣形式就是：

如果向量 a(xi,yi)經(jīng)過 n次旋轉(zhuǎn)才到達 b(xi,yi),其中第 k次旋轉(zhuǎn)的角度為 θk,那么第 k次旋轉(zhuǎn)的表達式為：

如果限制 tanθk=±2-k,則可以將 tanθk乘項的乘法操作變?yōu)橐莆徊僮?式(3)將只有一個乘積項 cosθk：

θk=Skarctan 2-k,Sk={-1,+1}。

除了 cosθk系數(shù)外,CORDIC算法只需要簡單的移位和相加操作即可完成。事實上 cosθk還可以事先算出來?？紤]到：

經(jīng)過無數(shù)次迭代后,cosθk系數(shù)項將變成一個常數(shù)。由于 cosθk系數(shù)項是一個常數(shù),因此可以在迭代的過程中忽略cosθk系數(shù)項,迭代的最后再將其乘入。這樣迭代式就變?yōu)椋?/p>

式(5)就是 CORDIC算法的迭代式。假設 z代表的是尚未旋轉(zhuǎn)的角度：

zk+1=(總角度 -已旋轉(zhuǎn)角度)=zk-Skarctan 2-k(未旋轉(zhuǎn)角度-剛旋轉(zhuǎn)角度),將此式和式(5)結(jié)合就得到了下面三個迭代方程式：其中 Sk的符號由第 k次旋轉(zhuǎn)時候的角度 zk決定,它們的關系是：Sk=-1,zk＜0

+1,zk≥0,向量 a(xi,yi)向向量 b(xj,yi)逼近的精度由迭代的次數(shù)決定,迭代的次數(shù)越多,逼近的精度就越高,迭代 n次(n→∞ )得到的最終結(jié)果為：

其中zn=0表明旋轉(zhuǎn)到了指定的角度。

2 CORDIC流水線結(jié)構(gòu)的 FPGA實現(xiàn)

CORDIC流水線結(jié)構(gòu)的 FPGA實現(xiàn)參考文獻[2-4]。在實際應用中,CORDIC的實現(xiàn)方式應該根據(jù)目標需求,在速度和資源之間進行折中。采用流水線結(jié)構(gòu),這種方式能夠在執(zhí)行進程的同時輸入數(shù)據(jù),從而極大提高了程序的運行效率,在該結(jié)構(gòu)中,每一個移位器都是固定的深度,而且旋轉(zhuǎn)角度集的各個值作為常數(shù)直接連接到累加器上,不需要存儲空間和讀取時間,圖 2是CORDIC算法的一般流水線結(jié)構(gòu)。

圖 2 CORDIC算法的一般流水線結(jié)構(gòu)

3 仿真結(jié)果與分析

仿真結(jié)果與分析參考文獻[5]。該設計中選用的FPGA芯片是 Altera公司 CycloneⅢ系列中EP3C25F256C6器件,使用 VHDL語言完成電路描述之后,在QuartusⅡ軟件平臺上進行編譯、仿真的結(jié)果如圖 3所示(表 1列出其計算結(jié)果)。

圖 3 用FPGA實現(xiàn)CORDIC算法的時序仿真

其中輸入信號有兩個,分別為時鐘 clk和要計算的角度Angle。輸出則有 3個,分別是 x_out(余弦值)、y_out(正弦值)和 z_out(迭代結(jié)束時的角度誤差)。由式(7)可知,為了使最后結(jié)果中 x_out和 y_out分別為余弦值和正弦值,就應該設置 xi和 yi的初始值分別為 1/An和 0。但程序里的初始值并不是這樣設置的,這是因為把第一次迭代精簡在了初始值中設置,同時還進行了預處理,即擴大了輸入角度的范圍。圖 3仿真結(jié)果中,輸入角度Angle用十六進制數(shù)表示,計算出的正弦值y_out和余弦值 x_out則用帶符號整數(shù)表示。 無論是輸入角度 Angle還是輸出的正、余弦值均擴大了 215倍,實際的角度和計算結(jié)果應該除以 215。表 1列出了圖 3的仿真結(jié)果中的 4個角度和CORDIC計算結(jié)果,同時還列出了理論的正弦值和余弦值?？梢钥闯?經(jīng)過 16次迭代后,CORDIC計算結(jié)果已經(jīng)非常精確。

表 1 CORDIC計算結(jié)果與理論值的比較

4 結(jié)語

探討了 CORDIC算法的一種硬件實現(xiàn),它具有速度快、精度高、結(jié)構(gòu)簡單易實現(xiàn)等優(yōu)點,從實驗結(jié)果來看,其誤差很小,能夠滿足速度和精度的要求,因而具有十分重要的工程研究和應用意義。

[1]VOLDER JE.The CORDIC Trigonometric Computing Technique[J].IRE Trans.Electronic Computers,1959(EC-8)：330-334.

[2]徐光輝,程旭東,黃如,等.基于 FPGA的嵌入式開發(fā)與應用[M].北京：電子工業(yè)出版社,2006.

[3]田耘,徐文波,張延偉,等.無線通信 FPGA設計[M].北京：電子工業(yè)出版社,2007.

[4]UWE M B.數(shù)字信號處理的 FPGA實現(xiàn)[M].北京：清華大學出版社,2006.

[5]徐小峰,唐治德,鄧玉娟,等.基于 CORDIC算法的 QAM調(diào)制器的 FPGA實現(xiàn)[J].通信技術,2008,41(09)：9-11.