基于FPGA的FFT處理器設計

　　1 引言

　　隨著(zhù)數字技術(shù)的快速發(fā)展，數字信號處理已深入到條個(gè)領(lǐng)域。在數字信號處理中，許多算法如相關(guān)、濾波、譜估計、卷積等都可通過(guò)轉化為離散傅立葉變換(DFT)實(shí)現，從而為離散信號分析從理論上提供了變換工具。但DFT計算量大，實(shí)現困難?？焖俑盗⑷~(FFT)的提出，大大減少了計算量，從根本上改變了傅立葉變換的地位，成為數字信號處理中的核心技術(shù)之一，廣泛應用于雷達、觀(guān)測、跟蹤、高速圖像處理、保密無(wú)線(xiàn)通信和數字通信等領(lǐng)域。

　　目前，硬件實(shí)現FFT算法的方案主要有：通用數字信號處理器(DSP)、FFT專(zhuān)用器件和現場(chǎng)可編程門(mén)陣列(FPCA)。DSP具有純軟件實(shí)現的靈活性，適用于流程復雜的算法，如通信系統中信道的編譯碼、QAM映射等算法。DSP完成FFT運算需占用大量DSP的運算時(shí)間，使整個(gè)系統的數據吞吐率降低，同時(shí)也無(wú)法發(fā)揮DSP軟件實(shí)現的靈活性。采用FFT專(zhuān)用器件，速度雖能夠達到要求，但其外圍電路復雜，可擴展性差，成本昂貴。隨著(zhù)FPGA發(fā)展，其資源豐富，易于組織流水和并行結構，將FFT實(shí)時(shí)性要求與FPGA器件設計的靈活性相結合，實(shí)現并行算法與硬件結構的優(yōu)化配置，不僅可以提高處理速度，并且具有靈活性高，開(kāi)發(fā)費用低、開(kāi)發(fā)周期短、升級簡(jiǎn)單的特點(diǎn)。針對某OFDM系統中FFT運算的實(shí)際需要，提出了基于FPGA的設計來(lái)實(shí)現FFT算法，并以16位長(cháng)數據，64點(diǎn)FFT為例，在QuartusⅡ軟件上通過(guò)綜合和仿真。

　　2 FFT原理及算法結構

　　FFT是離散傅立葉變換(DFT)的快速算法。對于N點(diǎn)離散的有限長(cháng)時(shí)間序列x(n)，其傅里葉變換為：

　　完成N點(diǎn)的DFT需要N2次復數乘法和N(N-1)次復數加法。點(diǎn)數大時(shí)，計算量也大，所以難以實(shí)現信號的實(shí)時(shí)處理。FFT的基本思想是利用旋轉因子WN的周期性、對稱(chēng)性、特殊性以及劇期N的可互換性，將長(cháng)度為N點(diǎn)的序列DFT運算逐次分為較短序列的DFT運算，合并相同項，大大減少了計算量。

　　FFT法分為兩大類(lèi)：一類(lèi)是針對N=2的整數次冪的算法，如基2算法、基4算法、實(shí)因子算法和分裂算法等；另一類(lèi)足N≠2的整數次冪算法，以winograd為代表的一類(lèi)算法。硬件實(shí)現時(shí)，不僅要考慮算法運算量的大小，而且要考慮算法的復雜性和模塊化?？刂坪?jiǎn)單、實(shí)現規整的算法在硬件系統中要優(yōu)于僅降低運算量的算法?，F有FFT算法的FPGA設計方案基本上都是針對于第一類(lèi)算法，而第二類(lèi)算法盡管有其重要的理論價(jià)值，但硬件不易實(shí)現。由于該設計點(diǎn)數不是太多，綜合考慮FFT處理器的面積和成本，所以采用按時(shí)間抽取的基2快速傅立葉算法(基2DIT-FFT)。

　　對于長(cháng)度為N=2m的序列x(n)，其中m是整數，將x(n)按奇偶分成兩組，即令：n=2r和n=2r+1，而r=0，1，…，N／2-1，于是：

　　所以A(k)和B(k)可完整表示X(k)。依次類(lèi)推，可一直向前追溯到2點(diǎn)的FFT，這樣整個(gè)N點(diǎn)的FFT算法分解成logN2級運算，每級有N／2個(gè)基2碟形運算。圖1是N=8的DIT-FFT運算流圖。

　　3 FFT處理器的結構設計

　　FFT實(shí)現的設計方案有順序處理、級聯(lián)處理、并行處理和陣列處理。順序處理每次運算僅用一個(gè)蝶形單元，處理方式簡(jiǎn)單，運算速度較慢。級聯(lián)處理、并行處理和陣列處理的速度較快，但占用資源較多?？紤]到該設計運算點(diǎn)數較少，因此采用改進(jìn)的順序處理方案，在原有順序處理的基礎上對FFT處理過(guò)程中數據傳輸進(jìn)行控制，使得該結構在繼承原有順序處理電路簡(jiǎn)單、占用資源較少優(yōu)點(diǎn)同時(shí)又兼有級聯(lián)處理運算速度較快的優(yōu)點(diǎn)。采用自頂向下的方法對處理器模塊化，其結構框圖如圖2所示。

　　4 模塊設計與綜合仿真

　　整個(gè)FFT處理器是由存儲器、蝶形運算單元、旋轉因子單元、控制單元和數據控制單元紺成，各個(gè)單元通過(guò)控制單元產(chǎn)生的控制和使能信號進(jìn)行工作。

　　4.1 蝶形運算單元

