卷积

在泛函分析中，捲積（convolution），或译为疊積、褶積或旋積，是透過两个函数${\displaystyle f}$和${\displaystyle g}$生成第三个函数的一种数学算子，表徵函数${\displaystyle f}$与经过翻转和平移的${\displaystyle g}$的乘積函數所圍成的曲邊梯形的面積。如果将参加卷积的一个函数看作区间的指示函数，卷积还可以被看作是“滑動平均”的推廣。

定义[编辑]

卷积是数学分析中一种重要的运算。设：${\displaystyle f(t)}$和${\displaystyle g(t)}$是实数${\displaystyle \mathbb {R} }$上的两个可积函数，定义二者的卷积${\displaystyle (f*g)(t)}$为如下特定形式的积分变换：

${\displaystyle (f*g)(t)\triangleq \int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,\mathrm {d} \tau }$

${\displaystyle (f*g)(t)}$仍为可积函数，并且有着：

${\displaystyle (f*g)(t)\triangleq \int _{-\infty }^{\infty }f(t-\tau )g(\tau )\,d\tau =(g*f)(t)}$

函数${\displaystyle f}$和${\displaystyle g}$，如果只支撑在${\displaystyle [0,\infty ]}$之上，则积分界限可以截断为：

${\displaystyle (f*g)(t)=\int _{0}^{t}f(\tau )g(t-\tau )\,d\tau \quad }$对于${\displaystyle \ f,g:[0,\infty )\to \mathbb {R} }$

对于两个得出复数值的多元实变函数（英语：Function of several real variables），可以定义二者的卷积为如下形式的多重积分：

${\displaystyle {\begin{aligned}(f*g)(t_{1},t_{2},\cdots ,t_{n})&\triangleq \int \int \cdots \int _{\mathbb {R} ^{n}}f(\tau _{1},\tau _{2},\cdots ,\tau _{n})g(t_{1}-\tau _{1},t_{2}-\tau _{2},\cdots ,t_{n}-\tau _{n},)\,d\tau _{1}d\tau _{2}\cdots d\tau _{n}\\&\triangleq \int _{\mathbb {R} ^{n}}f(\tau )g(t-\tau )\,d^{n}\tau \end{aligned}}}$

卷积有一个通用的工程上的符号约定^[1]：

${\displaystyle f(t)*g(t)\triangleq \underbrace {\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau } _{(f*g)(t)}}$

它必须被谨慎解释以避免混淆。例如：${\displaystyle f(t)*g(t-t_{0})}$等价于${\displaystyle (f*g)(t-t_{0})}$，而${\displaystyle f(t-t_{0})*g(t-t_{0})}$却实际上等价于${\displaystyle (f*g)(t-2t_{0})}$^[2]。

历史[编辑]

卷积运算的最早使用出现在达朗贝尔于1754年出版的《宇宙体系的几个要点研究》中对泰勒定理的推导之中^[3]。还有西尔维斯特·拉克鲁瓦（英语：Sylvestre François Lacroix），将${\textstyle \int f(u)\cdot g(x-u)\,du}$类型的表达式，用在他的1797年–1800年出版的著作《微分与级数论文》中^[4]。此后不久，卷积运算出现在皮埃尔-西蒙·拉普拉斯、约瑟夫·傅里叶和西梅翁·泊松等人的著作中。这个运算以前有时叫做“Faltung”（德语中的折叠）、合成乘积、叠加积分或卡森积分^[5]。

“卷积”这个术语早在1903年就出现了，然而其定义在早期使用中是相当生僻的^[6][7]，直到1950年代或1960年代之前都未曾广泛使用。

简介[编辑]

如果${\displaystyle f}$和${\displaystyle g}$都是在L^p 空间${\displaystyle L^{1}(\mathbb {R} ^{n})}$内的勒贝格可积函数，则二者的卷积存在，并且在这种情况下${\displaystyle f*g}$也是可积的^[8]。这是托內利定理的结论。对于在${\displaystyle L^{1}}$中的函数在离散卷积下，或更一般的对于在任何群的上的卷积，这也是成立的。同样的，如果${\displaystyle f\in L^{1}(\mathbb {R} ^{n})}$而${\displaystyle g\in L^{p}(\mathbb {R} ^{n})}$，这里的${\displaystyle 1\leq p\leq \infty }$，则${\displaystyle f*g\in L^{p}(\mathbb {R} ^{n})}$，并且其L^p 范数间有着不等式：

${\displaystyle \|{f}*g\|_{p}\leq \|f\|_{1}\|g\|_{p}}$

在${\displaystyle p=1}$的特殊情况下，这显示出${\displaystyle L^{1}}$是在卷积下的巴拿赫代数（并且如果${\displaystyle f}$和${\displaystyle g}$几乎处处非负则两边间等式成立）。

卷积与傅里叶变换有着密切的关系。例如两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换，利用此一性質，能簡化傅里叶分析中的许多问题。

