快速傅里叶变换FFT推导以及运算复杂度分析

对于长度为 $N$ 的序列 $x[n]$ ，DFT公式如下
$$\begin{gathered} X[k]=\sum _{n=0}^{N-1}x[n]W_N^{kn},0⩽k⩽N-1 \\ x[n]=\frac{1}{N}\sum _{k=0}^{N-1}X[k]W_N^{-nk},0⩽n⩽N-1 \end{gathered}$$
其中

$$W_N={\mathrm{e}}^{-\mathrm{j}2\pi /N}$$
相位因子 $W_N$ 具有对称性和周期性

$$\begin{gathered} W_N^{k+N/2}=-W_N^k \\ {W}_N^{k+N}=W_N^k \end{gathered}$$
将 $X[k]$ 和 $x[n]$ 写成复数形式，则
$$X_R[k]+\mathrm{j}{X}_I[k]=\sum _{n=0}^{N-1}(x_R[n]+\mathrm{j}{x}_I[n])(\cos \frac{2\pi kn}{N}-\mathrm{j}\sin \frac{2\pi kn}{N})$$
显然
$$\begin{array}{rl}& X_R[k]=\sum _{n=0}^{N-1}(x_R[n]\cos \frac{2\pi kn}{N}+x_I[n]\sin \frac{2\pi kn}{N})\\ & X_I[k]=-\sum _{n=0}^{N-1}(x_R[n]\sin \frac{2\pi kn}{N}-x_I[n]\cos \frac{2\pi kn}{N})\end{array}$$
对于一个 $N$ 点复序列，直接求解 DFT 需要的计算次数为：
（1）计算一个 $X[k]$ 需要 $2N$ 次三角函数计算，因此计算所有 $N$ 项 $X[k]$ 需要 $2N^2$ 次三角函数计算；

（2）计算一个 $X[k]$ 需要 $4N$ 次实数乘法，因此计算所有 $N$ 项 $X[k]$ 需要 $4N^2$ 次实数乘法；

（3） $X_R[k]$ 求和每一项需要 $1$ 次实数加法，总共有 $N$ 项，求和时项与项之间需要 $N-1$ 次实数加法，因此计算一个 $X_R[k]$ 需要 $2N-1$ 次实数加法。同理 $X_I[k]$ 也需要 $2N-1$ 次实数加法。 因此计算所有 $N$ 项 $X[k]$ 需要 $N(4N-2)$ 次实数加法。

假设 $N$ 为 $2$ 的指数幂，即 $N=2^p$ 。先看 $N=8$ 的情况
$$\begin{array}{rl}X[k]& =x[0]+x[1]W_8^k+x[2]W_8^{2k}+x[3]W_8^{3k}+x[4]W_8^{4k}+x[5]W_8^k+x[6]W_8^{6k}+x[7]W_8^{7k}\\ & =x[0]+x[2]W_8^{2k}+x[4]W_8^{4k}+x[6]W_8^{6k}+(x[1]W_8^k+x[3]W_8^{3k}+x[5]W_8^{5k}+x[7]W_8^{7k})\\ & =x[0]+x[2]W_4^k+x[4]W_4^{2k}+x[6]W_4^{3k}+W_8^k(x[1]+x[3]W_4^k+x[5]W_4^{2k}+x[7]W_4^{3k})\end{array}$$
定义序列 $y[n]=x[2n]$ ，即 $y[0]=x[0]$ ， $y[1]=x[2]$ ， $y[2]=x[4]$ ， $y[3]=x[6]$ 。

定义序列 $z[n]=x[2n+1]$ ，即 $z[0]=x[1]$ ， $z[1]=x[3]$ ， $z[2]=x[5]$ ， $z[3]=x[7]$ 。

