圓周摺積

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

$x_T(t)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}x(t-kT)=\sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}x(t+kT).$

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

$\begin{array}{cc}y(t)& =\underset{t_o}{\overset{t_o+T}{\int }}{h}_T(\tau )\cdot x_T(t-\tau )d\tau \\ & =\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}h(\tau )\cdot x_T(t-\tau )d\tau =(x_T*h)(t),\end{array}$

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

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

$\begin{array}{cc}(x_N*h)[n]& =\sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}h[m]\cdot x_N[n-m]\\ & =\sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}(h[m]\cdot \sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}x[n-m-kN]).\end{array}$

如果引入循环矩阵，那么两个长度都为 N 的离散信号（长度不一致，则可以通过补零来对齐两信号）的循环卷积则可以写成矩阵的形式。设有长度为 N 的离散信号 $𝒙={\left[\begin{array}{cccc}{x}_0& x_1& \cdots & x_{N-1}\end{array}\right]}^{\mathrm{T}}$，则由该向量构建的循环矩阵有如下形式

${𝐂}_x=\left[\begin{array}{cccc}{x}_0& x_{N-1}& \cdots & x_1\\ x_1& x_0& \cdots & x_2\\ ⋮& ⋮& \ddots & ⋮\\ x_{N-1}& x_{N-2}& \cdots & x_0\end{array}\right].$

此时，信号$𝒙\in {ℝ}^{N\times 1}$与信号$𝒚\in {ℝ}^{N\times 1}$的圆周卷积可以写为

$𝒙\otimes 𝒚={𝐂}_{𝒙}𝒚.$

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

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

相關條目

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

參考文獻

• Template:Cite book.
• Template:Cite book.

外部連結

cnx Template:Wayback