循環卷積和線性卷積在信號處理中的意義是什麼？

12-29

通常說卷積時指的是線性卷積，在信號處理領域是跟線性時不變系統有關的一種運算

如何理解卷積，另外如何理解圖像處理中的卷積？ - 水木八刀的回答

循環卷積我理解是使用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)。

卷積計算通常比較複雜，一種可能的簡化思路是考慮放到頻域計算， DTFT上場。

時域卷積，頻域相乘

DTFT[ y(n) ] = DTFT[ x(n) ] DTFT[ h(n) ]

但是DTFT由於頻域連續不便處理，

$DTFT[x(n)] := sum^{infty}_{n=-infty} x(n)e^{-jwn} \ = sum^{L-1}_{n=0} x(n)e^{-jwn} = X(e^{jw})$

因此找到DFT, 它將頻域離散化了，因此很方便計算機處理，特別是DFT還有快速演算法FFT。

那麼IDFT[ DFT[ x(n) ] DFT[ h(n) ] ] 是否等於IDFT[ DFT[ y(n) ] ] 呢？如果是，那簡直是極好的；如果不是，那二者又存在何種關係呢？

$IDFT[DFT[x(n)] DFT[h(n)]] stackrel{?}{=} IDFT[DFT[x(n)*h(n)]]$

其中

$DFT[x(n)] := sum^{N-1}_{n=0} x(n)e^{-j n kfrac{2pi}{N}} =X(k), k=0,...,N-1 \ IDFT[X(k)] := frac{1}{N}sum^{N-1}_{k=0} X(k)e^{j n kfrac{2pi}{N}} =hat{x}(n), n=0,...,N-1$

很遺憾，上式成立是有條件的，這個條件我會在後面分析。注意所有的DFT/IDFT都隱含了一個相同的參數 N，為DFT的點數，而上式成立條件正是跟N有關。

那麼 $IDFT[DFT[x(n)] ullet DFT[h(n)]]$ 究竟和 $x(n), h(n)$ 滿足什麼樣的關係呢？根據頻域相乘時域卷積的特點，結果應該類似卷積，但又不是卷積，而按照定義求解後發現表達式中有周期延拓（循環）的過程，那就將其定義為循環卷積吧。

$IDFT[DFT[x(n)] ullet DFT[h(n)]] = x(n) otimes h(n)$

循環卷積的點數和DFT/IDFT點數相同。

$x(n) otimes h(n) := left [sum^{N-1}_{m=0} x(m)h((n-m))_N ight ] R_N(n) \ = left [sum^{N-1}_{m=0} h(m)x((n-m))_N ight ] R_N(n)$

其中

$x((n))_N = sum^{+infty}_{r=-infty} x(n+rN)$

$R_N(n)=egin{cases}1, 0 le n le N-1 \ 0, else end{cases}$

當然，按照循環卷積的定義，任意兩個信號，我完全可以在時域上按照定義去計算，而絲毫不關DFT/IDFT什麼事，但是正常兩個信號，沒毛病我搞個又是循環又是卷積的這麼奇怪的運算算個什麼事！因此，我理解循環卷積是使用DFT計算線性卷積的衍生品。

下面分析IDFT[ DFT[ x(n) ] DFT[ h(n) ] ] = IDFT[ DFT[ y(n) ] ] 成立的條件，前面已經提到這個條件跟DFT點數N有關。

由定義

$DFT[x(n)] := sum^{N-1}_{n=0} x(n)e^{-jnkfrac{2pi}{N}} =X(k), k=0,...,N-1$

注意這裡N和L未必相同，顯然若 $Nge L$ , 則

$X(k) = X(e^{jw})|_{w=kfrac{2pi}{N}}, k=0,...,N-1$

而 $N <L$ 時，x(N), ... , x(L-1) 被丟棄了，因此上式的採樣關係不復存在，我們自然不希望如此。

注意到對 $X(e^{jw})$ 採樣其對應時域 $x(n)$ 將周期延拓，而 $x(n)$ 為有限長L點序列，因此只要延拓周期 $N ge L$ ，則可根據採樣信號 $X(k)$ 無失真重建原頻域信號 $X(e^{jw})$ ，此時頻域採樣間隔為 $2pi/N$ .

有了上面討論的基礎，下面就簡單明了了。

我們知道，

$Y(e^{jw}) = X(e^{jw})H(e^{jw})$

因此

$Y(e^{jw}) |_{w=frac{2pi}{N}}= X(e^{jw}) |_{w=frac{2pi}{N}}H(e^{jw}) |_{w=frac{2pi}{N}}$

這種採樣點間的關係是恆成立的，關鍵是能否轉換成DFT形式，這要求做DFT的點數N不能比原信號短。

我們首先假設 $N ge L$ 且 $N ge M$ , 這樣右邊的DTFT採樣形式可以轉換成DFT形式，即

$Y(e^{jw})|_{w=kfrac{2pi}{N}} = X(k) H(k),k=0,...,N-1$

