快速傅里叶变换——理论

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

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有以下情况：

再考虑

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}