基本原理
设序列\(x[n]\)的长度为\(N=4^M\)，\(M\)为整数。如果不满足这个条件，可以通过补零，使之达到这个要求。将\(x[n]\)分为四个长度为\(N/4\)的子序列, 则\(x[n]\)的DFT可以表示为：
\[\begin{split}\displaystyle \begin{equation*} \begin{split} X(k)& =\sum_{n=0}^{N-1}x[n]W_N^{kn} \\
& = \sum_{n=0}^{\frac{N}{4}-1}x[n]W_N^{kn} + \sum_{n=\frac{N}{4}}^{\frac{N}{2}-1}x[n]W_N^{kn} + \sum_{n=\frac{N}{2}}^{\frac{3N}{4}-1}x[n]W_N^{kn}+ \sum_{n=\frac{3N}{4}}^{N-1}x[n]W_N^{kn} \\
& = \sum_{n=0}^{\frac{N}{4}-1}x[n]W_N^{kn} + \sum_{n=0}^{\frac{N}{4}-1}x[n+\frac{N}{4}]W_N^{k(n+\frac{N}{4})} + \sum_{n=0}^{\frac{N}{4}-1}x[n+\frac{N}{2}]W_N^{k(n+\frac{N}{2})}+ \sum_{n=0}^{\frac{N}{4}-1}x[n+\frac{3N}{4}]W_N^{k(n+\frac{3N}{4})} \\
& = \sum_{n=0}^{\frac{N}{4}-1}(x[n] + W_N^{\frac{kN}{4}}x[n+\frac{N}{4}] + W_N^{\frac{kN}{2}}x[n+\frac{N}{2}] + W_N^{\frac{3kN}{4}}x[n+\frac{3N}{4}])W_N^{kn} \\
\end{split}
\end{equation*}\end{split}\]
其中，旋转因子\(W_N^{\frac{kN}{4}}\)，\(W_N^{\frac{kN}{2}}\)，\(W_N^{\frac{3kN}{4}}\)可以表示为：
\(\displaystyle W_N^{\frac{kN}{4}} = e^{-j\frac{2\pi}{N}\frac{kN}{4}} = e^{-j\frac{\pi}{2}k} = (-j)^k\)
\(\displaystyle W_N^{\frac{kN}{2}} = e^{-j\frac{2\pi}{N}\frac{kN}{2}} = e^{-j\pi k} = (-1)^k\)
\(\displaystyle W_N^{\frac{3kN}{4}} = e^{-j\frac{2\pi}{N}\frac{3kN}{4}} = e^{-j\frac{3\pi}{2}k} = (j)^k\)
当\(k=4r\),
\[\begin{split}\displaystyle \begin{equation*} \begin{split} X(4r)& = \sum_{n=0}^{\frac{N}{4}-1}(x[n] + x[n+\frac{N}{4}] + x[n+\frac{N}{2}] + x[n+\frac{3N}{4}])W_N^{4rn} \\
& = \sum_{n=0}^{\frac{N}{4}-1}(x[n] + x[n+\frac{N}{4}] + x[n+\frac{N}{2}] + x[n+\frac{3N}{4}])W_{N/4}^{rn} \end{split}
\end{equation*}\end{split}\]
\(X(4r)\)为\(x_0[n]=x[n] + x[n+\frac{N}{4}] + x[n+\frac{N}{2}] + x[n+\frac{3N}{4}]\)的\(N/4\)点的DFT。
当\(k=4r+1\),
\[\begin{split}\displaystyle \begin{equation*} \begin{split} X(4r+1)& = \sum_{n=0}^{\frac{N}{4}-1}(x[n] -j x[n+\frac{N}{4}] - x[n+\frac{N}{2}] + jx[n+\frac{3N}{4}])W_N^nW_N^{4rn} \\
& = \sum_{n=0}^{\frac{N}{4}-1}((x[n] -j x[n+\frac{N}{4}] - x[n+\frac{N}{2}] +j x[n+\frac{3N}{4}])W_N^n)W_{N/4}^{rn}\end{split}
\end{equation*}\end{split}\]
\(X(4r+1)\)为\(x_1[n]=(x[n] -j x[n+\frac{N}{4}] - x[n+\frac{N}{2}] +j x[n+\frac{3N}{4}])W_N^n\)的\(N/4\)点的DFT
当\(k=4r+2\),
\[\begin{split}\displaystyle \begin{equation*} \begin{split} X(4r+2)& = \sum_{n=0}^{\frac{N}{4}-1}(x[n] - x[n+\frac{N}{4}] + x[n+\frac{N}{2}] -x[n+\frac{3N}{4}])W_N^{2n}W_N^{4rn} \\
& = \sum_{n=0}^{\frac{N}{4}-1}((x[n] - x[n+\frac{N}{4}] + x[n+\frac{N}{2}] - x[n+\frac{3N}{4}])W_N^{2n})W_{N/4}^{rn}\end{split}
\end{equation*}\end{split}\]
\(X(4r+2)\)为\(x_2[n]=(x[n] - x[n+\frac{N}{4}] + x[n+\frac{N}{2}] - x[n+\frac{3N}{4}])W_N^{2n}\)的\(N/4\)点的DFT。
当\(k=4r+3\),
\[\begin{split}\displaystyle \begin{equation*} \begin{split} X(4r+3)& = \sum_{n=0}^{\frac{N}{4}-1}(x[n] +jx[n+\frac{N}{4}] - x[n+\frac{N}{2}] -jx[n+\frac{3N}{4}])W_N^{3n}W_N^{4rn} \\
& = \sum_{n=0}^{\frac{N}{4}-1}((x[n] +j x[n+\frac{N}{4}] - x[n+\frac{N}{2}] -j x[n+\frac{3N}{4}])W_N^{3n})W_{N/4}^{rn}\end{split}
\end{equation*}\end{split}\]
\(X(4r+3)\)为\(x_3[n]=(x[n] +j x[n+\frac{N}{4}] - x[n+\frac{N}{2}] -j x[n+\frac{3N}{4}])W_N^{3n}\)的\(N/4\)点的DFT。
我们可以用下面的示意图表示上述的过程：
对于中间序列\(x_1[n]\)，\(x_2[n]\)，\(x_3[n]\)，\(x_4[n]\)，我们可以继续用上述类似的方法将其每个中间序列分为四个长度为\(N/16\)的子序列，我们画出了\(x_1[n]\)划分的示意图：
我们继续用这种方法，直到最后的序列长度为4。4点的DFT计算如下：
\[\begin{split}\displaystyle \begin{bmatrix} X[0] \\ X[1] \\
X[2]\\ X[3] \end{bmatrix} =\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & -j & -1 & -j \\
1 & -1 & 1 & -1 \\
1 & j & -1 & j
\end{bmatrix}\cdot \begin{bmatrix} x[0] \\ x[1] \\
x[2]\\ x[3] \end{bmatrix} \end{split}\]
