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

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

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

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

  
    式(3)就是在FPGA上實(shí)現(xiàn)基-4 FFT算法的基本運(yùn)算法則。
    不同于以往的基-4 FFT算法，這里是將輸入的64點(diǎn)數(shù)據(jù)以8位輸入數(shù)據(jù)為一組，共分成8組的方式輸入給FFT運(yùn)算單元進(jìn)行FFT運(yùn)算的。完整的FFT蝶形運(yùn)算共分6級(jí)，經(jīng)歷196個(gè)循環(huán)狀態(tài)。將來(lái)自存儲(chǔ)單元的數(shù)據(jù)輸入到FFT運(yùn)算單元中，前三級(jí)是按8位1組的方法，分為8組進(jìn)行運(yùn)算；后三級(jí)是將前三級(jí)運(yùn)算所得到的中間數(shù)據(jù)送入運(yùn)算單元進(jìn)行運(yùn)算。經(jīng)過(guò)FFT運(yùn)算后，將所得到運(yùn)算結(jié)果寫(xiě)入存儲(chǔ)單元中保存。結(jié)果以倒位序方式輸出，需要經(jīng)過(guò)調(diào)整位序變換成為自然順序輸出。

2 FFT運(yùn)算器設(shè)計(jì)
2．1 系統(tǒng)的整體結(jié)構(gòu)
    一個(gè)完整的FFT運(yùn)算單元應(yīng)該包括以下幾個(gè)組成部分：
    全局控制單元包括控制器和地址產(chǎn)生單元，用于調(diào)控整個(gè)FFT運(yùn)算系統(tǒng)，生成蝶形運(yùn)算單元以及其他子單元所需的地址，控制各子單元時(shí)序，保證其正常有序地工作；
    蝶形運(yùn)算器單元 由蝶形運(yùn)算器和旋轉(zhuǎn)因子存儲(chǔ)單元(ROM)組成，負(fù)責(zé)將送入的輸人數(shù)據(jù)進(jìn)行蝶形運(yùn)算，是FFT運(yùn)算器的核心單元；
    存儲(chǔ)寄存器單元 采用兩個(gè)RAM乒乓通信，通過(guò)通信接口單元接收總線控制信號(hào)，負(fù)責(zé)存儲(chǔ)輸入數(shù)據(jù)、中間數(shù)據(jù)和運(yùn)算所得最終結(jié)果。
    系統(tǒng)整體框圖如圖1所示。

3 實(shí)驗(yàn)結(jié)果驗(yàn)證
    這里的FFT運(yùn)算器通過(guò)硬件描述語(yǔ)言VHDL代碼進(jìn)行編寫(xiě)，在ModelSimSE PLUS 6．1f環(huán)境下完成系統(tǒng)仿真，波形仿真如圖3所示。
    由波形仿真圖可以看出，地址控制單元以3位二進(jìn)制編碼定義各子單元的地址，存儲(chǔ)的數(shù)據(jù)在時(shí)序信號(hào)和地址總線單元控制下進(jìn)行FFT運(yùn)算。實(shí)驗(yàn)證明，當(dāng)外部時(shí)鐘頻率為40 MHz時(shí)，可以對(duì)隨機(jī)生成的64點(diǎn)序列進(jìn)行FFT定點(diǎn)運(yùn)算，運(yùn)算時(shí)間為10μs。

4 結(jié) 語(yǔ)
    這里的FFT運(yùn)算器采用定點(diǎn)數(shù)處理，當(dāng)處理浮點(diǎn)數(shù)時(shí)，系統(tǒng)存在處理異常、數(shù)據(jù)溢出等問(wèn)題。但是由于可以迅速處理多點(diǎn)數(shù)信號(hào)，因此在數(shù)字圖像處理、實(shí)時(shí)通信系統(tǒng)的調(diào)試和解調(diào)等方面具有一定的實(shí)際意義，達(dá)到了使用FPGA實(shí)現(xiàn)DSP算法的目的。
    本文在以下方面有所創(chuàng)新：
    (1)輸入的64位數(shù)據(jù)以8位共8組的方式并行輸入，將FFT運(yùn)算流程分為6級(jí)，整個(gè)FFT運(yùn)算過(guò)程清晰，結(jié)構(gòu)合理，提高了運(yùn)行效率。
    (2)使用2塊雙口RAM作為存儲(chǔ)器，采用“乒乓操作”，在一個(gè)時(shí)鐘周期內(nèi)保證數(shù)據(jù)傳遞的單向性，減少了數(shù)據(jù)傳輸?shù)娜哂?，提高了精度?br />    (3)將整個(gè)FFT運(yùn)算器進(jìn)行模塊化設(shè)計(jì)，在控制模塊的調(diào)配下，各個(gè)子模塊準(zhǔn)確工作，保證了運(yùn)算的可靠性。