　　蝶形運算單元是整個(gè)FFT處理單元的重要部分，直接影響整個(gè)FFT單元性能?；?時(shí)間抽取的蝶形信號流程圖如圖3所示，p和q為數據序號，xm(p)和xm(q)是第m級蝶形運算的輸入，xm+1(p)和xm+1(q)是該蝶形運算的輸出，W′N為相應的旋轉因子。

　　由上式看出，一個(gè)基2蝶形運算要進(jìn)行1次復乘、2次復加。為了提高運算速度采用并行運算，采用4個(gè)實(shí)數乘法器、3個(gè)實(shí)數加法器和3個(gè)實(shí)數減法器組成。設輸入數據：x1=x1_r+jx1_im，x2=x2_r+jx2_im，旋轉因子為W′N=c-jd，則輸出y1=y1_r+jy1_im和y2=y2_r+jy2_im。實(shí)現蝶型運算單元如圖4所示。

　　數據格式選擇定點(diǎn)16位二進(jìn)制補碼。設計時(shí)必須考慮乘法器速度，將會(huì )直接影響整個(gè)FFT處理單元的運算速度，該設計的乘法器利用Quartus II開(kāi)發(fā)軟件中所提供的宏單元生成。乘法器的兩輸入均為16位，輸出32位。因為乘法器中帶有旋轉因子項，所以乘法運算后不應改變輸入的幅值即乘法器的輸出仍為16位，因此要對輸出數據進(jìn)行截取，截取其中16位作為加(減)法器的輸入。

　　4.2 存儲單元

　　在FFT處理單元中存儲器是必不可少的單元，蝶形運算數據的輸入輸出和中間結果的存儲都要經(jīng)過(guò)存儲器，因此它們的頻繁讀寫(xiě)操作對整個(gè)FFT處理速度影響較大。圖2中存儲器A和存儲器B由RAM和狀態(tài)機組成，各自分別具有數據總線(xiàn)、地址總線(xiàn)和觸發(fā)時(shí)鐘。存儲器A接收外部輸入數據，存儲器B是中間結果單元，除第一級蝶形運算外每級數據的輸入輸出均經(jīng)過(guò)該存儲器。在兩塊存儲器和蝶形運算模塊之間加入兩個(gè)數據控制器配合工作，可以在寫(xiě)入上一組中間結果的同時(shí)讀取下一組蝶形運算數據，從而提高FFT的處理速度。

　　4.3 旋轉因子單元

　　旋轉因子單元是用于存儲FFT運算所需的旋轉因子W′N=exp(-j2πr／N)。在Matlab中旋轉因子分為實(shí)部和虛部產(chǎn)生，由于它們是小于1的小數，故在設計中需將其定點(diǎn)化。其過(guò)程是將旋轉因子擴大214倍，取整數部分轉化為16位定點(diǎn)數，以.hex文件格式保存，利用QuartusⅡ軟件的Megawizard工具設計ROM，并將.hex文件同化在其中。根據旋轉因子的對稱(chēng)性和周期性，在利用ROM存儲旋轉因子時(shí)，可以只存儲旋轉因子表的一部分，通過(guò)地址的改變查詢(xún)出每級蝶形運算所需的旋轉因子。

　　4.4 控制單元

　　控制單元用于協(xié)調驅動(dòng)各模塊，在FFT運算中具有關(guān)鍵作用。存儲器A、旋轉因子單元及數據控制器的讀信號，存儲器B的讀寫(xiě)信號都是由控制單元產(chǎn)生?？刂茊卧ㄟ^(guò)一個(gè)有限狀態(tài)機(FSM)實(shí)現，使用兩個(gè)內部計數器控制狀態(tài)機的翻轉?？刂茊卧哂袉为毜妮斎霑r(shí)鐘，可產(chǎn)生相應的控制信號。

　　4.5 綜合仿真

　　選用Altera公司的QuartusⅡ軟件作為開(kāi)發(fā)平臺，以Stratix系列中的EPlS25型FPGA為核心器件，采用自頂向下的設計思路和VHDL語(yǔ)言，實(shí)現對各個(gè)模塊單元的設計、綜合和仿真。為了簡(jiǎn)化設計，只在數據輸入時(shí)鐘下輸入了一組64個(gè)復數，其余輸入設為0，并且實(shí)部和虛部都限定在±1，±2，±3，±4，±5之內。為防止溢出先將輸入數據乘以一定比例因子2-9，再乘以215轉化為十六進(jìn)制數。輸出的結果如圖5所示。需要注意的是：仿真結果乘以2-6后才是實(shí)際結果。將仿真結果與Matlab計算的結果相比較，數據基本一致，說(shuō)明了設計正確，其誤差主要來(lái)源于數據的截取和旋轉因子的近似。

　    5 結束語(yǔ)

　　FFT算法是數字信號處理中一種重要運算，廣泛應用于雷達、觀(guān)測、跟蹤、高速圖像處理、保密無(wú)線(xiàn)通信和數字通信等領(lǐng)域。這里討論了一種基于FPGA的64點(diǎn)FFT處理器的設計方案，輸入數據的實(shí)部和虛部均以16位二進(jìn)制數表示，采用基2DIT-FFT算法，以Altera公司的QuartusⅡ軟件為開(kāi)發(fā)平臺對處理器各個(gè)的模塊進(jìn)行設計，在Stratix系列中的EPlS25型FPGA通過(guò)了綜合和仿真，運算結果正確。采用FPGA實(shí)現FFT算法在體積、速度、靈活性等方面都具有優(yōu)越性。