基于FPGA的CORDIC算法的改進(jìn)及實(shí)現

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

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

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

圖4是利用改進(jìn)的CORDIC算法計算的結果。從仿真圖可以看出：當輸入不同的迭代系數C時(shí)，就可以計算出不同的結果。
4 FFT處理器的仿真和測試
在完成了FFT的整體設計和具體模塊設計之后，選用ALTERA公司CycloneII系列的EP2C35F672C6來(lái)實(shí)現整個(gè)FFT處理器，并對設計進(jìn)行了時(shí)序仿真和硬件仿真[9-10]。
(1)直流信號的測試
使用MATLAB產(chǎn)生一個(gè)直流信號：i=1:256，x(i)=50。輸出計算結果和MATLAB的計算結果比較如圖5所示，MATLAB計算的直流信號FFT結果虛部全為0，實(shí)部只有一個(gè)值即：X(0)=14 000；FFT處理器的計算結果也一樣：X(0)=6 000，如圖6所示。因為運用CORDIC算法一方面使運算每一級的結果擴大了1.65倍，另一方面為了減少誤差和防止溢出，在FFT處理器的各級都進(jìn)行了1/2的截尾處理。但是這樣的處理不會(huì )影響頻譜的顯示。

(2)三角波信號的測試
仍然使用MATLAB：i=1:128，x(i)=i；(28+i)=128，產(chǎn)生一個(gè)三角波信號。MATLAB的計算結果見(jiàn)圖7和圖8，FFT 處理器中輸出計算結果見(jiàn)圖9和圖10。由于FFT 處理器對各級進(jìn)行了放大和截尾處理，所以為了便于比較，將FFT處理的結果進(jìn)行了還原(即除以1.65^3/16)，通過(guò)圖對實(shí)部和虛部進(jìn)行比較，可以證明計算結果基本一致。

采用CORDIC算法以較少的資源實(shí)現了快速乘法器，通過(guò)增加CORDIC運算單元的處理位數，減少了算法的誤差。設計使用16位寬，CORDIC單元的誤差不大于2-14，有效位數為13位。FFT有限字長(cháng)效應長(cháng)生量化誤差，主要來(lái)自輸入量化誤差、系統量化誤差和運算量化誤差。從仿真實(shí)驗可以看出，達到了預期目的。
參考文獻
[1] 胡國榮，孫允恭．CORDIC算法及其應用[J]．信號處理，1991(12)：229-242.
[2] VOLDER J E．The CORDIC trigonometric computing technique[J]．IRE TlectronComputers，1959(9)：330-334．
[3] 于效宇，宋立新，劉艷．CORDIC流水線(xiàn)結構在FFT設計中的改進(jìn)[J]．哈爾濱理工大學(xué)學(xué)報，2005，10(1)：55-57.
[4] 韓芳，初建朋，賴(lài)宗聲．一種CORDIC算法的精度分析及其在FFT中的應用[J].微電子學(xué)與計算機，2004，7（7）：14-16．
[5] 于效宇．基于FPGA的FFT處理器的實(shí)現[D]．哈爾濱：哈爾濱理工大學(xué)，2005.
[6] 李成詩(shī)，初建朋，李新兵．基于CORDIC的一種高速實(shí)時(shí)定點(diǎn)FFT的FPGA實(shí)現[J]．微電子學(xué)與計算機，2004，21(4)：88-91．
[7] 楊宏，李國輝，劉立新．基于FPGA的CORDIC算法的實(shí)現[J]．西安郵電學(xué)院學(xué)報，2008，3（1）：75-77．
[8] 楊宇，毛志剛，來(lái)逢昌．一種改進(jìn)的流水線(xiàn)CORDIC算法結構[J]．微處理機，2006（4）：10-13．
[9] 張俊濤，王紅倉．基于FPGA的CORDIC算法通用IP核設計[J]．微計算機信息，2008，24（7-3）：238-240．
[10] 劉桂華，傅佑麟，嚴平．FFT實(shí)時(shí)譜分析系統的FPGA設計和實(shí)現[J]．集成電路應用，2005（4）：65-67．