按時(shí)間抽取的基2FFT算法分析及MATLAB實(shí)現(xiàn)

1、按時(shí)間抽取的基2FFT算法分析及MATLA改現(xiàn)按時(shí)間抽取的基2FFT算法分析及MATLA現(xiàn)、DIT-FFT算法的基本原理基2FFT算法的基本思想是把原始的 N點(diǎn)序列依 次分解成一系列短序列，充分利用旋轉(zhuǎn)因子的周 期性和對(duì)稱性，分別求出這些短序列對(duì)應(yīng)的DFT, 再進(jìn)行適當(dāng)?shù)慕M合，得到原 N點(diǎn)序列的DFT最 終達(dá)到減少運(yùn)算次數(shù)，提高運(yùn)算速度的目的。按時(shí)間抽取的基2FFT算法，先是將N點(diǎn)輸入序 列x(n)在時(shí)域按奇偶次序分解成2個(gè)N/2點(diǎn)序 列x1(n)和x2(n),再分別進(jìn)行DFT運(yùn)算，求出 與之對(duì)應(yīng)的X1(k)和X2(k),然后利用圖1所示 的運(yùn)算流程進(jìn)行蝶形運(yùn)算，得到原N點(diǎn)序列的DFT只要N是

2、2的整數(shù)次騫，這種分解就可一 直進(jìn)行下去，直到其DFT就是本身的1點(diǎn)時(shí)域序 列。為俅*伏)=占十必治X2 3X (n+ N= * L w： x)圖1 DIT-FFT蝶形運(yùn)算流圖、DIT-FFT算法的運(yùn)算規(guī)律及編程思想1.原位計(jì)算對(duì)N=2M點(diǎn)的FFT共進(jìn)行M級(jí)運(yùn)算，每級(jí)由N/2 個(gè)蝶形運(yùn)算組成。在同一級(jí)中，每個(gè)蝶的輸入數(shù) 據(jù)只對(duì)本蝶有用，且輸出節(jié)點(diǎn)與輸入節(jié)點(diǎn)在同一 水平線上，這就意味著每算完一個(gè)蝶后，所得數(shù) 據(jù)可立即存入原輸入數(shù)據(jù)所占用的數(shù)組元素 （存 儲(chǔ)單元），經(jīng)過M級(jí)運(yùn)算后，原來存放輸入序列 數(shù)據(jù)的N個(gè)存儲(chǔ)單元中可依次存放 X（k）的N個(gè) 值，這種原位（址）計(jì)算的方法可節(jié)省大量?jī)?nèi)存。2.旋轉(zhuǎn)

3、因子的變化規(guī)律N點(diǎn)DITFFT運(yùn)算流圖中，每個(gè)蝶形都要乘以旋轉(zhuǎn)因子wNp, p稱為旋轉(zhuǎn)因子的指數(shù)。例如N= 8 =23時(shí)各級(jí)的旋轉(zhuǎn)因子：第一級(jí)：L=1,有1個(gè)旋轉(zhuǎn)因子：wNP=wN,4=w2jlJ=0第二級(jí)：L=2,有2個(gè)旋轉(zhuǎn)因子：wNP=wN,2 = w；J=0,1第三級(jí)：L=3,有4個(gè)旋轉(zhuǎn)因子：wNP=wN = w；lJ=0,1,2,3對(duì)于N= 2M的一般情況，第L級(jí)共有2L-1個(gè)不同的 旋轉(zhuǎn)因子：wN=w2J=0,1,2,，2L-1 12l =2M 油L-M = N , 2L-M故：按照上面兩式可以確定第 L級(jí)運(yùn)算的旋轉(zhuǎn) 因子%=%八吧=叫聲一p二八2Mt j=ojzLT3、同一級(jí)中，同

