圓周摺積

兩個函數的圓周摺積是由他們的週期延伸所來定義的。週期延伸意思是把原本的函數平移某個週期 T 的整數倍後再全部加起來，所產生的新函數。${\displaystyle x(t)}$ 的週期延伸可以寫成

${\displaystyle x_{T}(t)\ {\stackrel {\mathrm {def} }{=}}\ \sum _{k=-\infty }^{\infty }x(t-kT)=\sum _{k=-\infty }^{\infty }x(t+kT).}$

兩個函數 ${\displaystyle x(t)}$ 與 ${\displaystyle h(t)}$ 的圓周摺積 ${\displaystyle (x\otimes h)(t)}$ 可用兩種互相等價的方式來定義

${\displaystyle {\begin{aligned}y(t)&=\int _{t_{o}}^{t_{o}+T}h_{T}(\tau )\cdot x_{T}(t-\tau )\,d\tau \\&=\int _{-\infty }^{\infty }h(\tau )\cdot x_{T}(t-\tau )\,d\tau \quad =\quad (x_{T}*h)(t),\end{aligned}}}$

其中 ${\displaystyle *}$ 表示原本的（線性）摺積。

類似地，對於離散訊號（數列），可以定義週期 N 的圓周摺積 ${\displaystyle (x\otimes h)[n]}$ 為

${\displaystyle {\begin{aligned}(x_{N}*h)[n]&=\sum _{m=-\infty }^{\infty }h[m]\cdot x_{N}[n-m]\\&=\sum _{m=-\infty }^{\infty }\left(h[m]\cdot \sum _{k=-\infty }^{\infty }x[n-m-kN]\right).\,\end{aligned}}}$

如果引入循環矩陣，那麼兩個長度都為 N 的離散訊號（長度不一致，則可以通過補零來對齊兩訊號）的圓周摺積則可以寫成矩陣的形式。設有長度為 N 的離散訊號 ${\displaystyle {\boldsymbol {x}}={\begin{bmatrix}x_{0}&x_{1}&\cdots &x_{N-1}\end{bmatrix}}^{\rm {T}}}$，則由該向量構建的循環矩陣有如下形式

${\displaystyle \mathbf {C} _{x}={\begin{bmatrix}x_{0}&x_{N-1}&\cdots &x_{1}\\x_{1}&x_{0}&\cdots &x_{2}\\\vdots &\vdots &\ddots &\vdots \\x_{N-1}&x_{N-2}&\cdots &x_{0}\end{bmatrix}}.}$

此時，訊號${\displaystyle {\boldsymbol {x}}\in \mathbb {R} ^{N\times 1}}$與訊號${\displaystyle {\boldsymbol {y}}\in \mathbb {R} ^{N\times 1}}$的圓周摺積可以寫為

${\displaystyle {\boldsymbol {x}}\otimes {\boldsymbol {y}}=\mathbf {C} _{\boldsymbol {x}}{\boldsymbol {y}}.}$

離散訊號的圓周摺積可以經由圓周摺積定理使用快速傅立葉變換（FFT）而有效率的計算。因此，若原本的（線性）摺積能轉換成圓周摺積來計算，會遠比直接計算更快速。考慮到長度 ${\displaystyle L}$ 和長度 ${\displaystyle M}$ 的有限長度離散訊號，做摺積之後會成為長度 ${\displaystyle L+M-1}$ 的訊號，因此只要把兩離散訊號補上適當數目的零（zero-padding）成為 N 點訊號，其中  ${\displaystyle N\geq L+M-1\,}$  ，則它們的圓周摺積就與摺積相等。即可接著用 N 點 FFT 作計算。

用以上方法計算摺積時，若兩個訊號長度相差很多，則較短者須補上相當多的零，太不經濟。而且在某些情況下，例如較短的 ${\displaystyle h[n]}$ 是一個 FIR 濾波器而較長的 ${\displaystyle x[n]}$ 是未知長度的輸入（像語音）時，直接用以上方法要等所有的輸入都收到後才能開始算輸出訊號，太不方便。這時可以把 ${\displaystyle x[n]}$ 分割成許多適當長度的區塊（稱為 block convolution），然後一段一段的處理。經過濾波後的段落再仔細的連接起來，藉由輸入或輸出的重疊來處理區塊連接的部份。這兩種做法分別稱為重疊-儲存之摺積法和重疊-相加之摺積法。

相關條目

• 摺積
• 圓周摺積定理
• DFT與圓周摺積

參考文獻

• Rabiner, Lawrence R.; Gold, Bernard. Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. 1975: pp 63–67. ISBN 0-13-914101-4. 引文格式1維護：冗餘文本 (link).
• Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John A. Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. 1999. ISBN 0-13-754920-2..

外部連結

cnx （頁面存檔備份，存於網際網路檔案館）