CORDIC算法原理

曹劍英，劉凌云

（集寧師范學(xué)院 物理系，內(nèi)蒙古 烏蘭察布 012000）

CORDIC算法原理

曹劍英，劉凌云

（集寧師范學(xué)院 物理系，內(nèi)蒙古 烏蘭察布 012000）

CORDIC算法根據(jù)不同的旋轉(zhuǎn)軌跡分成線性系統(tǒng)、圓周系統(tǒng)和雙曲系統(tǒng)；每個(gè)系統(tǒng)又有旋轉(zhuǎn)模式和向量模式兩種，本文詳細(xì)地來(lái)闡述CORDIC的算法原理和實(shí)現(xiàn)不同的運(yùn)算，給初學(xué)者一些參考.

坐標(biāo)旋轉(zhuǎn)算法；CORDIC算法；原理

1 CORDIC算法原理

1.1 算法推導(dǎo)[1]

圖1 平面坐標(biāo)的旋轉(zhuǎn)

CORDIC算法是一種旋轉(zhuǎn)坐標(biāo)的方法.設(shè)起點(diǎn)坐標(biāo)為P0=(x(1),y(1))，旋轉(zhuǎn)θ角度，得到終點(diǎn)坐標(biāo)，設(shè)為Pn=(x(2),y(2))，如圖1所示.由三角函數(shù)知識(shí)，旋轉(zhuǎn)后的坐標(biāo)由式（1-1）計(jì)算得到(1-1)

其中

即

矩陣R可以寫(xiě)成

這樣，設(shè)P'n=Rc·P0，則

把cosθ去掉后相當(dāng)于把旋轉(zhuǎn)后矢量的模減小了，為了保證最終的結(jié)果正確，一般在結(jié)果的后面乘上一個(gè)系數(shù)K.對(duì)于某一個(gè)角度β，假定初始角度為z0，可以通過(guò)z0經(jīng)過(guò)若干個(gè)小角度θi的旋轉(zhuǎn)獲得

并可以得到如下所示的迭代公式：

假設(shè)我們從X軸開(kāi)始旋轉(zhuǎn)，通過(guò)一些列逐次減少的角度旋轉(zhuǎn)后，只要迭代的次數(shù)足夠多，就可以實(shí)現(xiàn)內(nèi)任意角度的旋轉(zhuǎn)，并且通過(guò)加法和移位運(yùn)算得到目的的橫坐標(biāo)和縱坐標(biāo).每次旋轉(zhuǎn)后得到的實(shí)際矢量和目標(biāo)矢量之間的誤差角度（目標(biāo)角度減去實(shí)際角度）如下式：

其中，z0為目標(biāo)矢量角度，若zi<0，則di=1.實(shí)際迭代后累計(jì)角度為：

其中a0=0.例如，要實(shí)現(xiàn)680的矢量旋轉(zhuǎn)，我們可以列出第i次對(duì)應(yīng)的旋轉(zhuǎn)角度、旋轉(zhuǎn)方向、迭代后的實(shí)際角度和誤差如表1所示.

表1 旋轉(zhuǎn)680的CORDIC實(shí)現(xiàn)

一旦zi迭代的次數(shù)確定了，∏Ki也就確定了，Ki的乘積可以在實(shí)現(xiàn)時(shí)不做處理，而是被當(dāng)做整個(gè)系統(tǒng)處理增益的一部分，實(shí)際的增益取決于迭代次數(shù)n.

當(dāng)n趨于無(wú)窮大時(shí)，An的極限值約為1.647.在實(shí)現(xiàn)CORDIC算法時(shí)，由于An當(dāng)作系統(tǒng)的處理增益不做處理，因此只需要移位、相加運(yùn)算就可完成矢量旋轉(zhuǎn)，很適合在FPGA中實(shí)現(xiàn)[2].

2 CORDIC算法引申及模型

以上所作的Cordic理論分析，只是Cordic算法提出時(shí)的理論雛形；之后，John Walther于1971年對(duì)其進(jìn)行了擴(kuò)展引申，進(jìn)一步的完備了Cordic算法，得到以下Cordic的迭代模型[2].

這里，

i表示迭代索引（比如i=1,2,…,N），δi=+1 -｛1視情況而定.

根據(jù)m=1,-1,0，分別稱(chēng)為圓周旋轉(zhuǎn)運(yùn)算（Circular）、雙曲旋轉(zhuǎn)

運(yùn)算(Hyperbolic)和線性旋轉(zhuǎn)運(yùn)算(Linear)，也即

根據(jù)δi取值的判讀方式，CORDIC算法又分為旋轉(zhuǎn)模式和向量模式.

2.1 向量模式

設(shè)初始旋轉(zhuǎn)的角度為z0=θ，經(jīng)過(guò)N次旋轉(zhuǎn)后，使得yN=0，這時(shí)

這樣的模式稱(chēng)為向量模式.根據(jù)式（2-11），可得迭代N次之后，有