4、一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目第L級(jí)FFT運(yùn)算中，同一旋轉(zhuǎn)因子用在2M-L 個(gè)蝶形中；4、同一級(jí)中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間 相隔的“距離”第L級(jí)中，蝶距：DB；5、同一蝶形運(yùn)算兩輸入數(shù)據(jù)的距離在輸入倒序，輸出原序的 FFT變換中，第L 級(jí)的每一個(gè)蝶形的2個(gè)輸入數(shù)據(jù)相距：B=2l-1。6、碼位顛倒輸入序列x(n)經(jīng)過M級(jí)時(shí)域奇、偶抽選后， 輸出序列X(k)的順序和輸入序列的順序關(guān)系為 倒位關(guān)系。將十進(jìn)制順序數(shù)用I表示，與之對(duì)應(yīng)的二進(jìn)制是 用舊表示，十進(jìn)制倒序數(shù)用J表示，與之對(duì)應(yīng) 的二進(jìn)制是用JB表示。十進(jìn)制順序數(shù)I增加1, 相當(dāng)于 舊最低位加1且逢2向高位進(jìn)1,即相 當(dāng)于JB最高位加1且逢2向低位

5、進(jìn)1。JB的變 化規(guī)律反映到J的變化分為兩種情況，若 JB的 最高位是0 (JN/2),則直接由加1 (J-J+N/2) 得到下一個(gè)倒序值，若 JB的最高位是1 (J三 N/2),則要先將最高位變 0 (J-J-N/2),再在 次高位加1 (J-J+N/4 ),但次高位加1時(shí)，同 樣要判斷0、1值，如果是0 (JN/4),則直接 加1 (J-J+N/4)，否則要先將次高位變0(J-J-N/4)再判斷下一位，依次類推，直到完 成最高位加1 ,逢2向右進(jìn)位的運(yùn)算。I=J時(shí)不 需要交換，只對(duì)IJ時(shí)的情況進(jìn)行數(shù)據(jù)交換即可， 數(shù)據(jù)倒序程序框圖如如2。7、蝶形運(yùn)算的規(guī)律序列經(jīng)過時(shí)域抽選后，存入數(shù)組中，如果