由卷积得到的函数${\displaystyle f*g}$，一般要比${\displaystyle f}$和${\displaystyle g}$都光滑。特别当${\displaystyle g}$为具有紧支集的光滑函数，${\displaystyle f}$为局部可积时，它们的卷积${\displaystyle f*g}$也是光滑函数。利用这一性质，对于任意的可积函数${\displaystyle f}$，都可以简单地构造出一列逼近于${\displaystyle f}$的光滑函数列${\displaystyle f_{s}}$，这种方法称为函数的光滑化或正则化。

函数${\displaystyle f(t)}$和${\displaystyle g(t)}$的互相关${\displaystyle (f\star g)(\tau )}$，等价于${\displaystyle f(-\tau )}$的共轭复数${\displaystyle {\overline {f(-\tau )}}}$与${\displaystyle g(\tau )}$的卷积：

${\displaystyle (f\star g)(\tau )\triangleq \int _{-\infty }^{\infty }{\overline {f(t-\tau )}}g(t)\,dt={\overline {f(-\tau )}}*g(\tau )}$

这里的${\displaystyle \tau }$叫做移位（displacement）或滞后（lag）。

对于單位脈衝函数${\displaystyle \delta (t)}$和某个函数${\displaystyle h(t)}$，二者得到的捲積就是${\displaystyle h(t)}$本身，此${\displaystyle h(t)}$被稱為衝激響應：

${\displaystyle (\delta *h)(t)=\int _{-\infty }^{\infty }\delta (\tau )h(t-\tau )\,d\tau =h(t)}$

在连续时间线性非时变系统中，输出信号${\displaystyle y(t)}$被描述为输入信号${\displaystyle x(t)}$与冲激响应${\displaystyle h(t)}$的卷积^[9]：

${\displaystyle y(t)=(x*h)(t)\ \triangleq \ \int \limits _{-\infty }^{\infty }x(t-\tau )\cdot h(\tau )\,\mathrm {d} \tau =\int \limits _{-\infty }^{\infty }x(\tau )\cdot h(t-\tau )\,\mathrm {d} \tau }$

两个独立的随机变量${\displaystyle U}$和${\displaystyle V}$，每个都有一个概率密度函数，二者之和的概率密度，是它们单独的密度函数的卷积：

${\displaystyle f_{U+V}(x)=\int _{-\infty }^{\infty }f_{U}(y)f_{V}(x-y)\,dy=\left(f_{U}*f_{V}\right)(x)}$

图解[编辑]

已知右侧第一行图中两个函数${\displaystyle f(t)}$和${\displaystyle g(t)}$。 首先將兩個函數都用约束变量${\displaystyle \tau }$來表示，并将${\displaystyle g(\tau )}$翻转至纵轴另一侧，从而得到右侧第二行图中${\displaystyle f(\tau )}$和${\displaystyle g(-\tau )}$。 向函数${\displaystyle g(-\tau )}$增加一个时间偏移量${\displaystyle t}$，得到函数${\displaystyle g(-(\tau -t))=g(t-\tau )}$。${\displaystyle t}$不是常数而是自由变量，当${\displaystyle t}$取不同值时，${\displaystyle g(t-\tau )}$能沿着${\displaystyle \tau }$轴“滑动”。如果${\displaystyle t}$是正值，则${\displaystyle g(t-\tau )}$等于${\displaystyle g(-\tau )}$沿着${\displaystyle \tau }$轴向右（朝向${\displaystyle +\infty }$）滑动数量${\displaystyle t}$。如果${\displaystyle t}$是负值，则${\displaystyle g(t-\tau )}$等价于${\displaystyle g(-\tau )}$向左（朝向${\displaystyle -\infty }$）滑动数量${\displaystyle |t|}$。 讓${\displaystyle t}$從${\displaystyle -\infty }$变化至${\displaystyle +\infty }$，当兩個函數交會時，計算交會範圍中兩個函數乘積的積分值。換句話說，在时间${\displaystyle t}$，计算函数${\displaystyle f(\tau )}$经过权重函数${\displaystyle g(t-\tau )}$施以权重后其下的面积。右侧第三、第四和第五行图中，分别是${\displaystyle t=0}$、${\displaystyle t=2.5}$和${\displaystyle t=5.5}$时的情况，从${\displaystyle t>1}$时开始有交会，例如在第四行图中，${\displaystyle \tau =0}$则${\displaystyle g(t-\tau )=g(2.5)}$，${\displaystyle \tau =1.5}$则${\displaystyle g(t-\tau )=g(1)}$，对于${\displaystyle \tau \notin [0,1.5]}$有着${\displaystyle f(\tau )g(t-\tau )=0}$。 最後得到的波形（未包含在此圖中）就是${\displaystyle f}$和${\displaystyle g}$的捲積。
两个矩形脈衝波的捲積。其中函数${\displaystyle g}$首先对${\displaystyle \tau =0}$反射，接著平移${\displaystyle t}$，成為${\displaystyle g(t-\tau )}$。那么重叠部份的面积就相当于${\displaystyle t}$处的卷积，其中橫坐標代表待变量${\displaystyle \tau }$以及新函數${\displaystyle f\ast g}$的自變量${\displaystyle t}$。
矩形脈衝波和指數衰減脈衝波的捲積（後者可能出現於RC電路中），同樣地重疊部份面積就相當於${\displaystyle t}$處的捲積。注意到因為${\displaystyle g}$是對稱的，所以在這兩張圖中，反射並不會改變它的形狀。

