循環卷積

計算兩個長度均為N的序列x₁(n)和x₂(n)的循環卷積，一個簡易的辦法是先把x₁(n)的數據，設x₁(n)=(1，2，3，4)，N=4，按逆時針方向均勻分佈在一個圓周上。如圖1中(a)。的內圓所示，而把x₂(n)，設x₂(n)={5，6，7，8}，按順時針的方向均勻分佈在另一個同心圓上，然後求兩圓上相應序列的乘積，並把V項乘積疊加起來作為n=0時刻的卷積值y(0)，即

y(0)=1×5+4×6+3×7+2×8=66

若求n=1時刻的y(l)值，可將外圓的：x₂(n)固定，把內圓上的序列x₁(n)順時針旋轉一個單位時間（或將x₁(n)固定，把外圓上的序列x₂(n)逆時針旋轉），然後把對應項的乘積疊加起來，即為所求。如圖1中的(b)圖所示，即

y(1)=2×5+1×6+4×7+3×8=68

這樣依次將內圓序列進行循環移位一週，便可以求得：y(2)=66，y(3)=60。所以循環卷積又稱圓周卷積，卷積結果y(n)長度仍等於N，其定義式如圖2。方括號內的運算代表兩個週期序列的週期卷積。它與線性卷積不同之處是卷積過程只限在m=0到N-1的一個週期內。乘以R_N(n)表示卷積結果只取長度為N的主值序列。

由於離散傅里葉變換(DFT)的實質是週期序列變換到頻域的描述。可以證明：兩個有限長序列在時域的循環卷積，其DFT等於在頻域兩個序列相應的DFT的乘積。 ^[1] 

式中X₁(k)和x₂(k)分別是x₁(n)和x₂(n)的N點DFT。它表明DFT具有循環卷積性質（CCP），也是區別於其他變換的重要特性。正是這種性質，用計算機通過計算DFT達到計算循環卷積和線性卷積的目的，提髙了運算效率。按長度為N的兩個序列，其線性卷積的長度應為2N-1，而循環卷積的長度仍然為N。為此，可以通過補零把序列長度增加到L≥2N-1。這樣，一方面使循環卷積的長度等於線性卷積，另一方面避免進行循環卷積過程出現混疊造成失真，使計算結果與線性卷積相等，從而實現利用DFT計算線性卷積的目的。循環卷積有快速算法，廣泛應用於對通信系統的分析和綜合以及對信號的數字處理。

對於線性非時變離散時間系統來説，若序列x(n)是系統的輸入，h(n)是系統在單位脈衝作用下的單位脈衝響應，則由於輸入序列x(n)可表示為一系列脈衝的線性組合，所以，根據線性系統的疊加性質，系統的輸出在系統初始不儲能的條件下(零狀態響應)可由圖4式求得.

上式在運算過程存在序列的翻轉、移位、相乘和相加，所以稱為卷積和。x(n)*h(n)表示兩個序列相卷積的運算符號，故式①也就是卷積的定義式。為了與離散傅里葉變換的循環卷積以及週期序列的週期卷積相區別，通常所指的卷積又稱為線性卷積。卷積運算符合交換率，可寫成另一種等效形式如圖5.

線性卷積的計算可以用解析法，也可以用圖解法。若兩 個序列的長度分別為N₁和N₂，則卷積結果的總長度應為L=N₁+N₂-1。

同理，對線性非時變連續系統來説，若連續時間信號x(t)是系統的輸入，h(t)是系統在單位脈衝作用下的單位衝激響應，則系統在零狀態的輸出為它們的卷積積分

線性卷積是數字信號處理中最常見的一種基本運算，不僅用於系統分析還用於系統設計。如果代表濾波器的脈衝響應則卷積運算就是一種線性濾波，y(n)是信號x(n)通過濾波器後的響應。

在實際問題中，碰到的問題大多數是求解線性卷積，例如，一個LSI系統，輸出y(n)為y(n)=x(n)*h(n)

下面將看到在一定條件下，可用循環卷積代替線性卷積，今後可看到循環卷積比線性卷積在計算速度上可提高許多倍。

設 x(n)是長度為 N 的有限長序列， h(n)是長度為 M 的有限長度序列。 ^[2] 

循環卷積是使用DFT(FFT)計算線性卷積時的衍生品。首先連續時間沒有循環卷積概念。離散時間時，不妨假設x(n)為L點信號， 僅在0~L-1有非零值；h(n)為M點信號，僅在0~M-1有非零值。以x(n)為輸入信號通過以h(n)為單位衝激響應的線性時不變系統得到輸出 y(n) = x(n) * h(n)，線性卷積，直接計算的複雜度為 O(LM) ^[1]  。