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

1、按時間抽取的基按時間抽取的基2FFT算法分析及算法分析及MATLAB實現(xiàn)實現(xiàn)一、一、DITFFT算法的基本原理算法的基本原理基2FFT算法的基本思想是把原始的N點序列依次分解成一系列短序列，充分利用旋轉(zhuǎn)因子的周期性和對稱性，分別求出這些短序列對應(yīng)的DFT，再進行適當(dāng)?shù)慕M合，得到原N點序列的DFT，最終達到減少運算次數(shù)，提高運算速度的目的。按時間抽取的基2FFT算法，先是將N點輸入序列x(n)在時域按奇偶次序分解成2個N2點序列x1(n)

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

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

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

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