周期卷积[编辑]

两个${\displaystyle T}$周期的函数${\displaystyle h_{_{T}}(t)}$和${\displaystyle x_{_{T}}(t)}$的“周期卷积”定义为^[10][11]：

${\displaystyle \int _{t_{0}}^{t_{0}+T}h_{_{T}}(\tau )x_{_{T}}(t-\tau )\,d\tau }$

这里的${\displaystyle t_{0}}$是任意参数。

任何可积分函数（英语：Absolutely integrable function）${\displaystyle s(t)}$，都可以通过求函数${\displaystyle s(t)}$的所有整数倍${\displaystyle P}$的平移的总和，从而制作出具有周期${\displaystyle P}$的周期函数 ${\displaystyle s_{_{P}}(t)}$，这叫做周期求和（英语：Periodic summation）：

${\displaystyle s_{_{P}}(t)\triangleq \sum _{m=-\infty }^{\infty }s(t+mP)=\sum _{m=-\infty }^{\infty }s(t-mP),\quad m\in \mathbb {Z} }$

对于无周期函数${\displaystyle h}$与${\displaystyle x}$，其周期${\displaystyle T}$的周期求和分别是${\displaystyle h_{_{T}}(t)}$与${\displaystyle x_{_{T}}(t)}$，${\displaystyle h}$与${\displaystyle x}$的周期卷积，可以定义为${\displaystyle h(t)}$与${\displaystyle x_{_{T}}(t)}$的常规卷积，或${\displaystyle x(t)}$与${\displaystyle h_{_{T}}(t)}$的常规卷积，二者都等价于${\displaystyle h_{_{T}}(t)}$与${\displaystyle x_{_{T}}(t)}$的周期积分：

${\displaystyle (h*x_{_{T}})(t)\ \triangleq \ \ \int _{-\infty }^{\infty }h(\tau )x_{_{T}}(t-\tau )\,d\tau \ =\ \int _{t_{0}}^{t_{0}+T}h_{_{T}}(\tau )x_{_{T}}(t-\tau )\,d\tau }$

${\displaystyle (h*x_{_{T}})(t)=(x*h_{_{T}})(t)}$

圆周卷积是周期卷积的特殊情况^[11][12]，其中函数${\displaystyle h}$和${\displaystyle x}$二者的非零部份，都限定在区间${\displaystyle [0,T]}$之内，此时的周期求和称为“周期延拓”。${\displaystyle h*x_{_{T}}}$中函数${\displaystyle x_{_{T}}}$可以通过取非负余数的模除运算表达为“圆周函数”：

${\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} }$

而积分的界限可以缩简至函数${\displaystyle h}$的长度范围${\displaystyle [0,T]}$：

${\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )x((t-\tau )_{\mathrm {mod} \ T})\ d\tau }$

离散卷积[编辑]

对于定义在整數${\displaystyle \mathbb {Z} }$上且得出复数值的函数${\displaystyle f[n]}$和${\displaystyle g[n]}$，离散卷积定义为^[13]：

${\displaystyle (f*g)[n]\ \ \triangleq \ \sum _{m=-\infty }^{\infty }{f[m]g[n-m]}=\sum _{m=-\infty }^{\infty }f[n-m]\,g[m]}$

這裡一樣把函數定義域以外的值當成零，所以可以擴展函數到所有整數上（如果本來不是的話）。两个有限序列的卷积的定义，是将这些序列扩展成在整数集合上有限支撑的函数。在这些序列是两个多项式的系数之时，这两个多项式的普通乘积的系数，就是这两个序列的卷积。这叫做序列系数的柯西乘积。

當${\displaystyle g[n]}$的支撐集為有限長度的${\displaystyle \{-M,-M+1,\dots ,M-1,M\}}$之时，上式會變成有限求和：

${\displaystyle (f*g)[n]=\sum _{m=-M}^{M}f[n-m]g[m]}$

多维离散卷积[编辑]

类似于一维情况，使用星号表示卷积，而维度体现在星号的数量上，${\displaystyle M}$维卷积就写为${\displaystyle M}$个星号。下面是${\displaystyle M}$维信号的卷积的表示法：

${\displaystyle y(n_{1},n_{2},...,n_{_{M}})=h(n_{1},n_{2},...,n_{_{M}})*{\overset {M}{\cdots }}*x(n_{1},n_{2},...,n_{_{M}})}$

