DFT 与 FFT 的计算：矩阵法与蝶形图的等效性

这份课程资料清晰地展示了离散傅里叶变换 (DFT) 的两种计算方法。无论是通过 DFT 定义的矩阵乘法，还是通过快速傅里叶变换 (FFT) 的蝶形图，其本质都是对输入序列 $x[n]$ 进行线性组合（即涉及 $\pm 1, \pm j$ 等系数的变形计算），两者在数学上是完全等价的。

FFT 是一种高效的算法实现，它通过巧妙地分解计算来降低复杂度。

N = 2 的情况 (基础构建)

我们首先分析最基础的 N=2 的情况。

方法一：DFT 矩阵 (直接定义)	方法二：FFT 蝶形图 (算法实现)
根据 DFT 定义 $W_N = e^{-j\frac{2\pi}{N}}$，当 $N=2$ 时，旋转因子 $W_2^0 = 1$，$W_2^1 = -1$。 DFT 矩阵 $W_2$ 定义为： $$ W_2 = \begin{bmatrix} W_2^0 & W_2^0 \\ W_2^0 & W_2^1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} $$ 计算 $X(k) = W_2 \cdot x(n)$ 并展开： $$ \begin{bmatrix} X(0) \\ X(1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} x(0) \\ x(1) \end{bmatrix} = \begin{bmatrix} x(0) + x(1) \\ x(0) - x(1) \end{bmatrix} $$	基-2 FFT 的蝶形图是该算法的核心单元。它以图形方式表示了 N=2 DFT 的计算。根据信号流图，我们可以直接写出： $X(0) = x(0) + x(1)$ $X(1) = x(0) + (-1) \cdot x(1) = x(0) - x(1)$

方法一：DFT 矩阵 (直接定义)

方法二：FFT 蝶形图 (算法实现)

根据 DFT 定义 $W_N = e^{-j\frac{2\pi}{N}}$，当 $N=2$ 时，旋转因子 $W_2^0 = 1$，$W_2^1 = -1$。

DFT 矩阵 $W_2$ 定义为：

$$ W_2 = \begin{bmatrix} W_2^0 & W_2^0 \\ W_2^0 & W_2^1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} $$

计算 $X(k) = W_2 \cdot x(n)$ 并展开：

$$ \begin{bmatrix} X(0) \\ X(1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} x(0) \\ x(1) \end{bmatrix} = \begin{bmatrix} x(0) + x(1) \\ x(0) - x(1) \end{bmatrix} $$

基-2 FFT 的蝶形图是该算法的核心单元。它以图形方式表示了 N=2 DFT 的计算。

根据信号流图，我们可以直接写出：

$X(0) = x(0) + x(1)$
$X(1) = x(0) + (-1) \cdot x(1) = x(0) - x(1)$

N = 4 的情况 (组合)

基于 N=2 的情况，我们可以构建 N=4 的计算。旋转因子为 $W_4^0 = 1$, $W_4^1 = -j$, $W_4^2 = -1$, $W_4^3 = j$。

此处的 FFT 采用**按时间抽取 (DIT)** 算法，因此输入序列需要按**比特反序**排列，即 $x(0), x(2), x(1), x(3)$。

