左侧：N=4 DFT 矩阵计算
对于 N=4 的离散傅里叶变换 (DFT)，其计算公式为：
$$ X[k] = \sum_{n=0}^{3} x[n] \cdot W_{4}^{kn}, \quad k = 0, 1, 2, 3 $$
其中，扭转因子 $W_N^k = e^{-j\frac{2\pi k}{N}}$。对于 $N=4$：
$$ W_4 = e^{-j\frac{2\pi}{4}} = e^{-j\frac{\pi}{2}} = \cos\left(-\frac{\pi}{2}\right) + j\sin\left(-\frac{\pi}{2}\right) = -j $$
1. 构建DFT矩阵 ($\mathbf{W}$)
矩阵元素 $W[k,n] = W_4^{kn}$。基于 $W_4^0=1, W_4^1=-j, W_4^2=-1, W_4^3=j$，可得4x4的DFT矩阵：
$$
\mathbf{W} =
\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}
=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & -j & -1 & j \\
1 & -1 & 1 & -1 \\
1 & j & -1 & -j
\end{bmatrix}
$$
2. 矩阵乘法计算
给定输入序列 $\mathbf{x} = [1, 2, 3, 4]^T$，计算 $\mathbf{X} = \mathbf{W} \cdot \mathbf{x}$。
$$
\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} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}
$$
3. 计算结果
$$
\begin{align*}
X[0] &= (1 \cdot 1) + (1 \cdot 2) + (1 \cdot 3) + (1 \cdot 4) &&= 1 + 2 + 3 + 4 &&= \mathbf{10} \\
X[1] &= (1 \cdot 1) + (-j \cdot 2) + (-1 \cdot 3) + (j \cdot 4) &&= 1 - 2j - 3 + 4j &&= \mathbf{-2 + 2j} \\
X[2] &= (1 \cdot 1) + (-1 \cdot 2) + (1 \cdot 3) + (-1 \cdot 4) &&= 1 - 2 + 3 - 4 &&= \mathbf{-2} \\
X[3] &= (1 \cdot 1) + (j \cdot 2) + (-1 \cdot 3) + (-j \cdot 4) &&= 1 + 2j - 3 - 4j &&= \mathbf{-2 - 2j}
\end{align*}
$$
右侧 (上): N=4 DIT-FFT (时域抽取)
输入序列按位倒序排列：x(0), x(2), x(1), x(3) $\rightarrow$ {1, 3, 2, 4}。输出为自然顺序。
右侧 (下): N=4 DIF-FFT (频域抽取)
输入序列为自然顺序：x(0), x(1), x(2), x(3) $\rightarrow$ {1, 2, 3, 4}。输出按位倒序排列。