還不了解fft原理?帶你三分鐘搞定fft原理

最近很多朋友問小編關(guān)于fft原理，所以為增加大家對fft的認(rèn)識，本文將對fft原理加以講解。如果你對fft原理具有興趣抑或正在接觸fft原理，都可以參閱本文哦。此外，本文還將對基于FPGA的fft算法的硬件實(shí)現(xiàn)予以講解，和小編一起來了解下吧。

一、簡介

快速傅里葉變換(FFT)作為計算和分析工具，在眾多學(xué)科領(lǐng)域(如信號處理、圖像處理、生物信息學(xué)、計算物理、應(yīng)用數(shù)學(xué)等)有著廣泛的應(yīng)用。在高速數(shù)字信號處理領(lǐng)域，如雷達(dá)信號處理，F(xiàn)FT的處理速度往往是整個系統(tǒng)設(shè)計性能的關(guān)鍵所在。

針對高速實(shí)時信號處理的要求，軟件實(shí)現(xiàn)方法顯然滿足不了其需要。近年來現(xiàn)場可編程門陣列(FPGA)以其高性能、高靈活性、友好的開發(fā)環(huán)境、在線可編程等特點(diǎn)，使得基于FPGA的設(shè)計可以滿足實(shí)時數(shù)字信號處理的要求，在市場競爭中具有很大的優(yōu)勢。

在FFT算法中，數(shù)據(jù)的寬度通常都是固定的寬度。然而，在FFT的運(yùn)算過程中，特別是乘法運(yùn)算中，運(yùn)算的結(jié)果將不可避免地帶來誤差。因此，為了保證結(jié)果的準(zhǔn)確性，采用定點(diǎn)分析是非常必要的。

二、FFT算法原理

FFT算法的基本思想就是利用權(quán)函數(shù)的周期性、對稱性、特殊性及周期N的可互換性，將較長序列的DFT運(yùn)算逐次分解為較短序列的DFT運(yùn)算。針對N=2的整數(shù)次冪，F(xiàn)FT算法有基-2算法、基-4算法、實(shí)因子算法和分裂基算法等。這里，從處理速度和占用資源的角度考慮，選用基-4按時間抽取FFT算法 (DIT)。對于N=4γ，基-4 DIT具有l(wèi)og4N=γ次迭代運(yùn)算，每次迭代包含N/4個蝶形單元。蝶形單元的運(yùn)算表達(dá)式為：

其信號流如圖1。式中：A，B，C，D和A′，B′，C′，D′均為復(fù)數(shù)據(jù);W=e-j2π/N。進(jìn)行1次蝶形運(yùn)算共需3次復(fù)乘和8次復(fù)加運(yùn)算。N=64 點(diǎn)的基-4DIT信號流其輸入數(shù)據(jù)序列是按自然順序排列的，輸出結(jié)果需經(jīng)過整序。64點(diǎn)數(shù)據(jù)只需進(jìn)行3次迭代運(yùn)算，每次迭代運(yùn)算含有N/4=16個蝶形單元。

三、FFT算法的硬件實(shí)現(xiàn)

3.1 流水線方式FFT算法的實(shí)現(xiàn)

為了提高FFT工作頻率和節(jié)省FPGA資源，采用3級流水線結(jié)構(gòu)實(shí)現(xiàn)64點(diǎn)的FFT運(yùn)算。流水線處理器的結(jié)構(gòu)如圖2所示。

每級均由延時單元、轉(zhuǎn)接器(SW)、蝶形運(yùn)算和旋轉(zhuǎn)因子乘法4個模塊組成，延時節(jié)拍由方框中的數(shù)字表示。各級轉(zhuǎn)接器和延時單元起到對序列進(jìn)行碼位抽取并將數(shù)據(jù)拉齊的作用。每級延時在FPGA內(nèi)部用FIFO實(shí)現(xiàn)，不需要對序列進(jìn)行尋址即可實(shí)現(xiàn)延時功能。數(shù)據(jù)串行輸入，經(jīng)過3級流水處理后，串行輸出。

轉(zhuǎn)接器有一定的工作規(guī)律。例如，當(dāng)?shù)?級變換做完進(jìn)入轉(zhuǎn)接器SW1前，先對后三路數(shù)據(jù)進(jìn)行一定節(jié)拍的延時，延遲節(jié)拍分別為4，8，12。為了說明規(guī)律，把輸入轉(zhuǎn)接器的四路數(shù)據(jù)按照前后次序進(jìn)行分組，每4個時鐘節(jié)拍為1組，共16組，如圖3(左)所示。在數(shù)據(jù)流串行經(jīng)過轉(zhuǎn)接器SW1時，第0組中的數(shù)據(jù)保持不變，第1組中的數(shù)據(jù)與第4組中的數(shù)據(jù)交換;5不變，2和8交換，3和12交換，6和9交換;10不變，7和13交換，11和14交換，15不變。交換完畢后，前三路數(shù)據(jù)經(jīng)過延遲節(jié)拍分別為12，8，4的FIFO存儲器輸出，位置關(guān)系如圖3所示。

