DIT-FFT算法的基本原理
有限長序列x_n的N點(diǎn)DFT定義為：X(k)=∑_(n=0)^(N-1)?〖x(n) W_N^Kn 〗,式中W_N=e^(-j 2π/N)。
DFT在實(shí)際應(yīng)用中很重要，但是如果直接按DFT變換進(jìn)行計(jì)算，當(dāng)序列長度N很大時(shí)，計(jì)算量會非常大，所需時(shí)間也很長，因此常用的是DFT的一種快速計(jì)算算法，簡稱FFT。
最常用的FFT算法是基于時(shí)間抽取的基2-FFT算法和基于頻率抽取的基2-FFT算法，這種算法的特點(diǎn)在于FFT會把一次大的DFT分割成幾個(gè)小的DFT，這樣遞歸式地細(xì)分下去，例如有8個(gè)采樣點(diǎn)的FFT，首先會把最外層的8點(diǎn)運(yùn)算分成兩個(gè)4點(diǎn)FFT的奇偶組合，第二層FFT又分成四個(gè)兩點(diǎn)FFT的奇偶組合，并且由此計(jì)算出的頻譜中很有趣的一點(diǎn)在于對于實(shí)數(shù)輸出的數(shù)組，后面一半和前面一半正好對稱相同，對于虛數(shù)輸出的數(shù)組，后面一半是前面數(shù)組對稱后乘上負(fù)1，因此，我們只需要算出FFT的一半即可求出全部。
本設(shè)計(jì)討論的是基于至簡設(shè)計(jì)法實(shí)現(xiàn)按時(shí)間抽選的基2-FFT算法（即DIF-FFT）實(shí)現(xiàn)過程，支持N由8到1024。 2、?蝶形運(yùn)算至簡實(shí)現(xiàn)過程  本模塊包括三個(gè)RAM模塊（RAM1，RAM2，RAM3）與一個(gè)DFT模塊，各模塊功能如下：
RAM1模塊：在開始進(jìn)行蝶形運(yùn)算前，全部采樣點(diǎn)（如圖1所示的x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)）已經(jīng)按照倒位序二進(jìn)制的地址依次存儲在RAM1模塊中，即地址0保存了采樣點(diǎn)x(0)，地址1保存了采樣點(diǎn)x(4)。選用雙端口RAM1可以同時(shí)對兩點(diǎn)采樣數(shù)據(jù)(如圖1的x（0）、x(4))進(jìn)行讀、寫操作。
RAM2模塊：RAM2模塊也是采用雙端口輸入輸出，可同時(shí)對兩點(diǎn)數(shù)據(jù)進(jìn)行讀、寫操作。
DFT模塊：DFT模塊用于對RAM1、RAM2輸出的兩點(diǎn)采樣數(shù)據(jù)（如圖1的x（0）、x(4)）進(jìn)行蝶形運(yùn)算，它將運(yùn)算結(jié)果輸出至RAM1、RAM2模塊進(jìn)行保存。
RAM3模塊：RAM3模塊是單輸出模塊，理論是應(yīng)保存N（N為采樣點(diǎn)個(gè)數(shù)）個(gè)運(yùn)算參數(shù)W_N^r，但由于每一次蝶形運(yùn)算結(jié)果（如 x_1 (k)+W_N^k X_2 (k), x_1 (k)-W_N^k X_2 (k)）具有對稱性，因此RAM3只需要保存N/2個(gè)W_N^r即可。
2、1、1 奇數(shù)輪蝶形運(yùn)算  如圖3所示，RAM1首先根據(jù)計(jì)數(shù)器給出的兩個(gè)點(diǎn)的地址（如地址0，地址1）進(jìn)行數(shù)據(jù)讀操作，然后將數(shù)據(jù)（如 和 ）送進(jìn)DFT模塊進(jìn)行運(yùn)算，最后RAM2將DFT模塊輸出的數(shù)據(jù)（如 , ）按照原來的地址順序進(jìn)行寫操作,直到RAM1全部讀完N個(gè)數(shù)據(jù)，并且RAM2全部寫完N個(gè)數(shù)據(jù)后，則第一輪蝶形運(yùn)算計(jì)算完畢。 2、1、2 偶數(shù)輪蝶形運(yùn)算  偶數(shù)輪運(yùn)算跟奇數(shù)輪運(yùn)算相似，唯一的不同就是：讀取RAM由RAM1改為RAM2，寫RAM由RAM2改為RAM1。 RAM1與RAM2按照這樣的讀寫交替順序，直至歷遍完n輪蝶形運(yùn)算（n為蝶形運(yùn)算一共要計(jì)算的輪數(shù)）。 2、2?計(jì)數(shù)器架構(gòu)設(shè)計(jì) 由于需要依次讀取和寫入RAM1和RAM2，并且還要經(jīng)過N輪的運(yùn)算，很明顯需要運(yùn)用到計(jì)數(shù)器。 計(jì)數(shù)器架構(gòu)，關(guān)乎到整個(gè)設(shè)計(jì)的可靠性和至簡性，因此是重中之中的設(shè)計(jì)。按照至簡設(shè)計(jì)法的建議，需要用到N輪運(yùn)算，這需要一個(gè)計(jì)數(shù)器但每輪的計(jì)數(shù)器如何設(shè)計(jì)呢？ 由于這些計(jì)數(shù)器主要是用于產(chǎn)生讀寫地址的，所以我們需要仔細(xì)分析地址的規(guī)律。我們以8點(diǎn)的FFT為例進(jìn)行分析。  觀察上圖，每一輪取址如表1所示: 蝶形運(yùn)算第幾輪 運(yùn)算節(jié)點(diǎn) 第一次蝶形運(yùn)算 第二次蝶形運(yùn)算 第三次蝶形運(yùn)算 第四次蝶形運(yùn)算
1 X_1 (k)的地址 0 2 4 6
X_2 (k)的地址 1 3 5 7
2 X_1 (k)的地址 0 1 4 5
X_2 (k)的地址 2 3 6 7
3 X_1 (k)的地址 0 1 2 3
X_2 (k)的地址 4 5 6 7
表1 N為8的蝶形運(yùn)算每一輪取址 蝶形運(yùn)算每一輪每一次的取地址滿足什么關(guān)系呢，如何才能在FPGA設(shè)計(jì)中實(shí)現(xiàn)如表1的取地址運(yùn)算，觀察上表，我們可以發(fā)現(xiàn)如下規(guī)律: 第幾級蝶形運(yùn)算 X_1 (k)的地址
第一次 第二次 第三次 第四次
第一級 0=0+0*2^(1 ) 2=0+1*2^(1 ) 4=0+2*2^(1 ) 6=0+3*2^(1 )
第二級 0=0+0*2^(2 ) 1=1+0*2^(2 ) 4=0+1*2^(2 ) 5=1+1*2^(2 )
第三級 0=0+0*2^(3 ) 1=1+0*2^(3 ) 2=2+0*2^(3 ) 3=3+0*2^(3 )
表2 X_1 (k)的取址
第幾級蝶形運(yùn)算 X_2 (k)的地址
第一次 第二次 第三次 第四次
第一級 1=2^(0 ) +0+0*2^(1 ) 3=2^(0 )+0+1*2^(1 ) 5=2^(0 )+0+2*2^(1 ) 7=2^(0 )+0+3*2^(1 )
第二級 2=2^(1 ) +0+0*2^(2 ) 3=2^(1 ) +1+0*2^(2 ) 6=2^(1 ) +0+1*2^(2 ) 7=2^(1 ) +1+1*2^(2 )
第三級 4=2^(2 ) +0+0*2^(3 ) 5=2^(2 ) +1+0*2^(3 ) 6=2^(2 ) +2+0*2^(3 ) 7=2^(2 ) +3+0*2^(3 )
表3 X_2 (k)的取址
根據(jù)表2、表3，可得到 與 與數(shù)組[a],[b],[c]有關(guān)的表達(dá)式 ; ；（式1） 通過上面的觀察，按照明德?lián)P的計(jì)數(shù)器架構(gòu)建議，可設(shè)計(jì)三個(gè)計(jì)數(shù)器cnt0,cnt1,cnt2分別表示數(shù)組[a],[b],[c]，因此可將式1變?yōu)椋?/p> ； ；（式2） 各個(gè)計(jì)數(shù)器每一輪的結(jié)束條件為： (式3) 其中n為蝶形運(yùn)算一共要計(jì)算的輪數(shù)，如采樣點(diǎn)數(shù)N為8時(shí)，則一共要進(jìn)行三輪運(yùn)算。通過這三個(gè)簡易的計(jì)數(shù)器設(shè)計(jì)，就能實(shí)現(xiàn)復(fù)雜的DIT-FFT蝶形運(yùn)算取址操作。 終上所述，無論是模塊劃分、計(jì)數(shù)器設(shè)計(jì)、還是乒乓操作的讀寫處理，都始終基于“至簡設(shè)計(jì)”的原則，用簡易的代碼結(jié)構(gòu)就能實(shí)現(xiàn)復(fù)雜的DIT-FFT蝶形運(yùn)算，代碼設(shè)計(jì)風(fēng)格極其簡潔，詳細(xì)可參考附錄代碼。 本案例是FFT的串行實(shí)現(xiàn)，但根據(jù)同樣的思路和資源換速度的思想，可以很方便地實(shí)現(xiàn)多個(gè)并行或者全并行的設(shè)計(jì)。
|
