DFT旋转因子与循环卷积详解

1. DFT中的旋转因子 (Twiddle Factor)

定义与几何意义

旋转因子，记为 $W_N$，是DFT定义中的核心复数。它代表了复平面单位圆上的一个基本旋转角度。

$$ W_N = e^{-j\frac{2\pi}{N}} = \cos\left(\frac{2\pi}{N}\right) - j\sin\left(\frac{2\pi}{N}\right) $$

在DFT的计算公式 $X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}$ 中，它的幂 $W_N^{kn}$ 的意义是：

$$ W_N^{kn} = (e^{-j\frac{2\pi}{N}})^{kn} = e^{-j\frac{2\pi kn}{N}} $$

这代表从复平面的点 (1, 0) 开始，沿着单位圆顺时针旋转 $kn$ 个大小为 $\frac{2\pi}{N}$ 的基本角度。这些旋转因子构成了DFT的正交基，用于分析信号在不同频率分量上的投影。

交互式可视化 (N=8)

下图展示了当N=8时，8个基本旋转因子 $W_8^k$ 在复平面单位圆上的位置。将鼠标悬停在点上可以查看其详细信息。

2. 循环卷积的直观理解：为何称为“循环”？

线性卷积是在一条无限长的直线上进行的，而循环卷积是在一个圆周上进行的。这个几何模型是理解其特性的关键。我们可以通过以下四步来形象地理解这个过程：

  1. 将序列 $x[n]$ 的N个点均匀地布置在一个固定的外圈上。
  2. 将序列 $h[n]$ 进行时间反转，得到 $h[-m \pmod N]$。
  3. 将反转后的 $h$ 序列布置在一个可旋转的内圈上，并与外圈的起始点对齐。
  4. 计算 $y[0]$：将内外圈对齐的元素相乘再求和。然后，将内圈顺时针旋转一格，计算 $y[1]$，如此循环往复，直到计算出所有N个输出点。
h[0] h[-1] h[-2] ... x[0] x[1] x[2] ... x[N-1] 内圈反转后，不断旋转

3. 循环卷积动画 (N=4)

以下动画直观演示了 $x[n] = \{1, 2, 2, 1\}$ 和 $h[n] = \{1, 0, 1, 0\}$ 的4点循环卷积过程。

点击按钮开始动画

4. 循环卷积计算过程详解

循环卷积的数学定义为：$ y[n] = x[n] \circledast_N h[n] = \sum_{m=0}^{N-1} x[m] h[(n-m) \pmod N] $

在实际应用和考试中，我们通常有四种方法来计算它。以下以 $x[n] = \{1, 2, 2, 1\}$ 和 $h[n] = \{1, 0, 1, 0\}$ 为例。

方法一：时域图示法 (定义法)

这是最基本的方法，按照定义进行反转、移位、相乘、求和。

  1. 计算 y[0]: (h序列初始对齐)

    (1×1)+(2×0)+(2×1)+(1×0) = 3

  2. 计算 y[1]: (h序列循环右移一位)

    (1×0)+(2×1)+(2×0)+(1×1) = 3

  3. 计算 y[2] 和 y[3]:

    同理循环移位计算，最终得到 3 和 3。

最终结果：$y[n] = \{3, 3, 3, 3\}$

方法二：频域计算 (DFT法)

基于离散卷积定理：时域的循环卷积等价于频域的乘积。即 $y[n] = \text{IDFT}( \text{DFT}(x) \cdot \text{DFT}(h) )$。

1. DFT($x$): 计算得 $X[k] = \{6, -1-j, 0, -1+j\}$

2. DFT($h$): 计算得 $H[k] = \{2, 0, 2, 0\}$

3. 点乘: $Y[k] = X[k] \cdot H[k] = \{12, 0, 0, 0\}$

4. IDFT: 由于只有直流分量 $Y[0]=12$，IDFT后平均分摊到每个点：$12/4 = 3$。

结果: $y[n] = \{3, 3, 3, 3\}$

方法三：循环矩阵法 (Circulant Matrix)

