數字訊號處理 - 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矩陣。

• 另一個序列表示為列矩陣。

• 兩個矩陣的乘法給出迴圈卷積的結果。