我們知道y(n)的長度為L+M-1 (由卷積定義可確定），因此當 $N ge L+M-1$ 時，左邊也正是Y(k) ，兩邊做IDFT，得

$y(n) = x(n)*h(n) = x(n) otimes h(n)$

而當 $N < L+M-1$ 時，左邊時域將按N點進行周期延拓產生混疊，最終取主值區。

$hat{y}(n)=IDFTleft[Y(e^{jw})|_{w=kfrac{2pi}{N}} ight] = sum^{+infty}_{r=-infty} y(n+rN) , n=0,...,N-1$

顯然， $N ge L+M-1$ 時， $y(n) = hat{y}(n)$

綜上，當 $N ge L$ 且 $N ge M$ 時，循環卷積和線性卷積的關係如下：

$(x otimes h)(n) = sum^{+infty}_{r=-infty} (x*h)(n+rN), n=0,...,N-1$

下面解決一下遺留問題：當 N &< L 或/與 N &< M 時，將會怎樣？

不妨假設 N &< L，此時定義x(n)信號的截斷信號為：

$x$

$R_N(n)=egin{cases}1, 0 le n le N-1 \ 0, else end{cases}$

那麼，信號x都變了，期望得到的循環卷積和線性卷積的關係就無從說起了。

$(x$

複雜度分析

上面討論了當 $N ge L+M-1$ 時，

$x(n)*h(n) = x(n) otimes h(n) = IDFT left[ DFT[x(n)]ullet DFT[h(n)] ight]$

從而可以考慮通過FFT(也就是DFT的快速演算法）間接求解兩個信號的卷積。由上式可知，需要做3次N點FFT(兩次正變換，一次反變換），一次N點複數乘法。 N點FFT的時間複雜度為 O(N logN)，對比直接卷積的時間複雜度O(LM)。忽略係數，僅考慮數量級差距，在 L, M相當時, $L approx M approx N/2$

因此直接卷積的時間複雜度為 $O(N^2)$ 大於通過FFT實現的間接卷積時間複雜度 $O(NlogN)$ .

注意，許多情況下，信號長度遠遠大於濾波器長度，濾波器長度M為常數，

$N approx L gg M$

此時直接卷積的效率反而優於基於FFT實現的卷積。（O(M N) V.S. O(N logN) )

這種情況下，通常會把信號分成許多小段，每個小段長度和濾波器長度相當，通過重疊相加法（Overlap-Add method）或重疊保留法（Overlap-Save method）來進行加速。而每個小段與濾波器的卷積通過FFT間接得到。對於很大的圖像與相對特別小的卷積核卷積時同樣可以類似通過對圖像分塊來獲得加速。

DFT定義分析

最後，我們補充分析一下DFT/IDFT的定義。我們來看DFT/IDFT的定義，最常見的定義方式如下

$DFT[x(n)] := sum^{N-1}_{n=0} x(n)e^{-j n kfrac{2pi}{N}} =X(k), k=0,...,N-1 \ IDFT[X(k)] := frac{1}{N}sum^{N-1}_{k=0} X(k)e^{j n kfrac{2pi}{N}} =hat{x}(n), n=0,...,N-1$

這是一個純數學意義上的定義，你不需要理解時頻對稱問題，不需要理解採樣定理，也無需處理可能的混疊問題，你僅需把DFT當成一個正交變換，對信號做一個旋轉。

$X = Wx \ hat{x} = frac{1}{N}W^HX$

其中x, X為N維向量， W為 $N imes N$ 矩陣；係數1/N放到正、反變換中均可，也可以分兩個 $1/sqrt{N}$ 分別放到正反變換中，那樣變換矩陣就是真正的正交陣了，傳統上係數常放在反變換中。按照這種定義，可以證明，

$frac{1}{N}W^HW = I$

因此， $hat{x} = frac{1}{N}W^HX = frac{1}{N}W^HWx = x$ , 也即可以完美重建原信號，當然對於DFT點數不夠，小於原信號長度時，那麼就是對截斷信號進行變換了，自然也能夠通過反變換恢復截斷信號。因為只是正交變換轉過去又轉回來嘛。

但是很多時候你做FFT時是考慮著信號頻域特徵的，也即心裡是考慮著物理意義的。此時應該把DFT理解成DTFT頻域等間隔採樣，而根據採樣定理如果採樣間隔足夠小，是能夠由採樣值序列恢復出連續的DTFT頻譜的，此時可以認為二者等價。當你做FFT後，你實際上得到了原時域信號的頻譜，那麼後續對X(k)的處理也就是對頻譜 $X(e^{jw})$ 的處理。而根據時頻對稱性，你心裡應該很清楚對應時域究竟在做著什麼事情，反之亦然。

我認為卷積在信號處理的意義就是，給定輸入信號 $x(u)$ ，當該信號通過一個線性時不變系統or線性空間不變系統 $h(u)$ ，則輸出信號 $y(u)$ 可以通過卷積 $*$ 計算：

$y(u)=x(u)*h(u)$

而線性卷積和循環卷積只是兩種不同計算卷積的方法吧。對兩個長度分別為L和M的離散信號做線性卷積，可以得到長度為 $N=L+M-1$ 的信號，線性卷積的複雜度是 $O(N^2)$ , 如果將兩個離散信號都補零成為長度為 $Ngeq L+M-1$ 的離散信號，則可以使用快速傅里葉變換做循環卷積得到和線性卷積相同的結果，複雜度降低為 $O(NlogN)$ .

我從矩陣的角度簡單給個直觀的解釋吧。對於系統：

$y=xast h$

其中 $y$ 是輸出信號， $x$ 是輸入信號， $h$ 是線性時不變系統響應。根據卷積的定義，整個過程其實可以寫成矩陣的形式（因為矩陣的運算是線性的）：

$[ egin{bmatrix} vdots \ y[-1] \ y[0] \ y[1] \ y[2] \ y[3] \ vdots end{bmatrix} = egin{bmatrix} ddots cdots \ h[1] h[2] cdots h[M-1] 0 00 \ 0h[1] h[2] cdots h[M-1] 0 0 \ 00h[1] h[2] cdots h[M-1] 0\ 000h[1] h[2] cdots h[M-1] \ 0000h[1] h[2] cdots \ cdots ddots end{bmatrix} cdot egin{bmatrix} vdots \ x[-1] \ x[0] \ x[1] \ x[2] \ x[3] \ vdots end{bmatrix} ]$

當我們考慮有限長輸入信號和系統響應時（ $x[n], n=0,1,cdots, N-1$ ； $h[m],m=0,1,cdots,M-1$ ），上述卷積可以寫成矩陣形式：

$egin{bmatrix} y[0] \ y[1] \ vdots \ y[N+M-2] \ y[N+M-1] end{bmatrix}_{(N+M-1) imes1} = egin{bmatrix} h[M-1] 0 cdots000 \ h[M-2] h[M-1] cdots00 0 \ vdots vdots \ 00cdotsh[1] h[2] h[3]\ 00cdots0h[1] h[2] \ 00cdots00h[1] end{bmatrix}_{(N+M-1) imes N} cdot egin{bmatrix} x[0] \ x[1] \ vdots \ x[N-2] \ x[N-1] end{bmatrix}_{N imes 1}$

然後，我們來考慮循環卷積的形式。定義循環的長度為 $L$ ，假設 $L>N ext{ and } L>M$ 。還要定義一個值 $K=（N+M-1）-L$ ，且 $K>0$ 表示卷積輸出信號長度和循環卷積輸出信號長度的差值。我們再來看循環卷積的矩陣形式應該是：

$egin{bmatrix} y[0] \ y[1] \ vdots \ y[L-2] \ y[L-1] end{bmatrix}_{L imes1} = egin{bmatrix} h[M-1] 0 cdotsh[1]cdotsh[lfloor frac{K-1}{2} floor -1]h[lfloor frac{K-1}{2} floor ] \ h[M-2] h[M-1] 0 cdotsh[1]cdots h[M-3] \ vdots vdots \ 0cdots h[1] cdots h[M-1] 0cdots \ vdots vdots \ h[M-lfloor frac{K-1}{2} floor ]cdotsh[M-1]0cdotsh[1] h[2] \ h[M-lfloor frac{K-1}{2} floor -1]cdotsh[M-2]h[M-1]cdots0 h[1] end{bmatrix}_{L imes N} cdot egin{bmatrix} x[0] \ x[1] \ vdots \ x[N-2] \ x[N-1] end{bmatrix}_{N imes 1}$

其中 $lfloor floor$ 表示向下取整。很明顯，循環卷積得到的輸出信號在頭和尾上產生了誤差，誤差的來源於周期延拓的系統響應對輸入信號的線性疊加。直觀上，可以想像為對原輸出信號進行 $L$ 長度的周期延拓，由於 $L$ 小於原輸出信號的周期 $(N+M-1)$ ，所以在原輸出信號的頭和尾產生了疊加，帶來了誤差（distortion）。

如果K&<0，則上述循環卷積形式有所不同，循環卷積矩陣不在有多出來的循環項。直觀上，輸出信號也不再有因為周期延拓帶來的誤差（distortion）。

循環卷積可以在fft的頻域處理，節約時間，工程上用的多些。在兩個信號長度和減一的範圍限制下兩者結果一樣。推薦看北京理工大學的數字信號處理，然後再自己模擬下，會很清楚。

刀是什麼刀? 金絲大環刀(誤

信號是什麼信號? 1-D音頻信號還是2-D圖像信號?

意義是什麼意義? 物理意義還是工程意義?

最後問題來了, 少年你為何要多打一個句號? 讓我這完美強迫症患者怎麼容忍!

題是要答的:

卷積的意義 - yeeman的專欄

滿意請結帖. (誤是贊同