快速傅里叶变换——理论

本文公式较多，欢迎大家勘误

1.周期离散信号的傅里叶变换

离散信号傅里叶变换的公式如下所示：

$X(e^{jw}) = \sum\limits^{+\infty}_{n = -\infty}{x[n] \times e^{-jwn}}$
离散傅里叶变换的原理是将原本非周期的信号复制扩展为周期信号，在实际的数字电路处理中，处理的信号是有限长的，取长度为N，即N为信号 $x[n]$ 的周期，对于有限长周期信号，其离散傅里叶变换有如下性质：
$X(e^{jw}) = \sum\limits_{k=-\infty}^{+\infty}{2\pi a_k\delta(w-\frac{2\pi k}{N})}$
其中 $a_k$ 为周期信号的傅里叶级数，而 $\delta(w-\frac{2\pi k}{N})$ 表示当且仅当 $w = \frac{2\pi k}{N},k=0,1,2,...$ 时有 $X(e^{jw}) \neq 0$ ，因此可以将傅里叶变换转为离散表达，如下所示：
$F[k] = X(e^{j\frac{2\pi}{N}k}) = \sum\limits_{n=0}^{N-1}{x[n] \times e^{-j\frac{2\pi}{N}nk}}$
考虑 $e^{j\frac{2\pi}{N}k}$ 以N为周期，因此仅需要计算k从0到N-1即可，取 $W_N^{k,n} = e^{-j\frac{2\pi}{N}nk}$ 此公式写成矩阵乘法模式如下所示：
$F = \left[\begin{matrix} F[0] \\ F[1] \\ ... \\ F[N-1] \end{matrix}\right] = \left[\begin{matrix} W_N^{0,0} & W_N^{0,1} & ... & W_N^{0,N-1} \\ W_N^{1,0} & W_N^{1,1} & ... & W_N^{1,N-1} \\ ... & ... & ... & ... \\ W_N^{N-1,0} & W_N^{N-1,1} & ... & W_N^{N-1,N-1} \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[1] \\ ... \\ x[N-1] \end{matrix}\right] = W \times X \\ W = \left[\begin{matrix} W_N^{0,0} & W_N^{0,1} & ... & W_N^{0,N-1} \\ W_N^{1,0} & W_N^{1,1} & ... & W_N^{1,N-1} \\ ... & ... & ... & ... \\ W_N^{N-1,0} & W_N^{N-1,1} & ... & W_N^{N-1,N-1} \end{matrix}\right],X = \left[\begin{matrix} x[0] \\ x[1] \\ ... \\ x[N-1] \end{matrix}\right]$
W为一个 $N \times N$ 的方阵，该计算的复杂度为 $O(N^2)$

2.快速傅里叶变换（分治法）

2.1.系数W性质

对于系数矩阵中的元素 $W_N^{k,n}$ ，其公式如下所示：
$W_N^{k,n} = e^{-j\frac{2\pi}{N}nk}$
考虑 $W^{k,n+\frac{N}{2}}$ ，推导公式如下所示：
$W^{k,n+\frac{N}{2}} = e^{-j\frac{2\pi}{N}k(n + \frac{N}{2})} = e^{-j\frac{2\pi}{N}nk} \times e^{-j\frac{2\pi}{N}k\frac{N}{2}} = e^{-j\frac{2\pi}{N}nk} \times e^{-j\pi k} = e^{-j\frac{2\pi}{N}nk} \times (-1)^k$
再考虑 $k=2r$ 和 $n=2m$ 的情况：
$W_N^{2r,n} = e^{-j\frac{2\pi}{N}2nr} = e^{-j\frac{2\pi}{\frac{N}{2}}nr} = W_{\frac{N}{2}}^{r,n} \\ W_N^{k,2m} = e^{-j\frac{2\pi}{N}2mk} = e^{-j\frac{2\pi}{\frac{N}{2}}mk} = W_{\frac{N}{2}}^{k,m}$
再考虑 $k = 2r + 1$ 和 $n=2m+1$ 的情况：
$W_N^{2r+1,n} = e^{-j\frac{2\pi}{N}2nr} \times e^{-j\frac{2\pi}{N}n} = W_{\frac{N}{2}}^{r,n} \times e^{-j\frac{2\pi}{N}n} \\ W_N^{k,2m+1} = e^{-j\frac{2\pi}{N}2mk} \times e^{-j\frac{2\pi}{N}k} = W_{\frac{N}{2}}^{k,m} \times e^{-j\frac{2\pi}{N}k}$
最后考虑 $k = r + \frac{N}{2}$ 且 $n=2m$ 或 $n = 2m+1$ 的情况：
$W_{N}^{r+\frac{N}{2},2m} = e^{-j\frac{2\pi}{N}2m(r+\frac{N}{2})} = e^{-j\frac{2\pi}{\frac{N}{2}}mr} \times e^{-j\frac{2\pi}{N}\times\frac{N}{2} \times 2m} = W_{\frac{N}{2}}^{r,m} \times e^{-j2\pi n} = W_{\frac{N}{2}}^{r,m} \\ W_{N}^{r+\frac{N}{2},2m+1} = e^{-j\frac{2\pi}{N}(2m+1)(r+\frac{N}{2})} = (e^{-j\frac{2\pi}{\frac{N}{2}}mr} \times e^{-j\frac{2\pi}{N}\times\frac{N}{2} \times 2m}) \times e^{-j\frac{2\pi}{N}(r+\frac{N}{2})} = W_{\frac{N}{2}}^{r,m} \times e^{-j\frac{2\pi}{N}r} \times e^{-j\pi} = -e^{-j\frac{2\pi}{N}r} \times W_{\frac{N}{2}}^{r,m}$
根据上述推导，可以得出系数W具有以下四条性质，这三条性质会在后续推导中用到：

