FFT(Fast Fourier transform)：快速傅裡葉變換，是DFT的工程化實作方法。
DFT直接求解太過于複雜，FFT方法根據DFT求解過程中旋轉因子的性質并引入分治算法思想，大大簡化計算過程，被廣泛應用在頻譜分析的工程實踐中，如matlab，C，C++，CUDA等底層實作
1 DFT簡介
頻譜分析是信号進行中的重要環節，從傅裡葉變換FT，到拉普拉斯變換LT，離散時間傅裡葉變換DTFT，Z變換ZT，到我們所講的離散傅裡葉變換DFT（他們之間的聯系和差別見我的其他部落格）。
相比于其他變換，DFT被廣泛應用的原因是其輸入的時域信号是離散的，輸出的頻域結果也是離散的。這就極大友善了我們進行基于計算機的頻譜計算，存儲和分析，沒辦法數字信号處理是大趨勢。
DFT變換的公式為：
但為了分析友善，在FFT的計算過程中，我們依然使用k = 0 ∼ N − 1 k = 0 \sim N-1k=0∼N−1的選取政策。也即，如下：
2 旋轉因子WWW的性質
3 FFT蝶形計算證明
4 FFT計算過程
1 matlab版本
2014a
2 參考文獻
[1] 蔡利梅.MATLAB圖像處理——理論、算法與執行個體分析[M].清華大學出版社，2020.
[2]楊丹,趙海濱,龍哲.MATLAB圖像處理執行個體詳解[M].清華大學出版社，2013.
[3]周品.MATLAB圖像處理與圖形使用者界面設計[M].清華大學出版社，2013.
[4]劉成龍.精通MATLAB圖像處理[M].清華大學出版社，2015.