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

1、按時(shí)間抽取的基按時(shí)間抽取的基2FFT算法分析及算法分析及MATLAB實(shí)現(xiàn)實(shí)現(xiàn)一、一、DITFFT算法的基本原理算法的基本原理基2FFT算法的基本思想是把原始的N點(diǎn)序列依次分解成一系列短序列，充分利用旋轉(zhuǎn)因子的周期性和對稱性，分別求出這些短序列對應(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è)N2點(diǎn)序列x1(n)

2、和x2(n)，再分別進(jìn)行DFT運(yùn)算，求出與之對應(yīng)的X1(k)和X2(k)，然后利用圖1所示的運(yùn)算流程進(jìn)行蝶形運(yùn)算，得到原N點(diǎn)序列的DFT。只要N是2的整數(shù)次冪，這種分解就可一直進(jìn)行下去，直到其DFT就是本身的1點(diǎn)時(shí)域序列。圖1DITFFT蝶形運(yùn)算流圖2、DITFFT算法的運(yùn)算規(guī)律及編程思想算法的運(yùn)算規(guī)律及編程思想1.原位計(jì)算對N=點(diǎn)的FFT共進(jìn)行M級運(yùn)算，每級由N2個(gè)蝶形運(yùn)算組成。在同一級中，每個(gè)蝶的M2輸入數(shù)據(jù)只對本蝶有用，且輸出節(jié)點(diǎn)

3、與輸入節(jié)點(diǎn)在同一水平線上，這就意味著每算完一個(gè)蝶后，所得數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的數(shù)組元素(存儲單元)，經(jīng)過M級運(yùn)算后，原來存放輸入序列數(shù)據(jù)的N個(gè)存儲單元中可依次存放X(k)的N個(gè)值，這種原位(址)計(jì)算的方法可節(jié)省大量內(nèi)存。2.旋轉(zhuǎn)因子的變化規(guī)律N點(diǎn)DIT―FFT運(yùn)算流圖中，每個(gè)蝶形都要乘以旋轉(zhuǎn)因子，p稱為旋轉(zhuǎn)因子的指數(shù)。例pWN如N＝8＝時(shí)各級的旋轉(zhuǎn)因子：32第一級：L=1，有1個(gè)旋轉(zhuǎn)因子：==J=0pWNJ4WNJ2LW1（J

4、←JN4），但次高位加1時(shí)，同樣要判斷0、1值，如果是0（JN4）則直接加1（J←JN4）否則要先將次高位變0（J←JN4）再判斷下一位，依次類推，直到完成最高位加1，逢2向右進(jìn)位的運(yùn)算。I=J時(shí)不需要交換，只對IJ時(shí)的情況進(jìn)行數(shù)據(jù)交換即可，數(shù)據(jù)倒序程序框圖如如2。7、蝶形運(yùn)算的規(guī)律序列經(jīng)過時(shí)域抽選后，存入數(shù)組中，如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，蝶形運(yùn)算可表示成如下形式：8、DITFFT程序框圖根據(jù)DITFFT原理和

5、過程，DITFFT的完整程序框圖如圖2：(1)倒序:輸入自然順序序列x(n)，根據(jù)倒序規(guī)律，進(jìn)行倒序處理；(2)循環(huán)層1:確定運(yùn)算的級數(shù)，L=1~M(N=)；確定一蝶形兩輸入數(shù)據(jù)距離B=M21L2(3)循環(huán)層2:確定L級的B=個(gè)旋轉(zhuǎn)因子；旋轉(zhuǎn)因子指數(shù)p=J，J=0~B1；1L2LM2(4)循環(huán)層3:對于同一旋轉(zhuǎn)因子，用于同一級個(gè)蝶形運(yùn)算中：k的取值從J到N1，步LM2長為(使用同一旋轉(zhuǎn)因子的蝶形相距的距離)L2(5)完成一個(gè)蝶形運(yùn)算。p