对于离散值的信号，这个卷积可以直接如下这样计算：

${\displaystyle \sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }...\sum _{k_{_{M}}=-\infty }^{\infty }h(k_{1},k_{2},...,k_{_{M}})x(n_{1}-k_{1},n_{2}-k_{2},...,n_{_{M}}-k_{_{M}})}$

结果的离散多维卷积所支撑的输出区域，基于两个输入信号所支撑的大小和区域来决定。

离散周期卷积[编辑]

对于离散序列和一个参数${\displaystyle N}$，无周期函数${\displaystyle h}$和${\displaystyle x}$的“周期卷积”是为：

${\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}\ =\ \sum _{m=0}^{N-1}\left(\sum _{k=-\infty }^{\infty }{h}[m-kN]\right)x_{_{N}}[n-m]}$

这个函数有周期${\displaystyle N}$，它有最多${\displaystyle N}$个唯一性的值。${\displaystyle h}$和${\displaystyle x}$的非零范围都是${\displaystyle [0,N-1]}$的特殊情况叫做圆周卷积：

${\displaystyle (h*x_{_{N}})[n]=\sum _{m=0}^{N-1}h[m]x_{_{N}}[n-m]=\sum _{m=0}^{N-1}h[m]x[(n-m)_{\bmod {N}}]}$

离散圆周卷积可简约为矩阵乘法，这里的积分变换的核函数是循环矩阵:

${\displaystyle {\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{_{N-1}}\end{bmatrix}}={\begin{bmatrix}h_{0}&h_{_{N-1}}&\cdots &h_{1}\\h_{1}&h_{0}&\cdots &h_{2}\\\vdots &\vdots &\ddots &\vdots \\h_{_{N-1}}&h_{_{N-2}}&\cdots &h_{0}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\\vdots \\x_{_{N-1}}\end{bmatrix}}}$

圆周卷积最经常出现的快速傅里叶变换的实现算法比如雷德演算法之中。

性质[编辑]

代数[编辑]

各种卷积算子都满足下列性质：

交换律

${\displaystyle f*g=g*f\,}$

结合律

${\displaystyle f*(g*h)=(f*g)*h\,}$

分配律

${\displaystyle f*(g+h)=(f*g)+(f*h)\,}$

数乘结合律

${\displaystyle a(f*g)=(af)*g=f*(ag)\,}$

其中${\displaystyle a}$为任意实数（或复数）。

复数共轭

${\displaystyle {\overline {f*g}}={\overline {f}}*{\overline {g}}}$

微分有关

