【正文】 其中同理，由和的周期性和Wm尼的對稱性最后得到： （）同理可得 （）其中有 這樣，經(jīng)過第二次的分解，一個N/2點(diǎn)的DFT就被拆分成為了兩個N/4點(diǎn)的DFT了。依次類推，經(jīng)過M1次分解，最后將N點(diǎn)DFT分解成N/2個2點(diǎn)DFT。圖中用到關(guān)系式。 N點(diǎn)DFT的第二次時域抽取分解圖(N_8) N點(diǎn)DITFFT運(yùn)算流圖（N=8）DITFFT算法與直接計(jì)算DFT運(yùn)算量的比較，N=2時，其運(yùn)算流圖應(yīng)該有M級蝶形，每一級都由N/2蝶形運(yùn)算構(gòu)成。所以，M級運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為復(fù)數(shù)加次數(shù)為而由前面的介紹，直接計(jì)算N點(diǎn)的DFT需要N2次復(fù)數(shù)乘法以及N(N1)次復(fù)數(shù)加法運(yùn)算。當(dāng)N=210=1024時，可以求得直接計(jì)算N點(diǎn)的DFT和使用基2DITFFT算法的所需乘法次數(shù)的比值為 這樣，運(yùn)算效率就提高了200多倍。 FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線DITFFT的一些運(yùn)算規(guī)律 DITFFT運(yùn)算中是存在一些規(guī)律的，下面簡單的介紹一下這些規(guī)律。N=2M點(diǎn)的FFT共需要進(jìn)行進(jìn)行M級運(yùn)算，每級由N/2個蝶形運(yùn)算組成。這兩個輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在同一水平線上，并且它們只對本蝶形運(yùn)算有效，對其它的蝶形運(yùn)算是無效的。這種利用同一存儲單元存儲蝶形運(yùn)算計(jì)算輸入、輸出數(shù)據(jù)的方法就稱為原址計(jì)算。(2)旋轉(zhuǎn)因子的變化規(guī)律 由8點(diǎn)DITFFT的運(yùn)算流圖可以推得在N點(diǎn)DITFFT運(yùn)算流圖中，每級都有N/2個蝶形。被稱為旋轉(zhuǎn)因子，其中p為旋轉(zhuǎn)因子的指數(shù)。N=23=8時的各級旋轉(zhuǎn)因子表示如下： ()對N=2M的一半情況，第L級的旋轉(zhuǎn)因子為 （）(3)蝶形運(yùn)算規(guī)律設(shè)序列x(n)經(jīng)時域抽選(倒序)后，存入數(shù)組X中。L=1,2,...,M 下標(biāo)L表示第L級運(yùn)算，XI，(J)則表示第L級運(yùn)算后數(shù)組元素X(J)的值。由于N=2M，所以順序數(shù)可用M位二迸制數(shù)()表示。 形成倒序的樹狀圖(N2) 順序和倒序二進(jìn)制數(shù)對照表順序 倒敘十進(jìn)制數(shù)I 二進(jìn)制數(shù) 二進(jìn)制數(shù) 十進(jìn)制數(shù)J0 000 000 01 001 100 42 010 010 23 011 110 64 100 001 15 101 101 56 110 011 37 111 111 7DITFFT的輸入順序輸出倒序的信號流圖 DITFFT的信號流圖的形式不是唯一的，它還有多種表現(xiàn)形式。從圖中很容易看出它是一種順序輸入，倒序輸出的方式。因此在大型數(shù)據(jù)處理系統(tǒng)的FFT算法中。浮點(diǎn)表示法所能表示的數(shù)值范圍將遠(yuǎn)遠(yuǎn)大于定點(diǎn)表示法。浮點(diǎn)運(yùn)算要比定點(diǎn)運(yùn)算復(fù)雜。 定點(diǎn)數(shù)加減法的溢出及檢測方法 在定點(diǎn)小數(shù)機(jī)器中，數(shù)的表示范圍為|X|1。在定點(diǎn)機(jī)中，正常情況下是不允許出現(xiàn)溢出的。 x=，Y=，那么[x]補(bǔ)=，[y]補(bǔ)=，同理可得： [x+y]補(bǔ)=，兩個負(fù)數(shù)相加的結(jié)果成為正數(shù)，這同樣是錯誤的。兩個正數(shù)相加，結(jié)果大于機(jī)器所能表示的最大正數(shù)，稱為上溢。為了判斷“溢出”是否發(fā)生，可以采用雙符號位法，也稱為“變形補(bǔ)碼”或“模4補(bǔ)碼”，從而可使模2補(bǔ)碼所能表示的數(shù)的范圍擴(kuò)大一倍。采用變形補(bǔ)碼后，任何小于l的正數(shù)，兩個符號位都是0，即00．；任何大于l的負(fù)數(shù)，兩個符號位都是“1”，即11．；如果兩個數(shù)相加后，其結(jié)果的符號位出現(xiàn)“01”或“10”兩種組合時，表示發(fā)生溢出。 定點(diǎn)數(shù)的定標(biāo) 數(shù)的定標(biāo)就是根據(jù)需要，人為地指定小數(shù)點(diǎn)的位置，這主要是由于在利用FPGA進(jìn)行數(shù)字系統(tǒng)設(shè)計(jì)的時候無法將小數(shù)直接表示出來?，F(xiàn)在以16位為例。 16位有符號數(shù)的定標(biāo)表示法Q表示 S表示 十進(jìn)制數(shù)表示范圍 Q15 1=x= Q14 2=x= Q13 4=x= Q12 8=x= Q11 16=x= Q10 32=x= Q9 64=x= Q8 128=x= Q7 256=x= Q6 512=x= Q5 1024=x= Q4 2048=x= Q3 4096=x= Q2 8192=x= Q1 16384=x= Q0 32768=x=32767 有限字長效應(yīng)和單片機(jī)、DSP等器件一樣，F(xiàn)PGA也是不能直接處理模擬信號的。由于A/D器件的精度是一定的，所以轉(zhuǎn)換之后的數(shù)值和真實(shí)值之間存在著偏差，這就是輸入的量化誤差。進(jìn)行舍位就會自然而然的引入誤差，這種誤差屬于運(yùn)算量化誤差，也稱為運(yùn)算噪聲。為了得到精確結(jié)果，一方面可以選用合適的運(yùn)算結(jié)構(gòu)，盡量減少有限字長效應(yīng)，另一方面可以采用合適的字長以降低運(yùn)算噪聲[3]。由于在執(zhí)行算術(shù)運(yùn)算時需要大量的硬件資源，所以浮點(diǎn)數(shù)記數(shù)方法的使用成本很高。在用FPGA實(shí)現(xiàn)FFT算法的時候，經(jīng)常會使用塊浮點(diǎn)的方式來進(jìn)行。塊浮點(diǎn)數(shù)可以跟蹤數(shù)值動態(tài)范圍的變化，例如做256點(diǎn)FFT變換，數(shù)據(jù)寬度為16位，動態(tài)范圍是32768～32767，經(jīng)過FFT的第一級運(yùn)算后，取值范圍是65536～65535。這種記數(shù)方法就是塊浮點(diǎn)數(shù)記數(shù)方法。3 FFT的算法設(shè)計(jì) FFT處理器的實(shí)現(xiàn)框圖本論文主要研究的是32點(diǎn)的按時間抽取的基2FFT算法的FPGA實(shí)現(xiàn)，同時為了提高運(yùn)行速度還運(yùn)用了流水線結(jié)構(gòu)，為了兼顧高精度和復(fù)雜度的特點(diǎn)還引入了塊浮點(diǎn)結(jié)構(gòu)。 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)生各個模塊的使能、控制信號，使整個流程正常工作。這種形式的FFT只有一個蝶形運(yùn)算單元，蝶形運(yùn)算按遞歸的方式，根據(jù)蝶形圖從左向右、從上向下先計(jì)算第一級的每個蝶形，然后計(jì)算第二級、第三級，逐級地循環(huán)運(yùn)算，直至第N/2 log2N個蝶形，完成N點(diǎn)FFT的全部運(yùn)算。在實(shí)際應(yīng)用中，輸入緩沖單元和輸出緩沖單元可以是同一個存儲單元，完成N點(diǎn)FFT運(yùn)算最少只需要N個存儲單元來緩存輸入數(shù)據(jù)和中間計(jì)算結(jié)果。這種結(jié)構(gòu)的優(yōu)點(diǎn)是只有一個蝶形運(yùn)算單元，所占的硬件資源少，結(jié)構(gòu)簡單，穩(wěn)定性能好，缺點(diǎn)是運(yùn)算速度緩慢，且時序控制較為復(fù)雜。 遞歸順序型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)。 input rst_n。 input [15:0] normal_re。input normal_valid。output fft_finish。output [13:0] dataout_a。output [13:0] dataout_b。output [3:0] number。wire [15:0] d_re。assign d_valid=normal_valid。assign d_im[15:0]=normal_im[15:0]。 //ram control signal and databus ,address busreg [35:0] dina,dinb。reg blka,blkb。wire [35:0] douta,doutb。reg [4:0] state。wire [31:0] datain_cf1,datain_cf2。//cfft dataout output signalwire [4:0] addr_cf1,addr_cf2。//cfft read write and blk_en signalwire finish_butterfly。reg valid。reg datain_wr,datain_blk。wire [31:0] twiddle_dataout。wire [15:0] d_im_conj。reg dataout_valid。wire [1:0] shift。assign blk_cf=rd_ramamp。wr_ram。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。assigndatain_cf2[31:0]=(shift[1:0]==0)?{doutb[33:18],doutb[15:0]}:(shift[1:0]==1)?{doutb[34:19],doutb[16:1]}:(shift[1:0]==2)?{doutb[35:20],doutb[17:2]}:3239。wire [24:0] dataout_cf1_t,dataout_cf2_t,dataout_cf1_t2,dataout_cf2_t2。assigndataout_cf2_t[24:0]={dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35],dataout_cf2[35:18]}number[3:0]。assign dataout_cf2_t2[24:0]=dataout_cf2_t[24:0]slice_number[4:0]。b0。b0。b0。b0。 if(!rst_n) valid=0。always(posedge clk or negedge rst_n) //input datain sync。 else if(d_valid) datain[31:0]={d_re[15:0],d_im_conj[15:0]}。 if(!rst_n) datain_t[4:0]=0。always(posedge clk or negedge rst_n)//write data into the pingpong ram if(!rst_n) begin datain_wr=1。 end else if(d_valid) begin datain_wr=0。 end else begin datain_wr=1。 endalways(posedge clk or negedge rst_n)begin if(!rst_n) sta