FFT至簡設(shè)計(jì)法實(shí)現(xiàn)法_FFT算法_蝶形運(yùn)算.docx

DIT-FFT至簡設(shè)計(jì)實(shí)現(xiàn)法1、 DIT-FFT算法的基本原理有限長序列xn的N點(diǎn)DFT定義為：Xk=n=0N-1xnWNKn,式中WN=e-j2N。DFT在實(shí)際應(yīng)用中很重要，但是如果直接按DFT變換進(jìn)行計(jì)算，當(dāng)序列長度N很大時(shí)，計(jì)算量會(huì)非常大，所需時(shí)間也很長，因此常用的是DFT的一種快速計(jì)算算法，簡稱FFT。最常用的FFT算法是基于時(shí)間抽取的基2-FFT算法和基于頻率抽取的基2-FFT算法，這種算法的特點(diǎn)在于FFT會(huì)把一次大的DFT分割成幾個(gè)小的DFT，這樣遞歸式地細(xì)分下去，例如有8個(gè)采樣點(diǎn)的FFT，首先會(huì)把最外層的8點(diǎn)運(yùn)算分成兩個(gè)4點(diǎn)FFT的奇偶組合，第二層FFT又分成四個(gè)兩點(diǎn)FFT的奇偶組合，并且由此計(jì)算出的頻譜中很有趣的一點(diǎn)在于對(duì)于實(shí)數(shù)輸出的數(shù)組，后面一半和前面一半正好對(duì)稱相同，對(duì)于虛數(shù)輸出的數(shù)組，后面一半是前面數(shù)組對(duì)稱后乘上負(fù)1，因此，我們只需要算出FFT的一半即可求出全部。 本設(shè)計(jì)討論的是基于至簡設(shè)計(jì)法實(shí)現(xiàn)按時(shí)間抽選的基2-FFT算法（即DIF-FFT）實(shí)現(xiàn)過程，支持N由8到1024。 圖 1按時(shí)間抽取的基2-FFT算法蝶形運(yùn)算流圖（N=8）2、 蝶形運(yùn)算至簡實(shí)現(xiàn)過程2、1 模塊劃分 圖 2蝶形運(yùn)算模塊框圖 本模塊包括三個(gè)RAM模塊（RAM1，RAM2，RAM3）與一個(gè)DFT模塊，各模塊功能如下：1） 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)制的地址依次存儲(chǔ)在RAM1模塊中，即地址0保存了采樣點(diǎn)x(0)，地址1保存了采樣點(diǎn)x(4)。選用雙端口RAM1可以同時(shí)對(duì)兩點(diǎn)采樣數(shù)據(jù)(如圖1的x（0）、x(4)進(jìn)行讀、寫操作。2） RAM2模塊：RAM2模塊也是采用雙端口輸入輸出，可同時(shí)對(duì)兩點(diǎn)數(shù)據(jù)進(jìn)行讀、寫操作。3） DFT模塊：DFT模塊用于對(duì)RAM1、RAM2輸出的兩點(diǎn)采樣數(shù)據(jù)（如圖1的x（0）、x(4)）進(jìn)行蝶形運(yùn)算，它將運(yùn)算結(jié)果輸出至RAM1、RAM2模塊進(jìn)行保存。4） RAM3模塊：RAM3模塊是單輸出模塊，理論是應(yīng)保存N（N為采樣點(diǎn)個(gè)數(shù)）個(gè)運(yùn)算參數(shù)WNr，但由于每一次蝶形運(yùn)算結(jié)果（如 x1k+WNkX2(k), x1k-WNkX2(k)）具有對(duì)稱性，因此RAM3只需要保存N/2個(gè)WNr即可。2、1、1 奇數(shù)輪蝶形運(yùn)算 圖3 第奇數(shù)輪蝶形運(yùn)算流圖如圖3所示，RAM1首先根據(jù)計(jì)數(shù)器給出的兩個(gè)點(diǎn)的地址（如地址0，地址1）進(jìn)行數(shù)據(jù)讀操作，然后將數(shù)據(jù)（如x1(k)和x2(k)）送進(jìn)DFT模塊進(jìn)行運(yùn)算，最后RAM2將DFT模塊輸出的數(shù)據(jù)（如x1k+WNkX2(k), x1k-WNkX2(k)）按照原來的地址順序進(jìn)行寫操作,直到RAM1全部讀完N個(gè)數(shù)據(jù)，并且RAM2全部寫完N個(gè)數(shù)據(jù)后，則第一輪蝶形運(yùn)算計(jì)算完畢。2、1、2 偶數(shù)輪蝶形運(yùn)算 圖4 第偶數(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)算1X1(k)的地址0246X2(k)的地址13572X1k的地址0145X2k的地址23673X1(k)的地址0123X2(k)的地址4567表1 N為8的蝶形運(yùn)算每一輪取址蝶形運(yùn)算每一輪每一次的取地址滿足什么關(guān)系呢，如何才能在FPGA設(shè)計(jì)中實(shí)現(xiàn)如表1的取地址運(yùn)算，觀察上表，我們可以發(fā)現(xiàn)如下規(guī)律:第幾級(jí)蝶形運(yùn)算X1(k)的地址第一次第二次第三次第四次第一級(jí)0=0+0*21 2=0+1*21 4=0+2*21 6=0+3*21 第二級(jí)0=0+0*22 1=1+0*22 4=0+1*22 5=1+1*22 第三級(jí)0=0+0*23 1=1+0*23 2=2+0*23 3=3+0*23 第幾級(jí)蝶形運(yùn)算X2(k)的地址第一次第二次第三次第四次第一級(jí)1=20 +0+0*21 3=20 +0+1*21 5=20 +0+2*21 7=20 +0+3*21 第二級(jí)2=21 +0+0*22 3=21 +1+0*22 6=21 +0+1*22 7=21 +1+1*22 第三級(jí)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有關(guān)的表達(dá)式X1k地址=a+b*2c;X2k地址=X1k地址+2c-1； （式1）通過上面的觀察，按照明德?lián)P的計(jì)數(shù)器架構(gòu)建議，可設(shè)計(jì)三個(gè)計(jì)數(shù)器cnt0,cnt1,cnt2分別表示數(shù)組a,b,c，因此可將式1變?yōu)椋篨1k地址=cnt0+cnt1*2cnt2+1；X2k地址=X1k地址+2cnt2； （式2）各個(gè)計(jì)數(shù)器每一輪的結(jié)束條件為： cnt0=2cnt2-1; cnt1=2n-1-cnt2-1; cnt2=n-1; (式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ì)。3、至簡設(shè)計(jì)代碼實(shí)現(xiàn)（附錄部分代碼）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272parameter N = 512;parameter LOGN = 9;/*/計(jì)數(shù)器架構(gòu)，下面三個(gè)計(jì)數(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 ;/*/計(jì)數(shù)器架構(gòu)，下面三個(gè)計(jì)數(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的設(shè)計(jì)*/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的設(shè)計(jì)*/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寫請(qǐng)求0的設(shè)計(jì)*/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的設(shè)計(jì)*/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的設(shè)計(jì)*/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寫請(qǐng)求1的設(shè)計(jì)*/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的設(shè)計(jì)*/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的設(shè)計(jì)*/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寫請(qǐng)求0的設(shè)計(jì)*/always (posedge clk or negedge rst_n)b