【正文】 dinb[35:0]=0。 dina[35:0]={datain[31],datain[31],datain[31:16],datain[15],datain[15],datain[15:0]}。 blkb=blk_cf。 dina[35:0]=0。 addrb[4:0]=addr_cf2[4:0]。 addra[4:0]=addr_cf1[4:0]。 理工大學(xué)學(xué)士學(xué)位論文 24 dataout_valid=0。 dinb[35:0]=0。 dina[35:0]={datain[31],datain[31],datain[31:16],datain[15],datain[15],datain[15:0]}。 addrb[4:0]=0。 addra[4:0]=datain_t[4:0]。 dataout_valid=0。 dinb[35:0]=0。//cfft address generate enable signal dina[35:0]=0。 end st5:begin if(startfft) state=st3。 else state=st3。// start input datain into the ram1 st2 : begin if(startfft) state = st3。 end always(posedge clk or negedge rst_n) begin if(!rst_n) state =st0。 end else if(d_valid) begin datain_wr=0。 if(!rst_n) datain_t[4:0]=0。 always(posedge clk or negedge rst_n) //input datain sync。b0。b0。 assign dataout_cf2_t2[24:0]=dataout_cf2_t[24:0]slice_number[4:0]。 wire [24:0] dataout_cf1_t,dataout_cf2_t,dataout_cf1_t2,dataout_cf2_t2。 assigndatain_cf1[31:0]=(shift[1:0]==0)?{douta[33:18],douta[15:0]}:(shift[1:0]==1)?{douta[34:19],douta[16:1]}:(shift[1:0]==2)?{douta[35:20],douta[17:2]}:3239。 assign blk_cf=rd_ramamp。 reg dataout_valid。 wire [31:0] twiddle_dataout。 reg valid。//cfft dataout output signal wire [4:0] addr_cf1,addr_cf2。 reg [4:0] state。 reg blka,blkb。 assign d_im[15:0]=normal_im[15:0]。 wire [15:0] d_re。 output [13:0] dataout_b。 output fft_finish。 input [15:0] normal_re。 圖 遞歸順序型 FFT 結(jié)構(gòu)框圖 module cfft32( clk, rst_n, slice_number, normal_re, normal_im, normal_valid, startfft, fft_finish, address_a, dataout_a, address_b, dataout_b, dataout_valid, number)。在實(shí)際應(yīng)用中，輸入緩沖單元和輸出緩沖單元可以是同一個存儲單元，完成 N 點(diǎn) FFT 運(yùn)算最少只需要 N 個存儲單元來緩存輸入數(shù)據(jù)和中間計(jì)算結(jié)果。 圖 FFT處理器結(jié)構(gòu)框圖 圖 中：蝶算單元采用 DIT 方式來完成基 2 蝶形運(yùn)算，如果數(shù)據(jù)從雙口 RAM1中讀出，則計(jì)算結(jié)果存入雙口 RAM2 中，反之亦然；存儲單元主要用來存儲輸入數(shù)據(jù)、中間結(jié) 果 (RAM)，預(yù)置旋轉(zhuǎn)因子 (ROM)，以及最后的計(jì)算結(jié)果 (RAM)；地址產(chǎn)生單元產(chǎn)生 RAM 的讀、寫地址和 ROM 的讀地址；功能切換單元用來完成 RAM1 和 RAM2 間數(shù)據(jù)讀寫功能的切換；塊浮點(diǎn)單元記錄蝶算單元輸出數(shù)據(jù)的位信息，并完成蝶算單元輸入數(shù)據(jù)的截位；時序控制單元產(chǎn)生各個模塊的使能、控制信號，使整個流程正常工作。這種記數(shù)方法就是塊浮點(diǎn)數(shù)記數(shù)方法。在用 FPGA實(shí)現(xiàn) FFT算法的時候，經(jīng)常會使用塊浮點(diǎn)的方式來進(jìn)行。為了得到精確結(jié)果，一 方面可以選用合適的運(yùn)算結(jié)構(gòu)，盡量減少有限字長效應(yīng)，另一方面可以采用合適的字長以降低運(yùn)算噪聲 [3]。由于 A/D器件的精度是一定的，所以轉(zhuǎn)換之后的數(shù)值和真實(shí)值之間存在著偏差，這就是輸入的量化誤差?，F(xiàn)在以 16位為例，通過表 精度。 理工大學(xué)學(xué)士學(xué)位論文 16 采用變形補(bǔ)碼后，任何小于 l的 正數(shù)，兩個符號位都是 0，即 00．nxxx ...21；任何大于 l的負(fù)數(shù)，兩個符號位都是“ 1”，即 11．nxx ...21；如果兩個數(shù)相加后，其結(jié)果的符號位出現(xiàn)“ 01”或“ 10”兩種組合時，表示發(fā)生溢出。兩個正數(shù)相加，結(jié)果大于機(jī)器所能表示的最大正數(shù)，稱為上溢。在定點(diǎn)機(jī)中，正常情況下是不允許出現(xiàn)溢出的。浮點(diǎn)運(yùn)算要比 定點(diǎn)運(yùn) 算 復(fù)雜。本課題也是采用的圖 。圖 DITFFT的一種變形的運(yùn)算流圖，其中蝶形運(yùn)算的旋轉(zhuǎn)因子、運(yùn)算量與圖 。 (4)序列的倒序 仔細(xì)分析可以發(fā)現(xiàn)看似毫無規(guī)律可循的 DITFFT算法的輸入序列的排序其實(shí)是很有規(guī)律的。 通過觀察圖 ，第 L級共有 2L1個不同的旋轉(zhuǎn)因子。很明顯原址計(jì)算可以節(jié)省存儲資源，從而降低硬件的成本。在同一級運(yùn)算中，每一個蝶形運(yùn)算是有兩個輸入和兩個輸出的。由此圖更加直觀地看出 FFT算法的優(yōu)越性，從圖 ， N越大時，優(yōu)越性就越明顯。所以， M級運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為 NNMNC M 2log22)2( ?? 復(fù)數(shù)加次數(shù)為 NNNMC A 2log)2( ?? 而由前面的介紹，直接計(jì)算 N點(diǎn)的 DFT需要 N2次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。圖中 用到關(guān)系式mkNk m WW ?/。 圖 N點(diǎn) DFT的一次時域抽取分解圖 (NtiS) 與第一次分解相同，1(3x和 4為)rx按奇偶分解成的兩個長為 N/4的子序列，即 14,.. .,1,0,)12()( )2()(1423 ???????? Nllxlx lxlx 那么，)(1kX又可表示為 ?? ?? ??? ??? 14/ 0 )12( 2/114/ 0 2 2/11 )12()2()( N i lkNN i klN WlxWlxkX ?? ???? ?? 14/ 0 4/42/14/ 0 4/3 )()( N i klNkNN i klN WlxWWlx 12/,.. .,1,0),()( 42/3 ???? NkkXWkx kN （ ） 其中 ??????????14/044/414/034/33)]([)())]([)()(NiklNNiklNlxDFTWlxklxDFTWlxkx 同理，由)(3kX和)(4k的周期性和 Wm2/N尼的對稱性2/2/4/ NkNNk WW ???最后得到： 理工大學(xué)學(xué)士學(xué)位論文 10 14/,.. .,1,0,)()()4/( )()()(42/3142/31 ?????????? ?? NkkXWkXNkX kXWkXkXkNkN （ ） 同理可得 14/,.. .,1,0,)()4/( )()()(62/5262/52 ?????????? ?? NkkXWkXNkX kXWkXkXkNkN （ ） 其中有 14/,.. .1,0,)12()()2()()]([)()()]([)()(2625614/04/66514/04/55??????????????????NllxlxlxlxlXDFTWlxkXlXDFTWlxkXNiklNNiklN 這樣，如圖 ，經(jīng)過第二次的分解，一個 N/2點(diǎn)的 DFT就被拆分成為了兩個 N/4點(diǎn)的 DFT了。由前面的說明可以 知道，計(jì)算一個 N/2點(diǎn) DFT需要 (N2)2次復(fù)數(shù) 乘 法 和 N/2(N/21) 次 復(fù) 數(shù) 加 法 。 圖 采用蝶形運(yùn)算符號的這種圖示方法，可以用圖 2． 2來表示前面所講到的運(yùn)算。 設(shè)序列 x(n)的長度為 N，并且有以下的條件成立 N=2M， M為自然數(shù) 1(r)和 2(r)是 x(n)按 n的奇偶性分解成的兩個 N/2 點(diǎn)的子序列，如下式所示 12,.. .1,0),2()(1 ??? Nrrxrx 12,...,1,0),12()(2 ???? Nrrxr 那么 x(n)的 DFT 為 ?? ?? ?? n knNn knN WnxWnxkX )()()( ?? ?? ??? ?? 12/ 0 )12(212/ 0 2 )12()2( N r rkNN r krN WrxWrx ?? ???? ? 12/ 0 2212/ 0 1 )()( N r krNN r kN WrxWrx 由于 krNkrNjkrNjkrN WeeW 2 2/22222 ??? ??ππ 所以 1,.. .,1,0)()()()()( 2112/0 2/212/0 2/1?????? ?? ????NkkXWkXWrxWWrxkW kNNrkrNkNNrkrN （ ） 其中)(1kX和)(2k分別為 1rx和(2r的 N/2 點(diǎn) DFT，即 理工大學(xué)學(xué)士學(xué)位論文 8 )]([)()()]([)()(212/02/22112/02/11rxDFTWrxkXrxDFTWrxkXNrkrNNrkrN?????????? （ ） （ ） 又由于)(1kX和)(2k都是以 N/2 為周期，且 kNNkN WW ??? 2 所以 X(k)又可 以表示為如下所示的表達(dá)式 12,...,1,0)()()( 21 ???? NkkXWkXkX kN （ ） 12,...1,0)()()2( 21 ????? NkkXWkXNk kN （ ） 這樣一個 N點(diǎn)的 DFT就被拆分成為了兩個 N/2點(diǎn)的 DFT。下面就以 8 點(diǎn)的 FFT 為例詳細(xì)分析基 2FFT 算法。此外，旋轉(zhuǎn)因子 wmN具有明顯的周期性和對稱性。所以要想使得 DFT在各種科學(xué)和工程計(jì)算中得 到廣泛的應(yīng)用就必須想辦法減少其運(yùn)算量。從上面的說明中可以看出， N點(diǎn)DFT的乘法和加法運(yùn)算次數(shù)均與 N2成正比。 基 2FFT 算法 概述 長度為 N的有限長