快速傅利葉變換與傅利葉變換有什麼聯絡嗎？

1樓：

其實在《電路分析教程》中就有這玩意，傅利葉變換的本質是積分正交，決定了它可以利用函式積分表示乙個函式。而《計算器代數系統的數學原理》中這玩意是用來還原快速多項式乘法中的多項式的係數的，僅僅是相量分析，其實對於一般情況用它求多項式乘法結果一點也不快，需要求值還要插值，而且需要高精度浮點。

它的加速原理主要在插值時的投機取巧，就和快速冪還有快速多項式求值差不多，就是小聰明。

2樓：DBinary

設：那麼式離散傅利葉變換可以寫成

設乙個有四個樣本的離散序列x[0],x[1],x[2],x[3]那麼DFT變換的行列式可以寫成:

時間複雜度是乙個用於描述演算法執行時間的函式，用符號O表示，從DFT的正變換及逆變換公式可以看出，其演算法的時間複雜度為 ,其運算時間與樣本數呈平方數增長,在一些樣本數較多的情況下,其運算量無疑是非常龐大的,為了簡化時間複雜度,可以對傅利葉變換的計算方式進行進一步優化。

設對離散序列x[n]的DFT變換寫作

其中n的範圍為[0,N-1],如果n是乙個偶數,那麼,就可以將x[n]分為兩組,設i為 ,設滿足x[2i]的序列為偶序列,設滿足x[2i+1]的序列為奇數列,奇數列和偶數列的個數分別是個,那麼就式子可以寫成

進一步可以得到

因為那麼,5.7可以寫成:

將用m進行替換,x[2i]用e[i]表示,意為偶序列(even),將x[2i+1]用o[i]表示,意為奇序列(odd),那麼就可以寫成:

於是乙個DFT變換變成了兩個

從式中可知,頻域復訊號的前可以分解為兩個傅利葉變換,下面對後半部分進行推導,設傅利葉變換後半部分的變換寫為

通過變形得到

因為那麼,5.13就變為了

其與前半部分的變換公式相比僅僅只是多取了乙個負號,那麼上式就可以寫成

即得到總結公式

其中DFT(e[i])與DFT[o[i]]可以根據上述推導進一步分解,,直到需要變換的點數為2,那麼,傅利葉變換的時間複雜度就由降低到了 ,當然,其需要樣本的點數滿足2的整數次冪,同時也將這種簡化方式稱為基2快速傅利葉變換(FFT)。

3樓：技術派到了中年

快速傅利葉變換是傅利葉變換的快速實現。快速傅利葉變換要求點數是2的冪次，傅利葉變換沒有這個要求。具體可以看看我之前寫的文章

技術派到了中年：傅利葉變換系列學習（3)----FS,FT,DTFT,DFS,DFT,FFT

4樓：馬天尼尼

要說聯絡的話，FFT到頭來是為了算出FT的結果，只不過採用了一些演算法，可以降低運算量。降低運算量在計算機裡面是尤其可貴的。