2024fft算法的基本原理

2024年 7月 28日下午3:20 • 激活谷笔记

FFT原理史上最精炼解读　　本文主要复习一下FFT, 　　虽然有很多博客书籍介绍FFT,但是个人认为还是介绍的稍微有一些复杂，本文将尽可能用最简单的方法来把其原理阐述清楚。　　首先给一个概念介绍：　　FFT是DFT的一种快速算法，DFT：离散傅里叶变换，这里假定读者知道DFT。　　先给出DFT公式: 　　
$X[k]=\sum_{n=0}^{N-1}x[n]e^{\frac{-j2\pi kn}{N}}$ 　　其中k取值范围也是0到N-1的离散点，可见按照常规方法计算k=0到N-1的值，大约要计算N*N次乘法，算法复杂度为O(N^2),复杂度较高，FFT就被发明出来加速计算　　下面我们来解释FFT算法，首先为了简化公式，我们记: 　　
$W_N=e^{-j2\pi/N}$ 　　同时，我们只考虑N为2的次幂的情形（这也是一般的FFT考虑的情形，对于非2的指数次幂，有一些特殊处理方法，这里为了简化我们不考虑）　　先给出
W_N 的三个性质：　　1，周期性
$W_N^k=W_N^{k+tN}$ 　　其中k,t是任意整数；证明：据
即可得　　2,
$W_N^{k+N/2} =-W_N^{k}$ 证明：根据
$W_N^{N/2}=-1$ 即可得　　3，
$W_N^2=W_{N/2}$ 证明：显然成立　　这三个性质，我们在后面会用到，后文中称为 “性质1”,“性质2”和“性质3” 　　那么，DFT公式简化为: 　　
$X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn}$ 　　我们将n 按照偶数和奇数归类，先把n为偶数的项求和，再把奇数项求和；令　　
$G[k]=\sum_{n=0}^{N-2}x[n]W_N^{kn}$ n为偶数　　
$H[k]=\sum_{n=1}^{N-1}x[n]W_N^{kn}$ n为奇数　　则，显然　　
　　下面，我们考察 X[k+N/2] ，根据DFT公式，有　　
$X[k+N/2]=\sum_{n=0}^{N-1}x[n]W_N^{n(k+N/2)}$ 　　将等式右边的求和分为n为偶数项的和，与n为奇数项的和，有　　偶数项: 　　
$\sum_{n=0}^{N-2}x[n]W_N^{n(k+N/2)}=\sum_{n=0}^{N-2}x[n]W_N^{nk+n*N/2} （1）$ 　　因为n是偶数，利用性质1，有　　
$（1）=\sum_{n=0}^{N-2}x[n]W_N^{nk} = G[k]$ 　　奇数项：　　
$\sum_{n=1}^{N-1}x[n]W_N^{n(k+N/2)}=\sum_{n=1}^{N-1}x[n]W_N^{nk+(n-1)*N/2+N/2} （2）$ 　　因为此时n为奇数，利用性质1，和性质2，有　　
$（2） = \sum_{n=1}^{N-1}x[n](-W_N^{nk}) =-H[k]$ 　　综上，　　
$G[k]=\sum_{n=0}^{N-2}x[n]W_N^{kn}$ n取偶数　　
$H[k]=\sum_{n=1}^{N-1}x[n]W_N^{kn}$ n取奇数　　
　　
　　这就意味着，我们只需计算X[0],X[1],,,X[N/2-1] 对应的H[k]和G[k]，之后这些计算结果可以复用到X[k+N/2]的计算,从而减小了计算量　　进一步，我们来化简化一下G[k],H[k]，利用性质3，有　　
$G[k]=\sum_{r=0}^{N/2-1}x[2r]W_N^{2kr} =\sum_{r=0}^{N/2-1}x[2r]W_{N/2}^{rk}$ 　　
$H[k]=\sum_{r=0}^{N/2-1}x[2r+1]W_N^{k(2r+1)} =W_N^k\sum_{r=0}^{N/2-1}x[2r+1]W_{N/2}^{rk}$ 　　我们单独的看G[k]和H[k]的表达式，发现它们分别各是一个标准的DFT(其中H[k]是在DFT的结果上乘以了一个系数因子
W_N^k ，其中k取值0到N/2-1) 　　这就意味着，我们通过FFT把一个阶为N的DFT分解为了两个阶为N/2的DFT，并在这个过程中减少了一半的计算量　　显然，我们可以对分解后的两个DFT分别再继续分解下去(作图的话是一个标准的2叉树结构)如此，即得到FFT算法　　虽然理论已经分析完毕，但是实际实现还是会有不少问题，首先，FFT是一个递归形式，由于递归涉及到入栈出栈，参数传递等，通常效率较低；最理想的自然是非递归实现；同时空间复杂度希望尽可能低。　　笔者研究之后给出了如下比较理想的实现，测试已经通过，读者可以参考:https://github.com/wiltchamberian/FFT-Algorithm

2024fft算法的基本原理

相关推荐