這里f(x,y,z)、g(x,y,z)表示某具體的函數(shù)，比如兩變量的乘法除法運(yùn)算，具體是哪類(lèi)函數(shù)，還需要根據(jù)式（2-13）中的m取值而定.

2.2 旋轉(zhuǎn)模式

設(shè)初始旋轉(zhuǎn)的角度為z0=θ，經(jīng)過(guò)N次旋轉(zhuǎn)后，使得zN=0，這時(shí)

這樣的模式稱(chēng)為旋轉(zhuǎn)模式.根據(jù)式（1-10），可得迭代N次之后，有

這里f(x,y,z)、g(x,y,z)表示某具體的函數(shù)，比如正弦余弦函數(shù)，具體是哪類(lèi)函數(shù)，還需要根據(jù)式（2-13）中的m取值而定.

2.3 線性CORDIC

當(dāng)式（2-13）中的m取值為0時(shí)，對(duì)應(yīng)的是線性運(yùn)算模式下的CORDIC算法.將m=0代入式（2-11），則得到如下迭代式

其中，根據(jù)式（2-12），得到θi的計(jì)算式，如下

對(duì)于初始變量x0,y0,z0，限制性條件為

由式（2-20）可知，在滿足式（2-21）的條件下，輸入z0=0，則可以迭代實(shí)現(xiàn)兩變量的除法操作.

在旋轉(zhuǎn)模式下，zi+1→0，迭代N+1次后，得到如下的結(jié)果

對(duì)于初始變量x0,y0,z0，限制性條件為

由式（2-22）可知，在滿足式（2-23）的條件下，輸入y0=0，則可以迭代實(shí)現(xiàn)兩變量的乘法操作.

2.4 圓周CORDIC

當(dāng)式（2-13）中的m取值為1時(shí)，對(duì)應(yīng)的是圓周運(yùn)算模式下的CORDIC算法.將m=1代入式（2-11），則得到如下迭代式

i=0,1,2,…,N是迭代次數(shù).

在向量模式下，yi+1→0，迭代N+1次后，得到如下的結(jié)果

其中，θi=arctan2-i，αi=2-i，i=0,1,2,3,…,N是迭代次數(shù).

在向量模式下，y→0，輸入值yin,xin的限制條件是|atanh (yin/xin)|≤1.7433(99.90)，迭代結(jié)果為

在旋轉(zhuǎn)模式下，x→0，輸入zin的限制條件是|zin|≤1.7433(99.90)，得到的迭代結(jié)果為

這里所能表示的角度范圍是在-99.90～99.90，在計(jì)算不在這個(gè)范圍角度值的三角函數(shù)值，需要進(jìn)行預(yù)處理.進(jìn)行預(yù)處理也是一個(gè)比較可行的方法，但是，這會(huì)較大程度上加大設(shè)計(jì)的復(fù)雜度[3].

2.5 雙曲CORDIC

雙曲模式下，m=-1，得到的迭代式是：

其中，θi=arctan2-i，αi=2-i，i=0,1,2,3,…,N是迭代次數(shù).

在向量模式下，y→0，輸入值yin,xin的限制條件是|atanh (yin/xin)|≤1.1182，可以用來(lái)計(jì)算方根以及反雙曲正切函數(shù)的值.

在旋轉(zhuǎn)模式下，x→0輸入zin的限制條件是|zin|≤1.1182，可以用來(lái)計(jì)算雙曲余弦和雙曲正弦函數(shù).

2.6 CORDIC算法小結(jié)

當(dāng)m取不同的值時(shí)，可以得到CORDIC的三種不同計(jì)算方式，在各個(gè)計(jì)算方式下，通過(guò)多次迭代，可以計(jì)算得到多個(gè)函數(shù)的值，比如三角函數(shù)、雙曲函數(shù)以及開(kāi)方運(yùn)算等.表2描述了線性系統(tǒng)、圓周系統(tǒng)和雙曲系統(tǒng)在旋轉(zhuǎn)和向量模式下的迭代結(jié)果.

表2 CORDIC算法在各種模式下的迭代結(jié)果[8]

圖2 圓周系統(tǒng)的旋轉(zhuǎn)模型迭代結(jié)果

〔1〕孔德元.針對(duì)正弦余弦計(jì)算的CORDIC算法優(yōu)化及其FPGA實(shí)現(xiàn)[D].中南大學(xué)碩士論文，2008.1-3.

〔2〕J.E.Volder.The CORDIC trigonometric computing technique [J].IRE Trans.on Electron.Computers,vol. EC-8,1959.330-334.

〔3〕Xiaobo Hu,Ronald G.Harber,and Steven C.Bass, Expanding the Range of Convergence of the CORDIC Algorithm,IEEE Trans.on Computers,[J].vol.40,no.1, 1991.Jan.P.13-P.21.

〔4〕曹劍英.M倍降速遞歸流水線技術(shù)實(shí)現(xiàn)正切余切函數(shù)[J].通信技術(shù)，2013(05).

O241

A

1673-260X（2014）04-0021-03