快速傅里葉變換演算法

1. 一維復數序列的快速傅里葉變換（FFT）

設x（N）為N點有限長離散序列，代入式（8－3）、式（8－4），並令 其傅里葉變換（DFT）為

地球物理數據處理基礎

反變換（IDFT）為

地球物理數據處理基礎

兩者的差異只在於W的指數符號不同，以及差一個常數1/N，因此下面我們只討論DFT正變換式（8－5）的運算量，其反變換式（8－6）的運算是完全相同的。

一般來說，W是復數，因此，X（j）也是復數，對於式（8－5）的傅里葉變換（DFT），計算一個X（j）值需要N次復數乘法和N－1次復數加法。而X（j）一共有N個值（j＝0，1，…，N－1），所以完成整個DFT運算總共需要N²次復數乘法和N（N－1）次復數加法。

直接計算DFT，乘法次數和加法次數都是與N²成正比的，當N很大時，運算量會很大，例如，當N＝8時，DFT需64次復數乘法；而當N＝1024時，DFT所需乘法為1048576次，即一百多萬次的復數乘法運算，對運算速度要求高。所以需要改進DFT的計算方法，以減少運算次數。

分析W^jk，表面上有N²個數值，由於其周期性，實際上僅有N個不同的值W⁰，W¹，…，W^N－1。對於N＝2^m時，由於其對稱性，只有N/2個不同的值W⁰，W¹，…，

地球物理數據處理基礎

因此可以把長序列的DFT分解為短序列DFT，而前面已經分析DFT與N²成正比，所以N越小越有利。同時，利用ab＋ac＝a（b＋c）結合律法則，可以將同一個W^r對應的系數x（k）相加後再乘以W^r，就能大大減少運算次數。這就是快速傅里葉變換（FFT）的演算法思路。

下面，我們來分析N＝2^m情況下的FFT演算法。

1.N＝4的FFT演算法

對於m＝2，N＝4，式（8－5）傅里葉變換為

地球物理數據處理基礎

將式（8－7）寫成矩陣形式

地球物理數據處理基礎

為了便於分析，將上式中的j，k寫成二進制形式，即

地球物理數據處理基礎

代入式（8－7），得

地球物理數據處理基礎

分析W^jk的周期性來減少乘法次數

地球物理數據處理基礎

則 代回式（8－9），整理得

地球物理數據處理基礎

上式可分層計算，先計算內層，再計算外層時就利用內層計算的結果，可避免重復計算。寫成分層形式

地球物理數據處理基礎

則X（j₁ j₀）＝X₂（j₁ j₀）。

上式表明對於N＝4的FFT，利用W^r的周期關系可分為m＝2步計算。實際上，利用W^r的對稱性，仍可以對式（8－11）進行簡化計算。考慮到

地球物理數據處理基礎

式（8－11）可以簡化為

地球物理數據處理基礎

令j＝j₀；k＝k₀，並把上式表示為十進制，得

地球物理數據處理基礎

可以看到，完成上式N＝4的FFT計算（表8－1）需要N·（m－1）/2＝2次復數乘法和N·m＝8次復數加法，比N＝4的DFT演算法的N²＝16次復數乘法和N·（N－1）＝12次復數加法要少得多。

表8－1 N＝4的FFT演算法計算過程

註：W⁰＝1；W¹＝－i。

［例1］求N＝4樣本序列1，3，3，1的頻譜（表8－2）。

表8－2 N＝4樣本序列

2.N＝8的FFT演算法

類似N＝4的情況，用二進制形式表示，有

地球物理數據處理基礎

寫成分層計算的形式：

地球物理數據處理基礎

則X（j₂ j₁ j₀）＝X₃（j₂ j₁ j₀）。

對式（8－14）的X₁（k₁ k₀ j₀）進行展開，有

地球物理數據處理基礎

還原成十進制，並令k＝2k₁＋k₀，即k＝0，1，2，3，有

地球物理數據處理基礎

用類似的方法對式（8－14）的X₂（k₀ j₁ j₀），X₃（j₂ j₁ j₀）進行展開，整理得

地球物理數據處理基礎

