基于FPGA的可擴展高速FFT處理器的設計與實(shí)現

一、引言
　　DFT(離散傅里葉變換)作為將信號從時(shí)域轉換到頻域的基本運算，在各種數字信號處理中起著(zhù)核心作用，其快速算法FFT(快速傅里葉變換)在無(wú)線(xiàn)通信、語(yǔ)音識別、圖像處理和頻譜分析等領(lǐng)域有著(zhù)廣泛的應用。用大規模集成電路FPGA(現場(chǎng)可編程門(mén)陣列)來(lái)實(shí)現FFT算法時(shí)，需要重點(diǎn)考慮的不再是算法運算量，而是算法的復雜性、規整性和模塊化，因為算法的簡(jiǎn)單性和規整性將更適合大規模集成，更方便于版圖設計，而算法的模塊化更有利于FFT處理器的靈活擴展。組合數FFT算法和CORDIC(坐標旋轉數字計算機)算法結合起來(lái)，在計算長(cháng)點(diǎn)數、可擴展FFT時(shí)具有較大的優(yōu)越性^{［1，2］}。而面向高速、大容量數據流的FFT的實(shí)時(shí)處理，可以通過(guò)VLSI(超大規模集成電路)器件的并行處理或多級流水線(xiàn)處理等來(lái)達到。特別是多級流水線(xiàn)處理的FFT結構使得基于FPGA器件的FFT處理器完成不同點(diǎn)數的FFT計算時(shí)可以通過(guò)增減模塊級數很容易地實(shí)現。

二、組合數N=r₁r₂點(diǎn)混合基FFT原理
　　計算N點(diǎn)DFT：
　　
　　式中k=0，1，…，N-1。
　　若N=r₁r₂的組合數，可將n(n＜N)表示為
　　
　　式(2)的意義在于，計算組合數N=r1r2點(diǎn)DFT，等價(jià)于先求出r?2組r?1點(diǎn)的DFT，其結果經(jīng)過(guò)對應旋轉因子的相位旋轉后，再計算r1組r2點(diǎn)的DFT。實(shí)際應用中，DFT往往用它的快速算法FFT實(shí)現，因而式(2)中的r1點(diǎn)DFT和r2點(diǎn)DFT都用r1點(diǎn)FFT和r2點(diǎn)FFT實(shí)現。

三、可擴展FFT處理器實(shí)現結構
　　根據式(2)的FFT算法原理設計FFT處理器的可擴展結構如圖1所示。

　　采用流水線(xiàn)模塊化級聯(lián)結構，把FFT處理器劃分成短點(diǎn)數FFT、級間混序RAM和相位旋轉等功能模塊，設計的各功能模塊可以重復利用，通過(guò)復用或增減各功能模塊可以靈活改變FFT處理器的計算規模，而且不增加設計量。在圖1結構中，當L_i＝1時(shí)，就演變成了基2 FFT；當L_i＝2時(shí)，就演變成了基4 FFT；同理，當L_i≠L_j時(shí)，就演變成了高組合數的混合基FFT。

1.短點(diǎn)數FFT陣列結構
　
－Tukey算法結構實(shí)現時(shí)，有大量的復數乘法實(shí)際上轉化為加減運算，所以用陣列結構實(shí)現不但具有速度快的優(yōu)點(diǎn)，而且所用器件資源也減少很多，通過(guò)對陣列結構短點(diǎn)數FFT進(jìn)行時(shí)分復用，可以提高運算單元的使用效率。

2.相位旋轉運算單元
　　實(shí)現短點(diǎn)數FFT級間相位旋轉，采用ROM存儲旋轉因子與數據復乘的傳統方法，不僅涉及乘法運算，而且會(huì )消耗大量存儲器資源。

　　利用CORDIC算法實(shí)現組合數FFT級間數據的相位旋轉，把乘法轉化成加減法運算，適合FPGA的大規模集成?？梢栽O計出統一結構的CORDIC處理器模塊，重復利用于不同級間實(shí)現相位旋轉，而且其控制邏輯非常簡(jiǎn)單。

　　(1)CORDIC算法原理
　　復數P=x+jy旋轉角度θ得到Q的表達式：
　　
　　如果旋轉角度θ可以分解成n個(gè)小角度φ_i之和，即：
　　
公式:
　　

　　(2)CORDIC處理器結構設計
　　本文提出了一種流水線(xiàn)CORDIC處理器結構的解決方案。實(shí)現式子(4)的迭代運算時(shí)采用補碼移位和補碼加減運算，可以減少大量求補運算，其迭代結構如圖2所示。

??

　　
前者在于左移補零的位數的不同，這樣，只需要改變n₀k₀的放大倍數(改變左移低位補零的位數)，就可以把同一方向向量功能模塊級聯(lián)到圖1 FFT處理器的不同級間來(lái)計算CORDIC處理器的MSB_i，這就大大地減小了重復設計，其迭代結構如圖3所示。

3.RAM結構及其級間數據混序用流水線(xiàn)讀/寫(xiě)RAM地址發(fā)生器的設計
　　設計的RAM，每個(gè)存儲單元為32 bit，高16位為復數的實(shí)部，低16位為復數的虛部。輸入輸出數據接口用RAM設計為乒乓結構，用兩塊相同的RAM交替讀出或交替寫(xiě)入數據，這樣就放寬了對I/O操作速度的要求，使得外圍電路可以不必工作于FPGA系統時(shí)鐘。

