一維復(fù)數(shù)序列的快速傅里葉變換（FFT）
設(shè)x（N）為N點(diǎn)有限長(zhǎng)離散序列，代入式（8－3）、式（8－4），并令 其傅里葉變換（DFT）為地球物理數(shù)據(jù)處理基礎(chǔ)反變換（IDFT）為地球物理數(shù)據(jù)處理基礎(chǔ)兩者的差異只在于W的指數(shù)符號(hào)不同，以及差一個(gè)常數(shù)1/N，因此下面我們只討論DFT正變換式（8－5）的運(yùn)算量，其反變換式（8－6）的運(yùn)算是相同的。一般來(lái)說(shuō)，W是復(fù)數(shù)，因此，X（j）也是復(fù)數(shù)，對(duì)于式（8－5）的傅里葉變換（DFT），計(jì)算一個(gè)X（j）值需要N次復(fù)數(shù)乘法和N－1次復(fù)數(shù)加法。而X（j）一共有N個(gè)值（j＝0，1，…，N－1），所以完成整個(gè)DFT運(yùn)算總共需要N2次復(fù)數(shù)乘法和N（N－1）次復(fù)數(shù)加法。直接計(jì)算DFT，乘法次數(shù)和加法次數(shù)都是與N2成正比的，當(dāng)N很大時(shí)，運(yùn)算量會(huì)很大，例如，當(dāng)N＝8時(shí)，DFT需64次復(fù)數(shù)乘法；而當(dāng)N＝1024時(shí)，DFT所需乘法為1048576次，即一百多萬(wàn)次的復(fù)數(shù)乘法運(yùn)算，對(duì)運(yùn)算速度要求高。所以需要改進(jìn)DFT的計(jì)算方法，以減少運(yùn)算次數(shù)。分析Wjk，表面上有N2個(gè)數(shù)值，由于其周期性，實(shí)際上僅有N個(gè)不同的值W0，W1，…，WN－1。對(duì)于N＝2m時(shí)，由于其對(duì)稱性，只有N/2個(gè)不同的值W0，W1，…，地球物理數(shù)據(jù)處理基礎(chǔ)因此可以把長(zhǎng)序列的DFT分解為短序列DFT，而前面已經(jīng)分析DFT與N2成正比，所以N越小越有利。
同時(shí)，利用ab＋ac＝a（b＋c）結(jié)合律法則，可以將同一個(gè)Wr對(duì)應(yīng)的系數(shù)x（k）相加后再乘以Wr，就能大大減少運(yùn)算次數(shù)。這就是快速傅里葉變換（FFT）的算法思路。下面，我們來(lái)分析N＝2m情況下的FFT算法。1.N＝4的FFT算法對(duì)于m＝2，N＝4，式（8－5）傅里葉變換為地球物理數(shù)據(jù)處理基礎(chǔ)將式（8－7）寫成矩陣形式地球物理數(shù)據(jù)處理基礎(chǔ)為了便于分析，將上式中的j，k寫成二進(jìn)制形式，即地球物理數(shù)據(jù)處理基礎(chǔ)代入式（8－7），得地球物理數(shù)據(jù)處理基礎(chǔ)分析Wjk的周期性來(lái)減少乘法次數(shù)地球物理數(shù)據(jù)處理基礎(chǔ)則 代回式（8－9），整理得地球物理數(shù)據(jù)處理基礎(chǔ)上式可分層計(jì)算，先計(jì)算內(nèi)層，再計(jì)算外層時(shí)就利用內(nèi)層計(jì)算的結(jié)果，可避免重復(fù)計(jì)算。寫成分層形式地球物理數(shù)據(jù)處理基礎(chǔ)則X（j1 j0）＝X2（j1 j0）。上式表明對(duì)于N＝4的FFT，利用Wr的周期關(guān)系可分為m＝2步計(jì)算。實(shí)際上，利用Wr的對(duì)稱性，仍可以對(duì)式（8－11）進(jìn)行簡(jiǎn)化計(jì)算?？紤]到地球物理數(shù)據(jù)處理基礎(chǔ)式（8－11）可以簡(jiǎn)化為地球物理數(shù)據(jù)處理基礎(chǔ)令j＝j(luò)0；k＝k0，并把上式表示為十進(jìn)制，得地球物理數(shù)據(jù)處理基礎(chǔ)可以看到，完成上式N＝4的FFT計(jì)算（表8－1）需要N·（m－1）/2＝2次復(fù)數(shù)乘法和N·m＝8次復(fù)數(shù)加法，比N＝4的DFT算法的N2＝16次復(fù)數(shù)乘法和N·（N－1）＝12次復(fù)數(shù)加法要少得多。
表8－1 N＝4的FFT算法計(jì)算過(guò)程注：W0＝1；W1＝－i。［例1］求N＝4樣本序列1，3，3，1的頻譜（表8－2）。表8－2 N＝4樣本序列2.N＝8的FFT算法類似N＝4的情況，用二進(jìn)制形式表示，有地球物理數(shù)據(jù)處理基礎(chǔ)寫成分層計(jì)算的形式：地球物理數(shù)據(jù)處理基礎(chǔ)則X（j2 j1 j0）＝X3（j2 j1 j0）。對(duì)式（8－14）的X1（k1 k0 j0）進(jìn)行展開，有地球物理數(shù)據(jù)處理基礎(chǔ)還原成十進(jìn)制，并令k＝2k1＋k0，即k＝0，1，2，3，有地球物理數(shù)據(jù)處理基礎(chǔ)用類似的方法對(duì)式（8－14）的X2（k0 j1 j0），X3（j2 j1 j0）進(jìn)行展開，整理得地球物理數(shù)據(jù)處理基礎(chǔ)用式（8－16）、式（8－17）逐次計(jì)算到X3（j）＝X（j）（j＝0，1，…，7），即完成N＝23＝8的FFT計(jì)算，其詳細(xì)過(guò)程見表8－3。表8－3 N＝8的FFT算法計(jì)算過(guò)程注：對(duì)于正變換 對(duì)于反變換 所 ［例2］求N＝8樣本序列（表8－4）x（k）＝1，2，1，1，3，2，1，2的頻譜。表8－4 N＝8樣本序列3.任意N＝2m的FFT算法列出N＝4，N＝8的FFT計(jì)算公式，進(jìn)行對(duì)比地球物理數(shù)據(jù)處理基礎(chǔ)觀察式（8－18）、式（8－19），不難看出，遵循如下規(guī)律：（1）等式左邊的下標(biāo)由1遞增到m，可用q＝1，2，…，m代替，則等式右邊為q－1；（2）k的上限為奇數(shù)且隨q的增大而減小，至q＝m時(shí)為0，所以其取值范圍為k＝0，1，2，…，（2m－q－1）；（3）j的上限為奇數(shù)且隨q的增大而增大，且q＝1時(shí)為0，其取值范圍為j＝0，1，2，…，（2q－1－1）；（4）k的系數(shù)，在等式左邊為2q，等式右邊為2q－1（包括W的冪指數(shù)）；（5）等式左邊序號(hào)中的常數(shù)是2的乘方形式，且冪指數(shù)比下標(biāo)q小1，即2q－1；等式右邊m對(duì)式子序號(hào)中的常數(shù)都是定值2m－1。
歸納上述規(guī)則，寫出對(duì)于任意正整數(shù)m，N＝2m的FFT算法如下：由X0（p）＝x（p）（p＝0，1，…，N－1）開始：（1）對(duì)q＝1，2，…，m，執(zhí)行（2）～（3）步；（2）對(duì)k＝0，1，2，…，（2m－q－1）及j＝0，1，2，…，（2q－1－1），執(zhí)行地球物理數(shù)據(jù)處理基礎(chǔ)（3）j，k循環(huán)結(jié)束；（4）q循環(huán)結(jié)束；由Xm（p）（p＝0，1，…，N－1）輸出原始序列x（p）的頻譜X（p）。在計(jì)算機(jī)上很容易實(shí)現(xiàn)上述FFT算法程序，僅需要三個(gè)復(fù)數(shù)數(shù)組高級(jí)傅里葉公式，編程步驟如下：（1）設(shè)置復(fù)數(shù)數(shù)組X1（N－1），X2（N－1）和 （數(shù)組下界都從0開始）；（2）把樣本序列x賦給X1，即X1（k）＝x（k）（k＝0，1，…，N－1）；（3）計(jì)算W，即正變換 反變換 （4）q＝1，2，…，m，若q為偶數(shù)高級(jí)傅里葉公式，執(zhí)行（6），否則執(zhí)行第（5）步；（5）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循環(huán)，作X2（2qk＋j）＝X1（2q－1k＋j）＋X1（2q－1k＋j＋2m－1）X2（2qk＋j＋2q－1）＝［X1（2q－1k＋j）－X1（2q－1k＋j＋2m－1）］W（2q－1k）至k，j循環(huán)結(jié)束；（6）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循環(huán)，作X1（2qk＋j）＝X2（2q－1k＋j）＋X2（2q－1k＋j＋2m－1）X1（2qk＋j＋2q－1）＝［X2（2q－1k＋j）－X2（2q－1k＋j＋2m－1）］W（2q－1k）至k，j循環(huán)結(jié)束；（7）q循環(huán)結(jié)束，若m為偶數(shù)，輸出X1（j），否則輸出X2（j）（j＝0，1，…，N－1），即為所求。
誰(shuí)能告訴我fft（快速傅里葉變換）的原理請(qǐng)教關(guān)于“實(shí)序列快速傅里葉變換"程序
自數(shù)字信號(hào)處理C語(yǔ)言程序集，但運(yùn)算結(jié)果與書中給的結(jié)果不符合，估計(jì)書中給的這個(gè)程序代碼有些錯(cuò)誤~哪位高手能幫忙看看錯(cuò)誤在哪呢?實(shí)序列快速傅里葉變換:#includ
誰(shuí)能告訴我快速傅里葉變換（FFT）是做什么用的？
簡(jiǎn)單來(lái)講，可以講信號(hào)從時(shí)域變換到頻域進(jìn)行分析
如何在MATLAB里實(shí)現(xiàn)信號(hào)的快速傅里葉變換FFT
代碼：
1 N=8;%原離散信號(hào)有8點(diǎn)
2 n=[0:1:N-1]%原信號(hào)是1行8列的矩陣
3 xn=0.5.^n;%構(gòu)建原始信號(hào)，為指數(shù)信號(hào)
4
5 w=[-800:1:800]*4*pi/800;%頻域共-800----+800 的長(zhǎng)度（本應(yīng)是無(wú)窮，高頻分量很少，故省去）
6 X=xn*exp(-j*(n'*w));%求dtft變換，采用原始定義的方法，對(duì)復(fù)指數(shù)分量求和而得
7 subplot(311)
8 stem(n,xn);
9 title('原始信號(hào)(指數(shù)信號(hào))');
10 subplot(312);
11 plot(w/pi,abs(X));
12 title('DTFT變換')
會(huì)員1.png)