数字信号处理 - DFT循环卷积

---

---

让我们考虑两个长度为N的有限长序列x₁(n)和x₂(n)。它们的DFT分别为X₁(K)和X₂(K)，如下所示：

$$X_1(K) = \sum_{n = 0}^{N-1}x_1(n)e^{\frac{j2\Pi kn}{N}}\quad k = 0,1,2...N-1$$ $$X_2(K) = \sum_{n = 0}^{N-1}x_2(n)e^{\frac{j2\Pi kn}{N}}\quad k = 0,1,2...N-1$$

现在，我们将尝试找到另一个序列x₃(n)的DFT，记为X₃(K)

$X_3(K) = X_1(K)\times X_2(K)$

通过对上述公式进行IDFT变换，我们得到

$x_3(n) = \frac{1}{N}\displaystyle\sum\limits_{n = 0}^{N-1}X_3(K)e^{\frac{j2\Pi kn}{N}}$

解上述方程后，最终得到

$x_3(n) = \displaystyle\sum\limits_{m = 0}^{N-1}x_1(m)x_2[((n-m))_N]\quad m = 0,1,2...N-1$

循环卷积的方法

通常，采用两种方法进行循环卷积，它们是：

• 同心圆法，
• 矩阵乘法法。

同心圆法

设x₁(n)和x₂(n)为两个给定的序列。x₁(n)和x₂(n)的循环卷积步骤如下：

• 画两个同心圆。在外部圆周上逆时针方向绘制x₁(n)的N个样本（保持相邻点之间的距离相等）。

• 对于x₂(n)的绘制，在内圆上顺时针方向绘制x₂(n)的N个样本，起始样本与x₁(n)的第0个样本位于同一点。

• 将两个圆上对应的样本相乘，并将结果相加以得到输出。

• 将内圆逆时针旋转一个样本。

矩阵乘法法

矩阵法将两个给定序列x₁(n)和x₂(n)表示为矩阵形式。

• 通过每次循环移位一个样本，重复其中一个给定序列以形成一个N X N矩阵。

• 另一个序列表示为列矩阵。

• 两个矩阵的乘法给出循环卷积的结果。