06. 快速傅里叶变换

快速傅里叶变换

快速傅里叶变换（FFT）是一种计算离散傅里叶变换的算法，其独有的计算方式能够大幅度减小离散傅里叶变换的计算量，使得离散傅里叶变换在计算机上具有可实现性。

离散傅里叶变换的计算量

回顾离散傅里叶变换：
\[X[k]=\sum_{n=0}^{N-1}x[n]W^{kn}_N\] 可以发现，计算一个离散傅里叶变换需要计算：
1. N个\(x[n]W\)，即N次复数乘法 2. N-1次\(x[i]W+x[i+1]W\)，即(N-1)次复数加法

根据复数乘法原则\((a+jb)(c+jd)=(ac-bd)+j(ad+bc)\)，和复数加法原则\((a+jb)+(c+jd)=(a+c)+j(b+d)\)，可以发现：1次复数乘法与4个实数乘法和2个实数加法等价；1次复数加法和2次实数加法等价。
因此计算一次离散傅里叶变换需要计算：
1. \(4N^2\)次实数乘法 2. \(4N^2-2N\)次实数加法

其中实数乘法对计算资源的消耗非常的大，因此考虑使用别的算法以简化实数乘法的次数。

时域抽取的快速傅里叶变换

将离散傅里叶变换分为奇数和偶数两个段落：
\[\begin{aligned} X[k]&=\sum_{r=0}^{\frac{N}{2}-1}x[2r]W^{2rk}_N+\sum_{r=0}^{\frac{N}{2}-1}x[2r+1]W^{(2r+1)k}_N\\ &=\sum_{r=0}^{\frac{N}{2}-1}x[2r]W^{2rk}_N+W_N^{k}\sum_{r=0}^{\frac{N}{2}-1}x[2r+1]W^{2rk}_N \end{aligned}\] 根据复数的共轭对称性质：\(W_N^{k(N-n)}=W_N^{kN}W^{-kn}_N=W^{-kn}_N\)，前半段（\(0-N/2\)）的表达式可以写作：
\[X[k]=\sum_{r=0}^{\frac{N}{2}-1}x[2r]W^{rk}_{N/2}+W_N^k\sum_{r=0}^{\frac{N}{2}-1}x[2r+1]W^{rk}_{N/2}\] 令\(G[k]=\sum_{r=0}^{\frac{N}{2}-1}x[2r]W^{rk}_{N/2}\)，\(H[k]=\sum_{r=0}^{\frac{N}{2}-1}x[2r+1]W^{rk}_{N/2}\):
\[X[k]=G[k]+W^k_NH[k],k=0,1,..,N-1\] 将前半段式子的下标加上\(N/2\)考虑后半段式子的和，由于\(W_N^{k+N/2}=-1\)，因此：
\[X[k+N/2]=G[k]-W^k_NH[k],k=0,1,..,N-1\] 综合两段，得到时域抽取的快速傅里叶变换：
\[X[k]=G[k]+W^k_NH[k],k=0,1,..,N/2-1\] \[X[k+N/2]=G[k]-W^k_NH[k],k=0,1,..,N/2-1\] 上述式子称为蝶式结构，用图示可以表示为：

可以将整个序列继续折中细分成多个小部分，每个部分计算蝶形结构。在\(N\)为2的次方数时，使用折中法正好可以使得最终细分到相邻的奇偶两项做蝶形结构运算：

比如\(N=8\)时就可以通过折中法多次两两分组，每组内部进行蝶形运算后的结果再进行蝶形运算：

其中最低一级的分组通过如下方式进行：

蝶形结构运算

观察整个快速傅里叶变换的结构：

可以得出如下结论：
1. 对于\(N=2^m\)，需要\(m\)级次蝶形结构的运算。
2. 对于第\(m\)级运算，组数为\(2^N-m-1\)。每一组的\(q\)总是被赋予\(-1\)和权重，权重表示为：
\[W_{2^{m+1}}^r,r=0,1,2,..,2^m-1\] <

注意计算之前首先得按照比特反转的方法对序列进行重排序。

快速傅里叶变换的计算量

由于一点蝶形运算中不包含乘法，快速傅里叶变换通过应用这样的蝶形结构来削减乘法计算的次数。当长度\(N=2^m\)时，简单分析可得快速傅里叶变换的计算量：
\[\frac{N^2}{2^m}+m\frac{N}{2}=N+\frac{N}{2}log_2N\]

频域抽取的快速傅里叶变换

在频域内对离散傅里叶变换进行拆分，可以得到：
\[\begin{aligned} X[2r]=&∑_{n=0}^{N/2-1}x[n]W_N^{2nr}+∑_{n=0}^{N/2-1}x[n+N/2]W^{2r(n+N/2)}_N\\ =&∑_{n=0}^{N/2-1}[x[n]+x[n+N/2]]W^{rn}_{N/2},r=0,1,..,N/2-1 \end{aligned}\] 同理对于频域内的奇数序列有：
\[X[2r+1]=[x[n]-x[n+N/2]]W^{rn}_{N/2},r=0,1,..,N/2-1\] 令\(g[n]=x[n]+x[n+N/2]\),\(h[n]=x[n]-x[n+N/2]\)，得到频域抽取的快速傅里叶变换：
\[X[2r]=∑_{n=0}^{N/2-1}g[n]W_{N/2}^{rn}\] \[X[2r+1]=W_N^n∑_{n=0}^{N/2-1}h[n]W_{N/2}^{rn},r=0,1,..,N/2-1\] 同样符合蝶形结构：