${\displaystyle (f*g)'=f'*g=f*g'}$

积分有关

如果${\textstyle F(t)=\int _{-\infty }^{t}f(\tau )d\tau }$，并且${\textstyle G(t)=\int _{-\infty }^{t}g(\tau )\,d\tau }$，则有：

${\displaystyle (F*g)(t)=(f*G)(t)=\int _{-\infty }^{t}(f*g)(\tau )\,d\tau }$

积分[编辑]

如果${\displaystyle f}$和${\displaystyle g}$是可积分函数，则它们在整个空间上的卷积的积分，简单的就是它们积分的乘积^[14]：

${\displaystyle \int _{\mathbb {R} ^{n}}(f*g)(t)\,d^{n}t=\left(\int _{\mathbb {R} ^{n}}f(t)\,d^{n}t\right)\left(\int _{\mathbb {R} ^{n}}g(t)\,d^{n}t\right)}$

这是富比尼定理的结果。如果${\displaystyle f}$和${\displaystyle g}$只被假定为非负可测度函数，根据托内利定理，这也是成立的。

微分[编辑]

在一元函数情况下，${\displaystyle f}$和${\displaystyle g}$的卷积的导数有着：

${\displaystyle {\frac {d}{dt}}(f*g)={\frac {df}{dt}}*g=f*{\frac {dg}{dt}}}$

这里的${\displaystyle {\frac {d}{dt}}}$是微分算子。更一般的说，在多元函数的情况下，对偏导数也有类似的公式：

${\displaystyle {\frac {\partial }{\partial t_{i}}}(f*g)={\frac {\partial f}{\partial t_{i}}}*g=f*{\frac {\partial g}{\partial t_{i}}}}$

这就有了一个特殊结论，卷积可以看作“光滑”运算：${\displaystyle f}$和${\displaystyle g}$的卷积可微分的次数，是${\displaystyle f}$和${\displaystyle g}$的总数。

这些恒等式成立的严格条件，为${\displaystyle f}$和${\displaystyle g}$是绝对可积分的，并且至少二者之一有绝对可积分（${\displaystyle L^{1}}$）弱导数，这是Young卷积不等式（英语：Young's convolution inequality）的结论。

在离散情况下，差分算子${\displaystyle \Delta [f](n)=f(n+1)-f(n)}$满足类似的关系：

${\displaystyle \Delta (f*g)=(\Delta f)*g=f*(\Delta g)}$

卷积定理[编辑]

卷积定理指出^[15]，在适当的条件下，两个函数（或信号）的卷积的傅里叶变换，是它们的傅里叶变换的逐点乘积。更一般的说，在一个域（比如时域）中的卷积等于在其他域（比如频域）逐点乘法。

设两个函数${\displaystyle g(x)}$和${\displaystyle h(x)}$，分别具有傅里叶变换${\displaystyle G(s)}$和${\displaystyle H(s)}$：

${\displaystyle {\begin{aligned}G(s)&\triangleq {\mathcal {F}}\{g\}(s)=\int _{-\infty }^{\infty }g(x)e^{-i2\pi sx}\,dx,\quad s\in \mathbb {R} \\H(s)&\triangleq {\mathcal {F}}\{h\}(s)=\int _{-\infty }^{\infty }h(x)e^{-i2\pi sx}\,dx,\quad s\in \mathbb {R} \end{aligned}}}$

这里的${\displaystyle {\mathcal {F}}}$算子指示傅里叶变换。

卷积定理声称：

${\displaystyle {\mathcal {F}}\{g*h\}(s)=G(s)H(s),\quad s\in \mathbb {R} }$

${\displaystyle {\mathcal {F}}\{g\cdot h\}(s)=G(s)*H(s),\quad s\in \mathbb {R} }$

应用逆傅里叶变换${\displaystyle {\mathcal {F}}^{-1}}$产生推论：

${\displaystyle (g*h)(s)={\mathcal {F}}^{-1}\{G\cdot H\},\quad s\in \mathbb {R} }$

${\displaystyle (g\cdot h)(s)={\mathcal {F}}^{-1}\{G*H\},\quad s\in \mathbb {R} }$

这里的算符${\displaystyle \,\cdot \,}$指示逐点乘法。

这一定理对拉普拉斯变换、双边拉普拉斯变换、Z变换、梅林变换和Hartley变换（英语：Hartley transform）等各种傅里叶变换的变体同样成立。在调和分析中还可以推广到在局部紧致的阿贝尔群上定义的傅里叶变换。

周期卷积[编辑]

对于周期为${\displaystyle P}$的函数${\displaystyle g_{_{P}}(x)}$和${\displaystyle h_{_{P}}(x)}$，可以被表达为二者的周期求和（英语：Periodic summation）：

${\displaystyle {\begin{aligned}g_{_{P}}(x)\ &\triangleq \sum _{m=-\infty }^{\infty }g(x-mP),\quad m\in \mathbb {Z} \\h_{_{P}}(x)\ &\triangleq \sum _{m=-\infty }^{\infty }h(x-mP),\quad m\in \mathbb {Z} \end{aligned}}}$

它们的傅里叶级数系数为：

${\displaystyle {\begin{aligned}G[k]&\triangleq {\mathcal {F}}\{g_{_{P}}\}[k]={\frac {1}{P}}\int _{P}g_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \\H[k]&\triangleq {\mathcal {F}}\{h_{_{P}}\}[k]={\frac {1}{P}}\int _{P}h_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \end{aligned}}}$

这里的${\displaystyle {\mathcal {F}}}$算子指示傅里叶级数积分。

逐点乘积${\displaystyle g_{_{P}}(x)\cdot h_{_{P}}(x)}$的周期也是${\displaystyle P}$，它的傅里叶级数系数为：

${\displaystyle {\mathcal {F}}\{g_{_{P}}\cdot h_{_{P}}\}[k]=(G*H)[k]}$

周期卷积${\displaystyle (g_{_{P}}*h)(x)}$的周期也是${\displaystyle P}$，周期卷积的卷积定理为：

${\displaystyle {\mathcal {F}}\{g_{_{P}}*h\}[k]=\ P\cdot G[k]\ H[k]}$

离散卷积[编辑]

对于作为两个连续函数采样的序列${\displaystyle g[n]}$和${\displaystyle h[n]}$，它们具有离散时间傅里叶变换${\displaystyle G(s)}$和${\displaystyle H(s)}$：

${\displaystyle {\begin{aligned}G(s)&\triangleq {\mathcal {F}}\{g\}(s)=\sum _{n=-\infty }^{\infty }g[n]\cdot e^{-i2\pi sn}\;,\quad s\in \mathbb {R} \\H(s)&\triangleq {\mathcal {F}}\{h\}(s)=\sum _{n=-\infty }^{\infty }h[n]\cdot e^{-i2\pi sn}\;,\quad s\in \mathbb {R} \end{aligned}}}$

这里的${\displaystyle {\mathcal {F}}}$算子指示离散时间傅里叶变换（DTFT）。

离散卷积的卷积定理为：

${\displaystyle {\mathcal {F}}\{g*h\}(s)=\ G(s)H(s)}$

离散周期卷积[编辑]

对于周期为${\displaystyle N}$的序列${\displaystyle g_{_{N}}[n]}$和${\displaystyle h_{_{N}}[n]}$：

${\displaystyle {\begin{aligned}g_{_{N}}[n]\ &\triangleq \sum _{m=-\infty }^{\infty }g[n-mN],\quad m,n\in \mathbb {Z} \\h_{_{N}}[n]\ &\triangleq \sum _{m=-\infty }^{\infty }h[n-mN],\quad m,n\in \mathbb {Z} \end{aligned}}}$

相较于离散时间傅里叶变换${\displaystyle G(s)}$和${\displaystyle H(s)}$的周期是${\displaystyle 1}$，它们是按间隔${\displaystyle 1/N}$采样${\displaystyle G(s)}$和${\displaystyle H(s)}$，并在${\displaystyle N}$个采样上进行了逆离散傅里叶变换（DFT^-1或IDFT）的结果。

离散周期卷积${\displaystyle (g_{_{N}}*h)[n]}$的周期也是${\displaystyle N}$。离散周期卷积定理为：

${\displaystyle {\mathcal {F}}\{g_{_{N}}*h\}[k]=\ \underbrace {{\mathcal {F}}\{g_{_{N}}\}[k]} _{G(k/N)}\cdot \underbrace {{\mathcal {F}}\{h_{_{N}}\}[k]} _{H(k/N)},\quad k,n\in \mathbb {Z} }$

这里的${\displaystyle {\mathcal {F}}}$算子指示长度${\displaystyle N}$的离散傅里叶变换（DFT）。

它有着推论：

${\displaystyle (g_{_{N}}*h)[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{g_{_{N}}\}\cdot {\mathcal {F}}\{h_{_{N}}\}\}}$

对于其非零时段小于等于${\displaystyle N}$的${\displaystyle g}$和${\displaystyle h}$，离散圆周卷积的卷积定理为：

${\displaystyle (g_{_{N}}*h)[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{g\}\cdot {\mathcal {F}}\{h\}\}}$

推广[编辑]

卷积的概念还可以推广到数列、测度以及广义函数上去。函数${\displaystyle f,g}$是定義在${\displaystyle \mathbb {R} ^{n}}$上的可測函數（measurable function），${\displaystyle f}$与${\displaystyle g}$存在卷积并记作${\displaystyle f*g}$。如果函數不是定義在${\displaystyle \mathbb {R} ^{n}}$上，可以把函數定義域以外的值都規定成零，這樣就變成一個定義在${\displaystyle \mathbb {R} ^{n}}$上的函數。

若G是有某m 测度的群（例如豪斯多夫空间上哈尔测度下局部紧致的拓扑群），对于G上m-勒贝格可积的实数或复数函数f和g，可定义它们的卷积：

${\displaystyle (f*g)(x)=\int _{G}f(y)g(xy^{-1})\,dm(y)\,}$

对于这些群上定义的卷积同样可以给出诸如卷积定理等性质，但是这需要对这些群的表示理论以及调和分析的彼得-外尔定理。

离散卷積的計算方法[编辑]

計算卷積${\displaystyle f[n]*g[n]}$有三種主要的方法，分別為

1. 直接計算（Direct Method）
2. 快速傅立葉轉換（FFT）
3. 分段卷積（sectioned convolution）

方法1是直接利用定義來計算卷積，而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法，如使用數論轉換。

方法1：直接計算[编辑]

• 作法：利用卷積的定義

${\displaystyle y[n]=f[n]*g[n]=\sum _{m=0}^{M-1}f[n-m]g[m]}$

• 若${\displaystyle f[n]}$和${\displaystyle g[n]}$皆為實數信號，則需要${\displaystyle MN}$個乘法。

• 若${\displaystyle f[n]}$和${\displaystyle g[n]}$皆為更一般性的複數信號，不使用複數乘法的快速演算法，會需要${\displaystyle 4MN}$個乘法;但若使用複數乘法的快速演算法，則可簡化至${\displaystyle 3MN}$個乘法。

因此，使用定義直接計算卷積的複雜度為${\displaystyle O(MN)}$。

方法2：快速傅立葉轉換[编辑]

• 概念：由於兩個離散信號在時域（time domain）做卷積相當於這兩個信號的離散傅立葉轉換在頻域（frequency domain）做相乘：

${\displaystyle y[n]=f[n]*g[n]\leftrightarrow Y[f]=F[f]G[f]}$

，可以看出在頻域的計算較簡單。

• 作法：因此這個方法即是先將信號從時域轉成頻域：

${\displaystyle F[f]=DFT_{P}(f[n]),G[f]=DFT_{P}(g[n])}$

，於是

${\displaystyle Y[f]=DFT_{P}(f[n])DFT_{P}(g[n])}$

，最後再將頻域信號轉回時域，就完成了卷積的計算：

${\displaystyle y[n]=IDFT_{P}{DFT_{P}(f[n])DFT_{P}(g[n])}}$

總共做了2次DFT和1次IDFT。

• 特別注意DFT和IDFT的點數${\displaystyle P}$要滿足${\displaystyle P\geq M+N-1}$。

• 由於DFT有快速演算法FFT，所以運算量為${\displaystyle O(P\log _{2}P)}$

• 假設${\displaystyle P}$點DFT的乘法量為${\displaystyle a}$，${\displaystyle f[n]}$和${\displaystyle g[n]}$為一般性的複數信號，並使用複數乘法的快速演算法，則共需要${\displaystyle 3a+3P}$個乘法。

方法3：分段卷積[编辑]

• 概念：將${\displaystyle f[n]}$切成好幾段（section），每一段分別和${\displaystyle g[n]}$做卷積後，再將結果相加。

• 作法：先將${\displaystyle f[n]}$切成每段長度為${\displaystyle L}$的區段（${\displaystyle L>M}$），假設共切成S段：

${\displaystyle f[n](n=0,1,...,N-1)\to f_{1}[n],f_{2}[n],f_{3}[n],...,f_{S}[n](S=\left\lceil {\frac {N}{L}}\right\rceil )}$

Section 1: ${\displaystyle f_{1}[n]=f[n],n=0,1,...,L-1}$

Section 2: ${\displaystyle f_{2}[n]=f[n+L],n=0,1,...,L-1}$

${\displaystyle \vdots }$

Section r: ${\displaystyle f_{r}[n]=f[n+(r-1)L],n=0,1,...,L-1}$

${\displaystyle \vdots }$

Section S: ${\displaystyle f_{S}[n]=f[n+(S-1)L],n=0,1,...,L-1}$

，${\displaystyle f[n]}$為各個section的和

${\displaystyle f[n]=\sum _{r=1}^{S}f_{r}[n+(r-1)L]}$。

因此，

${\displaystyle y[n]=f[n]*g[n]=\sum _{r=1}^{S}\sum _{m=0}^{M-1}f_{r}[n+(r-1)L-m]g[m]}$，

每一小段作卷積則是採用方法2，先將時域信號轉到頻域相乘，再轉回時域：

${\displaystyle y[n]=IDFT(\sum _{r=1}^{S}\sum _{m=0}^{M-1}DFT_{P}(f_{r}[n+(r-1)L-m])DFT_{P}(g[m])),P\geq M+L-1}$。

• 總共只需要做${\displaystyle P}$點FFT ${\displaystyle 2S+1}$次，因為${\displaystyle g[n]}$只需要做一次FFT。

• 假設${\displaystyle P}$點DFT的乘法量為${\displaystyle a}$，${\displaystyle f[n]}$和${\displaystyle g[n]}$為一般性的複數信號，並使用複數乘法的快速演算法，則共需要${\displaystyle (2S+1)a+3SP}$個乘法。

• 運算量：${\displaystyle {\frac {N}{L}}3(L+M-1)[\log _{2}(L+M-1)+1]}$

• 運算複雜度：${\displaystyle O(N)}$，和${\displaystyle N}$呈線性，較方法2小。
• 分為 Overlap-Add 和 Overlap-Save 兩種方法。

分段卷積: Overlap-Add

欲做${\displaystyle x[n]*h[n]}$的分段卷積分，${\displaystyle x[n]}$ 長度為 ${\displaystyle N}$，${\displaystyle h[n]}$ 長度為 ${\displaystyle M}$,

Step 1: 將${\displaystyle x[n]}$每 ${\displaystyle L}$ 分成一段

Step 2: 再每段 ${\displaystyle L}$ 點後面添加 ${\displaystyle M-1}$ 個零，變成長度 ${\displaystyle L+M-1}$

Step 3: 把 ${\displaystyle h[n]}$ 添加 ${\displaystyle L-1}$個零，變成長度 ${\displaystyle L+M-1}$的 ${\displaystyle h'[n]}$

Step 4: 把每個 ${\displaystyle x[n]}$ 的小段和 ${\displaystyle h'[n]}$ 做快速卷積，也就是${\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])}\}}$，每小段會得到長度 ${\displaystyle L+M-1}$ 的時域訊號

Step 5: 放置第 ${\displaystyle i}$ 個小段的起點在位置 ${\displaystyle L\times i}$ 上, ${\displaystyle i=0,1,...,\lceil {\frac {N}{L}}\rceil -1}$

Step 6: 會發現在每一段的後面 ${\displaystyle M-1}$ 點有重疊，將所有點都相加起來，顧名思義 Overlap-Add，最後得到結果

舉例來說:

${\displaystyle x[n]=[1,2,3,4,5,-1,-2,-3,-4,-5,1,2,3,4,5]}$, 長度 ${\displaystyle N=15}$

${\displaystyle h[n]=[1,2,3]}$, 長度 ${\displaystyle M=3}$

令 ${\displaystyle L=5}$

• 
  x[n]和h[n]

令 ${\displaystyle L=5}$ 切成三段，分別為 ${\displaystyle x_{0}[n],x_{1}[n],x_{2}[n]}$, 每段填 ${\displaystyle M-1}$ 個零，並將 ${\displaystyle h[n]}$ 填零至長度 ${\displaystyle L+M-1}$

• 
  分段x[n]

將每一段做${\displaystyle IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])}\}}$

