1 前言
傅里叶变换作为一种有效的数学分析工具，应用非常广泛。网上也有比较多的文章记录快速傅里叶变换的原理，但是它们大都基于二分思想导出对应公式。在这里，采用同样的思路，力争导出一种更具通用性的分治算法。也就是说，当数据长度为2、3、5、7等等的倍数时，也能进行快速傅里叶变换。
2 离散傅里叶变换
对于序列\(x_0,x_1,…,x_N\)，其离散傅里叶变换定义如下
(2-1)
$$
X_k = \sum_{j = 0}^{N-1}x_j \exp(-\frac{2\pi kj}{N}i)
$$
而傅里叶逆变换定义如下
(2-2)
$$
x_k =\frac{1}{N} \sum_{j = 0}^{N-1}X_j \exp(\frac{2\pi kj}{N}i)
$$
上面公式中\(k = 0,1,2,…, N – 1\).
3 变换的周期性
在正式导出快速傅里叶变换的公式前，从定义上来看一个性质
(3-1)
$$
\begin{aligned}
X_{k+N} &= \sum_{j = 0}^{N-1}x_j \exp(-\frac{2\pi (k+N)j}{N}i)
\\
&= \sum_{j = 0}^{N-1}x_j (\exp(-2\pi j)\exp(-\frac{2\pi kj}{N}i))
\\
&= \sum_{j = 0}^{N-1}x_j \exp(-\frac{2\pi kj}{N}i)
\\
&= X_k
\end{aligned}
$$
同理，傅里叶逆变换可以得到类似的结果
(3-2)
$$
x_{k+N} =x_k
$$
4 快速傅里叶变换
这里假设\(N = nM\)，那么，我们就可以将序列分成\(n\)份进行计算，每一份的数据长度为\(M\)，即
(4-1)
$$
\begin{aligned}
X_k &= \sum_{j = 0}^{N-1} x_j \exp(-\dfrac{2\pi kj}{N}i)
\\
&= \sum_{j = 0}^{M-1} x_{nj} \exp(-\dfrac{2\pi k(nj)}{N}i) + \sum_{j = 0}^{M-1} x_{nj+1} \exp(-\dfrac{2\pi k(nj+1)}{N}i)
\\
&\ \ \ \ + … + \sum_{j = 0}^{M-1} x_{nj+n-1} \exp(-\dfrac{2\pi k(nj+n-1)}{N}i)
\\
&= \sum_{p = 0}^{n-1} \sum_{j = 0}^{M-1} x_{nj + p} \exp(-\dfrac{2\pi k(nj+p)}{N}i)
\\
&= \sum_{p = 0}^{n-1} \sum_{j = 0}^{M-1} x_{nj + p} (\exp(-\dfrac{2\pi kp}{N}i) \exp(-\dfrac{2\pi knj}{N}i))
\\
&= \sum_{p = 0}^{n-1} ((\exp(-\dfrac{2\pi kp}{N}i)\sum_{j = 0}^{M-1} x_{nj + p}\exp(-\dfrac{2\pi knj}{N}i))
\\
&= \sum_{p = 0}^{n-1} ((\exp(-\dfrac{2\pi kp}{N}i)\sum_{j = 0}^{M-1} x_{nj + p}\exp(-\dfrac{2\pi kj}{M}i))
\end{aligned}
$$
这里令
(4-2)
$$
G_{p,M} = \sum_{j = 0}^{M-1} x_{nj + p}\exp(-\dfrac{2\pi kj}{M}i)
\\
H_{p,M} = \frac{1}{M} \sum_{j = 0}^{M-1} X_{nj + p}\exp(\dfrac{2\pi kj}{M}i)
$$
最终可以得到
(4-3)
$$
X_k = \sum_{p = 0}^{n-1} ((\exp(-\dfrac{2\pi kp}{N}i)G_{p,M})
$$
同理，对于傅里叶逆变换，可以得到如下结论
(4-4)
$$
x_k =\frac{1}{n} \sum_{p = 0}^{n-1} ((\exp(\dfrac{2\pi kp}{N}i)H_{p,M})
$$
最终，公式(4-3)、(4-4)就是快速傅里叶变换以及逆变换的表达式，这里表示将序列分成\(n\)份来求解。而公式(4-2)中的表达式，又是范围更小的傅里叶变换，因此可根据条件对其进行再分割，进而达到降低计算次数的目的。
特别地，当\(n = 2\)时，就上网上常见的快速傅里叶变换表达式。
5 验证
可点击这里下载上面实现的c++代码：快速傅里叶变换代码
在自己电脑上，伪造了长度\(N = 143325\)的序列数据，然后测试结果如下：
使用原始定义计算耗时：52128.6ms；使用快速傅里叶变换耗时：49.5361 ms。也就说，使用快速傅里叶变换，耗时变为原来的0.00095026722375倍。当然，如果\(N\)值更大，效果越明显。
6 二维FFT
对于二维FFT，可以直接对二维数据每一行单独做FFT，然后对新的二维数据的每一列再单独FFT。而对于FFT逆变换，则按相反操作即可。