查看“︁卷积”︁的源代码

{{noteTA
|G1=Signals and Systems
|G2=Math
}}
[[File:comparison convolution correlation.svg|thumb|400px|卷积、[[互相关]]和[[自相关函数|自相关]]的图示比较。运算涉及函数<math>f</math>，并假定<math>f</math>的高度是1.0，在5个不同点上的值，用在每个点下面的阴影面积来指示。<math>f</math>的对称性是卷积<math>g*f</math>和互相关<math>f \star g</math>在这个例子中相同的原因。<!--Note that g∗f and f∗g would be identical even without the symmetry of f, so please don't change the statement above.-->]]

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

== 定义 ==
卷积是[[数学分析]]中一种重要的运算。设：<math> f(t)</math>和<math>g(t)</math>是[[实数]]<math>\mathbb{R}</math>上的两个[[可积函数]]，定义二者的卷积<math>(f * g)(t)</math>为如下特定形式的[[积分]][[积分变换|变换]]：
:<math>(f * g)(t) \triangleq \int_{-\infty}^{\infty} f(\tau) g(t - \tau)\, \mathrm{d}\tau</math>
<math>(f * g)(t)</math>仍为可积函数，并且有着：
:<math>(f * g)(t) \triangleq \int_{-\infty}^\infty f(t - \tau) g(\tau)\, d\tau  =  (g * f)(t)</math>

函数<math>f</math>和<math>g</math>，如果只[[支撑集|支撑]]在<math>[0, \infty]</math>之上，则积分界限可以截断为：

:<math>(f * g )(t) = \int_{0}^{t} f(\tau) g(t - \tau)\, d\tau \quad</math>对于<math>\ f, g : [0, \infty) \to \mathbb{R}</math>

对于两个得出[[复数 (数学)|复数]]值的{{en-link|多元实变函数|Function of several real variables}}，可以定义二者的卷积为如下形式的[[多重积分]]：
: <math>\begin{align}
(f  * g)(t_1,t_2,\cdots,t_n) &\triangleq \int\int\cdots\int_{\Reals^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_{\Reals^n} f(\tau)g(t-\tau)\,d^n\tau 
\end{align}</math>

卷积有一个通用的工程上的符号约定<ref>{{cite book|last1=Smith|first1=Stephen W|title=The Scientist and Engineer's Guide to Digital Signal Processing|date=1997|publisher=California Technical Publishing|isbn=0-9660176-3-3|edition=1|chapter-url=http://www.dspguide.com/ch13/2.htm|access-date=22 April 2016|chapter=13.Convolution|archive-date=2023-06-26|archive-url=https://web.archive.org/web/20230626124155/http://www.dspguide.com/ch13/2.htm|dead-url=no}}</ref>：

:<math> f(t) * g(t) \triangleq \underbrace{\int_{-\infty}^\infty f(\tau) g(t - \tau)\, d\tau}_{(f * g )(t)}</math>

它必须被谨慎解释以避免混淆。例如：<math>f(t) * g(t- t_0)</math>等价于<math>(f*g) (t - t_0) </math>，而<math>f(t - t_0)*g(t - t_0)</math>却实际上等价于<math>(f*g)(t - 2 t_0)</math><ref>{{cite book|last1=Irwin|first1=J. David|author-link=J. David Irwin|title=The Industrial Electronics Handbook|url=https://archive.org/details/industrialelectr0000unse_m6c8|date=1997|publisher=CRC Press|location=Boca Raton, FL|isbn=0-8493-8343-9|page=[https://archive.org/details/industrialelectr0000unse_m6c8/page/75 75]|edition=1|chapter=4.3}}</ref>。

==历史==
卷积运算的最早使用出现在[[让·勒朗·达朗贝尔|达朗贝尔]]于1754年出版的《宇宙体系的几个要点研究》中对[[泰勒定理]]的推导之中<ref>Dominguez-Torres, p 2</ref>。还有{{en-link|西尔维斯特·弗朗索瓦·拉克鲁瓦|Sylvestre François Lacroix|西尔维斯特·拉克鲁瓦}}，将<math display="inline">\int f(u)\cdot g(x - u) \, du</math>类型的表达式，用在他的1797年–1800年出版的著作《微分与级数论文》中<ref>on page 505 of his book entitled ''Treatise on differences and series'', which is the last of 3 volumes of the encyclopedic series: ''Traité du calcul différentiel et du calcul intégral'', Chez Courcier, Paris, 1797–1800. Dominguez-Torres, p 4</ref>。此后不久，卷积运算出现在[[皮埃尔-西蒙·拉普拉斯]]、[[约瑟夫·傅里叶]]和[[西梅翁·德尼·泊松|西梅翁·泊松]]等人的著作中。这个运算以前有时叫做“Faltung”（德语中的折叠）、合成乘积、叠加积分或卡森积分<ref>
{{Citation
 | chapter = Early work on imaging theory in radio astronomy
 | author = R. N. Bracewell
 | editor = W. T. Sullivan
 | title = The Early Years of Radio Astronomy: Reflections Fifty Years After Jansky's Discovery
 | publisher = Cambridge University Press
 | year = 2005
 | isbn = 978-0-521-61602-7
 | page = 172
 | chapter-url = https://books.google.com/books?id=v2SqL0zCrwcC&pg=PA172
}}</ref>。

“卷积”这个术语早在1903年就出现了，然而其定义在早期使用中是相当生僻的<ref>
{{Citation
 | title = The algebra of invariants
 | author = John Hilton Grace and Alfred Young
 | publisher = Cambridge University Press
 | year = 1903
 | page = 40
 | url = https://books.google.com/books?id=NIe4AAAAIAAJ&pg=PA40
}}</ref><ref>
{{Citation
 | title = Algebraic invariants
 | author = Leonard Eugene Dickson
 | publisher = J. Wiley
 | year = 1914
 | page = 85
 | url = https://books.google.com/books?id=LRGoAAAAIAAJ&pg=PA85
}}</ref>，直到1950年代或1960年代之前都未曾广泛使用。

==简介==
如果<math>f</math>和<math>g</math>都是在[[Lp空间|''L<sup>p</sup>'' 空间]]<math>L^1(\Reals^n)</math>内的[[勒貝格積分|勒贝格可积函数]]，则二者的卷积存在，并且在这种情况下<math>f * g</math>也是可积的<ref>{{harv|Stein|Weiss|1971|loc=Theorem 1.3}}</ref>。这是[[富比尼定理#非负函数的Tonelli定理|托內利定理]]的结论。对于在<math>L^1</math>中的函数在离散卷积下，或更一般的对于在任何群的上的卷积，这也是成立的。同样的，如果<math>f \in L^1(\Reals^n)</math>而<math>g \in L^p(\Reals^n)</math>，这里的<math>1 \le p \le \infty</math>，则<math>f * g \in L^p(\Reals^n)</math>，并且其[[Lp範數|''L<sup>p</sup>'' ]][[范数]]间有着[[不等式]]：

:<math>\|{f}* g\|_p\le \|f\|_1\|g\|_p</math>

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

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

由卷积得到的函数<math>f*g</math>，一般要比<math>f</math>和<math>g</math>都光滑。特别当<math>g</math>为具有紧支集的[[光滑函数]]，<math>f</math>为局部可积时，它们的卷积<math>f * g</math>也是光滑函数。利用这一性质，对于任意的可积函数<math>f</math>，都可以简单地构造出一列逼近于<math>f</math>的光滑函数列<math>f_s</math>，这种方法称为函数的光滑化或[[正则化 (数学)|正则化]]。

函数<math>f(t)</math>和<math>g(t)</math>的[[互相关]]<math>(f \star g)(\tau)</math>，等价于<math>f(-\tau)</math>的[[共轭复数]]<math>\overline{f(-\tau)}</math>与<math>g(\tau)</math>的卷积：
: <math>(f \star g)(\tau) \triangleq \int_{-\infty}^{\infty} \overline{f(t-\tau)} g(t)\,dt = \overline{f(-\tau)} * g(\tau) </math>
这里的<math>\tau</math>叫做移位（displacement）或滞后（lag）。

对于[[狄拉克δ函數|單位脈衝]]函数<math>\delta(t)</math>和某个函数<math>h(t)</math>，二者得到的捲積就是<math>h(t)</math>本身，此<math>h(t)</math>被稱為[[衝激響應]]：
: <math>(\delta * h)(t) = \int_{-\infty}^\infty \delta(\tau) h(t - \tau)\, d\tau = h(t)</math>
在连续时间[[线性时不变系统理论|线性非时变系统]]中，输出信号<math>y(t)</math>被描述为输入[[信号 (信息论)|信号]]<math>x(t)</math>与[[冲激响应]]<math>h(t)</math>的卷积<ref>{{citation
  | last=Crutchfield
  | first=Steve
  | url=http://www.jhu.edu/signals/convolve/index.html
  | title=The Joy of Convolution
  | work=Johns Hopkins University
  | date=October 12, 2010
  | access-date=November 21, 2010
  | archive-date=2013-09-11
  | archive-url=https://web.archive.org/web/20130911022447/http://www.jhu.edu/signals/convolve/index.html
  | dead-url=no
  }}</ref>：
:<math>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</math>

两个[[独立 (概率论)|独立]]的[[随机变量]]<math>U</math>和<math>V</math>，每个都有一个[[概率密度函数]]，二者之和的概率密度，是它们单独的密度函数的卷积：
:<math>f_{U+V}(x) = \int_{-\infty}^\infty f_U(y) f_V(x - y)\,dy = \left( f_{U} * f_{V} \right) (x)</math>

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

== 周期卷积 ==
{{Main article|圆周卷积}}
{{multiple image
 | direction = vertical
 | align = right
 | total_width = 480
 | image1 = Splotc2.gif
 | image2 = Splotc1.gif
 | footer = [[矩形函数|矩形]][[脉冲波]]和[[指数衰减]][[脉冲波]]的周期卷积
}}
两个<math>T</math>周期的函数<math>h_{_T}(t)</math>和<math>x_{_T}(t)</math>的“周期卷积”定义为<ref name=Jeruchim>
{{cite book
 |last1=Jeruchim
 |first1=Michel C.
 |last2=Balaban
 |first2=Philip
 |last3=Shanmugan
 |first3=K. Sam
 |title=Simulation of Communication Systems: Modeling, Methodology and Techniques
 |pages=73–74
 |publisher=Kluwer Academic Publishers
 |edition=2nd
 |date=October 2000 
 |location=New York
 |isbn=0-30-646267-2
}}</ref><ref name=Udayashankara>
{{cite book
 |last=Udayashankara
 |first=V.
 |title=Real Time Digital Signal Processing
 |page=189
 |publisher=Prentice-Hall
 |date=June 2010
 |location=India
 |isbn=978-8-12-034049-7
}}</ref>：

:<math>\int_{t_0}^{t_0+T} h_{_T}(\tau) x_{_T}(t - \tau)\,d\tau</math>

这里的<math>t_0</math>是任意参数。

任何{{en-link|绝对可积分函数|Absolutely integrable function|可积分函数}}<math>s(t)</math>，都可以通过求函数<math>s(t)</math>的所有[[倍数|整数倍]]<math>P</math>的[[平移]]的[[求和符号|总和]]，从而制作出具有[[周期]]<math>P</math>的[[周期函数]] <math>s_{_P}(t)</math>，这叫做{{en-link|周期求和|Periodic summation}}：
:<math>s_{_P}(t) \triangleq \sum_{m=-\infty}^\infty s(t + mP) = \sum_{m=-\infty}^\infty s(t - mP), \quad m \in \mathbb{Z}</math>

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

:<math>(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</math>
:<math>(h *x_{_T})(t) = (x * h_{_T})(t) </math>

[[圆周卷积]]是周期卷积的特殊情况<ref name=Udayashankara/><ref name=Priemer>{{cite book
 |last=Priemer
 |first=Roland
 |title=Introductory Signal Processing
 |pages=286–289
 |publisher=World Scientific Pub Co Inc.
 |series=Advanced Series in Electrical and Computer Engineering
 |volume=6
 |date=July 1991
 |location=Teaneck,N.J.
 |url=https://books.google.com/books?id=QBT7nP7zTLgC&q=Priemer,+Roland
 |isbn=9971-50-919-9
 |access-date=2023-10-26
 |archive-date=2023-10-11
 |archive-url=https://web.archive.org/web/20231011035931/https://books.google.com/books?id=QBT7nP7zTLgC&q=Priemer,+Roland
 |dead-url=no
 }}</ref>，其中函数<math>h</math>和<math>x</math>二者的非零部份，都限定在区间<math>[0,T]</math>之内，此时的周期求和称为“周期延拓”。<math>h *x_{_T}</math>中函数<math>x_{_T}</math>可以通过取[[性质符号|非负]][[余数]]的[[模除]]运算表达为“圆周函数”：

:<math>x_{_T}(t) = x(t_{\mathrm{mod}\ T}), \quad t\in\mathbb{R}</math>

而积分的界限可以缩简至函数<math>h</math>的长度范围<math>[0,T]</math>：

:<math>(h *x_{_T})(t) = \int_{0}^{T} h(\tau) x((t - \tau)_{\mathrm{mod}\ T})\ d\tau</math>

== 离散卷积 ==
[[File:Konvolutsioon.png|thumb|right|200px|离散卷积示意图]]
对于定义在整數<math>\mathbb{Z}</math>上且得出[[复数 (数学)|复数]]值的函数<math>f[n]</math>和<math>g[n]</math>，离散卷积定义为<ref>{{harvnb|Damelin|Miller|2011|p=219}}</ref>：
:<math>(f  * g)[n]\ \ \triangleq \ \sum_{m=-\infty}^{\infty} {f[m] g[n-m]} = \sum_{m=-\infty}^\infty f[n-m]\, g[m]</math>
這裡一樣把函數定義域以外的值當成零，所以可以擴展函數到所有整數上（如果本來不是的話）。两个有限序列的卷积的定义，是将这些序列扩展成在整数集合上有限支撑的函数。在这些序列是两个[[多项式]]的系数之时，这两个多项式的普通乘积的系数，就是这两个序列的卷积。这叫做序列系数的[[柯西乘积]]。

當<math> g[n] </math>的[[支撐集]]為有限長度的<math>\{-M,-M+1,\dots,M-1,M\}</math>之时，上式會變成有限[[求和符号|求和]]：
:<math>(f*g)[n]=\sum_{m=-M}^M f[n-m]g[m]</math>

===多维离散卷积===
{{main|{{en-link|多维离散卷积|Multidimensional discrete convolution}}}}
[[File:2D Convolution Animation.gif|thumb|right|390px|用离散二维卷积对[[数字图像|图像]]进行{{en-link|核 (图像处理)|Kernel (image processing)|锐化}}[[图像处理|处理]]的动画]]
类似于一维情况，使用[[星号]]表示卷积，而维度体现在星号的数量上，<math>M</math>维卷积就写为<math>M</math>个星号。下面是<math>M</math>维信号的卷积的表示法：

:<math>y(n_1,n_2,...,n_{_M})=h(n_1,n_2,...,n_{_M})* \overset{M}{\cdots}  *x(n_1,n_2,...,n_{_M})</math>

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

:<math>\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})</math>

结果的离散多维卷积所支撑的输出区域，基于两个输入信号所支撑的大小和区域来决定。
:[[File:Picture1_wiki.png|thumb|600px|none|在两个二维信号之间的卷积的可视化]]

===离散周期卷积===
[[File:Aperiodisch periodische Faltung.svg|thumb|right|390px|对比离散无周期卷积（左列）与离散圆周卷积（右列）]]
对于离散序列和一个参数<math>N</math>，无周期函数<math>h</math>和<math>x</math>的“周期卷积”是为：
:<math>(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]</math>

这个函数有周期<math>N</math>，它有最多<math>N</math>个唯一性的值。<math>h</math>和<math>x</math>的非零范围都是<math>[0, N-1]</math>的特殊情况叫做[[圆周卷积]]：
:<math>(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}]</math>
离散圆周卷积可简约为[[矩阵乘法]]，这里的[[积分变换]]的核函数是[[循环矩阵]]:
:<math> \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}
 </math>
圆周卷积最经常出现的[[快速傅里叶变换]]的实现算法比如[[雷德演算法]]之中。

== 性质 ==
===代数===
{{main|{{en-link|卷积代数|Convolution algebra}}}}
各种卷积算子都满足下列性质：

;[[交换律]]
: <math>f * g = g * f \,</math>

;[[结合律]]
: <math>f  * (g * h) = (f * g) * h \,</math>

;[[分配律]]
: <math>f * (g + h) = (f * g) + (f * h) \,</math>

;数乘结合律
: <math>a (f * g) = (a f) * g = f * (a g) \,</math>
其中<math>a</math>为任意[[实数]]（或[[复数 (数学)|复数]]）。

;复数共轭
: <math>\overline{f * g} = \overline{f} * \overline{g}</math>

;微分有关
:<math>(f * g)' = f' * g = f * g'</math>

;积分有关
:如果<math display="inline">F(t) = \int^t_{-\infty} f(\tau) d\tau</math>，并且<math display="inline">G(t) = \int^t_{-\infty} g(\tau) \, d\tau</math>，则有：
:<math>(F * g)(t) = (f * G)(t) = \int^t_{-\infty}(f * g)(\tau)\,d\tau</math>

=== 积分 ===
如果<math>f</math>和<math>g</math>是可积分函数，则它们在整个空间上的卷积的积分，简单的就是它们积分的乘积<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Convolution|url=https://mathworld.wolfram.com/Convolution.html|access-date=2021-09-22|website=mathworld.wolfram.com|language=en|archive-date=2002-01-14|archive-url=https://web.archive.org/web/20020114175851/https://mathworld.wolfram.com/Convolution.html|dead-url=no}}</ref>：
: <math>\int_{\Reals^n}(f * g)(t) \, d^nt=\left(\int_{\Reals^n}f(t) \, d^nt\right) \left(\int_{\Reals^n}g(t) \, d^nt\right)</math>

这是[[富比尼定理]]的结果。如果<math>f</math>和<math>g</math>只被假定为非负可测度函数，根据[[富比尼定理#非负函数的Tonelli定理|托内利定理]]，这也是成立的。

===微分===
在一元函数情况下，<math>f</math>和<math>g</math>的卷积的[[导数]]有着：
: <math>\frac{d}{dt}(f * g) = \frac{df}{dt} * g = f * \frac{dg}{dt}</math>
这里的<math>\frac{d}{dt}</math>是[[微分算子]]。更一般的说，在[[多元函数]]的情况下，对[[偏导数]]也有类似的公式：
: <math>\frac{\partial}{\partial t_i}(f * g) = \frac{\partial f}{\partial t_i} * g = f * \frac{\partial g}{\partial t_i}</math>
这就有了一个特殊结论，卷积可以看作“光滑”运算：<math>f</math>和<math>g</math>的卷积可微分的次数，是<math>f</math>和<math>g</math>的总数。

这些恒等式成立的严格条件，为<math>f</math>和<math>g</math>是绝对可积分的，并且至少二者之一有绝对可积分（<math>L^1</math>）弱导数，这是{{en-link|Young卷积不等式|Young's convolution inequality}}的结论。

在离散情况下，[[差分]][[算子]]<math> \Delta[f](n) = f(n+1)-f(n)</math>满足类似的关系：
: <math>\Delta(f * g) = (\Delta f) * g = f * (\Delta g)</math>

== 卷积定理 ==
{{main|卷积定理}}
[[卷积定理]]指出<ref>{{cite web |last1=Weisstein |first1=Eric W |title=From MathWorld--A Wolfram Web Resource |url=https://mathworld.wolfram.com/ConvolutionTheorem.html |access-date=2023-10-23 |archive-date=2000-07-11 |archive-url=https://web.archive.org/web/20000711062946/https://mathworld.wolfram.com/ConvolutionTheorem.html |dead-url=no }}</ref>，在适当的条件下，两个函数（或[[信号]]）的卷积的[[傅里叶变换]]，是它们的傅里叶变换的[[逐点乘积]]。更一般的说，在一个域（比如[[时域]]）中的卷积等于在其他域（比如[[频域]]）[[逐点]]乘法。

设两个函数<math>g(x)</math>和<math>h(x)</math>，分别具有[[傅里叶变换]]<math>G(s)</math>和<math>H(s)</math>：
:<math>\begin{align}
G(s) &\triangleq \mathcal{F}\{g\}(s) = \int_{-\infty}^{\infty}g(x) e^{-i 2 \pi s x} \, dx, \quad s \in \mathbb{R}\\
H(s) &\triangleq \mathcal{F}\{h\}(s) = \int_{-\infty}^{\infty}h(x) e^{-i 2 \pi s x} \, dx, \quad s \in \mathbb{R}
\end{align}</math>
这里的<math>\mathcal{F}</math>[[算子]]指示[[傅里叶变换]]。

卷积定理声称：
:<math>\mathcal{F}\{g * h\}(s) = G(s) H(s) , \quad s \in \mathbb{R}</math>
:<math>\mathcal{F}\{g \cdot h\}(s) = G(s)*H(s), \quad s \in \mathbb{R}</math>

应用逆傅里叶变换<math>\mathcal{F}^{-1}</math>产生推论：
:<math>(g * h)(s) = \mathcal{F}^{-1}\{G\cdot H\} , \quad s \in \mathbb{R}</math>
:<math>(g \cdot h)(s) = \mathcal{F}^{-1} \{G * H\} , \quad s \in \mathbb{R}</math>
这里的算符<math>\, \cdot \, </math>指示[[逐点]]乘法。

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

===周期卷积===
对于周期为<math>P</math>的函数<math>g_{_P}(x)</math>和<math>h_{_P}(x)</math>，可以被表达为二者的{{en-link|周期求和|Periodic summation}}：
:<math>\begin{align}
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{align}</math>
它们的[[傅里叶级数]][[系数]]为：
:<math>\begin{align}
   G[k] &\triangleq \mathcal{F}\{g_{_P}\}[k] = \frac{1}{P} \int_P g_{_P}(x) e^{-i 2\pi k x/P} \, dx, \quad k \in \mathbb{Z} \\
   H[k] &\triangleq \mathcal{F}\{h_{_P}\}[k] = \frac{1}{P} \int_P h_{_P}(x) e^{-i 2\pi k x/P} \, dx, \quad k \in \mathbb{Z}
 \end{align}</math>
这里的<math>\mathcal{F}</math>算子指示[[傅里叶级数]][[积分]]。

[[逐点乘积]]<math>g_{_P}(x)\cdot h_{_P}(x)</math>的周期也是<math>P</math>，它的傅里叶级数系数为：
:<math>\mathcal{F}\{g_{_P}\cdot h_{_P}\}[k] = (G*H)[k]</math>

周期卷积<math>(g_{_P} * h)(x)</math>的周期也是<math>P</math>，周期卷积的卷积定理为：
:<math> \mathcal{F}\{g_{_P} * h\}[k] =\ P\cdot G[k]\ H[k]</math>

===离散卷积===
对于作为两个连续函数[[采样]]的[[序列]]<math>g[n]</math>和<math>h[n]</math>，它们具有[[离散时间傅里叶变换]]<math>G(s)</math>和<math>H(s)</math>：
:<math>\begin{align}
G(s) &\triangleq \mathcal{F}\{g\}(s) = \sum_{n=-\infty}^{\infty} g[n]\cdot e^{-i 2\pi s n}\;, \quad s \in \mathbb{R} \\
H(s) &\triangleq \mathcal{F}\{h\}(s) = \sum_{n=-\infty}^{\infty} h[n]\cdot e^{-i 2\pi s n}\;, \quad s \in \mathbb{R}
\end{align}</math>
这里的<math>\mathcal {F}</math>算子指示[[离散时间傅里叶变换]]（DTFT）。

离散卷积的卷积定理为：
:<math>\mathcal{F}\{g * h\}(s) =\ G(s) H(s)</math>

===离散周期卷积===
对于周期为<math>N</math>的[[序列]]<math>g_{_N}[n]</math>和<math>h_{_N}[n]</math>：
:<math>\begin{align}
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{align}</math>
相较于离散时间傅里叶变换<math>G(s)</math>和<math>H(s)</math>的周期是<math>1</math>，它们是按间隔<math>1/N</math>采样<math>G(s)</math>和<math>H(s)</math>，并在<math>N</math>个采样上进行了逆[[离散傅里叶变换]]（DFT<sup>-1</sup>或IDFT）的结果。

离散周期卷积<math>(g_{_N} * h)[n]</math>的周期也是<math>N</math>。离散周期卷积定理为：
:<math>\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}</math>
这里的<math>\mathcal{F}</math>算子指示长度<math>N</math>的[[离散傅里叶变换]]（DFT）。

它有着推论：
:<math>(g_{_N} * h)[n] =\ \mathcal{F}^{-1}\{\mathcal{F}\{g_{_N}\} \cdot \mathcal{F}\{h_{_N}\}\}</math>

对于其非零时段小于等于<math>N</math>的<math>g</math>和<math>h</math>，离散圆周卷积的卷积定理为：
:<math>(g_{_N} * h)[n] =\ \mathcal{F}^{-1}\{\mathcal{F}\{g\} \cdot \mathcal{F}\{h\}\}</math>

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

若''G''是有某''m'' [[测度]]的[[群]]（例如[[豪斯多夫空间]]上[[哈尔测度]]下[[局部紧致]]的[[拓扑群]]），对于''G''上''m''-[[勒贝格可积]]的[[实数]]或[[复数 (数学)|复数]]函数''f''和''g''，可定义它们的卷积：
:<math>(f * g)(x) = \int_G f(y)g(xy^{-1})\,dm(y) \,</math>

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

==离散卷積的計算方法 ==
計算卷積<math>f[n]*g[n]</math>有三種主要的方法，分別為
#直接計算（Direct Method）
#[[快速傅立葉轉換]]（FFT）
#分段卷積（sectioned convolution）
方法1是直接利用定義來計算卷積，而方法2和3都是用到了FFT來快速計算卷積。也有不需要用到FFT的作法，如使用[[數論轉換]]。

===方法1：直接計算===

*作法：利用卷積的定義

:: <math> y[n] = f[n]*g[n] = \sum_{m=0}^{M-1} f[n-m]g[m] </math>

*若<math> f[n] </math>和<math> g[n] </math>皆為實數信號，則需要<math> MN </math>個乘法。

*若<math> f[n] </math>和<math> g[n] </math>皆為更一般性的複數信號，不使用複數乘法的快速演算法，會需要<math> 4MN </math>個乘法；但若使用複數乘法的快速演算法，則可簡化至<math> 3MN </math>個乘法。

:因此，使用定義直接計算卷積的複雜度為<math> O(MN) </math>。

===方法2：快速傅立葉轉換===

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

::<math> y[n] = f[n]*g[n] \leftrightarrow Y[f] = F[f]G[f] </math>

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

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

::<math> F[f] = DFT_P(f[n]), G[f] = DFT_P(g[n])  </math> 

:，於是

::<math> Y[f] = DFT_P(f[n])DFT_P(g[n])  </math> 

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

::<math> y[n] = IDFT_P{DFT_P(f[n])DFT_P(g[n])}  </math> 

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

*特別注意DFT和IDFT的點數<math>P</math>要滿足<math> P \ge M+N-1 </math>。

*由於DFT有快速演算法FFT，所以運算量為<math> O(P\log_{2}P) </math>

*假設<math> P </math>點DFT的乘法量為<math> a </math>，<math> f[n] </math>和<math> g[n] </math>為一般性的複數信號，並使用複數乘法的快速演算法，則共需要<math> 3a + 3P </math>個乘法。

===方法3：分段卷積===

*概念：將<math> f[n] </math>切成好幾段（section），每一段分別和<math> g[n] </math>做卷積後，再將結果相加。

*作法：先將<math> f[n] </math>切成每段長度為<math> L </math>的區段（<math> L > M </math>），假設共切成S段：

::<math> 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)</math>

::Section 1: <math> f_1[n] = f[n]  , n=0,1,...,L-1</math>

::Section 2: <math> f_2[n] = f[n+L], n=0,1,...,L-1</math>

:::<math> \vdots </math> 

::Section r: <math> f_r[n] = f[n+(r-1)L], n=0,1,...,L-1 </math> 

:::<math> \vdots </math> 

::Section S: <math> f_S[n] = f[n+(S-1)L], n=0,1,...,L-1</math>

:，<math> f[n] </math>為各個section的和

::<math> f[n] =  \sum_{r=1}^{S} f_r[n+(r-1)L] </math>。

:因此，

::<math> y[n] = f[n]*g[n] =  \sum_{r=1}^{S} \sum_{m=0}^{M-1} f_r[n+(r-1)L-m]g[m] </math>，

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

::<math> 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 \ge M+L-1 </math>。

*總共只需要做<math> P </math>點FFT <math>2S+1</math>次，因為<math> g[n] </math>只需要做一次FFT。

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

*運算量：<math> \frac{N}{L}3(L+M-1)[\log_{2}(L+M-1)+1] </math>

*運算複雜度：<math> O(N)</math>，和<math> N </math>呈線性，較方法2小。
*分為 Overlap-Add 和 Overlap-Save 兩種方法。
'''分段卷積: Overlap-Add'''

欲做<math> x[n]*h[n] </math>的分段卷積分，<math> x[n] </math> 長度為 <math> N
 </math>，<math> h[n] </math> 長度為 <math> M
 </math>,

Step 1: 將<math> x[n] </math>每 <math> L </math> 分成一段

Step 2: 再每段 <math> L </math> 點後面添加 <math> M-1 </math> 個零，變成長度 <math> L+M-1 </math>

Step 3: 把 <math> h[n] </math> 添加 <math> L-1 </math>個零，變成長度 <math> L+M-1 </math>的 <math> h'[n] </math>

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

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

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

舉例來說:

<math> x[n]=[1, 2, 3, 4, 5, -1, -2, -3, -4, -5, 1, 2, 3, 4, 5] </math>, 長度 <math> N=15 </math>

<math> h[n]=[1, 2, 3] </math>, 長度 <math> M=3 </math>

令 <math> L=5 </math> <gallery mode="nolines" widths="300" heights="300">
File:Data overlap add.png|x[n]和h[n]
</gallery>

令 <math> L=5 </math> 切成三段，分別為 <math> x_0[n], x_1[n], x_2[n] </math>, 每段填 <math> M-1 </math> 個零，並將 <math> h[n] </math> 填零至長度 <math> L+M-1 </math><gallery mode="nolines" widths="300" heights="300">
File:Seperate x overlap add.png|分段x[n]
</gallery>將每一段做<math> IDFT_{L+M-1}\{{DFT_{L+M-1}(x[n])DFT_{L+M-1}(h'[n])} \} </math><gallery mode="nolines" widths="300" heights="300">
File:Seperate result overlap add.png|分段運算結果
</gallery>若將每小段擺在一起，可以注意到第一段的範圍是 <math> 0\thicksim6 </math> ，第二段的範圍是 <math> 5\thicksim 11 </math>，第三段的範圍是 <math> 10\thicksim 16 </math>，三段的範圍是有重疊的<gallery mode="nolines" widths="300" heights="300">
File:Summation overlap add.png|合併分段運算結果
</gallery>最後將三小段加在一起，並將結果和未分段的卷積做比較，上圖是分段的結果，下圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。<gallery mode="nolines" widths="300" heights="300">
File:Final result overlap add.png|結果比較圖
</gallery>'''分段卷積: Overlap-Save'''

欲做<math> x[n]*h[n] </math>的分段卷積分，<math> x[n] </math> 長度為 <math> N
 </math>，<math> h[n] </math> 長度為 <math> M
 </math>,

Step 1: 將 <math> x[n] </math> 前面填 <math> M-1 </math> 個零

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

Step 3: 把 <math> h[n] </math> 添加 <math> L-M </math> 個零，變成長度 <math> L </math> 的 <math> h'[n] </math>

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

Step 5: 對於每個 <math> i </math> 小段，只會保留末端的 <math> L-(M-1) </math> 點，因此得名 Overlap-Save

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

舉例來說:

<math> x[n]=[1, 2, 3, 4, 5, 6,7, 8, 9, 10, 11, 12, 13, 14, 15] </math>, 長度 <math> N=15 </math>

<math> h[n]=[1, 2, 3] </math>, 長度 <math> M=3 </math>

令 <math> L=7 </math> <gallery mode="nolines" widths="300" heights="300">
File:Data overlap save.png|x[n]和h[n]
</gallery>將 <math> x[n] </math> 前面填 <math> M-1 </math> 個零以後，按照 Step 2 的方式分段，可以看到每一段都重複上一段的 <math> M-1 </math> 點<gallery mode="nolines" widths="300" heights="300">
File:Seperate x overlap save.png|分段x[n]
</gallery>再將每一段做 <math> IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])} \} </math>以後可以得到<gallery mode="nolines" widths="300" heights="300">
File:Seperate result overlap save.png|分段運算結果
</gallery>保留每一段末端的 <math> L-(M-1) </math> 點，擺在一起以後，可以注意到第一段的範圍是 <math> 0\thicksim 4 </math> ，第二段的範圍是 <math> 5\thicksim 9 </math>，第三段的範圍是 <math> 10\thicksim 14 </math>，第四段的範圍是 <math> 15\thicksim 16 </math>，四段的範圍是沒有重疊的<gallery mode="nolines" widths="300" heights="300">
File:Summation overlap save.png|合併分段運算結果
</gallery>將結果和未分段的卷積做比較，下圖是分段的結果，上圖是沒有分段並利用快速卷積所算出的結果，驗證兩者運算結果相同。<gallery mode="nolines" widths="300" heights="300">
File:Final compare overlap save.png|結果比較圖
</gallery>至於為什麼要把前面 <math> M-1 </math> 丟掉?

以下以一例子來闡述:

<math> x[n]=[1, 2, 3, 4, 5, 6,7, 8, 9, 10] </math>, 長度 <math> L=10 </math>，

<math> h[n]=[1, 2, 3, 4, 5] </math>, 長度 <math> M=5 </math>,

第一條藍線代表 <math> y </math> 軸，而兩條藍線之間代表長度 <math> L </math>，是在做快速摺積時的週期<gallery mode="nolines" widths="300" heights="300">
File:Original ov extra.png|x[n]和h[n]
</gallery>當在做快速摺積時<math> IDFT_{L}\{{DFT_{L}(x[n])DFT_{L}(h'[n])} \} </math>，是把訊號視為週期 <math> L </math>，在時域上為循環摺積分,

而在一開始前 <math> M-1 </math> 點所得到的值，是 <math> h[0], h[6], h[7], h[8], h[9] </math> 和 <math> x[0], x[6], x[7], x[8], x[9] </math> 內積的值，

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

而今天因為在做快速摺積時長度為 <math> L </math> 才會把這 <math> M-1 </math> 點算進來，因此我們要丟棄這 <math> M-1 </math> 點內積的結果<gallery mode="nolines" widths="300" heights="300">
File:Cir conv ov extra.png|循環摺積
</gallery>為了要丟棄這 <math> M-1 </math> 點內積的結果，位移 <math> h[-n] </math> <math> M-1 </math> 點，並把位移以後內積合的值才算有效。<gallery mode="nolines" widths="300" heights="300">
File:Cir conv shift ov extra.png|位移以後內積
</gallery>

=== 應用時機 ===

以上三種方法皆可用來計算卷積，其差別在於所需總體乘法量不同。基於運算量以及效率的考量，在計算卷積時，通常會選擇所需總體乘法量較少的方法。

以下根據<math> f[n] </math>和<math> g[n] </math>的長度（<math> N, M </math>）分成5類，並列出適合使用的方法：

# <math> M </math>為一非常小的整數 - 直接計算
# <math> M \ll N </math> - 分段卷积
# <math> M \approx N </math> - 快速傅里叶变换
# <math> M \gg N </math> - 分段卷积
# <math> N </math>為一非常小的整數 - 直接計算

基本上，以上只是粗略的分類。在實際應用時，最好還是算出三種方法所需的總乘法量，再選擇其中最有效率的方法來計算卷積。

=== 例子 ===

Q1：當<math> N = 2000, M = 17 </math>，適合用哪種方法計算卷積?

Ans：

:方法1：所需乘法量為<math> 3MN = 102000 </math> 

:方法2：<math> P \ge M+N-1 = 2016 </math>，而2016點的DFT最少乘法數<math> a = 12728 </math>，所以總乘法量為<math> 3(a+P) = 44232 </math> 

:方法3： 
::若切成8塊（<math> S = 8 </math>），則<math> L = 250, P \ge M+L-1=266 </math>。選<math> P = 288 </math>，則總乘法量為<math>(2S+1)a+3SP = 26632 </math>，比方法1和2少了很多。
::但是若要找到最少的乘法量，必須依照以下步驟
:::(1)先找出<math> L </math>:解<math> L</math> : <math> \frac{\partial {\frac{N}{L}3(L+M-1)[\log_{2}(L+M-1)+1]}}{\partial L}=0 </math>
:::(2)由<math>P \ge L+M-1</math>算出點數在<math> P </math>附近的DFT所需最少的乘法量，選擇DFT的點數
:::(3)最後由<math>L = P+1-M</math>算出<math> L_{opt} </math>
::因此，
:::(1)由運算量對<math> L </math>的偏微分為0而求出<math> L = 85 </math>
:::(2)<math> P \ge L+M-1 = 101 </math>，所以選擇101點DFT附近點數乘法量最少的點數<math>P = 96 </math>或<math>P = 120</math>。
:::(3-1)當<math> P = 96 \to a = 280, L = P+1-M = 80 \to S = 25</math>，總乘法量為<math>(2S+1)a+3SP = 21480 </math>。
:::(3-2)當<math> P = 120 \to a = 380, L = P+1-M = 104 \to S = 20</math>，總乘法量為<math>(2S+1)a+3SP = 22780 </math>。
::由此可知，切成20塊會有較好的效率，而所需總乘法量為21480。
*因此，當<math> N = 2000, M = 17 </math>，所需總乘法量：分段卷積<快速傅立葉轉換<直接計算。故，此時選擇使用分段卷積來計算卷積最適合。
  
Q2：當<math> N = 1024, M = 3 </math>，適合用哪種方法計算卷積?

Ans：

:方法1：所需乘法量為<math> 3MN = 9216 </math> 
  
:方法2：<math> P \ge M+N-1 = 1026 </math>，選擇1026點DFT附近點數乘法量最少的點數，<math> \to P = 1152, a = 7088 </math>。
:::因此，所需乘法量為<math> 3(a+P) = 24342 </math> 

:方法3： 
:::(1)由運算量對<math> L </math>的偏微分為0而求出<math> L = 5 </math>
:::(2)<math> P \ge L+M-1 = 7 </math>，所以選擇7點DFT附近點數乘法量最少的點數<math>P = 8</math>或<math>P = 6</math>或<math>P = 4</math>。
:::(3-1)當<math> P = 8 \to a = 4, L = P+1-M = 6 \to S = 171</math>，總乘法量為<math>(2S+1)a+3SP = 5476 </math>。
:::(3-2)當<math> P = 6 \to a = 4, L = P+1-M = 4 \to S = 256</math>，總乘法量為<math>(2S+1)a+3SP = 6660 </math>。
:::(3-3)當<math> P = 4 \to a = 0, L = P+1-M = 2 \to S = 512</math>，總乘法量為<math>(2S+1)a+3SP = 6144 </math>。
::由此可知，切成171塊會有較好的效率，而所需總乘法量為5476。
*因此，當<math> N = 1024, M = 3 </math>，所需總乘法量：分段卷積<直接計算<快速傅立葉轉換。故，此時選擇使用分段卷積來計算卷積最適合。
*雖然當<math>M </math>是個很小的正整數時，大致上適合使用直接計算。但實際上還是將3個方法所需的乘法量都算出來，才能知道用哪種方法可以達到最高的效率。

Q3：當<math> N = 1024, M = 600 </math>，適合用哪種方法計算卷積?

Ans：

:方法1：所需乘法量為<math> 3MN = 1843200 </math> 
  
:方法2：<math> P \ge M+N-1 = 1623 </math>，選擇1026點DFT附近點數乘法量最少的點數，<math> \to P = 2016, a = 12728 </math>。
:::因此，所需乘法量為<math> 3(a+P) = 44232 </math> 

:方法3： 
:::(1)由運算量對<math> L </math>的偏微分為0而求出<math> L = 1024 </math>
:::(2)<math> P \ge L+M-1 = 1623 </math>，所以選擇1623點DFT附近點數乘法量最少的點數<math>P = 2016</math>。
:::(3)當<math> P = 2016 \to a = 12728, L = P+1-M = 1417 \to S = 1</math>，總乘法量為<math>(2S+1)a+3SP = 44232 </math>。
::由此可知，此時切成一段，就跟方法2一樣，所需總乘法量為44232。
*因此，當<math> N = 1024, M = 600 </math>，所需總乘法量：快速傅立葉轉換 = 分段卷積<直接計算。故，此時選擇使用分段卷積來計算卷積最適合。

== 应用 ==
[[File:Halftone, Gaussian Blur.jpg|thumb|right|[[高斯模糊]]可被用来从[[半色调]]印刷品复原出光滑灰度数字图像。]]
卷积在科学、工程和数学上都有很多应用：
* [[代数]]中，整数乘法和多项式乘法都是卷积。
* [[卷积神经网络]]应用了多重级联的卷积{{en-link|核心 (图像处理)|Kernel (image processing)|核心}}，它被用于[[机器视觉]]和[[人工智能]]<ref>{{Cite journal|last1=Zhang|first1=Yingjie|last2=Soon|first2=Hong Geok|last3=Ye|first3=Dongsen|last4=Fuh|first4=Jerry Ying Hsi|last5=Zhu|first5=Kunpeng|date=September 2020|title=Powder-Bed Fusion Process Monitoring by Machine Vision With Hybrid Convolutional Neural Networks|url=https://ieeexplore.ieee.org/document/8913613|journal=IEEE Transactions on Industrial Informatics|volume=16|issue=9|pages=5769–5779|doi=10.1109/TII.2019.2956078|s2cid=213010088|issn=1941-0050|access-date=2023-10-24|archive-date=2023-07-31|archive-url=https://web.archive.org/web/20230731120013/https://ieeexplore.ieee.org/document/8913613/|dead-url=no}}</ref><ref>{{Cite journal|last1=Chervyakov|first1=N.I.|last2=Lyakhov|first2=P.A.|last3=Deryabin|first3=M.A.|last4=Nagornov|first4=N.N.|last5=Valueva|first5=M.V.|last6=Valuev|first6=G.V.|date=September 2020|title=Residue Number System-Based Solution for Reducing the Hardware Cost of a Convolutional Neural Network|url=https://linkinghub.elsevier.com/retrieve/pii/S092523122030583X|journal=Neurocomputing|language=en|volume=407|pages=439–453|doi=10.1016/j.neucom.2020.04.018|s2cid=219470398|quote=Convolutional neural networks represent deep learning architectures that are currently used in a wide range of applications, including computer vision, speech recognition, time series analysis in finance, and many others.|access-date=2023-10-24|archive-date=2023-06-29|archive-url=https://web.archive.org/web/20230629155646/https://linkinghub.elsevier.com/retrieve/pii/S092523122030583X|dead-url=no}}</ref>，尽管在多数情况下实际上用的是[[互相关]]而非卷积<ref>{{Cite journal|last=Atlas, Homma, and Marks|title=An Artificial Neural Network for Spatio-Temporal Bipolar Patterns: Application to Phoneme Classification|url=https://papers.nips.cc/paper/1987/file/98f13708210194c475687be6106a3b84-Paper.pdf |archive-url=https://web.archive.org/web/20210414091306/https://papers.nips.cc/paper/1987/file/98f13708210194c475687be6106a3b84-Paper.pdf |archive-date=2021-04-14 |url-status=live|journal=Neural Information Processing Systems (NIPS 1987)|volume=1}}</ref>。
* 在非[[人工智能]]的[[图像处理]]中，用作图像模糊、锐化、[[边缘检测]]。
* [[统计学]]中，加权的滑动平均是一种卷积。
* [[概率论]]中，两个统计独立变量X与Y的和的[[概率密度函数]]是X与Y的概率密度函数的卷积。
* [[声学]]中，[[回声]]可以用源声与一个反映各种反射效应的函数的卷积表示。
* [[电子工程]]与[[信号处理]]中，任一个线性系统的输出都可以通过将输入信号与系统函数（系统的[[冲激响应]]）做卷积获得。
* [[物理学]]中，任何一个线性系统（符合[[叠加原理]]）都存在卷积。

== 参见 ==
* [[反褶积|反卷积]]
* [[自相关函数]]
* [[傅里叶变换]]

==引用==
{{reflist|2}}

==延伸阅读==
* {{citation | last1=Bracewell | first1=R. | title=The Fourier Transform and Its Applications| edition=2nd |
publisher=McGraw–Hill | year=1986 | isbn=0-07-116043-4}}.
* {{citation | last1=Damelin | first1=S. | last2=Miller | first2=W. | title=The Mathematics of Signal Processing | publisher=Cambridge University Press | isbn=978-1107601048 | year=2011}}
* {{citation | last=Diggle | first=P. J. | s2cid=116746157 | title=A kernel method for smoothing point process data | journal=Journal of the Royal Statistical Society, Series C | volume = 34 | issue=2 | pages = 138–147 |doi=10.2307/2347366 | year=1985 | jstor=2347366}}
* Dominguez-Torres, Alejandro (Nov 2, 2010). "Origin and history of convolution". 41 pgs. http://www.slideshare.net/Alexdfar/origin-adn-history-of-convolution {{Wayback|url=http://www.slideshare.net/Alexdfar/origin-adn-history-of-convolution |date=20231030184051 }}. Cranfield, Bedford MK43 OAL, UK. Retrieved Mar 13, 2013.
* {{Citation | last1=Ghasemi | first1=S. Hooman | last2=Nowak | first2=Andrzej S. | title=Reliability Index for Non-normal Distributions of Limit State Functions | doi=10.12989/sem.2017.62.3.365 | year=2017 | journal=Structural Engineering and Mechanics | volume=62 | issue=3 | pages=365–372}}
*{{Citation | last1=Grinshpan | first1=A. Z. | title=An inequality for multiple convolutions with respect to Dirichlet probability measure | doi=10.1016/j.aam.2016.08.001 | year=2017 | 
journal=Advances in Applied Mathematics | volume=82 | issue=1 | pages=102–119 | doi-access=free}}
* {{Citation | last1=Hewitt | first1=Edwin | last2=Ross | first2=Kenneth A. | title=Abstract harmonic analysis. Vol. I | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] | isbn=978-3-540-09434-0 | mr=551496 | year=1979 | volume=115}}.
* {{Citation | last1=Hewitt | first1=Edwin | last2=Ross | first2=Kenneth A. | title=Abstract harmonic analysis. Vol. II: Structure and analysis for compact groups. Analysis on locally compact Abelian groups | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Die Grundlehren der mathematischen Wissenschaften, Band 152 | mr=0262773 | year=1970}}.
* {{citation | last=Hörmander | first=L. | author-link=Lars Hörmander | mr=0717035 | title=The analysis of linear partial differential operators I | series= Grundl. Math. Wissenschaft. | volume= 256 | publisher= Springer | year=1983 | isbn=3-540-12104-8 | doi=10.1007/978-3-642-96750-4}}.
* {{Citation | last1=Kassel | first1=Christian | title=Quantum groups | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Graduate Texts in Mathematics | isbn=978-0-387-94370-1 | mr=1321145 | year=1995 | volume=155 | doi=10.1007/978-1-4612-0783-2 | url-access=registration | url=https://archive.org/details/quantumgroups0000kass}}.
* {{citation | last=Knuth | first=Donald | author-link=Donald Knuth | title=Seminumerical Algorithms|edition=3rd. | location=Reading, Massachusetts | publisher=Addison–Wesley | year=1997 | isbn=0-201-89684-2}}.
* {{Narici Beckenstein Topological Vector Spaces|edition=2}} <!-- {{sfn | Narici | 2011 | p=}} -->
* {{citation | last1=Reed | first1=Michael | last2=Simon | first2=Barry | author2-link=Barry Simon | title=Methods of modern mathematical physics. II. Fourier analysis, self-adjointness | publisher=Academic Press Harcourt Brace Jovanovich, Publishers|location=New York-London | year= 1975 | pages= xv+361 | isbn =0-12-585002-6 | mr=0493420}}
* {{Citation<!-- Citation bot--> | last1=Rudin | first1=Walter | author1-link=Walter Rudin | title=Fourier analysis on groups | publisher=Interscience Publishers | location=New York–London | series=Interscience Tracts in Pure and Applied Mathematics | volume=12 | mr=0152834 | year=1962 | isbn=0-471-52364-X}}.
* {{Schaefer Wolff Topological Vector Spaces|edition=2}} <!-- {{sfn | Schaefer | 1999 | p=}} -->
* {{citation | last1=Stein | first1=Elias | author-link1=Elias Stein | last2=Weiss | first2=Guido | title=Introduction to Fourier Analysis on Euclidean Spaces|publisher=Princeton University Press|year=1971|isbn=0-691-08078-X|url-access=registration|url=https://archive.org/details/introductiontofo0000stei}}.
* {{springer | last=Sobolev | first=V.I.|id=C/c026430|title=Convolution of functions|year=2001}}.
* {{citation | last=Strichartz | first=R.|year=1994|title=A Guide to Distribution Theory and Fourier Transforms|publisher=CRC Press|isbn=0-8493-8273-4}}.
* {{citation | last=Titchmarsh | first=E|author-link=Edward Charles Titchmarsh|title=Introduction to the theory of Fourier integrals|isbn=978-0-8284-0324-5|year=1948|edition=2nd|publication-date=1986|publisher=Chelsea Pub. Co.|location=New York, N.Y.}}.
* {{Trèves François Topological vector spaces, distributions and kernels}} <!-- {{sfn | Treves | 2006 | p=}} -->
* {{citation | last=Uludag | first=A. M. |author-link=A. Muhammed Uludag|title=On possible deterioration of smoothness under the operation of convolution|journal=J. Math. Anal. Appl. |volume=227 |issue=2 |pages=335–358|year=1998|doi=10.1006/jmaa.1998.6091 |doi-access=free}}
* {{citation | last1=von zur Gathen | first1=J. | last2=Gerhard | first2=J .|title=Modern Computer Algebra|isbn=0-521-82646-2|year=2003|publisher=Cambridge University Press}}.
*{{cite book
 |ref=Oppenheim
 |last1=Oppenheim
 |first1=Alan V.
 |authorlink=Alan V. Oppenheim
 |last2=Schafer
 |first2=Ronald W.
 |author2-link=Ronald W. Schafer
 |last3=Buck
 |first3=John R.
 |title=Discrete-time signal processing
 |pages=[https://archive.org/details/discretetimesign00alan/page/548 548], 571
 |year=1999
 |publisher=Prentice Hall
 |location=Upper Saddle River,N.J.
 |isbn=0-13-754920-2
 |edition=2nd
 |url-access=registration
 |url=https://archive.org/details/discretetimesign00alan
}}
*{{cite book
 |ref=McGillem
 |last1=McGillem
 |first1=Clare D.
 |last2=Cooper
 |first2=George R.
 |title=Continuous and Discrete Signal and System Analysis
 |url=https://archive.org/details/continuousdiscre0000mcgi
 |publisher=Holt, Rinehart and Winston
 |edition=2
 |date=1984
 |isbn=0-03-061703-0
}}

== 外部链接 ==
{{Commons category|Convolution}}
* [http://jeff560.tripod.com/c.html Earliest Uses: The entry on Convolution has some historical information.] {{Wayback|url=http://jeff560.tripod.com/c.html |date=20110501074959 }}
* [https://web.archive.org/web/20060221234856/http://rkb.home.cern.ch/rkb/AN16pp/node38.html#SECTION000380000000000000000 Convolution], on [https://web.archive.org/web/20060512020859/http://rkb.home.cern.ch/rkb/titleA.html The Data Analysis BriefBook]
* http://www.jhu.edu/~signals/convolve/index.html {{Wayback|url=http://www.jhu.edu/~signals/convolve/index.html |date=20120831101935 }} Visual convolution Java Applet
* http://www.jhu.edu/~signals/discreteconv2/index.html {{Wayback|url=http://www.jhu.edu/~signals/discreteconv2/index.html |date=20120831102747 }} Visual convolution Java Applet for discrete-time functions
* https://get-the-solution.net/projects/discret-convolution discret-convolution online calculator
*https://lpsa.swarthmore.edu/Convolution/CI.html {{Wayback|url=https://lpsa.swarthmore.edu/Convolution/CI.html |date=20230715160527 }} Convolution demo and visualization in javascript
*https://phiresky.github.io/convolution-demo/ {{Wayback|url=https://phiresky.github.io/convolution-demo/ |date=20231029022044 }} Another convolution demo in javascript
* [https://archive.org/details/Lectures_on_Image_Processing Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lecture 7 is on 2-D convolution.], by Alan Peters
* * https://archive.org/details/Lectures_on_Image_Processing
* [http://micro.magnet.fsu.edu/primer/java/digitalimaging/processing/kernelmaskoperation/ Convolution Kernel Mask Operation Interactive tutorial] {{Wayback|url=http://micro.magnet.fsu.edu/primer/java/digitalimaging/processing/kernelmaskoperation/ |date=20231210161008 }}
* [http://mathworld.wolfram.com/Convolution.html Convolution] {{Wayback|url=http://mathworld.wolfram.com/Convolution.html |date=20230315013334 }} at [[MathWorld]]
* [http://www.nongnu.org/freeverb3/ Freeverb3 Impulse Response Processor] {{Wayback|url=http://www.nongnu.org/freeverb3/ |date=20231029093122 }}: Opensource zero latency impulse response processor with VST plugins
* Stanford University CS 178 [http://graphics.stanford.edu/courses/cs178/applets/convolution.html interactive Flash demo ] {{Wayback|url=http://graphics.stanford.edu/courses/cs178/applets/convolution.html |date=20231029022042 }} showing how spatial convolution works.
* [https://www.youtube.com/watch?v=IW4Reburjpc A video lecture on the subject of convolution] {{Wayback|url=https://www.youtube.com/watch?v=IW4Reburjpc |date=20231029022044 }} given by [[Salman Khan (educator)|Salman Khan]]
* [http://www.dspguide.com/ch24/6.htm Example of FFT convolution for pattern-recognition (image processing)] {{Wayback|url=http://www.dspguide.com/ch24/6.htm |date=20230319094048 }}
*[https://betterexplained.com/articles/intuitive-convolution/ Intuitive Guide to Convolution] {{Wayback|url=https://betterexplained.com/articles/intuitive-convolution/ |date=20231207202207 }} A blogpost about an intuitive interpretation of convolution.

{{Differentiable computing}}

[[Category:泛函分析|J]]
[[Category:信号处理|J]]
[[Category:二元運算|J]]
[[Category:双线性算子]]
[[Category:特征检测_(计算机视觉)]]