我们先从DFT说起,假设我要做N点的DFT,
\[X(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N}n}\]
为了简化书写,我们令
\[W_N=e^{-j\frac{2\pi}{N}}\]
于是刚刚的式子就可以写为
\[X(k)=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N}n}=\sum_{n=0}^{N-1}x[n]W_N^{kn}\]
算出一个频点需要计算N次乘法,计算出一整个频谱则需要重复N次,所以DFT的时间复杂度为\(O(N^2)\)
现在我们希望进行优化,如果我们把N点的DFT分解为两个\(\frac{N}{2}\)的DFT,那么我们的复杂度从\(N^2\)变成了\(2(\frac{N}{2})^2=\frac{N^2}{2}\),复杂度在下降,不过它并不是没有花销的,它的花销在于拆分和重建,但是不会是\(N^2\)的级别.并且这样的分解还可以继续往下.这样的思路在快速排序中也有使用.最后的复杂度会下降到\(O(NlogN)\).
我们按照N的奇偶性来进行拆分,于是
\[\begin{aligned}X(k)&=\sum_{n_{even}}^{N-1}x[n]W_N^{kn}+\sum_{n_{odd}}^{N-1}x[n]W_N^{kn}=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_N^{2kn}+\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_N^{k(2n+1)}\\&=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_N^{2kn}+W_N^k\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_N^{2kn}\end{aligned}\]
第二项前的系数\(W_N^k\)叫做Twindle Factor.而
\[W_N^{2kn}=e^{-j\frac{2\pi}{N}2kn}=e^{-j\frac{4\pi}{N}kn}=e^{-j\frac{2\pi}{\frac{N}{2}}kn}=W_{\frac{N}{2}}^{kn}\]
所以原式为
\[\begin{aligned}X(k)&=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_{\frac{N}{2}}^{kn}+W_N^k\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_{\frac{N}{2}}^{kn}\end{aligned}\]
这样我们就完成了第一步.我们的DFS从原来的N点变成了两个\(\frac{N}{2}\)点.而
\[X(k+\frac{N}{2})=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_{\frac{N}{2}}^{(k+\frac{N}{2})n}+W_N^{k+\frac{N}{2}}\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_{\frac{N}{2}}^{(k+\frac{N}{2}))n}\]
而
\[W_{\frac{N}{2}}^{(k+\frac{N}{2})n}=W_{\frac{N}{2}}^{kn}\cdot W_{\frac{N}{2}}^{\frac{Nn}{2}}=W_{\frac{N}{2}}^{kn}\cdot W_N^{Nn}=W_{\frac{N}{2}}^{kn}\]
代入上式可得
\[X(k+\frac{N}{2})=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_{\frac{N}{2}}^{kn}+W_N^{\frac{N}{2}}W_N^{k}\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_{\frac{N}{2}}^{kn}=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_{\frac{N}{2}}^{kn}-W_N^{k}\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_{\frac{N}{2}}^{kn}\]
现在令
\[X_1[k]=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_{\frac{N}{2}}^{kn},X_2{[k]}=\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_N^{2kn}\]
于是可以得到
\[X(k)=X_1[k]+W_N^kX_2{[k]},X(k+\frac{N}{2})=X_1[k]-W_N^kX_2{[k]}\]
]
这样就建立起了相距\(\frac{N}{2}\)的频点的关系.然后我可以一直重复这个操作,直到遍历过整个信号
而每一个\(\alpha\)都是\(\frac{N}{2}\)个点的DFT,于是就可以往下推广.
以\(N=8\)为例子,我们可以画出如下的图:

这个图实际上是从右往左画的.现在输出顺序已经排序好了,但是输入可不能这么排,回到上面的式子
\[\begin{cases}\alpha_1^{(k)}=\sum_{n=0}^{\frac{N}{2}-1}x[2n]W_{\frac{N}{2}}^{kn}\\\alpha_2^{(k)}=\sum_{n=0}^{\frac{N}{2}-1}x[2n+1]W_N^{2kn}\end{cases}\Rightarrow \begin{cases}X(k)=\alpha_1^{(k)}+W_N^k\alpha_2^{(k)}\\X(k+\frac{N}{2})=\alpha_1^{(k)}-W_N^k\alpha_2^{(k)}\end{cases}\]
我的\(X(k)\)是前四个,由\(\alpha_1\)和\(\alpha_2\)组成的,\(\alpha_1\)对应偶数序列,从图上可以看出,是前一阶段的前四个,\(\alpha_2\)对应奇数序列,对应前一阶段的后四个.所以上一阶段的顺序为0,2,4,6,1,3,5,7.现在被分为上下两组:0,2,4,6和1,3,5,7.再往前推:0,2,4,6分为奇数位和偶数位,偶数位0,4在上,奇数位2,6在下.1,3,5,7偶数位1,5在上,奇数位3,7在下,而1,3,5,7在0,2,4,6的下部,所以最后的顺序是0,4,2,6,1,5,3,7.

从这里也说明一个问题,只有当点数是2的幂次的时候,FFT的效率才会高.
那么这一步困难吗?如果困难的化,它的实用性就大打折扣了.但是幸运的是,它并不困难.
左边和右边的顺序进行二进制的对应
\[\begin{gather}000\Leftrightarrow 000\\001\Leftrightarrow100\\010\Leftrightarrow010\\011\Leftrightarrow110\\100\Leftrightarrow001\\101\Leftrightarrow101\\110\Leftrightarrow011\\111\Leftrightarrow111\end{gather}\]
显然,规律是明确的,只需要把输入和输出按比特位进行翻转就可以(以中间数为轴进行对称).
现在只剩了一个问题:我们为什么要用奇偶数来进行分划.
#不懂
我们考虑四点的FFT

结果为
\[\begin{gather}X_0(0)=x[0]+W_2^0x[2]=x[0]+x[2]\\ X_0(2)=x[0]-W_2^0x[2]=x[0]-x[2]\\ X_0(1)=x[1]+W_2^0x[3]=x[1]+x[3]\\ X_0(3)=x[1]-W_2^0x[3]=x[1]-x[3]\\ \end{gather}\Rightarrow \begin{cases} X(0)=X_0(0)+W_4^0X_0(1)=x[0]+x[1]+x[2]+x[3]\\ X(1)=X_0(2)+W_4^1X_0(3)=x[0]-x[2]-j(x[1]-x[3])\\ X(2)=X_0(0)-W_4^0X_0(1)=x[0]-x[1]+x[2]-x[3]\\ X(3)=X_0(2)-W_4^1X_0(3)=x[0]-x[2]+j(x[1]-x[3]) \end{cases}\]
通常来说,如果我们的点不是2的整数次幂,我们会进行补零,但是这样做效率有点低,所以有时我们需要考虑n=pq的情况.这叫做分裂基.考虑\(0\leq a\leq p-1,0\leq b\leq q-1\),
\[X(aq+b)=\sum_{m=0}^{p-1}\sum_{n=0}^{q-1}x(np+m)W_N^{(aq+b)(np+m)}\]
#不懂

