昨天写了两篇关乎傅立叶变换的小短文。
第一篇以9副图展示了傅立叶变换把信号分解成若干个正弦波的能力，并且实现了两个For循环版本的DFT,最后分析了FFT蝶形算法的实现思路以及计算量。
第一篇文章地址：https://www.toutiao.com/a7047374338911224357
第二篇主要展示了卷积操作与傅立叶变换的等效性，都具有滤波能力。在某些场合，比如相关滤波做跟踪，我们就用FFT方法实现滤波。在深度神经网络中，我们直接用点集来实现滤波。其实，无论哪种滤波方法，都是可以相互转换的。
第二篇文章地址：https://www.toutiao.com/a7047478476533694987
今天我们就把蝶形算法的代码实现出来。
自己实现的FFT结果与scipy的FFT结果一致
代码下载链接：https://gitee.com/anjiang2020_admin/fft/blob/master/fft_zmm.py
推导先看一下DFT的公式：
为了简化写法：
再详细一点，表示成W(N,n,k)
要求解信号f(n)中含有频率为k的正选信号的幅值，使用公式（1）写代码：
F(k)=0
for n in range(0:N):
F(k) =f(n)*W(N,n,k)
可以看到，理论上非常简单的。我们再对k取0，1，2，，，，N值，即可得到F(0),F(1),....F(N)