6、蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，蝶形運(yùn)算可表示成如下形式：XL (J尸 XL-1(J)+ WNp X L-1J(J+B)X L-1 (J+B)/、 Xl (J) = Xl-i(J)-WnP - XL-1WNp(J+B)p=J X2M-L, J=0,1,2,2l-1- 18、DIT-FFT程序框圖根據(jù)DIT-FFT原理和過程，DIT-FFT的完整程序框圖如圖2:(1)倒序：輸入自然順序序列x(n),根據(jù)倒序規(guī) 律，進(jìn)行倒序處理； 循環(huán)層1:確定運(yùn)算的級(jí)數(shù)，L=1M (N=2M)；確定一蝶形兩輸入數(shù)據(jù)距離B=2L-1循環(huán)層2:確定L級(jí)的B=2L-1個(gè)旋轉(zhuǎn)因子；旋轉(zhuǎn) 因子指數(shù)p=JM

7、M-L, J=0B-1;(4)循環(huán)層3:對(duì)于同一旋轉(zhuǎn)因子，用于同一級(jí)2m-l 個(gè)蝶形運(yùn)算中：k的取值從J到N-1,步長(zhǎng)為2L(使用同一旋轉(zhuǎn)因子的蝶形相距的距離)(5)完成一個(gè)蝶形運(yùn)算。f開始圖2數(shù)據(jù)倒序程序框圖圖3 DIT-FFT的完整程序框圖三、程序源代碼設(shè)計(jì)函數(shù)myDitFFT(xn)完成一個(gè)序列的DIT-FFT 運(yùn)算:function y=myDitFFT(xn)M=nextpow2(length(xn);N=2AM;disp(調(diào)用fft函數(shù)運(yùn)算的結(jié)果:),fftxn=fft(xn,N);if length(xn)Nxn=xn,zeros(1,N-length(xn); endfor m

8、=0:N/2-1;%旋轉(zhuǎn)因子指數(shù)范圍WN(m+1)=exp(-j*2*pi/Nm;%計(jì)算旋轉(zhuǎn)因子end disp(輸入到各存儲(chǔ)單元的數(shù)據(jù)：),disp(xn);%數(shù)據(jù)倒序操作 J=0; %給倒序數(shù)賦初值 for I=0:N-1;%$序交換數(shù)據(jù)和算倒序數(shù)if I=K;J=J-K;K=K/2;endJ=J+K;enddisp(倒序后各存儲(chǔ)單元的數(shù)據(jù)：)，disp(xn);%分級(jí)按序依次進(jìn)行蝶形運(yùn)算for L=1:M;%分級(jí)計(jì)算disp( 運(yùn)算級(jí)次：),disp(L);B=2A(L-1);for R=0:B-1;%各級(jí)按序蝶算P=2A(M-L)*R;for K=R:2AL:N-2;%每序依次計(jì)算T=

9、xn(K+1)+xn(K+B+1)*WN(P+1);xn(K+B+1)=xn(K+1)-xn(K+B+1)*WN(P+1);xn(K+1)=T;endenddisp( 本級(jí)運(yùn)算后各存儲(chǔ)單元的數(shù)據(jù)：),disp(xn);end在主函數(shù)中調(diào)用 myDitFFT(xn)函數(shù)實(shí)現(xiàn)DIT-FFT并和直接DFT運(yùn)算結(jié)果做對(duì)比：xn=0,1,2,3,4,5,6,7;myDitFFT(xn);調(diào)用fft函數(shù)運(yùn)算的結(jié)果：1至7歹U28.0000 + 0.0000i-4.0000+ 4.0000i-4.0000+ 9.6569i-4.0000+ 1.6569i-4.0000+ 0.0000i-4.0000-4.0

10、000 - 4.0000i8列-4.0000 - 9.6569i調(diào)用myDitFFT(xn)函數(shù)運(yùn)行的結(jié)果:輸入到各存儲(chǔ)單元的數(shù)據(jù)： TOC o 1-5 h z 01234567倒序后各存儲(chǔ)單元的數(shù)據(jù)：04261537運(yùn)算級(jí)次：1本級(jí)運(yùn)算后各存儲(chǔ)單元的數(shù)據(jù)：-1.6569i6-44-48-4運(yùn)算級(jí)次:2本級(jí)運(yùn)算后各存儲(chǔ)單元的數(shù)據(jù)1 至7歹U12.0000+ 0.0000i-4.0000+ 0.0000i16.0000 + 0.0000i-4.0000 + 0.0000i8列-4.0000 - 4.0000i-4.0000 + 4.0000i-4.0000-4.0000i-4.0000+4.00

11、00i運(yùn)算級(jí)次:3本級(jí)運(yùn)算后各存儲(chǔ)單元的數(shù)據(jù)1 至7歹U28.0000+ 0.0000i-4.0000+ 4.0000i-4.0000+ 0.0000i-4.0000 + 9.6569i-4.0000+ 1.6569i-4.0000- 1.6569i-4.0000 - 9.6569i經(jīng)對(duì)比可知DIT-FFT與直接DFT勺運(yùn)行結(jié)果完全 相同。四、總結(jié)經(jīng)過驗(yàn)證可發(fā)現(xiàn)DIT-FFT較直接DFT運(yùn)算有著明 顯的優(yōu)勢(shì)，我們可以將這個(gè)函數(shù)運(yùn)用在多個(gè)領(lǐng)域 以簡(jiǎn)化運(yùn)算，例如計(jì)算離散時(shí)間序列的卷積或計(jì) 算IDFT時(shí)都可以應(yīng)用到DIT-FFT算法，我感受 到數(shù)字信號(hào)處理中科學(xué)思想的魅力。由于對(duì)設(shè)計(jì) 思路的缺乏，我在設(shè)計(jì)程序時(shí)，在網(wǎng)絡(luò)上查找了 很多有關(guān)DIT-FFT的資料，經(jīng)過學(xué)習(xí)他人的解決 思路最后才整理出DIT-FFT的程序，在有些地方 我自己理解的還不是很透徹，比如在實(shí)現(xiàn)數(shù)據(jù)倒 序的程序我認(rèn)為比較困難；當(dāng)然即使自己想不到 能學(xué)習(xí)一下別人的思路也