CORDIC算法簡(jiǎn)介

在信號(hào)處理領(lǐng)域，CORDIC（Coordinate Rotation Digital Computer，坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算機(jī)）算法具有重大工程意義。CORDIC算法由Vloder于1959年在設(shè)計(jì)美國航空導(dǎo)航控制系統(tǒng)時(shí)提出，主要用于解決導(dǎo)航系統(tǒng)中三角函數(shù)、反三角函數(shù)和開方等運(yùn)算的實(shí)時(shí)計(jì)算問題。

1971年，Walther將圓周系統(tǒng)、線性系統(tǒng)和雙曲線系統(tǒng)統(tǒng)一到一個(gè)CORDIC迭代方程里，從而額提出了一種統(tǒng)一的CORDIC算法形式。

CORDIC算法的核心是利用加法和移位的迭代操作去替代復(fù)雜的運(yùn)算，從而非常有利于硬件實(shí)現(xiàn)。CORDIC算法應(yīng)用廣泛，如離散傅里葉變換（DFT）、離散余弦變換（DCT）、離散Hartley變換、Chirp-Z變換、各種濾波以及矩陣中的奇異值分解。

在工程領(lǐng)域，可采用CORDIC算法實(shí)現(xiàn)直接數(shù)字頻率合成器（DDS）、計(jì)算I/Q信號(hào)的幅度和相位。

01CORDIC基本原理

我們假設(shè)在笛卡爾坐標(biāo)系（也就是我們常見的XY直角坐標(biāo)系）中，將點(diǎn)（x1，y1）旋轉(zhuǎn)θ角度到點(diǎn)（x2，y2）的標(biāo)準(zhǔn)方法如下所示：

根據(jù)上圖，我們利用高中學(xué)習(xí)的三角函數(shù)、圓方程和極坐標(biāo)等中學(xué)知識(shí)，可以得到：

這被稱為是平面旋轉(zhuǎn)、向量旋轉(zhuǎn)或者線性 （ 矩陣） 代數(shù)中的 Givens 旋轉(zhuǎn)。

上面的式子，我們將大學(xué)二年級(jí)學(xué)習(xí)的線性代數(shù)知識(shí)拿出來，用矩陣的形式來表示，于是得到：

例如，我們做一個(gè)90°的相移，即θ=90：

這里注意cos和sin函數(shù)在直角坐標(biāo)系下的物理意義，于是我們得到下面的圖示。

上面的第一個(gè)式子，我們假設(shè)提出一個(gè)公因子cosθ，那么我們可以得到：

如果去除項(xiàng)，我們得到 偽旋轉(zhuǎn) 方程式 ：

即旋轉(zhuǎn)的角度是正確的，但是x 與 y 的值增加cos-1θ 倍 （ 由于cos-1θ》 1），所以模值變大。

注意我們并不能通過適當(dāng)?shù)臄?shù)學(xué)方法去除cosθ 項(xiàng) ， 然而隨后我們發(fā)現(xiàn)去除項(xiàng)可以簡(jiǎn)化坐標(biāo)平面旋轉(zhuǎn)的計(jì)算操作。

怎么說呢？

在XY坐標(biāo)系中，結(jié)合上面的偽旋轉(zhuǎn)公式，我們可以用下圖表示：

于是，我們得出以下結(jié)論：

經(jīng)過偽旋轉(zhuǎn)之后，向量 R 的模值將增加1/cosθ 倍。

向量旋轉(zhuǎn)了正確的角度 ， 但模值出現(xiàn)錯(cuò)誤。

經(jīng)過偽旋轉(zhuǎn)后， 輸出進(jìn)行適當(dāng)?shù)姆壬炜s（1/cosθ），是不是就可以得到旋轉(zhuǎn)后的坐標(biāo)了。

02CORDIC方法

CORDIC 方法的核心是 （ 偽） 旋轉(zhuǎn)角θ，其中，

這個(gè)等式是怎么推導(dǎo)出來的呢？

所以方程為：

下面的表格指出用于 CORDIC 算法中每個(gè)迭代 （i） 的旋轉(zhuǎn)角度 （精確到 9位小數(shù)）：

note：由于i是整數(shù)，所以對(duì)應(yīng)的角度值都是一一確定的，只能通過幾個(gè)角度的加減組合來達(dá)到你所想要的角度值。

注意有三個(gè)方面的變化：

角度累加（減）

坐標(biāo)值累加（減）

向量的模（也就是長度的，相對(duì)于橫縱坐標(biāo)的）累加（減）