方法一：DFT 矩阵 (直接定义)	方法二：FFT 蝶形图 (算法实现)
N=4 的 DFT 矩阵 $W_4$ 定义为： $$ W_4 = \begin{bmatrix} W_4^0 & W_4^0 & W_4^0 & W_4^0 \\ W_4^0 & W_4^1 & W_4^2 & W_4^3 \\ W_4^0 & W_4^2 & W_4^4 & W_4^6 \\ W_4^0 & W_4^3 & W_4^6 & W_4^9 \end{bmatrix} $$ 代入旋转因子的值，计算 $X(k) = W_4 \cdot x(n)$： $$ \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} \begin{bmatrix} x(0) \\ x(1) \\ x(2) \\ x(3) \end{bmatrix} = \begin{bmatrix} x(0) + x(1) + x(2) + x(3) \\ x(0) - jx(1) - x(2) + jx(3) \\ x(0) - x(1) + x(2) - x(3) \\ x(0) + jx(1) - x(2) - jx(3) \end{bmatrix} $$	N=4 的 DIT-FFT 蝶形图将计算分解为两级。展开结果 (跟踪信号流图)： $X(0) = [x(0)+x(2)] + W_4^0[x(1)+x(3)] = x(0)+x(2) + 1(x(1)+x(3))$ $= \mathbf{x(0) + x(1) + x(2) + x(3)}$ $X(1) = [x(0)-x(2)] + W_4^1[x(1)-x(3)] = x(0)-x(2) + (-j)(x(1)-x(3))$ $= \mathbf{x(0) - jx(1) - x(2) + jx(3)}$ $X(2) = [x(0)+x(2)] - W_4^0[x(1)+x(3)] = x(0)+x(2) - 1(x(1)+x(3))$ $= \mathbf{x(0) - x(1) + x(2) - x(3)}$ $X(3) = [x(0)-x(2)] - W_4^1[x(1)-x(3)] = x(0)-x(2) - (-j)(x(1)-x(3))$ $= \mathbf{x(0) + jx(1) - x(2) - jx(3)}$

方法一：DFT 矩阵 (直接定义)

方法二：FFT 蝶形图 (算法实现)

N=4 的 DFT 矩阵 $W_4$ 定义为：

$$ W_4 = \begin{bmatrix} W_4^0 & W_4^0 & W_4^0 & W_4^0 \\ W_4^0 & W_4^1 & W_4^2 & W_4^3 \\ W_4^0 & W_4^2 & W_4^4 & W_4^6 \\ W_4^0 & W_4^3 & W_4^6 & W_4^9 \end{bmatrix} $$

代入旋转因子的值，计算 $X(k) = W_4 \cdot x(n)$：

$$ \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} \begin{bmatrix} x(0) \\ x(1) \\ x(2) \\ x(3) \end{bmatrix} = \begin{bmatrix} x(0) + x(1) + x(2) + x(3) \\ x(0) - jx(1) - x(2) + jx(3) \\ x(0) - x(1) + x(2) - x(3) \\ x(0) + jx(1) - x(2) - jx(3) \end{bmatrix} $$

N=4 的 DIT-FFT 蝶形图将计算分解为两级。

展开结果 (跟踪信号流图)：

$X(0) = [x(0)+x(2)] + W_4^0[x(1)+x(3)] = x(0)+x(2) + 1(x(1)+x(3))$
$= \mathbf{x(0) + x(1) + x(2) + x(3)}$
$X(1) = [x(0)-x(2)] + W_4^1[x(1)-x(3)] = x(0)-x(2) + (-j)(x(1)-x(3))$
$= \mathbf{x(0) - jx(1) - x(2) + jx(3)}$
$X(2) = [x(0)+x(2)] - W_4^0[x(1)+x(3)] = x(0)+x(2) - 1(x(1)+x(3))$
$= \mathbf{x(0) - x(1) + x(2) - x(3)}$
$X(3) = [x(0)-x(2)] - W_4^1[x(1)-x(3)] = x(0)-x(2) - (-j)(x(1)-x(3))$
$= \mathbf{x(0) + jx(1) - x(2) - jx(3)}$

N=4 对比结论

通过对比两侧的展开结果（矩阵展开式与蝶形图展开式），可以清晰地看到：尽管计算路径不同（矩阵法一次完成，FFT 分两级），但两种方法得到的 $X(k)$ 最终表达式完全相同。

N = 8 DIT-FFT 蝶形图

当 N=8 时，DIT-FFT 算法将计算分解为 3 级（$\log_2 8 = 3$）。输入序列按比特反序 $x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7)$ 排列。

旋转因子 $W_8^k = e^{-j\frac{2\pi k}{8}}$，主要值为：
$W_8^0 = 1$, $W_8^1 = \frac{1}{\sqrt{2}}(1-j)$, $W_8^2 = -j$, $W_8^3 = \frac{1}{\sqrt{2}}(-1-j)$