FFT至簡設計法實現(xiàn)法_FFT算法_蝶形運算.docx

DIT-FFT至簡設計實現(xiàn)法1、 DIT-FFT算法的基本原理有限長序列xn的N點DFT定義為：Xk=n=0N-1xnWNKn,式中WN=e-j2N。DFT在實際應用中很重要，但是如果直接按DFT變換進行計算，當序列長度N很大時，計算量會非常大，所需時間也很長，因此常用的是DFT的一種快速計算算法，簡稱FFT。最常用的FFT算法是基于時間抽取的基2-FFT算法和基于頻率抽取的基2-FFT算法，這種算法的特點在于FFT會把一次大的DFT分割成幾個小的DFT，這樣遞歸式地細分下去，例如有8個采樣點的FFT，首先會把最外層的8點運算分成兩個4點FFT的奇偶組合，第二層FFT又分成四個兩點FFT的奇偶組合，并且由此計算出的頻譜中很有趣的一點在于對于實數(shù)輸出的數(shù)組，后面一半和前面一半正好對稱相同，對于虛數(shù)輸出的數(shù)組，后面一半是前面數(shù)組對稱后乘上負1，因此，我們只需要算出FFT的一半即可求出全部。 本設計討論的是基于至簡設計法實現(xiàn)按時間抽選的基2-FFT算法（即DIF-FFT）實現(xiàn)過程，支持N由8到1024。 圖 1按時間抽取的基2-FFT算法蝶形運算流圖（N=8）2、 蝶形運算至簡實現(xiàn)過程2、1 模塊劃分 圖 2蝶形運算模塊框圖 本模塊包括三個RAM模塊（RAM1，RAM2，RAM3）與一個DFT模塊，各模塊功能如下：1） RAM1模塊：在開始進行蝶形運算前，全部采樣點（如圖1所示的x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)）已經(jīng)按照倒位序二進制的地址依次存儲在RAM1模塊中，即地址0保存了采樣點x(0)，地址1保存了采樣點x(4)。選用雙端口RAM1可以同時對兩點采樣數(shù)據(jù)(如圖1的x（0）、x(4)進行讀、寫操作。2） RAM2模塊：RAM2模塊也是采用雙端口輸入輸出，可同時對兩點數(shù)據(jù)進行讀、寫操作。3） DFT模塊：DFT模塊用于對RAM1、RAM2輸出的兩點采樣數(shù)據(jù)（如圖1的x（0）、x(4)）進行蝶形運算，它將運算結果輸出至RAM1、RAM2模塊進行保存。4） RAM3模塊：RAM3模塊是單輸出模塊，理論是應保存N（N為采樣點個數(shù)）個運算參數(shù)WNr，但由于每一次蝶形運算結果（如 x1k+WNkX2(k), x1k-WNkX2(k)）具有對稱性，因此RAM3只需要保存N/2個WNr即可。2、1、1 奇數(shù)輪蝶形運算 圖3 第奇數(shù)輪蝶形運算流圖如圖3所示，RAM1首先根據(jù)計數(shù)器給出的兩個點的地址（如地址0，地址1）進行數(shù)據(jù)讀操作，然后將數(shù)據(jù)（如x1(k)和x2(k)）送進DFT模塊進行運算，最后RAM2將DFT模塊輸出的數(shù)據(jù)（如x1k+WNkX2(k), x1k-WNkX2(k)）按照原來的地址順序進行寫操作,直到RAM1全部讀完N個數(shù)據(jù)，并且RAM2全部寫完N個數(shù)據(jù)后，則第一輪蝶形運算計算完畢。2、1、2 偶數(shù)輪蝶形運算 圖4 第偶數(shù)輪蝶形運算流圖偶數(shù)輪運算跟奇數(shù)輪運算相似，唯一的不同就是：讀取RAM由RAM1改為RAM2，寫RAM由RAM2改為RAM1。RAM1與RAM2按照這樣的讀寫交替順序，直至歷遍完n輪蝶形運算（n為蝶形運算一共要計算的輪數(shù)）。2、2 計數(shù)器架構設計由于需要依次讀取和寫入RAM1和RAM2，并且還要經(jīng)過N輪的運算，很明顯需要運用到計數(shù)器。計數(shù)器架構，關乎到整個設計的可靠性和至簡性，因此是重中之中的設計。按照至簡設計法的建議，需要用到N輪運算，這需要一個計數(shù)器但每輪的計數(shù)器如何設計呢？由于這些計數(shù)器主要是用于產(chǎn)生讀寫地址的，所以我們需要仔細分析地址的規(guī)律。我們以8點的FFT為例進行分析。觀察上圖，每一輪取址如表1所示:蝶形運算第幾輪運算節(jié)點第一次蝶形運算第二次蝶形運算第三次蝶形運算第四次蝶形運算1X1(k)的地址0246X2(k)的地址13572X1k的地址0145X2k的地址23673X1(k)的地址0123X2(k)的地址4567表1 N為8的蝶形運算每一輪取址蝶形運算每一輪每一次的取地址滿足什么關系呢，如何才能在FPGA設計中實現(xiàn)如表1的取地址運算，觀察上表，我們可以發(fā)現(xiàn)如下規(guī)律:第幾級蝶形運算X1(k)的地址第一次第二次第三次第四次第一級0=0+0*21 2=0+1*21 4=0+2*21 6=0+3*21 第二級0=0+0*22 1=1+0*22 4=0+1*22 5=1+1*22 第三級0=0+0*23 1=1+0*23 2=2+0*23 3=3+0*23 第幾級蝶形運算X2(k)的地址第一次第二次第三次第四次第一級1=20 +0+0*21 3=20 +0+1*21 5=20 +0+2*21 7=20 +0+3*21 第二級2=21 +0+0*22 3=21 +1+0*22 6=21 +0+1*22 7=21 +1+1*22 第三級4=22 +0+0*23 5=22 +1+0*23 6=22 +2+0*23 7=22 +3+0*23 表2 X1(k)的取址 表3 X2(k)的取址根據(jù)表2、表3，可得到X1k地址與X2k地址與數(shù)組a,b,c有關的表達式X1k地址=a+b*2c;X2k地址=X1k地址+2c-1； （式1）通過上面的觀察，按照明德?lián)P的計數(shù)器架構建議，可設計三個計數(shù)器cnt0,cnt1,cnt2分別表示數(shù)組a,b,c，因此可將式1變?yōu)椋篨1k地址=cnt0+cnt1*2cnt2+1；X2k地址=X1k地址+2cnt2； （式2）各個計數(shù)器每一輪的結束條件為： cnt0=2cnt2-1; cnt1=2n-1-cnt2-1; cnt2=n-1; (式3)其中n為蝶形運算一共要計算的輪數(shù)，如采樣點數(shù)N為8時，則一共要進行三輪運算。通過這三個簡易的計數(shù)器設計，就能實現(xiàn)復雜的DIT-FFT蝶形運算取址操作。終上所述，無論是模塊劃分、計數(shù)器設計、還是乒乓操作的讀寫處理，都始終基于“至簡設計”的原則，用簡易的代碼結構就能實現(xiàn)復雜的DIT-FFT蝶形運算，代碼設計風格極其簡潔，詳細可參考附錄代碼。本案例是FFT的串行實現(xiàn)，但根據(jù)同樣的思路和資源換速度的思想，可以很方便地實現(xiàn)多個并行或者全并行的設計。3、至簡設計代碼實現(xiàn)（附錄部分代碼）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272parameter N = 512;parameter LOGN = 9;/*/計數(shù)器架構，下面三個計數(shù)器用于產(chǎn)生讀地址*/always (posedge clk or negedge rst_n)begin if(!rst_n)begin cnt0 = 0; end else if(add_cnt0)begin if(end_cnt0) cnt0 = 0; else cnt0 = cnt0 + 1; endendassign add_cnt0 = flag;assign end_cnt0 = add_cnt0 & cnt0= (1cnt2)-1 ;always (posedge clk or negedge rst_n)begin if(!rst_n)begin cnt1 = 0; end else if(add_cnt1)begin if(end_cnt1) cnt1 = 0; else cnt1 (cnt2+1)-1 ;always (posedge clk or negedge rst_n)begin if(!rst_n)begin cnt2 = 0; end else if(add_cnt2)begin if(end_cnt2) cnt2 = 0; else cnt2 = cnt2 + 1; endendassign add_cnt2 = end_cnt1;assign end_cnt2 = add_cnt2 & cnt2=LOGN-1 ;/*/計數(shù)器架構，下面三個計數(shù)器用于產(chǎn)生寫地址*/always (posedge clk or negedge rst_n)begin if(!rst_n)begin wr_cnt0 = 0; end else if(add_wr_cnt0)begin if(end_wr_cnt0) wr_cnt0 = 0; else wr_cnt0 = wr_cnt0 + 1; endendassign add_wr_cnt0 = fft_dout_vld;assign end_wr_cnt0 = add_wr_cnt0 & wr_cnt0=(1wr_cnt2)-1 ;always (posedge clk or negedge rst_n)begin if(!rst_n)begin wr_cnt1 = 0; end else if(add_wr_cnt1)begin if(end_wr_cnt1) wr_cnt1 = 0; else wr_cnt1 (wr_cnt2+1)-1 ;always (posedge clk or negedge rst_n)begin if(!rst_n)begin wr_cnt2 = 0; end else if(add_wr_cnt2)begin if(end_wr_cnt2) wr_cnt2 = 0; else wr_cnt2 = wr_cnt2 + 1; endendassign add_wr_cnt2 = end_wr_cnt1;assign end_wr_cnt2 = add_wr_cnt2 & wr_cnt2=LOGN-1 ;/*RAM1地址0的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin addr_0 = 0; end else if(wr_cnt20=0) begin addr_0 = cnt0 + cnt1*(1(cnt2+1); end else begin addr_0 = wr_cnt0 + wr_cnt1*(1(wr_cnt2+1); endend/*RAM1寫數(shù)據(jù)0的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin wdata_0 = 0; end else begin wdata_0 = fft_dout0; endend/*RAM1寫請求0的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin wrreq_0 = 0; end else if(wr_cnt20=1) begin wrreq_0 = fft_dout_vld; end else begin wrreq_0 = 0; endend/*RAM1地址1的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin addr_1 = 0; end else if(wr_cnt20=0) begin addr_1 = cnt0 + cnt1*(1(cnt2+1) + (1cnt2); end else begin addr_1 = wr_cnt0 + wr_cnt1*(1(wr_cnt2+1) + (1wr_cnt2); endend/*RAM1寫數(shù)據(jù)1的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin wdata_1 = 0; end else begin wdata_1 = fft_dout1; endend/*RAM1寫請求1的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin wrreq_1 = 0; end else if(wr_cnt20=1)begin wrreq_1 = fft_dout_vld; end else begin wrreq_1 = 0; endend/*RAM2地址0的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin addr_2 = 0; end else if(wr_cnt20=1) begin addr_2 = cnt0 + cnt1*(1(cnt2+1); end else begin addr_2 = wr_cnt0 + wr_cnt1*(1(wr_cnt2+1); endend/*RAM2寫數(shù)據(jù)0的設計*/always (posedge clk or negedge rst_n)begin if(rst_n=1b0)begin wdata_2 = 0; end else begin wdata_2 = fft_dout0; endend/*RAM2寫請求0的設計*/always (posedge clk or negedge rst_n)b