這三個(gè)累加的變化時(shí)不一樣的，注意區(qū)別，角度的累加和長度的累加有一定的對(duì)應(yīng)關(guān)系。

03角度累加器

上述三個(gè)方程式為圓周坐標(biāo)系中用于角度旋轉(zhuǎn)的 CORDIC 算法的表達(dá)式。后續(xù)部分中我們還將看到CORDIC 算法被用于其它的坐標(biāo)系，通過使用這些坐標(biāo)系可以執(zhí)行更大范圍的函數(shù)計(jì)算。

04移位-加法算法

因此， 原始的算法現(xiàn)在已經(jīng)被減化為使用向量的偽旋轉(zhuǎn)來表示的迭代移位-相加算法 ：

因此，每個(gè)迭代需要：

note：前面提到的去除 cos 項(xiàng)的原因是顯而易見的。當(dāng)將該項(xiàng)去除時(shí)，轉(zhuǎn)換公式已經(jīng)被簡(jiǎn)化為偽旋轉(zhuǎn)的迭代移位相加計(jì)算。

CORDIC 硬件實(shí)現(xiàn)結(jié)構(gòu)：

05伸縮因子

前面提到，為了得到偽旋轉(zhuǎn)公式，我們把公因子cosθ忽略了，但在實(shí)際運(yùn)算中，不能就這樣簡(jiǎn)單粗暴拋棄。

我們?cè)俅螌?duì)cosθ進(jìn)行變形：

于是，我們可以得到：

如果我們已知了將被執(zhí)行的迭代次數(shù)，我們便可以預(yù)先計(jì)算出 1/Kn 的值，并通過將 1/Kn 與 x（n） 和 y（n）相乘來校正x（n） 和 y（n） 的最終值。

CORDIC有兩種工作模式：旋轉(zhuǎn)模式和向量模式。

06三種坐標(biāo)系下的CORDIC

然而， 我們將會(huì)看到，通過考慮其它坐標(biāo)系中的旋轉(zhuǎn)， 我們可以直接計(jì)算更多的函數(shù)， 如乘法和除法， 進(jìn)而間接計(jì)算更多的其它函數(shù)。

使用其它坐標(biāo)系的 CORDIC 算法的優(yōu)點(diǎn)是可以計(jì)算更多的函數(shù)， 而缺點(diǎn)則是系統(tǒng)將變得更加復(fù)雜。當(dāng)把CORDIC 算法用于線性或雙曲坐標(biāo)系時(shí)， 在圓周坐標(biāo)系中的旋轉(zhuǎn)角度集將不再有效。所以， 這些系統(tǒng)應(yīng)使用其它的兩種旋轉(zhuǎn)角度集。

我們會(huì)發(fā)現(xiàn)，可以推導(dǎo)出可在 3 個(gè)坐標(biāo)系中表示 CORDIC 方程的通用公式。這意味著在方程式中引入兩個(gè)新變量。其中一個(gè)新變量 （e（i）） 代表了適當(dāng)?shù)淖鴺?biāo)系中用于表示旋轉(zhuǎn)的角度集。

當(dāng)把CORDIC算法用于雙曲線旋轉(zhuǎn)時(shí)，伸縮因子K與圓周旋轉(zhuǎn)的因子有所不同。

我們通過引入一個(gè)新變量μ，得到CORDIC的通用方程：

至此，三個(gè)坐標(biāo)系下的CORDIC方程得到大一統(tǒng)。

在使用FPGA進(jìn)行CORDIC算法實(shí)現(xiàn)時(shí)，理想CORDIC 架構(gòu)取決于具體應(yīng)用中速率與面積的權(quán)衡。

可以將 CORDIC 方程直接翻譯成迭代型的位并行設(shè)計(jì)，然而：

位并行變量移位器不能很好地映射到 FPGA 中

需要若干個(gè) FPGA 單元。導(dǎo)致設(shè)計(jì)規(guī)模變大而設(shè)計(jì)時(shí)間變長

參考文獻(xiàn)

關(guān)于 CORDIC 算法的基礎(chǔ)以及細(xì)節(jié)問題，可參見下面的材料 ：

［1］ R. Andraka. A survey of CORDIC algorithms for FPGA based computers. www.andraka.com/cordic.htm

［2］ The CORDIC Algorithms. www.ee.byu.edu/ee/class/ee621/Lectures/L22.PDF

［3］ CORDIC Tutorial. http://my.execpc.com/~geezer/embed/cordic.htm

［4］ M. J. Irwin. Computer Arithmetic. http://www.cse.psu.edu/~cg575/lectures/cse575-cordic.pdf

編輯：jq