王亞春, 蔡德林, 張夢(mèng)龍, 王俊

(①安徽大學(xué)電子科學(xué)與技術(shù)學(xué)院,安徽 合肥 230039;②中國(guó)電子科技集團(tuán)第 38研究所,安徽 合肥 200031)

0 引言

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

1 CORDIC算法的基本原理

以基于圓周模式的 CORDIC算法實(shí)現(xiàn)為例,介紹CORDIC算法的基本原理[1]。假設(shè)平面直角坐標(biāo)系里有一向量：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)過(guò) n次旋轉(zhuǎn)才到達(dá) b(xi,yi),其中第 k次旋轉(zhuǎn)的角度為 θk,那么第 k次旋轉(zhuǎn)的表達(dá)式為：

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

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

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

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

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

zk+1=(總角度 -已旋轉(zhuǎn)角度)=zk-Skarctan 2-k(未旋轉(zhuǎn)角度-剛旋轉(zhuǎn)角度),將此式和式(5)結(jié)合就得到了下面三個(gè)迭代方程式：其中 Sk的符號(hào)由第 k次旋轉(zhuǎn)時(shí)候的角度 zk決定,它們的關(guān)系是：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實(shí)現(xiàn)

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

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

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

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