用式（8－16）、式（8－17）逐次計算到X₃（j）＝X（j）（j＝0，1，…，7），即完成N＝2³＝8的FFT計算，其詳細過程見表8－3。

表8－3 N＝8的FFT演算法計算過程

註：對於正變換 對於反變換 所

［例2］求N＝8樣本序列（表8－4）x（k）＝1，2，1，1，3，2，1，2的頻譜。

表8－4 N＝8樣本序列

3.任意N＝2^m的FFT演算法

列出N＝4，N＝8的FFT計算公式，進行對比

地球物理數據處理基礎

觀察式（8－18）、式（8－19），不難看出，遵循如下規律：

（1）等式左邊的下標由1遞增到m，可用q＝1，2，…，m代替，則等式右邊為q－1；

（2）k的上限為奇數且隨q的增大而減小，至q＝m時為0，所以其取值范圍為k＝0，1，2，…，（2^m－q－1）；

（3）j的上限為奇數且隨q的增大而增大，且q＝1時為0，其取值范圍為j＝0，1，2，…，（2^q－1－1）；

（4）k的系數，在等式左邊為2^q，等式右邊為2^q－1（包括W的冪指數）；

（5）等式左邊序號中的常數是2的乘方形式，且冪指數比下標q小1，即2^q－1；等式右邊m對式子序號中的常數都是定值2^m－1。

歸納上述規則，寫出對於任意正整數m，N＝2^m的FFT演算法如下：

由X₀（p）＝x（p）（p＝0，1，…，N－1）開始：

（1）對q＝1，2，…，m，執行（2）～（3）步；

（2）對k＝0，1，2，…，（2^m－q－1）及j＝0，1，2，…，（2^q－1－1），執行

地球物理數據處理基礎

（3）j，k循環結束；

（4）q循環結束；由X_m（p）（p＝0，1，…，N－1）輸出原始序列x（p）的頻譜X（p）。

在計算機上很容易實現上述FFT演算法程序，僅需要三個復數數組，編程步驟如下：

（1）設置復數數組X₁（N－1），X₂（N－1）和 （數組下界都從0開始）；

（2）把樣本序列x賦給X₁，即X₁（k）＝x（k）（k＝0，1，…，N－1）；

（3）計算W，即正變換 反變換

（4）q＝1，2，…，m，若q為偶數，執行（6），否則執行第（5）步；

（5）k＝0，1，2，…，（2^m－q－1）和j＝0，1，2，…，（2^q－1－1）循環，作

X₂（2^qk＋j）＝X₁（2^q－1k＋j）＋X₁（2^q－1k＋j＋2^m－1）

X₂（2^qk＋j＋2^q－1）＝［X₁（2^q－1k＋j）－X₁（2^q－1k＋j＋2^m－1）］W（2^q－1k）

至k，j循環結束；

（6）k＝0，1，2，…，（2^m－q－1）和j＝0，1，2，…，（2^q－1－1）循環，作

X₁（2^qk＋j）＝X₂（2^q－1k＋j）＋X₂（2^q－1k＋j＋2^m－1）

X₁（2^qk＋j＋2^q－1）＝［X₂（2^q－1k＋j）－X₂（2^q－1k＋j＋2^m－1）］W（2^q－1k）

至k，j循環結束；

（7）q循環結束，若m為偶數，輸出X₁（j），否則輸出X₂（j）（j＝0，1，…，N－1），即為所求。

2. 如何理解傅里葉變換公式

1、傅里葉變換公式

(2)快速傅里葉變換演算法擴展閱讀：

根據原信號的不同類型，可以把傅里葉變換分為四種類別：

1、非周期性連續信號傅里葉變換（Fourier Transform）

2、周期性連續信號傅里葉級數(Fourier Series)

3、非周期性離散信號離散時域傅里葉變換（Discrete Time Fourier Transform）

4、周期性離散信號離散傅里葉變換(Discrete Fourier Transform)

3. 快速傅里葉變換的演算法類型

