---

DSP - DFT 循环卷积

DFT 循环卷积是一种在信号处理和数字信号处理领域常用的技术。它将两个序列进行卷积，但不同于常规的卷积，DFT循环卷积可以有效地避免直接进行大规模的乘法运算，从而减少计算复杂度。

我们取两个有限持续时间序列 x₁(n) 和 x₂(n)，长度为 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$$

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

$X_3(K) = X_1(K) imes 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_1(n)$和$x_2(n)$为两个给定序列。对$x_1(n)$和$x_2(n)$进行循环卷积的步骤如下

• 取两个同心圆。在外圆的圆周上以逆时针方向绘制 N 个 $x_1(n)$ 样本（保持相等距离的连续点）。

• 要绘制 $x_2(n)$，请在内圆上以顺时针方向绘制 N 个 $x_2(n)$ 样本，起始样本放置在与 $x_1(n)$ 的第 0 个样本相同的位置

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

• 每次一个样本，逆时针旋转内圆。

矩阵乘法

矩阵方法以矩阵形式表示两个给定序列 $x_1(n)$ 和 $x_2(n)$。

• 给定序列之一通过循环移位一个样本重复一次形成 N X N 矩阵的时间。

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

• 两个矩阵相乘得到循环卷积的结果。

---