$W^{k,n+\frac{N}{2}} = W_N^{k,n} \times (-1)^k$
$W_N^{2r,n} = W_{\frac{N}{2}}^{r,n}$ ，同理有 $W_N^{k,2m} = W_{\frac{N}{2}}^{k,m}$
$W_N^{2r+1,n} = W_{\frac{N}{2}}^{r,n} \times e^{-j\frac{2\pi}{N}n}$ ，同理有 $W_N^{k,2m+1}= W_{\frac{N}{2}}^{k,m} \times e^{-j\frac{2\pi}{N}k}$
$W_{N}^{k+\frac{N}{2},n} =-W_N^{k,n}$ 和 $W_{N}^{r+\frac{N}{2},2m+1}=-e^{-j\frac{2\pi}{N}r} \times W_{\frac{N}{2}}^{r,m}$

2.2.频域抽取基2快速傅里叶变换

基n快速傅里叶变换用于一个长度N为 $n^m$ 的序列，例如基2快速傅里叶作用在 $N=2^m$ 的序列上，基4快速傅里叶作用在 $N=4^m$ 的序列上。现在考虑基2FFT的推导（硬件实现一般使用基4或基8FFT实现），首先写出有限长离散序列的傅里叶变换，记一个信号 $x[n]$ 的FFT变换为 $FFT(x[n])$ ：
$F[k] = FFT(x[n]) = \sum\limits_{n=0}^{N-1}{x[n] \times W_{N}^{k,n}}$
快速傅里叶变换的核心思想为分而治之，即分治法，该思想的核心是将一个长度为N的问题，分级为两个长度为 $\frac{N}{2}$ 的问题，应用在这里即是需要将一个序列长度为N的FFT变换问题分解为两个序列长度为 $\frac{N}{2}$ 的FFT变换。首先进行如下变换：
$F[k] = \sum\limits_{n=0}^{N-1}{x[n] \times W_N^{k,n}} = \sum\limits_{n=0}^{\frac{N}{2} - 1}{x[n] \times W_N^{k,n}} + \sum\limits_{n=0}^{\frac{N}{2} - 1}{x[n+\frac{N}{2}] \times W_N^{k,n+\frac{N}{2}}}$
矩阵的形式如下所示：
$F = \left[\begin{matrix} W_N^{0,0} & W_N^{0,1} & ... & W_N^{0,N-1} \\ W_N^{1,0} & W_N^{1,1} & ... & W_N^{1,N-1} \\ ... & ... & ... & ... \\ W_N^{N-1,0} & W_N^{N-1,1} & ... & W_N^{N-1,N-1} \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[1] \\ ... \\ x[N-1] \end{matrix}\right] \\ = \left[\begin{matrix} W_N^{0,0} & W_N^{0,1} & ... & W_N^{0,N/2-1} \\ W_N^{1,0} & W_N^{1,1} & ... & W_N^{1,N/2-1} \\ ... & ... & ... & ... \\ W_N^{N-1,0} & W_N^{N-1,1} & ... & W_N^{N-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[1] \\ ... \\ x[N/2-1] \end{matrix}\right] + \left[\begin{matrix} W_N^{0,N/2} & W_N^{0,N/2+1} & ... & W_N^{0,N-1} \\ W_N^{1,N/2} & W_N^{1,N/2+1} & ... & W_N^{1,N-1} \\ ... & ... & ... & ... \\ W_N^{N-1,N/2} & W_N^{N-1,N/2+1} & ... & W_N^{N-1,N-1} \end{matrix}\right] \times \left[\begin{matrix} x[N/2] \\ x[N/2+1] \\ ... \\ x[N-1] \end{matrix}\right]$
根据W的性质 $W^{k+\frac{N}{2},n} = e^{-j\frac{2\pi}{N}nk} \times (-1)^k$ ，代入后有：
$F[k] = \sum\limits_{n=0}^{\frac{N}{2} - 1}{x[n] \times W_N^{k,n}} +\sum\limits_{n=0}^{\frac{N}{2} - 1}{(-1)^n \times x[n+\frac{N}{2}] \times W_N^{k,n+\frac{N}{2}}} = \sum\limits_{n=0}^{\frac{N}{2} - 1}{W_N^{k,n}[x[n] + (-1)^kx[n+\frac{N}{2}]]}$
矩阵形式的表达如下所示，现在的矩阵为两个个高度为N，长度为N/2的矩阵。
$F = \left[\begin{matrix} W_N^{0,0} & W_N^{0,1} & ... & W_N^{0,N/2-1} \\ W_N^{1,0} & W_N^{1,1} & ... & W_N^{1,N/2-1} \\ ... & ... & ... & ... \\ W_N^{N-1,0} & W_N^{N-1,1} & ... & W_N^{N-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[1] \\ ... \\ x[N/2-1] \end{matrix}\right] + \left[\begin{matrix} W_N^{0,0} & W_N^{0,1} & ... & W_N^{0,N/2-1} \\ -W_N^{1,0} & -W_N^{1,1} & ... & -W_N^{1,N/2-1} \\ ... & ... & ... & ... \\ -W_N^{N-1,0} & -W_N^{N-1,1} & ... & -W_N^{N-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[N/2] \\ x[N/2+1] \\ ... \\ x[N-1] \end{matrix}\right]$
代入 $k=2r$ ，根据W的性质 $W_N^{2r,n} = W_{\frac{N}{2}}^{r,n}$ 有：
$F[2r] = \sum\limits_{n=0}^{\frac{N}{2} - 1}{W_N^{2r,n}[x[n] + x[n+\frac{N}{2}]]} = \sum\limits_{n=0}^{\frac{N}{2} - 1}{W_{\frac{N}{2}}^{r,n}[x[n] + x[n+\frac{N}{2}]]} = FFT(x[n] + x[n+\frac{N}{2}])$
矩阵表达如下所示：
$F_0 = \left[\begin{matrix} F[0] \\ F[2] \\ ... \\ F[N-2] \end{matrix}\right] = \left[\begin{matrix} W_{N/2}^{0,0} & W_{N/2}^{0,1} & ... & W_{N}^{0,N/2-1} \\ W_{N/2}^{1,0} & W_{N/2}^{1,1} & ... & W_{N}^{1,N/2-1} \\ ... & ... & ... & ... \\ W_{N/2}^{N/2-1,0} & W_{N/2}^{N/2-1,1} & ... & W_{N}^{N/2-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[0]+x[N/2] \\ x[1]+x[N/2+1] \\ ... \\ x[N/2-1] + x[N-1] \end{matrix}\right]$
代入 $k=2r+1$ ，根据W的性质 $W_N^{2r+1,n} = W_{\frac{N}{2}}^{r,n} \times e^{-j\frac{2\pi}{N}n}$ 有：
$F[2r+1] = \sum\limits_{n=0}^{\frac{N}{2} - 1}{W_N^{2r+1,n}[x[n] -x[n+\frac{N}{2}]]} = \sum\limits_{n=0}^{\frac{N}{2} - 1}{W_{\frac{N}{2}}^{r,n} \times e^{-j\frac{2\pi}{N}n}[x[n] - x[n+\frac{N}{2}]]} = FFT(e^{-j\frac{2\pi}{N}n}[x[n] - x[n+\frac{N}{2}]])$
矩阵表达如下所示：
$F_1 = \left[\begin{matrix} F[1] \\ F[3] \\ ... \\ F[N-1] \end{matrix}\right] = \left[\begin{matrix} W_{N/2}^{0,0} & W_{N/2}^{0,1} & ... & W_{N}^{0,N/2-1} \\ W_{N/2}^{1,0} & W_{N/2}^{1,1} & ... & W_{N}^{1,N/2-1} \\ ... & ... & ... & ... \\ W_{N/2}^{N/2-1,0} & W_{N/2}^{N/2-1,1} & ... & W_{N}^{N/2-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[0]-x[N/2] \\ e^{-j\frac{2\pi}{N}} \times (x[1]-x[N/2+1]) \\ ... \\ e^{-j\frac{2\pi}{N}(N/2-1)} \times (x[N/2-1] - x[N-1]) \end{matrix}\right]$
根据上述推导，一个长度为N点的离散傅里叶变换被变为一个长度为 $\frac{N}{2}$ 的离散傅里叶变换，取 $W_N^n = e^{-j\frac{2\pi}{N}n}$ 公式如下所示：
$FFT(x)[k] = \begin{cases} FFT(x_0)[k/2] & k\%2==0 \\ FFT(x_1)[(k-1)/2] & k\%2==1 \end{cases} \\ x_0[n] = x[n] + x[n+\frac{N}{2}],x_1[n] = W_N^n[x[n] - x[n+\frac{N}{2}]],W_N^n = e^{-j\frac{2\pi}{N}n}$

2.3.时域抽取基2快速傅里叶变换

根据频域抽取基2FFT的算法，除了按前后分类外，还可以直接按奇偶进行分类，公式如下所示：
$F[k] = \sum\limits_{n=0}^{\frac{N}{2}-1}{x[2n] \times W_N^{k,2n}} + \sum\limits_{n=0}^{\frac{N}{2}-1}{x[2n+1] \times W_N^{k,2n+1}}$
对应的矩阵表示为：
$F = \left[\begin{matrix} W_N^{0,0} & W_N^{0,2} & ... & W_N^{0,N-2} \\ W_N^{1,0} & W_N^{1,2} & ... & W_N^{1,N-2} \\ ... & ... & ... & ... \\ W_N^{N-1,0} & W_N^{N-1,2} & ... & W_N^{N-1,N-2} \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[2] \\ ... \\ x[N-2] \end{matrix}\right] + \left[\begin{matrix} W_N^{0,1} & W_N^{0,3} & ... & W_N^{0,N-1} \\ W_N^{1,1} & W_N^{1,3} & ... & W_N^{1,N-1} \\ ... & ... & ... & ... \\ W_N^{N-1,1} & W_N^{N-1,3} & ... & W_N^{N-1,N-1} \end{matrix}\right] \times \left[\begin{matrix} x[1] \\ x[3] \\ ... \\ x[N-1] \end{matrix}\right]$
取序列 $x_0[n] = x[2n]$ ， $x_1[n]=x[2n+1]$ 代入上述表达式，取 $k < \frac{N}{2}$ 再代入W的变换性质可得：
$F[k] = \sum\limits_{n=0}^{\frac{N}{2}-1}{x_0[n] \times W_N^{k,2n}} + \sum\limits_{n=0}^{\frac{N}{2}-1}{x_1[n] \times W_N^{k,2n+1}} \\ = \sum\limits_{n=0}^{\frac{N}{2}-1}{x_0[n] \times W_{\frac{N}{2}}^{k,n}} + e^{-j\frac{2\pi}{N}k} \sum\limits_{n=0}^{\frac{N}{2}-1}{x_1[n] \times W_{\frac{N}{2}}^{k,n}},k=0,1,...,\frac{N}{2} - 1$
其对应的矩阵为：
$F_0 = \left[\begin{matrix} F[0] \\ F[1] \\ ... \\ F[N/2-1] \end{matrix}\right] = \left[\begin{matrix} W_{N/2}^{0,0} & W_{N/2}^{0,2} & ... & W_{N/2}^{0,N/2-1} \\ W_{N/2}^{1,0} & W_{N/2}^{1,2} & ... & W_{N/2}^{1,N/2-1} \\ ... & ... & ... & ... \\ W_{N/2}^{N/2-1,0} & W_{N/2}^{N/2-1,2} & ... & W_{N/2}^{N/2-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[2] \\ ... \\ x[N-2] \end{matrix}\right] \\ + e^{-j\frac{2\pi}{N}k} \times \left[\begin{matrix} W_{N/2}^{0,0} & W_{N/2}^{0,2} & ... & W_{N/2}^{0,N/2-1} \\ W_{N/2}^{1,0} & W_{N/2}^{1,2} & ... & W_{N/2}^{1,N/2-1} \\ ... & ... & ... & ... \\ W_{N/2}^{N/2-1,0} & W_{N/2}^{N/2-1,2} & ... & W_{N/2}^{N/2-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[1] \\ x[3] \\ ... \\ x[N-1] \end{matrix}\right]$
即将对F[k]的上半部分结果分解为两个FFT结果的和，即：
$F_0[k] = FFT(x_0)[k] + e^{-j\frac{2\pi}{N}k}\times FFT(x_1)[k],k=0,1,...,\frac{N}{2}-1$
现在考虑F[k]的下半部分，公式如下所示：
$F[k] = \sum\limits_{n=0}^{\frac{N}{2}-1}{x_0[n] \times W_N^{k,2n}} + \sum\limits_{n=0}^{\frac{N}{2}-1}{x_1[n] \times W_N^{k,2n+1}},k=\frac{N}{2},\frac{N}{2}+1,...,N-1$
取 $k=i+\frac{N}{2}$ ，代入有：
$F[i+\frac{N}{2}] = \sum\limits_{n=0}^{\frac{N}{2}-1}{x_0[n] \times W_N^{i+N/2,2n}} + \sum\limits_{n=0}^{\frac{N}{2}-1}{x_1[n] \times W_N^{i+N/2,2n+1}},i=0,1,...,\frac{N}{2}-1$
代入W的性质 $W_{N}^{k+\frac{N}{2},n} =-W_N^{k,n}$ 和 $W_{N}^{r+\frac{N}{2},2m+1}=-e^{-j\frac{2\pi}{N}r} \times W_{\frac{N}{2}}^{r,m}$ ，有：
$F[i+\frac{N}{2}] = \sum\limits_{n=0}^{\frac{N}{2}-1}{x_0[n] \times W_{\frac{N}{2}}^{i,n}} - e^{-j\frac{2\pi}{N}i} \sum\limits_{n=0}^{\frac{N}{2}-1}{x_1[n] \times W_{\frac{N}{2}}^{i,n}},i=0,1,...,\frac{N}{2}-1$
将变量i更换为k，其矩阵形式为：
$F_1 = \left[\begin{matrix} F[N/2] \\ F[N/2+1] \\ ... \\ F[N-1] \end{matrix}\right] = \left[\begin{matrix} W_{N/2}^{0,0} & W_{N/2}^{0,2} & ... & W_{N/2}^{0,N/2-1} \\ W_{N/2}^{1,0} & W_{N/2}^{1,2} & ... & W_{N/2}^{1,N/2-1} \\ ... & ... & ... & ... \\ W_{N/2}^{N/2-1,0} & W_{N/2}^{N/2-1,2} & ... & W_{N/2}^{N/2-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[2] \\ ... \\ x[N-2] \end{matrix}\right] \\ - e^{-j\frac{2\pi}{N}k} \times \left[\begin{matrix} W_{N/2}^{0,0} & W_{N/2}^{0,2} & ... & W_{N/2}^{0,N/2-1} \\ W_{N/2}^{1,0} & W_{N/2}^{1,2} & ... & W_{N/2}^{1,N/2-1} \\ ... & ... & ... & ... \\ W_{N/2}^{N/2-1,0} & W_{N/2}^{N/2-1,2} & ... & W_{N/2}^{N/2-1,N/2-1} \end{matrix}\right] \times \left[\begin{matrix} x[1] \\ x[3] \\ ... \\ x[N-1] \end{matrix}\right]$
最终可以将结果汇总为：
$FFT(x)[k] = \begin{cases} FFT(x_0)[k] + W_N^k\times FFT(x_1)[k]& k<\frac{N}{2} \\ FFT(x_0)[k] - W_N^k\times FFT(x_1)[k]& k\geq\frac{N}{2}\end{cases} \\ x_0[n] = \{x[n] | n\%2=0\},x_1[n] = \{x[n] | n \%2=1\},W_N^k = e^{-j\frac{2\pi}{N}k}$

3.快速傅里叶变换的实现

3.1.蝶形运算

蝶形运算的公式如下，蝶形运算输入为 $X_0$ 和 $X_1$ ，输出为 $Y_0$ 和 $Y_1$ ，系数为 $W$ ：
$\begin{cases}Y_0 = X_0 + W \times X_1 \\ Y_1 = X_0 - W \times X_1 \end{cases}$
其转换为矩阵表达为：
$\left[\begin{matrix}Y_0 \\ Y_1 \end{matrix}\right] = \left[\begin{matrix} 1 & W \\ 1 & -W \end{matrix}\right] \times \left[\begin{matrix}X_0 \\ X_1\end{matrix}\right]$
蝶形公式对应着2点FFT的计算，2点FFT的计算如下所示：
$X[0] = x[0] \times W_2^{0,0} + x[1] \times W_2^{0,1},W_2^{0,0} = e^{-j\frac{2\pi}{2}\times 0} = 1,W_2^{0,1} = e^{-j\frac{2\pi}{2}\times 0} = 1 \\ X[1] = x[0] \times W_2^{1,0} + x[1] \times W_2^{1,1},W_2^{1,0} = e^{-j\frac{2\pi}{2} \times 0} = 1 ,W_2^{1,1} = e^{-j\frac{2\pi}{2}} = -1$
转换为矩阵表达为：
$\left[\begin{matrix}X[0] \\ X[1] \end{matrix}\right] = \left[\begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix}\right] \times \left[\begin{matrix}x[0] \\ x[1]\end{matrix}\right]$
对应到蝶形运算有：
$Y_0 = X[0],Y_1 = X[1],X_0 = x[0],X_1 = x[1],W=1$

3.2.频域抽取基2FFT的实现

首先列出基2频域抽取FFT的分治公式：
$FFT(x)[k] = \begin{cases} FFT(x_0)[k/2] & k\%2==0 \\ FFT(x_1)[(k-1)/2] & k\%2==1 \end{cases} \\ x_0[n] = x[n] + x[n+\frac{N}{2}],x_1[n] = W_N^n[x[n] - x[n+\frac{N}{2}]],W_N^n = e^{-j\frac{2\pi}{N}n}$
以一个8点FFT为例，输入序列为：
$x[0],x[1],x[2],x[3],x[4],x[5],x[6],x[7]$
进行第一次分治，分为两个4点FFT，序列为：
$X_{0,0} = \{x[0]+x[4],x[1]+x[5],x[2]+x[6],x[3]+x[7] \} \\ X_{0,1} = \{W_8^0(x[0]-x[4]),W_8^1(x[1]-x[5]),W_8^2(x[2]-x[6]),W_8^3(x[3]-x[7])\}$
示意图如下所示，偶数标号的结果由第一个FFT生成，奇数标号的结果由第二个FFT生成：

tu1.png

随后进行第二次分治，将每个4点FFT分解为两个2点FFT，每个序列为：
$X_{1,0} = \{X_{0,0}[0]+X_{0,0}[2],X_{0,0}[1]+X_{0,0}[3]\} \\ X_{1,1} = \{W_4^0(X_{0,0}[0]-X_{0,0}[2]),W_4^1(X_{0,0}[1] - X_{0,0}[3])\} \\ X_{1,2} = \{X_{0,1}[0]+X_{0,1}[2],X_{0,1}[1]+X_{0,1}[3]\} \\ X_{1,3} = \{W_4^0(X_{0,1}[0]-X_{0,1}[2]),W_4^1(X_{0,1}[1] - X_{0,1}[3])\} \\$
示意图如下所示：

tu2.png

最终通过2点FFT计算出结果，但如上图所示，计算出的结果位置与标号并不对应，例如计算输出的标号为2的数据（Y10[1]）应当位于输出序列（X）的标号4（X[4]）。其变换规律为计算输出的标号为n的数据（第n+1个数据）对应到输出序列标号为m的数据，n为m的二进制反序。以计算输出标号为6（第七个数据）的数据Y13[0]为例，6的二进制为110，反序为011，对应十进制数为3，即有 $X[3] = Y13[0]$ 。

3.3.时域抽取基2FFT的实现

首先列出时域抽取FFT的分治公式：
$FFT(x)[k] = \begin{cases} FFT(x_0)[k] + W_N^k\times FFT(x_1)[k]& k<\frac{N}{2} \\ FFT(x_0)[k] - W_N^k\times FFT(x_1)[k]& k\geq\frac{N}{2}\end{cases} \\ x_0[n] = \{x[n] | n\%2=0\},x_1[n] = \{x[n] | n \%2=1\},W_N^k = e^{-j\frac{2\pi}{N}k}$
和频域抽取不同，时域抽取为先进行FFT，再进行结果的累加。同样以8点FFT为例，要想获取8点FFT的结果，首先将其分为两个4点FFT，分别处理标号为奇数和标号为偶数的序列，示意图如下所示：

tu3.png

随后进行第二次分治，将每个4点的FFT再分解成2点FFT，示意图如下所示：

tu4.png

与频域抽取类似，时域抽取的输入序列（x）和计算输入序列（X1*）的标号不统一，二者同样存在二进制倒序的关系，例如x[1]，标号为001，二进制倒序后为100，对应十进制5，对应计算输入序列的X12[0]。

4.其他基的快速傅里叶变换

4.1.不同基下系数W的性质

对于基4的FFT，先推导W系数的性质：
$W_N^{k,n+\frac{m}{4}N} = e^{-j\frac{2\pi}{N}k(n+\frac{m}{4}N)} = e^{-j\frac{2\pi}{N}kn} \times e^{-j\frac{2\pi}{N}\times\frac{m}{4}Nk } = W_N^{k,n} \times e^{-j\frac{\pi}{2}mk}$
对于不同的m有以下情况：

m取值	等式
1	$W_N^{k,n+\frac{1}{4}N} = W_N^{k,n} \times e^{-j\frac{\pi}{2}k} = (-j)^kW_N^{k,n}$
2	$W_N^{k,n+\frac{1}{2}N} = W_N^{k,n} \times e^{-j\pi k} = (-1)^{k}W_N^{k,n}$
3	$W_N^{k,n+\frac{3}{4}N} = W_N^{k,n} \times e^{-j\frac{3\pi}{2}k} = (j)^kW_N^{k,n}$

再考虑 $k = 4r+m$ 在m取1,2,3下的情况，将 $k=4r+m$ 代入W的表达式：
$W_N^{4r+m,n} = e^{-j\frac{2\pi}{N}(4r+m)n} = e^{-j\frac{2\pi}{N/4}rn} \times e^{-j\frac{2\pi}{N}mn} = e^{-j\frac{2\pi}{N}mn} \times W_{N/4}^{r,n}$

考虑 $n = 4m+r$ 在r取1,2,3下的情况，代入：
$W_N^{k,4m+r} = e^{-j\frac{2\pi}{N}k(4m+r)} = e^{-j\frac{2\pi}{N/4}mk} \times e^{-j\frac{2\pi}{N}rk} = e^{-j\frac{2\pi}{N}rk} \times W_{N/4}^{k,m}$
考虑 $k = r + m\times \frac{N}{4}$ 且周期为 $\frac{N}{4}$ 的情况：
$W_{N/4}^{r+m\times \frac{N}{4},n} = e^{-j\frac{2\pi}{N/4}(r+m\frac{N}{4})n} = e^{-j\frac{2\pi}{N/4}rn} \times e^{-j\frac{2\pi}{N/4}mn\frac{N}{4}} =e^{-j2\pi mn} \times W_{N/4}^{r,n} = W_{N/4}^{r,n}$

4.2.基4的快速傅里叶变换

4.2.1.基4FFT蝶形运算

在实际的硬件实现中，由于每一步的结果都需要保存，对于流水线式的FFT而言，则分解的次数就是流水线的级数，此若使用基2FFT，则需要消耗大量的寄存器或RAM空间保存中间数据，因此实际ASIC实现时多使用基4的FFT和基8的FFT。首先考虑基4FFT，4点DFT的计算公式如下所示：
$X[k] = \sum\limits_{n=0}^3{W_4^{n,k}\times x[n]},W_4^{n,k} = e^{-j\frac{\pi}{2}nk}$
考虑量化系数，将其展开为矩阵模式，可以发现每个结果的计算均不包含乘法：
$X = \left[\begin{matrix} X[0] \\ X[1] \\ X[2] \\ X[3] \end{matrix}\right] = \left[\begin{matrix} W_4^{0,0} & W_4^{0,1} & W_4^{0,2} & W_4^{0,3} \\ W_4^{1,0} & W_4^{1,1} & W_4^{1,2} & W_4^{1,3} \\ W_4^{2,0} & W_4^{2,1} & W_4^{2,2} & W_4^{2,3} \\ W_4^{3,0} & W_4^{3,1} & W_4^{3,2} & W_4^{3,3} \\ \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[1] \\ x[2] \\ x[3] \end{matrix}\right] = \left[\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 &-1 & 1 & -1 \\ 1 & j & -1 & -j \\ \end{matrix}\right] \times \left[\begin{matrix} x[0] \\ x[1] \\ x[2] \\ x[3] \end{matrix}\right]$

其蝶形运算如下所示，左右分别是保持输入顺序和保持输出顺序的蝶形运算示意图：

tu5.png

4.2.2.频域抽取

现在考虑将一个长度为 $N=4^a$ 的傅里叶变换进行基4分解，首先考虑频域抽取的方法，将计算序列按先后分为四段：
$X[k] = \sum\limits_{n=0}^{\frac{N}{4}-1}{x[n] \times W_N^{k,n}} + \sum\limits_{n=0}^{\frac{N}{4}-1}{x[n+\frac{N}{4}] \times W_N^{k,n+\frac{N}{4}}} + \sum\limits_{n=0}^{\frac{N}{4}-1}{x[n+\frac{N}{2}] \times W_N^{k,n+\frac{N}{2}}}+ \sum\limits_{n=0}^{\frac{N}{4}-1}{x[n+\frac{3}{4}N] \times W_N^{k,n+\frac{3}{4}N}}$
代入W的变换性质，有：
$X[k] = \sum\limits_{n=0}^{\frac{N}{4}-1}{(x[n] + (-j)^kx[n+\frac{N}{4}] + (-1)^kx[n + \frac{N}{2}] + (j)^kx[n + \frac{3}{4}N]) \times W_N^{k,n}}$
再进行间隔抽取，代入 $k =4r+m$ 和W的性质有：
$X[4r+m] = \sum\limits_{n=0}^{\frac{N}{4}-1}{(x[n] + (-j)^{4r+m}x[n+\frac{N}{4}] + (-1)^{4r+m}x[n + \frac{N}{2}] + (j)^{4r+m}x[n + \frac{3}{4}N]) \times W_N^{4r+m,n}} \\ = \sum\limits_{n=0}^{\frac{N}{4}-1}{(x[n] + (-j)^{m}x[n+\frac{N}{4}] + (-1)^{m}x[n + \frac{N}{2}] + (j)^{m}x[n + \frac{3}{4}N]) \times e^{-j\frac{2\pi}{N}mn} \times W_{N/4}^{r,n}}$
取序列 $T_m$ ，其表达为：
$T_m[n] = (x[n] + (-j)^{m}x[n+\frac{N}{4}] + (-1)^{m}x[n + \frac{N}{2}] + (j)^{m}x[n + \frac{3}{4}N]) \times e^{-j\frac{2\pi}{N}mn},n < \frac{N}{4}$
使用矩阵形式为，其使用的系数矩阵和蝶形计算相同：
$\left[\begin{matrix} T_0[n] \\ T_1[n] \\ T_2[n] \\T_3[n] \end{matrix}\right] = \left[\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 &-1 & 1 & -1 \\ 1 & j & -1 & -j \\ \end{matrix}\right] \times \left[\begin{matrix} x[n] \\ x[n+\frac{N}{4}] \\ x[x+\frac{N}{2}] \\x[x+\frac{3N}{4}] \end{matrix}\right]$
取其FFT为：
$FFT(T_m) = \sum\limits_{n=0}^{\frac{N}{4}-1}{(x[n] + (-j)^{m}x[n+\frac{N}{4}] + (-1)^{m}x[n + \frac{N}{2}] + (j)^{m}x[n + \frac{3}{4}N]) \times e^{-j\frac{2\pi}{N}mn} \times W_{N/4}^{r,n}}$
则可获得基4的FFT递推公式，即：
$FFT(X)[k] = \begin{cases} FFT(T_0)[k/4] & k\%4=0 \\ FFT(T_1)[(k-1)/4] & k\%4=1 \\FFT(T_2)[(k-2)/4] & k\%4=2\\FFT(T_3)[(k-3)/4] & k\%4=3\end{cases}\\T_m[n] = (x[n] + (-j)^{m}x[n+\frac{N}{4}] + (-1)^{m}x[n + \frac{N}{2}] + (j)^{m}x[n + \frac{3}{4}N]) \times e^{-j\frac{2\pi}{N}mn},n < \frac{N}{4}$
以16点FFT为例，基4FFT将其分为两级实现，如下图所示：

tu6.png

4.2.3.时域抽取

对于离散傅里叶计算公式，进行间隔抽取，将 $n=4m+r$ 代入：
$X[k] = \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m]\times W_N^{k,4m}} + \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+1]\times W_N^{k,4m+1}} + \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+2]\times W_N^{k,4m+2}} + \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+3]\times W_N^{k,4m+3}}$
代入W的性质，取 $k < \frac{N}{4}$ ，有：
$X[k] = \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m]\times W_{N/4}^{k,m}} + e^{-j\frac{2\pi}{N}k} \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+1]\times W_{N/4}^{k,m}} + e^{-j\frac{2\pi}{N}2k}\sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+2]\times W_{N/4}^{k,m}} + e^{-j\frac{2\pi}{N}3k}\sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+3]\times W_{N/4}^{k,m}},k < \frac{N}{4}$
取序列 $T_r$ 有：
$T_r[n] = x[4n+r]$
代入有：
$X[k] = FFT(T_0) + e^{-j\frac{2\pi}{N}k} \times FFT(T_1) + e^{-j\frac{2\pi}{N}2k}\times FFT(T_2) + e^{-j\frac{2\pi}{N}3k}\times FFT(T_3),k < \frac{N}{4}$
现在考虑 $\frac{N}4{} \leq k < N$ 的情况，代入 $k = k + r\frac{N}{4},r=1,2,3$ 和W的性质，有：
$X[k+r\frac{N}{4}] = \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m]\times W_{N/4}^{k,m}} + e^{-j\frac{2\pi}{N}(k+r\frac{N}{4})} \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+1]\times W_{N/4}^{k,m}} \\+ e^{-j\frac{2\pi}{N}2(k+r\frac{N}{4})}\sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+2]\times W_{N/4}^{k,m}} + e^{-j\frac{2\pi}{N}3(k+r\frac{N}{4})}\sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+3]\times W_{N/4}^{k,m}},k < \frac{N}{4}$
整理可得：
$X[k+r\frac{N}{4}] = \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m]\times W_{N/4}^{k,m}} + e^{-j\frac{\pi}{2}r} e^{-j\frac{2\pi}{N}k} \sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+1]\times W_{N/4}^{k,m}} \\+ e^{-j\pi r} e^{-j\frac{2\pi}{N}2k}\sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+2]\times W_{N/4}^{k,m}} + e^{-j\frac{3\pi}{2}r} e^{-j\frac{2\pi}{N}3k}\sum\limits_{m=0}^{\frac{N}{4}-1}{x[4m+3]\times W_{N/4}^{k,m}} \\ = FFT(T_0)[k] + (-j)^re^{-j\frac{2\pi}{N}k} \times FFT(T_1)[k] + (-1)^re^{-j\frac{2\pi}{N}2k}\times FFT(T_2)[k] + (j)^re^{-j\frac{2\pi}{N}3k}\times FFT(T_3)[k],k < \frac{N}{4}$
根据上式列出矩阵形式：
$\left[\begin{matrix} X[k] \\ X[k+\frac{N}{4}] \\ X[k +\frac{N}{2}] \\X[k+\frac{3N}{4}] \end{matrix}\right] = \left[\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 &-1 & 1 & -1 \\ 1 & j & -1 & -j \\ \end{matrix}\right] \times \left[\begin{matrix} FFT(T_0)[k] \\ e^{-j\frac{2\pi}{N}k} \times FFT(T_1)[k] \\e^{-j\frac{2\pi}{N}2k} \times FFT(T_2)[k] \\e^{-j\frac{2\pi}{N}3k} \times FFT(T_3)[k] \end{matrix}\right]$
可以得到递推公式：
$X[k] = \begin{cases} FFT(T_0)[k] + e^{-j\frac{2\pi}{N}k} \times FFT(T_1)[k] +e^{-j\frac{2\pi}{N}2k}\times FFT(T_2)[k] +e^{-j\frac{2\pi}{N}3k}\times FFT(T_3)[k] & k < \frac{N}{4} \\ FFT(T_0)[k-\frac{N}{4}] -j \times e^{-j\frac{2\pi}{N}k} \times FFT(T_1)[k-\frac{N}{4}] -e^{-j\frac{2\pi}{N}2k}\times FFT(T_2)[k-\frac{N}{4}] +j\times e^{-j\frac{2\pi}{N}3k}\times FFT(T_3)[k-\frac{N}{4}] & \frac{N}{4} \leq k < \frac{N}{2} \\ FFT(T_0)[k-\frac{N}{2}] - e^{-j\frac{2\pi}{N}k} \times FFT(T_1)[k-\frac{N}{2}] +e^{-j\frac{2\pi}{N}2k}\times FFT(T_2)[k-\frac{N}{2}] - e^{-j\frac{2\pi}{N}3k}\times FFT(T_3)[k-\frac{N}{2}] & \frac{N}{2} \leq k < \frac{3N}{4} \\ FFT(T_0)[k-\frac{3N}{4}] +j \times e^{-j\frac{2\pi}{N}k} \times FFT(T_1)[k-\frac{3N}{4}] -e^{-j\frac{2\pi}{N}2k}\times FFT(T_2)[k-\frac{3N}{4}] -j\times e^{-j\frac{2\pi}{N}3k}\times FFT(T_3)[k-\frac{3N}{4}] & k>\frac{3N}{4} \\ \end{cases}$

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,378评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,356评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,702评论 0赞 342
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,259评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,263评论 5赞 371
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,036评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,349评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,979评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,469评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,938评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,059评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,703评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,257评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,262评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,485评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,501评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,792评论 2赞 345