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.