循环卷积可以转化为一个特殊的矩阵乘法 $y = H_{circ} \cdot x$。其中矩阵 $H_{circ}$ 是通过将序列 $h[n]$ 作为第一列，后续每一列都是前一列的向下循环移位生成的。

$\begin{bmatrix} y[0] \\ y[1] \\ y[2] \\ y[3] \end{bmatrix}$
=
$\begin{bmatrix} h[0] & h[3] & h[2] & h[1] \\ h[1] & h[0] & h[3] & h[2] \\ h[2] & h[1] & h[0] & h[3] \\ h[3] & h[2] & h[1] & h[0] \end{bmatrix}$
$\cdot$
$\begin{bmatrix} x[0] \\ x[1] \\ x[2] \\ x[3] \end{bmatrix}$

代入数值计算：

注意矩阵的第一行是 $h[n]$ 的反转（时间反转），即 $\{1, 0, 1, 0\}$ 的反转是 $\{1, 0, 1, 0\}$ (因为 $h[1]$ 和 $h[3]$ 交换)。

$$ \begin{bmatrix} 3 \\ 3 \\ 3 \\ 3 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 2 \\ 1 \end{bmatrix} $$

例如第一行计算：$1\cdot1 + 0\cdot2 + 1\cdot2 + 0\cdot1 = 1 + 2 = 3$。

方法四：线性卷积 + 周期延拓 (最适合笔算)

这是手动计算最快的方法。循环卷积等于线性卷积的结果，按照长度 N 进行分段并叠加。

  1. 计算线性卷积： 忽略循环性质，直接计算 $x[n] * h[n]$。
    由下文动画或表格计算可知，线性卷积结果为 $y_{lin} = \{1, 2, 3, 3, 2, 1, 0\}$ (长度为 7)。
  2. 分段： 将结果按照长度 $N=4$ 进行切割。
    • 第一段 (索引 0-3): $\{1, 2, 3, 3\}$
    • 第二段 (索引 4-6): $\{2, 1, 0, \text{补}0\}$
  3. 叠加 (混叠)： 将超出 N 的部分“卷”回来加到开头。
    索引0123
    主段1233
    尾段(+)2100
    结果3333
这个方法直观地展示了“时域混叠” (Time Domain Aliasing) 的概念。当线性卷积长度超过 DFT 点数 N 时，多出来的尾部就会叠加到头部，形成循环卷积。

5. 线性卷积 (Linear Convolution) 回顾

理论与动画

线性卷积可以想象成一个序列反转后，在另一个序列上“滑窗相乘求和”的过程。其结果的长度为 $L = N_1 + N_2 - 1$。

点击按钮开始动画

表格计算法

对于 $x[n] = \{1, 2, 2, 1\}$ 和 $h[n] = \{1, 0, 1, 0\}$，结果长度为 $L = 4+4-1=7$。表格法可以清晰地展示每一步的计算：

$x[m]$1221
$h[-m]$ (反转)...0101...
计算步骤序列 $h[n-m]$ (滑动)y[n]
$y[0]$...1010...$1 \times 1 = 1$1
$y[1]$...1010...$1 \times 0 + 2 \times 1 = 2$2
$y[2]$...1010...$1 \times 1 + 2 \times 0 + 2 \times 1 = 3$3
$y[3]$...1010...$1 \times 0 + 2 \times 1 + 2 \times 0 + 1 \times 1 = 3$3
$y[4]$...1010$2 \times 0 + 2 \times 1 + 1 \times 0 = 2$2
$y[5]$...101$2 \times 0 + 1 \times 1 = 1$1
$y[6]$...10$1 \times 0 = 0$0

6. 总结与验证

卷积类型结果序列长度
4点循环卷积{3, 3, 3, 3}4
线性卷积{1, 2, 3, 3, 2, 1, 0}7

时域混叠的可视化

我们在“方法四”中提到，循环卷积是线性卷积的周期延拓叠加。下图再次直观验证了这一结论：线性卷积的尾部“卷绕”回来与头部相加，正是循环卷积的结果。

线性结果:
1
2
3
3
2
1
0
卷绕部分 (+):
2
1
0
循环结果:
3
3
3
3