摘 要: 介紹了CORDIC算法的基本原理,分析了其具體計算方法。針對利用CORDIC流水線實現(xiàn)FFT蝶形運算耗費資源多的問題,依據(jù)CORDIC計算迭代系數(shù)的方法改進了CORDIC流水線的結構形式,使其適應FFT算法。選用 ALTERA 公司CycloneII系列的EP2C35F672C6 來實現(xiàn)整個FFT 處理器,并對設計進行了時序仿真和硬件仿真。通過比較,計算結果與設計基本一致。
關鍵詞: CORDIC;FFT;Cyclone II;流水線
坐標旋轉計算機CORDIC(The Coordinate Rotational Digital Computer)算法是一種用于計算一些常用的基本運算函數(shù)和算術操作的循環(huán)迭代算法。其基本思想是用一系列與運算基數(shù)相關的角度的不斷偏擺來逼近所需旋轉的角度,從廣義上講它是一個數(shù)值型計算逼近的方法。由于這些固定的角度與計算基數(shù)有關,運算只有移位和加/減。若用傳統(tǒng)的乘、除等計算方法,需要占用大量的硬件資源,甚至算法是難以實現(xiàn)的,這樣就不能滿足設計者的要求。CORDIC算法正是由此產生的,它僅在硬件電路上用到了移位和加/減,大大節(jié)約了硬件資源,使得這些算法在硬件上可以得到較好地實現(xiàn),從而滿足設計者的要求。根據(jù)它的迭代原理,CORDIC單元可以用流水線結構表示,使向量旋轉并行處理,大大加快了蝶形運算的速度[1]。但是CORDIC運算單元的多級迭代也占用了大量的芯片資源,尤其是在使用多個蝶形進行FFT處理時,使用的資源是非常巨大的,為了盡量降低資源占用,對CORDIC流水線進行了結構上的改進。
1 CORDIC算法原理
1959年,VOLDER開發(fā)了一類計算三角函數(shù)、雙曲函數(shù)的算法,其中包括指數(shù)和對數(shù)運算。此算法的基本思想是用一系列固定的與運算基數(shù)相關的角度不斷偏擺從而逼近所需的角度。從廣義上講它是提供一個數(shù)值計算的逼近方法。由于這些固定的角度只與計算基數(shù)有關,運算只有移位和加減。CORDIC算法雖然可以實現(xiàn)很多基本函數(shù),但一開始并沒有引起人們很大的注意,只是CAGGETT用它來實現(xiàn)二進制和十進制的轉換。整個60年代沒什么進展,直到1971年WALTHER提出統(tǒng)一的CORDIC算法,加上VLSI技術的不斷發(fā)展,CORDIC算法才越來越受到人們的重視,并展示出廣泛的應用前景[2]。CORDIC算法已被廣泛用作現(xiàn)代信號處理各種算法實現(xiàn)中的運算單元,諸如離散傅里葉變換、矩陣的分解、矩陣特征值的求解、場分解、線性預測參數(shù)的求解等。
如圖1所示,一對直角坐標軸順時針旋轉角度A(點M相對于坐標軸逆時針旋轉),點M的坐標從(x0,y0)變?yōu)?x,y)[3-6]。
為了滿足FFT在速度上的要求,CORDIC可以設計成流水線的形式。將需要旋轉的角度加到Z0數(shù)據(jù)通道,通過Z1與固定角度相加減產生所取的值。需要旋轉的(x0,y0)向量在各級迭代中旋轉方向。Zn通過多次迭代,趨近于零,向量旋轉到相應角度。如果在FFT的蝶形單元中用CORDIC代替復乘單元,只需要將數(shù)據(jù)的實部和虛部分別加到x0和y0通道,將復乘系數(shù)作為角度從Z0處輸入,達到了乘以的目的。實際應用中將FFT使用的角度值存儲在ROM中,由地址發(fā)生器控制,在計算時將相應的旋轉角度讀入CORDIC中即可。使用CORDIC算法可以方便快捷地計算FFT蝶形,但是由于迭代次數(shù)多,導致耗費資源也比較多。
將CORDIC流水線形式進行改進,如圖3所示,需要旋轉的向量的實部和虛部分別加到X0和Y0數(shù)據(jù)通道上,系數(shù)輸入到D觸發(fā)器中與向量保持同步,用來控制向量在各級迭代中旋轉的方向。向量經多次迭代旋轉到相應角度[7-8]。
3 CORDIC的旋轉系數(shù)
按照改進后CORDIC的結構,需要事先求出CORDIC的旋轉系數(shù)。根據(jù)CORDIC 算法的迭代原理以及此結構的具體情況,使用 MATLAB 語言編寫程序求出各級旋轉系數(shù),存在ROM中。時序仿真結果如圖4所示。