• 
  分段運算結果

若將每小段擺在一起，可以注意到第一段的範圍是 ${\displaystyle 0\thicksim 6}$ ，第二段的範圍是 ${\displaystyle 5\thicksim 11}$，第三段的範圍是 ${\displaystyle 10\thicksim 16}$，三段的範圍是有重疊的

• 
  合併分段運算結果

最後將三小段加在一起，並將結果和未分段的卷積做比較，上圖是分段的結果，下圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。

• 
  結果比較圖

分段卷積: Overlap-Save

欲做${\displaystyle x[n]*h[n]}$的分段卷積分，${\displaystyle x[n]}$ 長度為 ${\displaystyle N}$，${\displaystyle h[n]}$ 長度為 ${\displaystyle M}$,

Step 1: 將 ${\displaystyle x[n]}$ 前面填 ${\displaystyle M-1}$ 個零

Step 2: 第一段 ${\displaystyle i=0}$, 從新的 ${\displaystyle x[n]}$ 中 ${\displaystyle L\times i-(M-1)\times i}$ 取到 ${\displaystyle L\times (i+1)-(M-1)\times i-1}$ 總共 ${\displaystyle L}$ 點當做一段，因此每小段會重複取到前一小段的 ${\displaystyle M-1}$ 點，取到新的一段全為零為止

