采用FPGA實(shí)現(xiàn)FFT算法

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

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

2 FFT原理及算法結(jié)構(gòu)

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

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

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

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

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

3 FFT處理器的結(jié)構(gòu)設(shè)計(jì)

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

4 模塊設(shè)計(jì)與綜合仿真

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

4.1 蝶形運(yùn)算單元

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

采用FPGA實(shí)現(xiàn)FFT算法

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

數(shù)據(jù)格式選擇定點(diǎn)16位二進(jìn)制補(bǔ)碼。設(shè)計(jì)時(shí)必須考慮乘法器速度，將會(huì)直接影響整個(gè)FFT處理單元的運(yùn)算速度,該設(shè)計(jì)的乘法器利用QuartusⅡ開發(fā)軟件中所提供的宏單元生成。乘法器的兩輸入均為16位，輸出32位。因?yàn)槌朔ㄆ髦袔в行D(zhuǎn)因子項(xiàng).所以乘法運(yùn)算后不應(yīng)改變輸入的幅值即乘法器的輸出仍為16位，因此要對(duì)輸出數(shù)據(jù)進(jìn)行截取，截取其中16位作為加(減)法器的輸入。

4.2 存儲(chǔ)單元

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

4.3 旋轉(zhuǎn)因子單元

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

4.4 控制單元

控制單元用于協(xié)調(diào)驅(qū)動(dòng)各模塊，在FFT運(yùn)算中具有關(guān)鍵作用。存儲(chǔ)器A、旋轉(zhuǎn)因子單元及數(shù)據(jù)控制器的讀信號(hào)，存儲(chǔ)器B的讀寫信號(hào)都是由控制單元產(chǎn)生。控制單元通過(guò)一個(gè)有限狀態(tài)機(jī)(FSM)實(shí)現(xiàn)，使用兩個(gè)內(nèi)部計(jì)數(shù)器控制狀態(tài)機(jī)的翻轉(zhuǎn)。控制單元具有單獨(dú)的輸入時(shí)鐘，可產(chǎn)生相應(yīng)的控制信號(hào)。

4.5 綜合仿真

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

5 結(jié)束語(yǔ)

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