基于FPGA的可擴展高速FFT處理器的設計與實現
關鍵詞:快速傅里葉變換;處理器;坐標旋轉數字計算機;現場可編程門陣列;設計
一、引言
DFT(離散傅里葉變換)作為將信號從時域轉換到頻域的基本運算,在各種數字信號處理中起著核心作用,其快速算法FFT(快速傅里葉變換)在無線通信、語音識別、圖像處理和頻譜分析等領域有著廣泛的應用。用大規(guī)模集成電路FPGA(現場可編程門陣列)來實現FFT算法時,需要重點考慮的不再是算法運算量,而是算法的復雜性、規(guī)整性和模塊化,因為算法的簡單性和規(guī)整性將更適合大規(guī)模集成,更方便于版圖設計,而算法的模塊化更有利于FFT處理器的靈活擴展。組合數FFT算法和CORDIC(坐標旋轉數字計算機)算法結合起來,在計算長點數、可擴展FFT時具有較大的優(yōu)越性[1,2]。而面向高速、大容量數據流的FFT的實時處理,可以通過VLSI(超大規(guī)模集成電路)器件的并行處理或多級流水線處理等來達到。特別是多級流水線處理的FFT結構使得基于FPGA器件的FFT處理器完成不同點數的FFT計算時可以通過增減模塊級數很容易地實現。
二、組合數N=r1r2點混合基FFT原理
計算N點DFT:
式中k=0,1,…,N-1。
若N=r1r2的組合數,可將n(n<N)表示為
式(2)的意義在于,計算組合數N=r1r2點DFT,等價于先求出r?2組r?1點的DFT,其結果經過對應旋轉因子的相位旋轉后,再計算r1組r2點的DFT。實際應用中,DFT往往用它的快速算法FFT實現,因而式(2)中的r1點DFT和r2點DFT都用r1點FFT和r2點FFT實現。
三、可擴展FFT處理器實現結構
根據式(2)的FFT算法原理設計FFT處理器的可擴展結構如圖1所示。
采用流水線模塊化級聯結構,把FFT處理器劃分成短點數FFT、級間混序RAM和相位旋轉等功能模塊,設計的各功能模塊可以重復利用,通過復用或增減各功能模塊可以靈活改變FFT處理器的計算規(guī)模,而且不增加設計量。在圖1結構中,當Li=1時,就演變成了基2 FFT;當Li=2時,就演變成了基4 FFT;同理,當Li≠Lj時,就演變成了高組合數的混合基FFT。
1.短點數FFT陣列結構
-Tukey算法結構實現時,有大量的復數乘法實際上轉化為加減運算,所以用陣列結構實現不但具有速度快的優(yōu)點,而且所用器件資源也減少很多,通過對陣列結構短點數FFT進行時分復用,可以提高運算單元的使用效率。
2.相位旋轉運算單元
實現短點數FFT級間相位旋轉,采用ROM存儲旋轉因子與數據復乘的傳統(tǒng)方法,不僅涉及乘法運算,而且會消耗大量存儲器資源。
利用CORDIC算法實現組合數FFT級間數據的相位旋轉,把乘法轉化成加減法運算,適合FPGA的大規(guī)模集成??梢栽O計出統(tǒng)一結構的CORDIC處理器模塊,重復利用于不同級間實現相位旋轉,而且其控制邏輯非常簡單。
(1)CORDIC算法原理
復數P=x+jy旋轉角度θ得到Q的表達式:
如果旋轉角度θ可以分解成n個小角度φi之和,即:
公式:
(2)CORDIC處理器結構設計
本文提出了一種流水線CORDIC處理器結構的解決方案。實現式子(4)的迭代運算時采用補碼移位和補碼加減運算,可以減少大量求補運算,其迭代結構如圖2所示。
??
前者在于左移補零的位數的不同,這樣,只需要改變n0k0的放大倍數(改變左移低位補零的位數),就可以把同一方向向量功能模塊級聯到圖1 FFT處理器的不同級間來計算CORDIC處理器的MSBi,這就大大地減小了重復設計,其迭代結構如圖3所示。
3.RAM結構及其級間數據混序用流水線讀/寫RAM地址發(fā)生器的設計
設計的RAM,每個存儲單元為32 bit,高16位為復數的實部,低16位為復數的虛部。輸入輸出數據接口用RAM設計為乒乓結構,用兩塊相同的RAM交替讀出或交替寫入數據,這樣就放寬了對I/O操作速度的要求,使得外圍電路可以不必工作于FPGA系統(tǒng)時鐘。
級與級之間數據混序用RAM設計為讀/寫RAM,對RAM同一存儲單元用兩個時鐘完成一次讀/寫操作,即用流水線讀/寫同一塊RAM來實現級與級之間的數據混序。此結構取代了用兩塊RAM完成數據混序的乒乓結構的傳統(tǒng)方法,不涉及存儲器之間的讀寫切換,控制邏輯非常簡單,而且消耗的存儲器資源節(jié)省一半,這是實現結構可靈活擴展的高速FFT處理器的關鍵和難點??梢酝ㄟ^理論推導,求得第i級FFT與第i-1級FFT級間混序用RAM的奇次讀/寫地址為
的基礎上向左循環(huán)移位,位長為Li-Li-1位;同時,后者又表示在前者的基礎上向左循環(huán)移位,位長為Li-Li-1位,從而形成地址的循環(huán)移位規(guī)律。把Li-1=Li和Li-1Li兩種情況統(tǒng)一起來,即Li-1=Li時,Li-Li-1=0,不用循環(huán)移位,只需要計數器的高Li-1位和低Li-1位進行交替。利用此地址發(fā)生規(guī)律,可以設計基于圖1結構的基2、基4等任意基x FFT以及混合基FFT級間數據混序用流水線讀/寫RAM地址發(fā)生器。
4.842點組合數FFT處理器的實驗結果及其分析
我們利用FPGA實現的各功能模塊按圖1實現結構組裝了842點組合數FFT處理器,通過仿真驗證了其設計的正確性后,又在FPGA實驗板上對它進行了硬件驗證,其實驗驗證平臺如圖4所示。
硬件驗證時采取的實驗方法是,用相同的抽樣頻率fs等間隔地抽取不同頻率單頻正弦信號相同點數64點,即固定FFT的頻率分辨率fr,利用設計的64點FFT處理器計算其幅度譜,觀察其幅度譜中直流分量譜線和諧波分量譜線間隔大小的變化,把實驗結果和理論分析結果進行對照,以確認FFT處理器工作的正常與否。
系統(tǒng)時鐘工作在 40.861 MHz 時,抽樣頻率為 40.861/2=20.4305 MHz,抽樣周期為1/20.4305 MHz=48.9 ns,抽取64個點的時間是48.964=3.13μs。因為每個采樣數據間隔時間是48.9μs,所以用設計的流水線方式工作的64點FFT處理器計算其幅度譜的譜線間隔也為48.9 ns。當輸入單頻正弦信號的頻率約為638.454 kHz時,其周期為1/638.454 kHz=1.567μs。用20.4305 MHz頻率抽樣,3.13μs時間內剛好在正弦信號的2個周期內抽取64點,輸入單頻正弦信號的頻率是頻率分辨率319.227 kHz的2倍,直流分量為幅度譜的第1根譜線,一次諧波分量為幅度譜的第3根譜線,其理論計算結果波形如圖5所示,實驗測試結果波形及其的局部放大波形如圖6和圖7所示。
從示波器上可以看出,橫坐標單元格間隔為1μs,FFT變換周期間隔約為3格,即約為3μs,抽取了信號波形的2個周期,64點FFT計算時間也約為3μs。
輸入單頻正弦信號的頻率是頻率分辨率319.227 kHz的2倍,直流分量為幅度譜的第1根譜線,一次諧波分量為幅度譜的第2根譜線。由于幅度譜的譜線間隔為48.9 ns,也就是說,直流分量和一次諧波分量間隔約為100 ns。從示波器上可以看出,橫坐標單元格間隔為100 ns,直流分量和一次諧波分量間隔約為100 ns,和理論分析結果一致。
四、結論
本文以高組合數混合基DFT算法為基礎,設計并用FPGA實現了變換點數可靈活擴展的流水線FFT處理器。輸入/輸出數據速率為20 MHz時,讀/寫RAM工作在40 MHz時鐘,計算出1 024點FFT的運算時間約為52μs。本設計采用模塊化設計結構,便于系統(tǒng)調試和實現,而且各設計模塊可以重復利用,避免重復相同的設計,從而縮短芯片設計開發(fā)時間,更易于FFT處理器的結構擴展。整個FFT設計結構新穎,實現容易,具有一定實用價值。
參考文獻
[1]程佩清.數字信號處理教程[M].北京:清華大學出版社,2001.
[2]侯伯亨,顧新.VHDL硬件描述語言與數字邏輯電路設計[M].西安:西安電子科技大學出版,1999.
[3]Stephan W.Mondwurf.BENEFITS OF THE CORDIC-ALGORITHM IN A VERSATILE COFDM MODULATOR/DEMODULATOR DESIGN[A]. Fourth IEEE International Caracas Conference on Devices, Circuits and Systems[C].Aruba, April 17~19, 2002.
[4]趙忠武,陳禾,韓月秋.基于FPGA的32位浮點FFT處理器的設計[J].電訊技術,2003,43(6).
[5]Y.Ma,L.Wanhammar.A Hardware efficient control of memory addressing for high performance FFT processors[J].IEEE transactions on signal processing, 2000,48(3):917~921.
[6]J.E.Volder.The CORDIC Trigonometric Computing Technique[J]. IRE Trans. on Electronic Computers,1959,8(3):330~334.
[7]韓穎,王旭,吳嗣亮.FPGA實現高速FFT處理器的設計[J].電訊技術,2003,43(2):74~78.
[8]A.M.Despain.Fourier Transform Computers Using CORDIC Iterations[J].IEEE Trans.on Computers,1993,C-23(10):993~1001.
評論