Can you summarize the following document?
        
  用FFT計算DFT會得到與直接用DFT定義計算相同的結果;最重要的區別是FFT更快。(由於舍入誤差的存在,許多FFT演算法還會比直接運用定義求值精確很多,後面會討論到這一點。)  令 "x",..., "x" 為複數。DFT由下式定義  直接按這個定義求值需要 O("N") 次運算:"X" 共有 "N" 個輸出,每個輸出需要 "N" 項求和。直接使用DFT運算需使用N個複數乘法(4N 個實數乘法)與N-1個複數加法(2N-2個實數加法),因此,計算使用DFT所有N點的值需要"N"複數乘法與"N"-N 個複數加法。FFT則是能夠在 O("N" log "N") 次操作計算出相同結果的任何方法。更準確的說,所有已知的FFT演算法都需要 O("N" log "N") 次運算(技術上O只標記上界),雖然還沒有已知的證據證明更低的複雜度是不可能的。(Johnson and Frigo, 2007)  要說明FFT節省時間的方式,就得考慮複數相乘和相加的次數。直接計算DFT的值涉及到 "N" 次複數相乘和 "N"("N"−1) 次複數相加(可以通過削去瑣碎運算(如乘以1)來節省 O("N") 次運算)。眾所周知的基2庫利-圖基演算法,"N" 為2的冪,可以只用 ("N"/2)log("N") 次複數乘法(再次忽略乘以1的簡化)和 "N"log("N") 次加法就可以得到相同結果。在實際中,現代計算機通常的實際效能通常不受算術運算的速度和對複雜主體的分析主導(參見Frigo & Johnson, 2005),但是從 O("N") 到 O("N" log "N") 的總體改進仍然能夠體現出來。

  假設一個M*N型矩陣S可分解成列向量以及行向量相乘:  formula_5  若formula_6有formula_7個相異的非平凡值(formula_8 where formula_9)  formula_10有formula_11個相異的非平凡值  則S共需要formula_12個乘法。  formula_13  Step 1:formula_14  Step 2:formula_15  簡化理論的變型:  formula_16  formula_17也是一個M*N的矩陣。  若formula_17有formula_19個值不等於0,則formula_20的乘法量上限為formula_21。

  假設formula_22,其中formula_23彼此互質  formula_24點DFT的乘法量為formula_25,則formula_26點DFT的乘法量為:  假設formula_28,P是一個質數。  若formula_29點的DFT需要的乘法量為formula_30  且formula_31當中(formula_32)  有formula_33個值不為formula_34及formula_35的倍數,  有formula_36個值為formula_34及formula_35的倍數,但不為formula_39的倍數,  則N點DFT的乘法量為:

  庫利-圖基演算法是最常見的FFT演算法。這一方法以分治法為策略遞迴地將長度為formula_41的離散傅立葉變換分解為長度為formula_42的formula_43個較短序列的離散傅立葉變換,以及與formula_44個旋轉因子的複數乘法。  這種方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作發表"An algorithm for the machine calculation of complex Fourier series"之後開始為人所知。但後來發現,實際上這兩位作者只是重新發明了高斯在1805年就已經提出的演算法(此演算法在歷史上數次以各種形式被再次提出)。  庫利-圖基演算法最有名的應用,是將序列長為"N "的DFT分割為兩個長為"N/2 "的子序列的DFT,因此這一應用只適用於序列長度為2的冪的DFT計算,即基2-FFT。實際上,如同高斯和Cooley與Tukey都指出的那樣,Cooley-Tukey演算法也可以用於序列長度"N "為任意因數分解形式的DFT,即混合基FFT,而且還可以應用於其他諸如分裂基FFT等變種。儘管Cooley-Tukey演算法的基本思路是採用遞迴的方法進行計算,大多數傳統的演算法實現都將顯式的遞迴演算法改寫為非遞迴的形式。另外,因為Cooley-Tukey演算法是將DFT分解為較小長度的多個DFT,因此它可以同任一種其他的DFT演算法聯合使用。

  下面,我們用N次單位根formula_45來表示formula_46。  formula_45的性質:  為了簡單起見,我們下面設待變換序列長度formula_55。根據上面單位根的對稱性,求級數formula_56時,可以將求和區間分為兩部分:  formula_57  formula_58和formula_59是兩個分別關於序列formula_60奇數號和偶數號序列N/2點變換。由此式只能計算出formula_61的前N/2個點,對於後N/2個點,注意formula_58和formula_59都是週期為N/2的函式,由單位根的對稱性,於是有以下變換公式:  這樣,一個N點變換就分解成了兩個N/2點變換。照這樣可繼續分解下去。這就是庫利-圖基快速傅立葉變換演算法的基本原理。根據主定理不難分析出此時演算法的時間複雜度為formula_66

  由於按蝶形結網路計算n點變換要進行log "n"層計算,每層計算n個點的變換,故演算法的時間複雜度為formula_69。

  在Cooley-Tukey演算法之外還有其他DFT的快速演算法。對於長度formula_70且formula_42與formula_43互質的序列,可以採用基於中國剩餘定理的互質因子演算法將N長序列的DFT分解為兩個子序列的DFT。與Cooley-Tukey演算法不同的是,互質因子演算法不需要旋轉因子。  Rader-Brenner演算法是類似於Cooley-Tukey演算法,但是採用的旋轉因子都是純虛數,以增加加法運算和降低了數值穩定性為代價減少了乘法運算。這方法之後被split-radix variant of Cooley-Tukey所取代,與Rader-Brenner演算法相比,有一樣多的乘法量,卻有較少的加法量,且不犧牲數值的準確性。  Bruun以及QFT演算法是不斷的把DFT分成許多較小的DFT運算。(Rader-Brenner以及QFT演算法是為了2的指數所設計的演算法,但依然可以適用在可分解的整數上。Bruun演算法則可以運用在可被分成偶數個運算的數字)。尤其是Bruun演算法,把FFT看成是formula_73,並把它分解成formula_74與formula_75的形式。  另一個從多項式觀點的快速傅立葉變換法是Winograd演算法。此演算法把formula_73分解成cyclotomic多項式,而這些多項式的係數通常為1,0,-1。這樣只需要很少的乘法量(如果有需要的話),所以winograd是可以得到最少乘法量的快速傅立葉演算法,對於較小的數字,可以找出有效率的算方式。更精確地說,winograd演算法讓DFT可以用formula_77點的DFT來簡化,但減少乘法量的同時,也增加了非常多的加法量。Winograd也可以利用剩餘值定理來簡化DFT。  Rader演算法提出了利用點數為N(N為質數)的DFT進行長度為N-1的迴旋折積來表示原本的DFT,如此就可利用折積用一對基本的FFT來計算DFT。另一個prime-size的FFT演算法為chirp-Z演算法。此法也是將DFT用折積來表示,此法與Rader演算法相比,能運用在更一般的轉換上,其轉換的基礎為Z轉換(Rabiner et al., 1969)。

  在許多的運用當中,要進行DFT的資料是純實數,如此一來經過DFT的結果會滿足對稱性:  而有一些演算法是專門為這種情形設計的(e.g. Sorensen, 1987)。另一些則是利用舊有的演算法(e.g. Cooley-Tukey),刪去一些不必要的演算步驟,如此省下了記憶體的使用,也省下了時間。另一方面,也可以把一個偶數長度且純實數的DFT,用長度為原本一半的複數型態DFT來表示(實數項為原本純實數資料的偶數項,虛數項則為奇數項)。  在Matlab上用一次N點FFT計算兩個N點實數訊號x,y的FFT:  一度人們認為,用離散哈特利轉換(Discrete Hartley Transform)來處理純實數的DFT會更有效率,但接著人們發現,對於同樣點數的純實數DFT,經過設計的FFT,可以比DHT省下更多的運算。Bruun演算法是第一個試著從減少實數輸入的DFT運算量的演算法,但此法並沒有成為人們普遍使用的方法。  對於實數輸入,且輸入為偶對稱或奇對稱的情形,可以更進一步的省下時間以及記憶體,此時DFT可以用離散餘弦轉換或離散正弦轉換來代替(Discrete cosine/sine transforms)。由於DCT/DST也可以設計出FFT的演算法,故在此種情形下,此方法取代了對DFT設計的FFT演算法。  DFT可以應用在頻譜分析以及做折積的運算,而在此處,不同應用可以用不同的演算法來取代,列表如下:  用來做頻譜分析的情況下,DFT可用下列的演算法代替:  用來做折積的情況下,DFT可用下列的演算法代替:

  長久以來,人們對於求出快速傅立葉變換的複雜度下限以及需要多少的運算量感到很有興趣,而實際上也還有許多問題需要解決。即使是用較簡單的情形,即formula_77點的DFT,也還沒能夠嚴謹的證明出FFT至少需要formula_81(不比formula_82小)的運算量,目前也沒有發現複雜度更低的演算法。通常數學運算量的多寡會是運算效率好壞最主要的因素,但在現實中,有許多因素也會有很大的影響,如快取記憶體以及CPU均有很大的影響。  在1978年,Winograd率先匯出一個較嚴謹的FFT所需乘法量的下限:formula_83。當formula_84時,DFT只需要formula_85次無理實數的乘法即可以計算出來。更詳盡,且也能趨近此下限的演算法也一一被提出(Heideman & Burrus, 1986; Duhamel, 1990)。很可惜的是,這些演算法,都需要很大量的加法計算,目前的硬體無法克服這個問題。  對於所需加法量的數目,雖然我們可以在某些受限制的假設下,推得其下限,但目前並沒有一個精確的下限被推匯出來。1973年,Morgenstern在乘法常數趨近巨大的情形下(對大部分的FFT演算法為真,但不是全部)推匯出加法量的下限:formula_86。Pan(1986)在假設FFT演算法的不同步的情形有其極限下證明出加法量的下限formula_87,但一般來說,此假設相當的不明確。長度為formula_84的情形下,在某些假設下,Papadimitriou(1979)提出使用Cooley-Tukey演算法所需的複數加法量formula_89是最少的。到目前為止,在長度為formula_84情況,還沒有任何FFT的演算法可以讓複數的加法量比formula_89還少。  還有一個問題是如何把乘法量與加法量的總和最小化,有時候稱作"演算複雜度"(在這裡考慮的是實際的運算量,而不是漸近複雜度)。同樣的,沒有一個嚴謹下限被證明出來。從1968年開始,formula_84點DFT而言,split-radix FFT演算法需要最少的運算量,在formula_93的情形下,其需要formula_94個乘法運算以及加法運算。最近有人匯出更低的運算量:formula_95。(Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007)  大多數嘗試要降低或者證明FFT複雜度下限的人都把焦點放在複數資料輸入的情況,因其為最簡單的情形。但是,複數資料輸入的FFT演算法,與實數資料輸入的FFT演算法,離散餘弦轉換(DCT),離散哈特列轉換(DHT),以及其他的演算法,均有很大的關連性。故任何一個演算法,在複雜度上有任何的改善的話,其他的演算法複雜度也會馬上獲得改善(Duhamel & Vetterli, 1990)。

  當輸入訊號長度為N時:  N = 1~60  N < 1000  N > 1000
快速傅立葉變換(英語:Fast Fourier Transform, FFT),是快速計算序列的離散傅立葉變換(DFT)或其逆變換的方法。傅立葉分析將訊號從原始域(通常是時間或空間)轉換到頻域的表示或者逆過來轉換。FFT會通過把DFT矩陣分解為稀疏(大多為零)因子之積來快速計算此類變換。 因此,它能夠將計算DFT的複雜度從只用DFT定義計算需要的 formula_1,降低到 formula_2,其中 formula_3 為資料大小。