　　級與級之間數據混序用RAM設計為讀/寫(xiě)RAM，對RAM同一存儲單元用兩個(gè)時(shí)鐘完成一次讀/寫(xiě)操作，即用流水線(xiàn)讀/寫(xiě)同一塊RAM來(lái)實(shí)現級與級之間的數據混序。此結構取代了用兩塊RAM完成數據混序的乒乓結構的傳統方法，不涉及存儲器之間的讀寫(xiě)切換，控制邏輯非常簡(jiǎn)單，而且消耗的存儲器資源節省一半，這是實(shí)現結構可靈活擴展的高速FFT處理器的關(guān)鍵和難點(diǎn)?？梢酝ㄟ^(guò)理論推導，求得第i級FFT與第i-1級FFT級間混序用RAM的奇次讀/寫(xiě)地址為
　　
　　的基礎上向左循環(huán)移位，位長(cháng)為L(cháng)_i-L_i-1位；同時(shí)，后者又表示在前者的基礎上向左循環(huán)移位，位長(cháng)為L(cháng)_i-L_i-1位，從而形成地址的循環(huán)移位規律。把L_i-1=L_i和L_i-1L_i兩種情況統一起來(lái)，即L_i-1=L_i時(shí)，L_i-L_i-1=0，不用循環(huán)移位，只需要計數器的高L_i-1位和低L_i-1位進(jìn)行交替。利用此地址發(fā)生規律，可以設計基于圖1結構的基2、基4等任意基x FFT以及混合基FFT級間數據混序用流水線(xiàn)讀/寫(xiě)RAM地址發(fā)生器。

4.842點(diǎn)組合數FFT處理器的實(shí)驗結果及其分析
　　我們利用FPGA實(shí)現的各功能模塊按圖1實(shí)現結構組裝了842點(diǎn)組合數FFT處理器，通過(guò)仿真驗證了其設計的正確性后，又在FPGA實(shí)驗板上對它進(jìn)行了硬件驗證，其實(shí)驗驗證平臺如圖4所示。

　　硬件驗證時(shí)采取的實(shí)驗方法是，用相同的抽樣頻率f_s等間隔地抽取不同頻率單頻正弦信號相同點(diǎn)數64點(diǎn)，即固定FFT的頻率分辨率f_r，利用設計的64點(diǎn)FFT處理器計算其幅度譜，觀(guān)察其幅度譜中直流分量譜線(xiàn)和諧波分量譜線(xiàn)間隔大小的變化，把實(shí)驗結果和理論分析結果進(jìn)行對照，以確認FFT處理器工作的正常與否。

　　系統時(shí)鐘工作在 40.861 MHz 時(shí)，抽樣頻率為 40.861/2=20.4305 MHz，抽樣周期為1/20.4305 MHz=48.9 ns，抽取64個(gè)點(diǎn)的時(shí)間是48.964＝3.13μs。因為每個(gè)采樣數據間隔時(shí)間是48.9μs，所以用設計的流水線(xiàn)方式工作的64點(diǎn)FFT處理器計算其幅度譜的譜線(xiàn)間隔也為48.9 ns。當輸入單頻正弦信號的頻率約為638.454 kHz時(shí)，其周期為1/638.454 kHz＝1.567μs。用20.4305 MHz頻率抽樣，3.13μs時(shí)間內剛好在正弦信號的2個(gè)周期內抽取64點(diǎn)，輸入單頻正弦信號的頻率是頻率分辨率319.227 kHz的2倍，直流分量為幅度譜的第1根譜線(xiàn)，一次諧波分量為幅度譜的第3根譜線(xiàn)，其理論計算結果波形如圖5所示，實(shí)驗測試結果波形及其的局部放大波形如圖6和圖7所示。

　　從示波器上可以看出，橫坐標單元格間隔為1μs，FFT變換周期間隔約為3格，即約為3μs，抽取了信號波形的2個(gè)周期，64點(diǎn)FFT計算時(shí)間也約為3μs。

　　輸入單頻正弦信號的頻率是頻率分辨率319.227 kHz的2倍，直流分量為幅度譜的第1根譜線(xiàn)，一次諧波分量為幅度譜的第2根譜線(xiàn)。由于幅度譜的譜線(xiàn)間隔為48.9 ns，也就是說(shuō)，直流分量和一次諧波分量間隔約為100 ns。從示波器上可以看出，橫坐標單元格間隔為100 ns，直流分量和一次諧波分量間隔約為100 ns，和理論分析結果一致。

四、結論
　　本文以高組合數混合基DFT算法為基礎，設計并用FPGA實(shí)現了變換點(diǎn)數可靈活擴展的流水線(xiàn)FFT處理器。輸入/輸出數據速率為20 MHz時(shí)，讀/寫(xiě)RAM工作在40 MHz時(shí)鐘，計算出1 024點(diǎn)FFT的運算時(shí)間約為52μs。本設計采用模塊化設計結構，便于系統調試和實(shí)現，而且各設計模塊可以重復利用，避免重復相同的設計，從而縮短芯片設計開(kāi)發(fā)時(shí)間，更易于FFT處理器的結構擴展。整個(gè)FFT設計結構新穎，實(shí)現容易，具有一定實(shí)用價(jià)值。

參考文獻

［1］程佩清.數字信號處理教程［M］.北京：清華大學(xué)出版社，2001.
［2］侯伯亨，顧新.VHDL硬件描述語(yǔ)言與數字邏輯電路設計［M］.西安：西安電子科技大學(xué)出版，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位浮點(diǎn)FFT處理器的設計［J］.電訊技術(shù)，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實(shí)現高速FFT處理器的設計［Ｊ］.電訊技術(shù)，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.