《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 設(shè)計應(yīng)用 > 基于FPGA的CORDIC算法的改進(jìn)及實現(xiàn)
基于FPGA的CORDIC算法的改進(jìn)及實現(xiàn)
來源:微型機(jī)與應(yīng)用2011年第16期
刁 玉1,宋澤琳2,馬令坤2
(1.中國人民解放軍第四三二八工廠,山西 長治046011;2.陜西科技大學(xué) 電氣與信息工程學(xué)院,陜
摘要: 介紹了CORDIC算法的基本原理,分析了其具體計算方法。針對利用CORDIC流水線實現(xiàn)FFT蝶形運(yùn)算耗費資源多的問題,依據(jù)CORDIC計算迭代系數(shù)的方法改進(jìn)了CORDIC流水線的結(jié)構(gòu)形式,使其適應(yīng)FFT算法。選用 ALTERA 公司CycloneII系列的EP2C35F672C6 來實現(xiàn)整個FFT 處理器,并對設(shè)計進(jìn)行了時序仿真和硬件仿真。通過比較,計算結(jié)果與設(shè)計基本一致。
關(guān)鍵詞: FPGA CORDIC FFT Cyclone II 流水線
Abstract:
Key words :

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

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


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

 

 

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

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

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

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。