基于FPGA的FFT算法硬件實(shí)現

FFT(快速傅里葉變換)是一種非常重要的算法，在信號處理、圖像處理、生物信息學(xué)、計算物理、應用數學(xué)等方面都有著(zhù)廣泛的應用。在高速數字信號處理中，FFT的處理速度往往是整個(gè)系統設計性能的關(guān)鍵所在。FPGA(現場(chǎng)可編程門(mén)陣列)是一種具有大規?？删幊涕T(mén)陣列的器件，不僅具有ASIC(專(zhuān)用集成電路)快速的特點(diǎn)，更具有很好的系統實(shí)現的靈活性?；?a class="contentlabel" href="http://dyxdggzs.com/news/listbylabel/label/FPGA">FPGA的設計可以滿(mǎn)足實(shí)時(shí)數字信號處理的要求，在市
場(chǎng)競爭中具有很大的優(yōu)勢。因此，FPGA為高速FFT算法的實(shí)現提供了一個(gè)很好的平臺。

1 FFT算法的硬件實(shí)現
1．1 系統框圖
本設計利用流水線(xiàn)技術(shù)來(lái)提高系統的性能，系統框圖，如圖1所示。其中，地址產(chǎn)生單元生成RAM讀寫(xiě)地址，寫(xiě)使能信號以及相關(guān)模塊的啟動(dòng)、控制信號，是系統的控制核心；4點(diǎn)蝶形運算單元的最后一級輸出不是順序的；旋轉因子產(chǎn)生單元生成復乘運算中的旋轉因子的角度數據；旋轉因子ROM中預置了每一級運算中所需的旋轉因子。

在FPGA設計中，為提高系統的運行速度，而將指令分為幾個(gè)子操作，每個(gè)子操作由不同的單元完成，這樣，每一級的電路結構得到簡(jiǎn)化，從而減少輸入到輸出間的電路延時(shí)，在較小的時(shí)鐘周期內就能夠完成這一級的電路功能。在下一個(gè)時(shí)鐘周期到來(lái)時(shí)，將前一級的結果鎖存為該級電路的輸入，這樣逐級鎖存，由最后一級完成最終結果的輸出。也就是說(shuō)，流水線(xiàn)技術(shù)是將待處理的任務(wù)分解為相互有關(guān)而又相互
獨立、可以順序執行的子任務(wù)來(lái)逐步實(shí)現。本設計中，4點(diǎn)蝶形運算單元、旋轉因子復乘模塊以及最后的精度截取模塊采用流水線(xiàn)技術(shù)來(lái)處理。
1．2 基4蝶形運算算法原理

式(1)為基4蝶形運算單元的一般表達式，其中，，N為FFT運算的點(diǎn)數，本設計中為1 024，p為旋轉因子W的相位角，其規律將在1.4節討論。X(0)、X(1)、X(2)、X(3)為原始數據，順序輸入RAM后蝶形倒序輸出，與旋轉因子復乘再進(jìn)行4點(diǎn)蝶形運算，而X1(0)、X1(1)、X1(2)、X1(3)即為第1級蝶形運算的結果。此時(shí)RAM存儲的原始數據已經(jīng)清空，將第1級蝶形運算結果再存回RAM中，按照一定的地址輸出后，與第2級的旋轉因子復乘、4點(diǎn)蝶形運算，得到第2級蝶形運算結果，依此類(lèi)推。由于蝶形運算為同址操作，所以第2級的RAM寫(xiě)地址即為第一級的RAM讀地址，每一級的RAM讀地址規律將在1．3節中討論。
1024點(diǎn)的基4-FFT共需要5級蝶形運算，每級需要計算256個(gè)蝶形，其傳統實(shí)現框圖如圖2所示。

考慮到第一級蝶形運算不需要旋轉因子，所以第一級的旋轉因子復乘模塊可以省略，但本設計的硬件結構需要循環(huán)利用，一般情況下，可以對第一級數據進(jìn)行×1運算，再進(jìn)行4點(diǎn)蝶形運算。不過(guò)，考慮到我們并不關(guān)心每一級蝶形運算后的結果，本文提出了一種蝶形運算的新結構：即先進(jìn)行前一級的4點(diǎn)蝶形運算，再進(jìn)行本級的與旋轉因子復乘運算，如圖3所示。