昨天写了两篇关乎傅立叶变换的小短文。
第一篇以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)