摘 要： 介紹了CORDIC算法的基本原理,分析了其具體計(jì)算方法。針對(duì)利用CORDIC流水線(xiàn)實(shí)現(xiàn)FFT蝶形運(yùn)算耗費(fèi)資源多的問(wèn)題，依據(jù)CORDIC計(jì)算迭代系數(shù)的方法改進(jìn)了CORDIC流水線(xiàn)的結(jié)構(gòu)形式，使其適應(yīng)FFT算法。選用 ALTERA 公司CycloneII系列的EP2C35F672C6 來(lái)實(shí)現(xiàn)整個(gè)FFT 處理器，并對(duì)設(shè)計(jì)進(jìn)行了時(shí)序仿真和硬件仿真。通過(guò)比較，計(jì)算結(jié)果與設(shè)計(jì)基本一致。
關(guān)鍵詞： CORDIC；FFT；Cyclone II；流水線(xiàn)

　坐標(biāo)旋轉(zhuǎn)計(jì)算機(jī)CORDIC(The Coordinate Rotational Digital Computer)算法是一種用于計(jì)算一些常用的基本運(yùn)算函數(shù)和算術(shù)操作的循環(huán)迭代算法。其基本思想是用一系列與運(yùn)算基數(shù)相關(guān)的角度的不斷偏擺來(lái)逼近所需旋轉(zhuǎn)的角度,從廣義上講它是一個(gè)數(shù)值型計(jì)算逼近的方法。由于這些固定的角度與計(jì)算基數(shù)有關(guān)，運(yùn)算只有移位和加/減。若用傳統(tǒng)的乘、除等計(jì)算方法,需要占用大量的硬件資源，甚至算法是難以實(shí)現(xiàn)的，這樣就不能滿(mǎn)足設(shè)計(jì)者的要求。CORDIC算法正是由此產(chǎn)生的，它僅在硬件電路上用到了移位和加/減，大大節(jié)約了硬件資源,使得這些算法在硬件上可以得到較好地實(shí)現(xiàn),從而滿(mǎn)足設(shè)計(jì)者的要求。根據(jù)它的迭代原理，CORDIC單元可以用流水線(xiàn)結(jié)構(gòu)表示，使向量旋轉(zhuǎn)并行處理，大大加快了蝶形運(yùn)算的速度[1]。但是CORDIC運(yùn)算單元的多級(jí)迭代也占用了大量的芯片資源，尤其是在使用多個(gè)蝶形進(jìn)行FFT處理時(shí)，使用的資源是非常巨大的，為了盡量降低資源占用，對(duì)CORDIC流水線(xiàn)進(jìn)行了結(jié)構(gòu)上的改進(jìn)。
1 CORDIC算法原理
1959年，VOLDER開(kāi)發(fā)了一類(lèi)計(jì)算三角函數(shù)、雙曲函數(shù)的算法，其中包括指數(shù)和對(duì)數(shù)運(yùn)算。此算法的基本思想是用一系列固定的與運(yùn)算基數(shù)相關(guān)的角度不斷偏擺從而逼近所需的角度。從廣義上講它是提供一個(gè)數(shù)值計(jì)算的逼近方法。由于這些固定的角度只與計(jì)算基數(shù)有關(guān)，運(yùn)算只有移位和加減。CORDIC算法雖然可以實(shí)現(xiàn)很多基本函數(shù)，但一開(kāi)始并沒(méi)有引起人們很大的注意，只是CAGGETT用它來(lái)實(shí)現(xiàn)二進(jìn)制和十進(jìn)制的轉(zhuǎn)換。整個(gè)60年代沒(méi)什么進(jìn)展，直到1971年WALTHER提出統(tǒng)一的CORDIC算法，加上VLSI技術(shù)的不斷發(fā)展，CORDIC算法才越來(lái)越受到人們的重視，并展示出廣泛的應(yīng)用前景[2]。CORDIC算法已被廣泛用作現(xiàn)代信號(hào)處理各種算法實(shí)現(xiàn)中的運(yùn)算單元，諸如離散傅里葉變換、矩陣的分解、矩陣特征值的求解、場(chǎng)分解、線(xiàn)性預(yù)測(cè)參數(shù)的求解等。
如圖1所示，一對(duì)直角坐標(biāo)軸順時(shí)針旋轉(zhuǎn)角度A（點(diǎn)M相對(duì)于坐標(biāo)軸逆時(shí)針旋轉(zhuǎn)），點(diǎn)M的坐標(biāo)從(x0，y0)變?yōu)?x，y)[3-6]。

為了滿(mǎn)足FFT在速度上的要求，CORDIC可以設(shè)計(jì)成流水線(xiàn)的形式。將需要旋轉(zhuǎn)的角度加到Z0數(shù)據(jù)通道，通過(guò)Z1與固定角度相加減產(chǎn)生所取的值。需要旋轉(zhuǎn)的(x0，y0)向量在各級(jí)迭代中旋轉(zhuǎn)方向。Zn通過(guò)多次迭代，趨近于零，向量旋轉(zhuǎn)到相應(yīng)角度。如果在FFT的蝶形單元中用CORDIC代替復(fù)乘單元，只需要將數(shù)據(jù)的實(shí)部和虛部分別加到x0和y0通道，將復(fù)乘系數(shù)作為角度從Z0處輸入，達(dá)到了乘以的目的。實(shí)際應(yīng)用中將FFT使用的角度值存儲(chǔ)在ROM中，由地址發(fā)生器控制，在計(jì)算時(shí)將相應(yīng)的旋轉(zhuǎn)角度讀入CORDIC中即可。使用CORDIC算法可以方便快捷地計(jì)算FFT蝶形，但是由于迭代次數(shù)多，導(dǎo)致耗費(fèi)資源也比較多。
將CORDIC流水線(xiàn)形式進(jìn)行改進(jìn)，如圖3所示，需要旋轉(zhuǎn)的向量的實(shí)部和虛部分別加到X0和Y0數(shù)據(jù)通道上，系數(shù)輸入到D觸發(fā)器中與向量保持同步，用來(lái)控制向量在各級(jí)迭代中旋轉(zhuǎn)的方向。向量經(jīng)多次迭代旋轉(zhuǎn)到相應(yīng)角度[7-8]。

3 CORDIC的旋轉(zhuǎn)系數(shù)
按照改進(jìn)后CORDIC的結(jié)構(gòu)，需要事先求出CORDIC的旋轉(zhuǎn)系數(shù)。根據(jù)CORDIC 算法的迭代原理以及此結(jié)構(gòu)的具體情況，使用 MATLAB 語(yǔ)言編寫(xiě)程序求出各級(jí)旋轉(zhuǎn)系數(shù)，存在ROM中。時(shí)序仿真結(jié)果如圖4所示。