作者：July、dznlong 二零一一年二月二十日
推薦閱讀：The Scientist and Engineers Guide to Digital Signal Processing，By Steven W. Smith, Ph.D。此書地址：http://www.dspguide.com/pdfbook.htm。
博主說明：I、本文中闡述離散傅裡葉變換方法，是根據此書：The Scientist and Engineers Guide to Digital Signal Processing，By Steven W. Smith, Ph.D.而翻譯而成的，此書地址：http://www.dspguide.com/pdfbook.htm。II、同時，有相當一部分內容編輯整理自dznlong的博客，也貼出其博客地址，向原創的作者表示致敬：http://blog.csdn.net/dznlong 。這年頭，真正靜下心寫來原創文章的人，很少了。
------------------------------------
從頭到尾徹底理解傅裡葉變換算法、上
前言
第一部分、 DFT
第一章、傅立葉變換的由來
第二章、實數形式離散傅立葉變換（Real DFT）
第三章、復數
第四章、復數形式離散傅立葉變換
前言：
“關於傅立葉變換，無論是書本還是在網上可以很容易找到關於傅立葉變換的描述，但是大都是些故弄玄虛的文章，太過抽象，盡是一些讓人看了就望而生畏的公式的羅列，讓人很難能夠從感性上得到理解”---dznlong，
那麼，到底什麼是傅裡葉變換算法列?傅裡葉變換所涉及到的公式具體有多復雜列?
傅裡葉變換（Fourier transform）是一種線性的積分變換。因其基本思想首先由法國學者傅裡葉系統地提出，所以以其名字來命名以示紀念。
哦，傅裡葉變換原來就是一種變換而已，只是這種變換是從時間轉換為頻率的變化。這下，你就知道了，傅裡葉就是一種變換，一種什麼變換列?就是一種從時間到頻率的變化或其相互轉化。
ok，咱們再來總體了解下傅裡葉變換，讓各位對其有個總體大概的印象，也順便看看傅裡葉變換所涉及到的公式，究竟有多復雜：
以下就是傅裡葉變換的4種變體（摘自，維基百科）
連續傅裡葉變換
一般情況下，若“傅裡葉變換”一詞不加任何限定語，則指的是“連續傅裡葉變換”。連續傅裡葉變換將平方可積的函數f（t）表示成復指數函數的積分或級數形式。
這是將頻率域的函數F(ω)表示為時間域的函數f（t）的積分形式。
連續傅裡葉變換的逆變換 (inverse Fourier transform)為：
即將時間域的函數f（t）表示為頻率域的函數F(ω)的積分。
一般可稱函數f（t）為原函數，而稱函數F(ω)為傅裡葉變換的像函數，原函數和像函數構成一個傅裡葉變換對（transform pair）。
除此之外，還有其它型式的變換對，以下兩種型式亦常被使用。在通信或是信號處理方面，常以
來代換，而形成新的變換對:
或者是因系數重分配而得到新的變換對：
一種對連續傅裡葉變換的推廣稱為分數傅裡葉變換（Fractional Fourier Transform）。分數傅裡葉變換(fractional Fourier transform,FRFT)指的就是傅裡葉變換(Fourier transform,FT)的廣義化。
分數傅裡葉變換的物理意義即做傅裡葉變換 a 次，其中 a 不一定要為整數；而做了分數傅裡葉變換之後，信號或輸入函數便會出現在介於時域(time domain)與頻域(frequency domain)之間的分數域(fractional domain)。
當f（t）為偶函數（或奇函數）時，其正弦（或余弦）分量將消亡，而可以稱這時的變換為余弦變換（cosine transform）或正弦變換（sine transform）.
另一個值得注意的性質是，當f（t）為純實函數時，F(−ω) = F*(ω)成立.
傅裡葉級數
連續形式的傅裡葉變換其實是傅裡葉級數 (Fourier series)的推廣，因為積分其實是一種極限形式的求和算子而已。對於周期函數，其傅裡葉級數是存在的：
其中Fn為復幅度。對於實值函數，函數的傅裡葉級數可以寫成：
其中an和bn是實頻率分量的幅度。
離散時域傅裡葉變換
離散傅裡葉變換是離散時間傅裡葉變換（DTFT）的特例（有時作為後者的近似）。DTFT在時域上離散，在頻域上則是周期的。DTFT可以被看作是傅裡葉級數的逆變換。
離散傅裡葉變換
離散傅裡葉變換（DFT），是連續傅裡葉變換在時域和頻域上都離散的形式，將時域信號的采樣變換為在離散時間傅裡葉變換（DTFT）頻域的采樣。在形式上，變換兩端（時域和頻域上）的序列是有限長的，而實際上這兩組序列都應當被認為是離散周期信號的主值序列。即使對有限長的離散信號作DFT，也應當將其看作經過周期延拓成為周期信號再作變換。在實際應用中通常采用快速傅裡葉變換以高效計算DFT。
為了在科學計算和數字信號處理等領域使用計算機進行傅裡葉變換，必須將函數xn定義在離散點而非連續域內，且須滿足有限性或周期性條件。這種情況下，使用離散傅裡葉變換（DFT），將函數xn表示為下面的求和形式：
其中Xk是傅裡葉幅度。直接使用這個公式計算的計算復雜度為O（n*n），而快速傅裡葉變換（FFT）可以將復雜度改進為O（n*lgn）。（後面會具體闡述FFT是如何將復雜度降為O（n*lgn）的。）計算復雜度的降低以及數字電路計算能力的發展使得DFT成為在信號處理領域十分實用且重要的方法。
下面，比較下上述傅立葉變換的4種變體，
如上，容易發現：函數在時（頻）域的離散對應於其像函數在頻（時）域的周期性。反之連續則意味著在對應域的信號的非周期性。也就是說，時間上的離散性對應著頻率上的周期性。同時，注意，離散時間傅裡葉變換，時間離散，頻率不離散，它在頻域依然是連續的。
如果，讀到此，你不甚明白，大沒關系，不必糾結於以上4種變體，繼續往下看，你自會豁然開朗。（有什麼問題，也懇請提出，或者批評指正）
ok， 本文，接下來，由傅裡葉變換入手，後重點闡述離散傅裡葉變換、快速傅裡葉算法，到最後徹底實現FFT算法，全篇力求通俗易懂、閱讀順暢，教你從頭到尾徹底理解傅裡葉變換算法。由於傅裡葉變換，也稱傅立葉變換，下文所稱為傅立葉變換，同一個變換，不同叫法，讀者不必感到奇怪。
>第一部分、DFT
第一章、傅立葉變換的由來
要理解傅立葉變換，先得知道傅立葉變換是怎麼變換的，當然，也需要一定的高等數學基礎，最基本的是級數變換，其中傅立葉級數變換是傅立葉變換的基礎公式。
一、傅立葉變換的提出
傅立葉是一位法國數學家和物理學家，原名是Jean Baptiste Joseph Fourier(1768-1830), Fourier於1807年在法國科學學會上發表了一篇論文，論文裡描述運用正弦曲線來描述溫度分布，論文裡有個在當時具有爭議性的決斷：任何連續周期信號都可以由一組適當的正弦曲線組合而成。
當時審查這個論文拉格朗日堅決反對此論文的發表，而後在近50年的時間裡，拉格朗日堅持認為傅立葉的方法無法表示帶有稜角的信號，如在方波中出現非連續變化斜率。直到拉格朗日死後15年這個論文才被發表出來。
誰是對的呢？拉格朗日是對的：正弦曲線無法組合成一個帶有稜角的信號。但是，我們可以用正弦曲線來非常逼近地表示它，逼近到兩種表示方法不存在能量差別，基於此，傅立葉是對的。
為什麼我們要用正弦曲線來代替原來的曲線呢？如我們也還可以用方波或三角波來代替呀，分解信號的方法是無窮多的，但分解信號的目的是為了更加簡單地處理原來的信號。
用正余弦來表示原信號會更加簡單，因為正余弦擁有原信號所不具有的性質：正弦曲線保真度。一個正余弦曲線信號輸入後，輸出的仍是正余弦曲線，只有幅度和相位可能發生變化，但是頻率和波的形狀仍是一樣的。且只有正余弦曲線才擁有這樣的性質，正因如此我們才不用方波或三角波來表示。
二、傅立葉變換分類