上述轉(zhuǎn)換規(guī)律對于SW2也是適用的，只是轉(zhuǎn)接器前后的延時節(jié)拍和分組的大小有所不同。

3.2 存儲單元

為了實(shí)現(xiàn)算法的流水線設(shè)計，存儲器RAM設(shè)計為64×16 b的雙端口RAM，即在時鐘信號和寫控制信號同時為低電平時，從輸入總線寫入RAM;在時鐘信號和讀控制信號同時為高電平時，從RAM輸出數(shù)據(jù)。

ROM為17×16 b的ROM，儲存經(jīng)過量化后的旋轉(zhuǎn)因子，旋轉(zhuǎn)因子為正弦函數(shù)和余弦函數(shù)的組合。根據(jù)旋轉(zhuǎn)因子的對稱性和周期性，在利用ROM存儲旋轉(zhuǎn)因子時，可以只存儲旋轉(zhuǎn)因子的一部分。

3.3 運(yùn)算結(jié)構(gòu)

Radix-4蝶形運(yùn)算單元是整個FFT處理器中的核心部件。在用Radix-4運(yùn)算器計算時需要并行輸入數(shù)據(jù)，如果能以并發(fā)數(shù)據(jù)輸入的話，則同步性和控制度較好，但實(shí)際上常要進(jìn)行串并之間的轉(zhuǎn)換。存儲RAM按單節(jié)拍輸出16 b位寬數(shù)據(jù)，選擇器不停旋轉(zhuǎn)送入到確定的位置，每4點(diǎn)全部到位后R-4使能有效;然后4個時鐘節(jié)拍得到有效結(jié)果數(shù)據(jù)，再通過選擇器旋轉(zhuǎn)送入到對應(yīng)存儲 RAM中。

復(fù)數(shù)運(yùn)算中，對應(yīng)復(fù)數(shù)的實(shí)部和虛部RAM用同一個地址發(fā)生器。地址發(fā)生器在進(jìn)行RAM地址發(fā)生時采用兩套地址，第一套是計數(shù)器按時鐘節(jié)拍順序產(chǎn)生的，用于輸入數(shù)據(jù)的存儲;第二套是由數(shù)據(jù)寬度為16 b的ROM產(chǎn)生的，ROM中存放的數(shù)據(jù)為下級運(yùn)算所需倒序的序列地址，發(fā)生地址給RAM，然后RAM按倒序地址輸出下級需要進(jìn)行運(yùn)算的數(shù)據(jù)。

3.4 塊浮點(diǎn)結(jié)構(gòu)

數(shù)字信號處理系統(tǒng)可分為定點(diǎn)制、浮點(diǎn)制和塊浮點(diǎn)制，它們在實(shí)現(xiàn)時對系統(tǒng)資源的要求不同，工作速度也不同，有著不同的適用范圍。定點(diǎn)制算法簡單，速度快，但動態(tài)范圍有限，需要用合適的溢出控制規(guī)則(如定比例法)適當(dāng)壓縮輸入信號的動態(tài)范圍。浮點(diǎn)表示法動態(tài)范圍大，可避免溢出，但系統(tǒng)實(shí)現(xiàn)復(fù)雜，硬件需求量大，速度慢。

為了提高精度，并減少復(fù)雜度和存儲量，采用塊浮點(diǎn)結(jié)構(gòu)。塊浮點(diǎn)算法是以上兩種表示法的結(jié)合。這種表示方法是，一組數(shù)共用同一個階碼，這個階碼是這組數(shù)中最大數(shù)的階碼。塊浮點(diǎn)算法無需進(jìn)行額外的指數(shù)運(yùn)算，僅對尾數(shù)進(jìn)行運(yùn)算即可，其與定點(diǎn)運(yùn)算一樣方便，但需要在每級運(yùn)算結(jié)束后進(jìn)行本級運(yùn)算溢出最大位數(shù)判斷，以對數(shù)據(jù)塊進(jìn)行塊指數(shù)調(diào)整。在調(diào)整時僅保留一位符號位，因而能夠充分利用有限位長。這樣處理比定點(diǎn)方法擴(kuò)大了動態(tài)范圍，并且提高了精度，比浮點(diǎn)運(yùn)算在速度上有了提高。塊浮點(diǎn)結(jié)構(gòu)如圖4所示。

以上便是此次小編帶來的“fft原理”相關(guān)內(nèi)容，通過本文，希望大家對FFT算法原理和硬件實(shí)現(xiàn)具備一定的認(rèn)知。如果你喜歡本文，不妨持續(xù)關(guān)注我們網(wǎng)站哦，小編將于后期帶來更多精彩內(nèi)容。最后，十分感謝大家的閱讀，have a nice day!