0 引 言
DFT作為DSP領(lǐng)域中時域和頻域轉(zhuǎn)換的基本運(yùn)算，存在運(yùn)算量太大的缺點(diǎn)，導(dǎo)致其應(yīng)用受到局限。 DFT快速算法FFT的提出，簡化了DFT的運(yùn)算過程，使其在實時信號處理領(lǐng)域中得到廣泛應(yīng)用。FFT實現(xiàn)的方法包括軟件實現(xiàn)和硬件實現(xiàn)兩種。采用軟件實現(xiàn)FFT的方法存在計算慢，實現(xiàn)過程復(fù)雜等缺點(diǎn)，所以目前比較流行的方式是采用硬件實現(xiàn)FFT。硬件實現(xiàn)的具體方法可以分為ASIC方法、FPGA方法、 DSP方法和通用處理機(jī)方法等。
FPGA是20世紀(jì)80年代中期出現(xiàn)的一種新的電子設(shè)計自動化技術(shù)，具有集成度高，邏輯實現(xiàn)能力強(qiáng)，設(shè)計靈活等優(yōu)勢。在FPGA上實現(xiàn)數(shù)字信號處理，即用純數(shù)字邏輯進(jìn)行DSP模塊設(shè)計，為高速數(shù)字信號處理算法提供了實現(xiàn)途徑。在此，采用FPGA方法設(shè)計64點(diǎn)FFT處理器。
現(xiàn)有的FFT模塊可以對多點(diǎn)數(shù)據(jù)進(jìn)行運(yùn)算，但是存在運(yùn)算周期長。結(jié)構(gòu)復(fù)雜，硬件資源耗費(fèi)大等缺陷。采用64點(diǎn)FFT可以通過優(yōu)化結(jié)構(gòu)來快速處理多點(diǎn)數(shù)數(shù)據(jù)。目前設(shè)計的64點(diǎn)FFT處理器主要采用以專用處理單元取代常規(guī)FFT處理單元的方法，或者按照固定幾何結(jié)構(gòu)設(shè)計FFT處理器的方法。這里所介紹的64 點(diǎn)FFT處理器是在固定幾何結(jié)構(gòu)設(shè)計方法的基礎(chǔ)上加以改進(jìn)，將輸入的64點(diǎn)數(shù)據(jù)均勻分成8組，并行輸入給FFT運(yùn)算單元，進(jìn)行FFT運(yùn)算。通過對蝶形運(yùn)算單元進(jìn)行優(yōu)化設(shè)計，所設(shè)計的64點(diǎn)FFT處理器模塊較之以往的FFT模塊，節(jié)省了硬件資源，提高了運(yùn)算效率。通過ModelSim仿真實驗證明，在外部工作時鐘頻率為40 MHz下，對隨機(jī)生成的序列進(jìn)行64點(diǎn)FFT運(yùn)算處理，運(yùn)算時間為10μs，縮短了現(xiàn)有FFT模塊的運(yùn)算時間。

1 按頻率抽取的基――4FFT算法原理
對于序列長度為N(N為2的整數(shù)次冪)的FFT算法主要有基-2 FFT和基-4 FFT兩種。計算一次基-2FFT需要二次復(fù)乘和兩次復(fù)加；計算一次基-4 FFT需要三次復(fù)乘和八次復(fù)加。從運(yùn)算次數(shù)上看，基-2 FFT較為簡單，但是因為基-2 FFT的復(fù)數(shù)運(yùn)算較為復(fù)雜，所以在硬件實現(xiàn)上反而要比基-4 FFT占用的資源更多。為了滿足對數(shù)據(jù)高速處理的要求，在此選擇在FP-GA上實現(xiàn)基-4 FFT的算法。
根據(jù)定義，對于長度為N的序列x(N)(0≤N≤N-1)，它的DFT可表示為：

式中：WnkN=e-J2π/Nnk稱為旋轉(zhuǎn)因子。直接計算DFT，需要的計算量為N2次復(fù)乘和N(N-1)次復(fù)加。當(dāng)N很大時，運(yùn)算量相當(dāng)大，無法滿足實時處理的要求。因此利用旋轉(zhuǎn)因子的對稱性、周期性和可約性，把長序列分解成為短序列來進(jìn)行快速傅里葉變換。
由式(1)可以得到4個子序列：

利用旋轉(zhuǎn)因子WnkN的特性，如：將A，B，C，D作為復(fù)數(shù)操作數(shù)進(jìn)行運(yùn)算，由式(2)可得簡化計算式：

式(3)就是在FPGA上實現(xiàn)基-4 FFT算法的基本運(yùn)算法則。