FFT演算法很多，根據實現運算過程是否有指數因子WN可分為有、無指數因子的兩類演算法。
有指數因子的演算法
經典庫利-圖基演算法 當輸入序列的長度N不是素數(素數只能被1而它本身整除）而是可以高度分解的復合數，即N=N1N2N3…Nr時，若N1=N2=…=Nr=2，N=2則N點DFT的計算可分解為N=2×N/2，即兩個N/2點DFT計算的組合，而N/2點DFT的計算又可分解為N/2=2×N/4，即兩個N/4點DFT計算的組合。依此類推，使DFT的計算形成有規則的模式，故稱之為以2為基底的FFT演算法。同理，當N=4時，則稱之為以4為基底的FFT演算法。當N=N1·N2時，稱為以N1和N2為基底的混合基演算法。
在這些演算法中，基2演算法用得最普遍。通常按序列在時域或在頻域分解過程的不同，又可分為兩種：一種是時間抽取FFT演算法（DIT），將N點DFT輸入序列x(n)、在時域分解成2個N/2點序列而x1(n)和x2(n)。前者是從原序列中按偶數序號抽取而成，而後者則按奇數序號抽取而成。DIT就是這樣有規律地按奇、偶次序逐次進行分解所構成的一種快速演算法。
分裂基演算法(RSFFT) 1984年由P．杜哈美爾和H．赫爾曼等導出的一種比庫利圖基演算法更加有效的改進演算法，其基本思想是在變換式的偶部採用基2演算法，在變換式的奇部採用基4演算法。優點是具有相對簡單的結構，非常適用於實對稱數據，對長度N=2能獲得最少的運算量(乘法和加法），所以是選用固定基演算法中的一種最佳折衷演算法。

4. 如何理解和掌握快速傅里葉變換的計算和概念

MATLAB傅里葉變換：傅立葉變換的分類：傅立葉級數：將周期性連續函數變換為離散頻率點上的函數（連續）傅立葉變換：將連續函數變換為連續頻率的函數離散時間傅立葉變換：將離散函數變換為連續頻率的函數離散傅立葉變換：將有限長離散函數變換為離散頻率點上的函數其中FFT是離散傅立葉變換的快速計算方法，適用於離散信號，並且注意變換後的點數與信號的采樣點數一致。盡管可以將信號補0，但補0不能提高頻域的解析度。matlab中提供了函數fft做一維的FFT。時域譜和頻域譜是相互對應；時域的信號長度，決定頻域的采樣間隔，它們成導數關系；時域中信號有N點，每點間隔dt，所以時域信號長度為N*dt；那麼頻譜每點的間隔就是1/(N*dt)。傅立葉變換結果和原來信號有相同的點數，所以m=N，又第一點一定對應0頻率，所以頻域信號的很坐標就是(0:m-1)/(N*dt)，這句就是根據這個很坐標和頻譜c，畫出頻譜plot((0:m-1)/(N*dt),c），所以在頻譜圖上，可以根據峰值的位置的橫坐標讀出對應的頻率。clearall;N=256;dt=0.02;n=0:N-1;t=n*dt;x=sin(2*pi*t);m=N;a=zeros(1,m);b=zeros(1,m);fork=0:m-1 forii=0:N-1 a(k+1)=a(k+1)+2/N*x(ii+1)*cos(2*pi*k*ii/N); b(k+1)=b(k+1)+2/N*x(ii+1)*sin(2*pi*k*ii/N); endc(k+1)=sqrt(a(k+1)^2+b(k+1)^2);endsubplot(211);plot(t,x);title('原始信號'),xlabel('時間/t');f=(0:m-1)/(N*dt);subplot(212);plot(f,c);holdontitle('Fourier');xlabel('頻率/HZ');ylabel('振幅');ind=find(c==max(c),1,'first');%尋找最到值的位置x0=f(ind);%根據位置得到橫坐標（頻率）y0=c(ind);%根據位置得到縱坐標（幅度）plot(x0,y0,'ro');holdofftext(x0+1,y0-0.1,num2str(x0,'頻率=%f'));

5. 傅里葉變換公式

1、公式描述：公式中F(ω)為f(t)的像函數，f(t)為F(ω)的像原函數。 2、傅立葉變換，表示能將滿足一定條件的某個函數表示成三角函數（正弦和/或餘弦函數）或者它們的積分的線性組合。在不同的研究領域，傅立葉變換具有多種不同的變體形式，如連續傅立葉變換和離散傅立葉變換。最初傅立葉分析是作為熱過程的解析分析的工具被提出的。 3、相關 * 傅里葉變換屬於諧波分析。 * 傅里葉變換的逆變換容易求出，而且形式與正變換非常類似; * 正弦基函數是微分運算的本徵函數，從而使得線性微分方程的求解可以轉化為常系數的代數方程的求解.在線性時不變的物理系統內，頻率是個不變的性質，從而系統對於復雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取； *卷積定理指出：傅里葉變換可以化復雜的卷積運算為簡單的乘積運算，從而提供了計算卷積的一種簡單手段； * 離散形式的傅立葉變換可以利用數字計算機快速地算出（其演算法稱為快速傅里葉變換演算法（FFT))。

6. 快速傅里葉變換的計算方法

計算離散傅里葉變換的快速方法，有按時間抽取的FFT演算法和按頻率抽取的FFT演算法。前者是將時域信號序列按偶奇分排，後者是將頻域信號序列按偶奇分排。它們都藉助於的兩個特點：一是周期性；二是對稱性，這里符號*代表其共軛。這樣，便可以把離散傅里葉變換的計算分成若干步進行，計算效率大為提高。
時間抽取演算法 令信號序列的長度為N=2,其中M是正整數，可以將時域信號序列x(n)分解成兩部分，一是偶數部分x（2n），另一是奇數部分x（2n+1），於是信號序列x(n）的離散傅里葉變換可以用兩個N/2抽樣點的離散傅里葉變換來表示和計算。考慮到和離散傅里葉變換的周期性，式⑴可以寫成
⑶其中（4a）（4b）由此可見，式⑷是兩個只含有N/2個點的離散傅里葉變換，G(k）僅包括原信號序列中的偶數點序列，H(k）則僅包括它的奇數點序列。雖然k=0，1，2，…，N-1，但是G(k）和H(k）的周期都是N/2，它們的數值以N/2周期重復。
因為於是由式⑶和式⑷得到（5a）（5b)
因此，一個抽樣點數為N 的信號序列x(n）的離散傅里葉變換，可以由兩個 N/2抽樣點序列的離散傅里葉變換求出。依此類推，這種按時間抽取演算法是將輸入信號序列分成越來越小的子序列進行離散傅里葉變換計算，最後合成為N點的離散傅里葉變換。
通常用圖1中蝶形演算法的信號流圖來表示式⑸的離散傅里葉變換運算。例如，N=8=2的抽樣點的信號序列x(n）的離散傅里葉變換，可用如圖2所示的FET演算法的信號流圖來計算。
①N=2點的離散傅里葉變換的計算全由蝶形運算組成，需要M級運算，每級包括N/2個蝶形運算，總共有 個蝶形運算。所以，總的計算量為次復數乘法運算和N log2N次復數加法運算。
②FFT演算法按級迭代進行，計算公式可以寫成
⑹N抽樣點的輸入信號具有N個原始數據x0(n），經第一級運算後，得出新的N個數據x1(n），再經過第二級迭代運算，又得到另外N個數據x2(n），依此類推，直至最後的結果x(k)=xM(k)=X(k）在逐級迭代計算中，每個蝶形運算的輸出數據存放在原來存貯輸入數據的單元中，實行所謂「即位計算」，這樣可以節省大量存放中間數據的寄存器。
③蝶形運算中加權系數隨迭代級數成倍增加。由圖2可以看出系數的變化規律。對於N=8,M=3情況，需進行三級迭代運算。在第一級迭代中，只用到一種加權系數；蝶形運算的跨度間隔等於1。在第二級迭代中，用到兩種加權系數即、；蝶形運算的跨度間隔等於2。在第三級迭代中，用到4種不同的加權系數即、、、；蝶形運算的跨度間隔等於4。可見，每級迭代的不同加權系數的數目比前一級迭代增加一倍；跨度間隔也增大一倍。
④輸入數據序列x(n）需重新排列為x(0）、x⑷、x⑵、x⑹、x⑴、x⑸、x⑶、x⑺，這是按照二進制數的碼位倒置所得到的反序數，例如N=8中數「1」的二進制數為「001」，將其碼位倒轉變為「100」，即為十進制數「4」。
頻率抽取演算法按頻率抽取的 FFT演算法是將頻域信號序列X(k）分解為奇偶兩部分，但演算法仍是由時域信號序列開始逐級運算，同樣是把N點分成N/2點計算FFT，可以把直接計算離散傅里葉變換所需的N次乘法縮減到次。
在N=2的情況下，把N點輸入序列x(n）分成前後兩半
⑺
時間序列x1(n）±x2(n）的長度為N/2，於是N點的離散傅里葉變換可以寫成
（8a)
（8b)
頻率信號序列X（2l）是時間信號序列x1(n)+x2(n）的N/2點離散傅里葉變換，頻率信號序列X（2l+1）是時間信號序列【x1(n)-x2(n）】的N/2點離散傅里葉變換，因此，N點離散傅里葉變換的計算，通過兩次加（減）法和一次乘法，從原來序列獲得兩個子序列，所以，頻率抽取演算法也具有蝶形運算形式。以2為基數的FFT基本蝶形運算公式為
⑼
其計算量完全和時間抽取演算法一樣，即只需次乘法運算和Nlog2N次加（減）法運算。圖3 表示N=8=2點的離散傅里葉變換的信號流圖。由圖可見，它以三級迭代進行即位計算，輸入數據是按自然次序存放，使用的系數也是按自然次序，而最後結果則以二進制反序存放。
實際上，頻率抽取演算法與時間抽取演算法的信號流圖之間存在著轉置關系，如將流圖適當變形，可以得出多種幾何形狀。
除了基2的FFT演算法之外，還有基4、基8等高基數的FFT演算法以及任意數為基數的FFT演算法。

7. 快速傅里葉變換演算法可以分為兩大類,分別是(__)、(__)

快速傅里葉變換演算法可以分為兩大類,分別是(有指數因子）（無指數因子）兩類演算法，

8. 化學dft計算是啥

離散傅里葉變換（Discrete Fourier Transform，縮寫為DFT），是傅里葉變換在時域和頻域上都呈離散的形式，將信號的時域采樣變換為其DTFT的頻域采樣。在形式上，變換兩端（時域和頻域上）的序列是有限長的，而實際上這兩組序列都應當被認為是離散周期信號的主值序列。即使對有限長的離散信號作DFT，也應當將其看作其周期延拓的變換。在實際應用中通常採用快速傅里葉變換計算DFT。

(8)快速傅里葉變換演算法擴展閱讀:
傅立葉變換，表示能將滿足一定條件的某個函數表示成三角函數（正弦和/或餘弦函數）或者它們的積分的線性組合。在不同的研究領域，傅立葉變換具有多種不同的變體形式，如連續傅立葉變換和離散傅立葉變換。最初傅立葉分析是作為熱過程的解析分析的工具被提出的。
Fourier transform或Transformée de Fourier有多個中文譯名，常見的有「傅里葉變換」、「付立葉變換」、「傅立葉轉換」、「傅氏轉換」、「傅氏變換」、等等。
傅立葉變換是一種分析信號的方法，它可分析信號的成分，也可用這些成分合成信號。許多波形可作為信號的成分，比如正弦波、方波、鋸齒波等，傅立葉變換用正弦波作為信號的成分。
定義
f(t)是t的周期函數，如果t滿足狄里赫萊條件：在一個以2T為周期內f(X)連續或只有有限個第一類間斷點，附f（x）單調或可劃分成有限個單調區間，則F（x）以2T為周期的傅里葉級數收斂，和函數S（x）也是以2T為周期的周期函數，且在這些間斷點上，函數是有限值；在一個周期內具有有限個極值點；絕對可積。則有下圖①式成立。稱為積分運算f(t)的傅立葉變換，
②式的積分運算叫做F(ω)的傅立葉逆變換。F(ω)叫做f(t)的象函數，f(t)叫做
F(ω)的象原函數。F(ω)是f(t)的象。f(t)是F(ω)原象。
①傅立葉變換

②傅立葉逆變換

傅里葉變換在物理學、電子類學科、數論、組合數學、信號處理、概率論、統計學、密碼學、聲學、光學、海洋學、結構動力學等領域都有著廣泛的應用（例如在信號處理中，傅里葉變換的典型用途是將信號分解成頻率譜——顯示與頻率對應的幅值大小）。
相關
* 傅里葉變換屬於諧波分析。
* 傅里葉變換的逆變換容易求出，而且形式與正變換非常類似;
* 正弦基函數是微分運算的本徵函數，從而使得線性微分方程的求解可以轉化為常系數的代數方程的求解.在線性時不變的物理系統內，頻率是個不變的性質，從而系統對於復雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取；
*卷積定理指出：傅里葉變換可以化復雜的卷積運算為簡單的乘積運算，從而提供了計算卷積的一種簡單手段；
* 離散形式的傅立葉變換可以利用數字計算機快速地算出（其演算法稱為快速傅里葉變換演算法（FFT))

9. 快速傅立葉變換的問題

快速傅氏變換，是離散傅氏變換的快速演算法，它是根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的演算法進行改進獲得的。它對傅氏變換的理論並沒有新的發現，但是對於在計算機系統或者說數字系統中應用離散傅立葉變換，可以說是進了一大步。

設x(n)為N項的復數序列，由DFT變換，任一X（m）的計算都需要N次復數乘法和N-1次復數加法，而一次復數乘法等於四次實數乘法和兩次實數加法，一次復數加法等於兩次實數加法，即使把一次復數乘法和一次復數加法定義成一次「運算」（四次實數乘法和四次實數加法），那麼求出N項復數序列的X（m）, 即N點DFT變換大約就需要N2次運算。當N=1024點甚至更多的時候，需要N2=1048576次運算，在FFT中，利用WN的周期性和對稱性，把一個N項序列（設N=2k,k為正整數），分為兩個N/2項的子序列，每個N/2點DFT變換需要（N/2）2次運算，再用N次運算把兩個N/2點的DFT 變換組合成一個N點的DFT變換。這樣變換以後，總的運算次數就變成N+2（N/2）2=N+N2/2。繼續上面的例子，N=1024時，總的運算次數就變成了525312次，節省了大約50%的運算量。而如果我們將這種「一分為二」的思想不斷進行下去，直到分成兩兩一組的DFT運算單元，那麼N點的 DFT變換就只需要Nlog2N次的運算，N在1024點時，運算量僅有10240次，是先前的直接演算法的1%，點數越多，運算量的節約就越大，這就是 FFT的優越性.
傅里葉變換（Transformée de Fourier）是一種積分變換。因其基本思想首先由法國學者傅里葉系統地提出，所以以其名字來命名以示紀念。

應用
傅里葉變換在物理學、數論、組合數學、信號處理、概率論、統計學、密碼學、聲學、光學、海洋學、結構動力學等領域都有著廣泛的應用（例如在信號處理中，傅里葉變換的典型用途是將信號分解成幅值分量和頻率分量）。

概要介紹
傅里葉變換能將滿足一定條件的某個函數表示成三角函數（正弦和/或餘弦函數）或者它們的積分的線性組合。在不同的研究領域，傅里葉變換具有多種不同的變體形式，如連續傅里葉變換和離散傅里葉變換。最初傅里葉分析是作為熱過程的解析分析的工具被提出的（參見：林家翹、西格爾著《自然科學中確定性問題的應用數學》，科學出版社，北京。原版書名為 C. C. Lin & L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Inc., New York, 1974）。
傅里葉變換屬於諧波分析。
傅里葉變換的逆變換容易求出,而且形式與正變換非常類似;
正弦基函數是微分運算的本徵函數,從而使得線性微分方程的求解可以轉化為常系數的代數方程的求解.在線性時不變的物理系統內,頻率是個不變的性質,從而系統對於復雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取;
卷積定理指出:傅里葉變換可以化復雜的卷積運算為簡單的乘積運算,從而提供了計算卷積的一種簡單手段;
離散形式的傅里葉變換可以利用數字計算機快速的算出(其演算法稱為快速傅里葉變換演算法(FFT)).