Step 3: 把 ${\displaystyle h[n]}$ 添加 ${\displaystyle L-M}$ 個零，變成長度 ${\displaystyle L}$ 的 ${\displaystyle h'[n]}$

Step 4: 把每個 ${\displaystyle x[n]}$ 的小段和 ${\displaystyle h'[n]}$ 做快速卷積，也就是${\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}}$，每小段會得到長度 ${\displaystyle L}$ 的時域訊號

Step 5: 對於每個 ${\displaystyle i}$ 小段，只會保留末端的 ${\displaystyle L-(M-1)}$ 點，因此得名 Overlap-Save

Step 6: 將所有保留的點合再一起，得到最後結果

舉例來說:

${\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}$, 長度 ${\displaystyle N=15}$

${\displaystyle h[n]=[1,2,3]}$, 長度 ${\displaystyle M=3}$

令 ${\displaystyle L=7}$

• 
  x[n]和h[n]

將 ${\displaystyle x[n]}$ 前面填 ${\displaystyle M-1}$ 個零以後，按照 Step 2 的方式分段，可以看到每一段都重複上一段的 ${\displaystyle M-1}$ 點

• 
  分段x[n]

再將每一段做 ${\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}}$以後可以得到

• 
  分段運算結果

保留每一段末端的 ${\displaystyle L-(M-1)}$ 點，擺在一起以後，可以注意到第一段的範圍是 ${\displaystyle 0\thicksim 4}$ ，第二段的範圍是 ${\displaystyle 5\thicksim 9}$，第三段的範圍是 ${\displaystyle 10\thicksim 14}$，第四段的範圍是 ${\displaystyle 15\thicksim 16}$，四段的範圍是沒有重疊的

• 
  合併分段運算結果

將結果和未分段的卷積做比較，下圖是分段的結果，上圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。

• 
  結果比較圖

至於為什麼要把前面 ${\displaystyle M-1}$ 丟掉?

以下以一例子來闡述:

${\displaystyle x[n]=[1,2,3,4,5,6,7,8,9,10]}$, 長度 ${\displaystyle L=10}$，

${\displaystyle h[n]=[1,2,3,4,5]}$, 長度 ${\displaystyle M=5}$,

第一條藍線代表 ${\displaystyle y}$ 軸，而兩條藍線之間代表長度 ${\displaystyle L}$，是在做快速摺積時的週期

• 
  x[n]和h[n]

當在做快速摺積時${\displaystyle IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])}\}}$，是把訊號視為週期 ${\displaystyle L}$，在時域上為循環摺積分,

而在一開始前 ${\displaystyle M-1}$ 點所得到的值，是 ${\displaystyle h[0],h[6],h[7],h[8],h[9]}$ 和 ${\displaystyle x[0],x[6],x[7],x[8],x[9]}$ 內積的值，

然而 ${\displaystyle h[6],h[7],h[8],h[9]}$ 這 ${\displaystyle M-1}$ 個值應該要為零，以往在做快速摺積時長度為 ${\displaystyle L+M-1}$ 時不會遇到這些問題，

而今天因為在做快速摺積時長度為 ${\displaystyle L}$ 才會把這 ${\displaystyle M-1}$ 點算進來，因此我們要丟棄這 ${\displaystyle M-1}$ 點內積的結果