则当 $0\le k\le 3$ 时
$$\begin{gathered} Y[k]=y[0]+y[1]W_4^k+y[2]W_4^{2k}+y[3]W_4^{3k}=x[0]+x[2]W_4^k+x[4]W_4^{2k}+x[6]W_4^{3k} \\ Z[k]=z[0]+z[1]W_4^k+z[2]W_4^{2k}+z[3]W_4^{3k}=x[1]+x[3]W_4^k+x[5]W_4^{2k}+x[7]W_4^{3k} \end{gathered}$$
因此有
$$X[k]=Y[k]+W_8^{k}Z[k]$$
当 $4\le k\le 7$ 时，令 $m=k-4$ ，则
$$\begin{array}{rl}X[k]& =x[0]+x[2]W_4^k+x[4]W_4^{2k}+x[6]W_4^{3k}+W_8^k(x[1]+x[3]W_4^k+x[5]W_4^{2k}+x[7]W_4^{3k})\\ & =x[0]+x[2]W_4^{m+4}+x[4]W_4^{2(m+4)}+x[6]W_4^{3(m+4)}+W_8^{m+4}(x[1]+x[3]W_4^{m+4}+x[5]W_4^{2(m+4)}+x[7]W_4^{3(m+4)})\\ & =x[0]+x[2]W_4^m+x[4]W_4^{2m}+x[6]W_4^{3m}-W_8^m(x[1]+x[3]W_4^m+x[5]W_4^{2m}+x[7]W_4^{3m})\end{array}$$
因此有
$$X[k]=Y[k-4]-W_8^{k-4}Z[k-4]$$
综上
$$X[k]=\{\begin{array}{lc}Y[k]+W_8^{k}Z[k]& 0\le k\le 3\\ Y[k-4]-W_8^{k-4}Z[k-4]& 4\le k\le 7\end{array}$$
蝶形图如下

继续求 $y[n]$ 和 $z[n]$ 的 DFT 。

以 $y[n]$ 为例，令 $a[n]=y[2n]$ ，即 $a[0]=y[0]=x[0]$ ， $a[1]=y[2]=x[4]$ 。

令 $b[n]=y[2n+1]$ ， 即 $b[0]=y[1]=x[2]$ ， $b[1]=y[3]=x[6]$ 。

同理得到
$$y[k]=\{\begin{array}{lc}A[k]+W_4^{k}B[k]& 0\le k\le 1\\ A[k-2]-W_4^{k}B[k-2]& 2\le k\le 3\end{array}$$
$z[n]$ 的 4点 DFT 计算方法相同。

最后以 $a[n]$ 为例
$$A[k]=a[0]+a[1]W_2^k=x[0]+x[4]W_2^k$$
即
$$\begin{gathered} A[0]=x[0]+W_2^{0}x[4]=x[0]+x[4] \\ A[1]=x[0]-W_2^{0}x[4]=x[0]-x[4] \end{gathered}$$
2点 DFT 的算法相同。

完整蝶形图

对于一个 $N$ 点复序列，假设 $N=2^m$ ，使用 FFT 的计算次数为：

（1）只需要计算 $W_N^0,W_N^1,...,W_N^{N/2-1}$ 这 $N/2$ 个不同的旋转因子。而每个旋转因子对应2次三角函数运算，因此总共需要 $N$ 次三角函数计算。注意，如图8点 FFT 示例中由于 $W_2^0=W_4^0=W_8^0$ 以及 $W_4^1=W_8^2$ ，因此看作相同运算。

（2）FFT 由 $m$ 级构成。研究第 $p$ 级，则该级有 $2^{m-p}$ 个 $2^p$ 个节点的蝶形网（蝶形网定义如图）。对于 $s=2^p$ 个节点的蝶形网，有公式
$$X[k]=\{\begin{array}{lc}Y[k]+W_s^{k}Z[k]& 0\le k\le s/2-1\\ Y[k-4]-W_s^{k-4}Z[k-4]& s/2\le k\le s-1\end{array}$$
其中 $Y[k]$ 和 $Z[k]$ 是输入节点， $X[k]$ 是输出节点。

由
WpkZ[k]=(Re{Wsk}+jIm{Wsk})(Re{Z[k]}+jIm{Z[k]})=(Re{Wsk}Re{Z[k]}−Im{Wsk}Im{Z[k])+j(Re{Wsk}Im{Z[k]}+Im{Wsk}Re{Z[k]}) \begin{aligned} W_p^kZ[k]&=(Re\{W_s^k\}+\mathrm{j}Im\{W_s^k\})(Re\{Z[k]\}+\mathrm{j}Im\{Z[k]\}) \\ &=(Re\{W_s^k\}Re\{Z[k]\}-Im\{W_s^k\}Im\{Z[k])+\mathrm{j}(Re\{W_s^k\}Im\{Z[k]\}+Im\{W_s^k\}Re\{Z[k]\}) \end{aligned} Wpk​Z[k]​=(Re{Wsk​}+jIm{Wsk​})(Re{Z[k]}+jIm{Z[k]})=(Re{Wsk​}Re{Z[k]}−Im{Wsk​}Im{Z[k])+j(Re{Wsk​}Im{Z[k]}+Im{Wsk​}Re{Z[k]})​
可见运算 $W_s^{k}Z[k]$ 需要4次乘法和2次实数加法。注意后面两项 $W_s^{k}Z[k]$ 和 $W_s^{k-4}Z[k-4]$ 是相等的，因此每个蝶形网内对于 $W_s^{k}Z[k]$ 和 $W_s^{k-4}Z[k-4]$ 项需要计算 $s/2\times 4$ 次乘法以及 $s/2\times 2$ 次加法。

总乘法计算量为 $m\times 2^{m-p}\times s/2\times 4=2N{\log }_{2}N$ 。

（3）对于 $Y[k]+W_p^{k}Z[k]$ 和 $Y[k-4]-W_p^{k-4}Z[k-4]$ ，两个复数相加需要2次加法，因此总实数加法数为 $m\times 2^{m-p}\times [(s/2\times 2)+s\times 2]=3N{\log }_{2}N$ 。

总结