--- title: "DiscreteConvolve" language: "en" type: "Symbol" summary: "DiscreteConvolve[f, g, n, m] gives the convolution with respect to n of the expressions f and g. DiscreteConvolve[f, g, {n1, n2, ...}, {m1, m2, ...}] gives the multidimensional convolution." keywords: - convolution - discrete convolution - filtering - faltung - faltning canonical_url: "https://reference.wolfram.com/language/ref/DiscreteConvolve.html" source: "Wolfram Language Documentation" related_guides: - title: "Summation Transforms" link: "https://reference.wolfram.com/language/guide/SummationTransforms.en.md" - title: "Fourier Analysis" link: "https://reference.wolfram.com/language/guide/FourierAnalysis.en.md" - title: "Additive Number Theory" link: "https://reference.wolfram.com/language/guide/AdditiveNumberTheory.en.md" related_functions: - title: "Sum" link: "https://reference.wolfram.com/language/ref/Sum.en.md" - title: "Convolve" link: "https://reference.wolfram.com/language/ref/Convolve.en.md" - title: "ListConvolve" link: "https://reference.wolfram.com/language/ref/ListConvolve.en.md" - title: "ZTransform" link: "https://reference.wolfram.com/language/ref/ZTransform.en.md" - title: "GeneratingFunction" link: "https://reference.wolfram.com/language/ref/GeneratingFunction.en.md" - title: "FourierSequenceTransform" link: "https://reference.wolfram.com/language/ref/FourierSequenceTransform.en.md" - title: "DirichletConvolve" link: "https://reference.wolfram.com/language/ref/DirichletConvolve.en.md" --- # DiscreteConvolve DiscreteConvolve[f, g, n, m] gives the convolution with respect to n of the expressions f and g. DiscreteConvolve[f, g, {n1, n2, …}, {m1, m2, …}] gives the multidimensional convolution. ## Details and Options * The convolution $(\text{\textit{$f$}}*\text{\textit{$g$}})(\text{\textit{$m$}})$ of two sequences $f(n)$ and $g(n)$ is given by $\sum _{n=-\infty }^{\infty } f(n) g(m-n)$. * The multidimensional convolution is given by $\sum _{n_1=-\infty }^{\infty } \sum _{n_2=-\infty }^{\infty } \cdots \text{\textit{$f$}}\left(n_1,n_2,\ldots \right) g\left(m_1-n_1,m_2-n_2,\ldots \right)$. * The following options can be given: | | | | | ------------------- | ------------- | -------------------------------------------- | | Assumptions | \$Assumptions | assumptions to make about parameters | | GenerateConditions | False | whether to generate conditions on parameters | | Method | Automatic | method to use | | VerifyConvergence | True | whether to verify convergence | --- ## Examples (20) ### Basic Examples (3) Convolve a sequence with ``DiscreteDelta`` : ```wl In[1]:= DiscreteConvolve[DiscreteDelta[n], Sin[n], n, m] Out[1]= Sin[m] ``` --- Convolve two exponential sequences: ```wl In[1]:= DiscreteConvolve[(1 / 2) ^ n UnitStep[n], (1 / 2) ^ n UnitStep[n], n, m] Out[1]= Piecewise[{{(1 + m)/2^m, m >= 0}}, 0] ``` --- Convolve two ``UnitBox`` sequences and plot the result: ```wl In[1]:= DiscreteConvolve[UnitBox[n / 5], UnitBox[n / 5], n, m]; In[2]:= DiscretePlot[%, {m, -8, 8}, PlotRange -> All] Out[2]= [image] ``` ### Scope (4) #### Univariate Convolution (3) Convolution sums the product of translates: ```wl In[1]:= f[n_] := UnitBox[n / 7] In[2]:= g[n_] := 2 UnitBox[n / 3 + 1] In[3]:= GraphicsRow@Table[DiscretePlot[{f[x], g[x - i]}, {x, -10, 10}, ImageSize -> 110, Ticks -> None, PlotRange -> All], {i, -1, 2}] Out[3]= [image] In[4]:= DiscreteConvolve[f[n], g[n], n, m] Out[4]= 2 (Piecewise[{{1, m == -7 || m == 1}, {2, m == -6 || m == 0}, {3, -6 < m < 0}}, 0]) In[5]:= DiscretePlot[%, {m, -10, 10}] Out[5]= [image] ``` --- Convolution of elementary sequences: ```wl In[1]:= DiscreteConvolve[1 / (2n + 1) ^ 2, 1 / (3n - 1) ^ 2, n, m] Out[1]= (π (π + 6 m π + (1 + 6 m) π Sec[((1/6) + m) π]^2 - 12 Tan[((1/6) + m) π])/(1 + 6 m)^3) ``` --- Convolution of piecewise sequences: ```wl In[1]:= DiscreteConvolve[4 ^ (-n) UnitStep[n], 7 ^ n UnitStep[n], n, m] Out[1]= Piecewise[{{((1/27)*(-1 + 28^(1 + m)))/4^m, m >= 0}}, 0] ``` #### Multivariate Convolution (1) ```wl In[1]:= DiscreteConvolve[UnitBox[m / 4, n / 7 + 1], m ^ 2 + n, {m, n}, {r, s}] Out[1]= 35 (2 + r^2) + 35 (7 + s) ``` ### Generalizations & Extensions (1) Multiplication by ``UnitStep`` effectively gives the convolution over a finite interval: ```wl In[1]:= DiscreteConvolve[2 ^ n UnitStep[n], n UnitStep[n], n, m] Out[1]= Piecewise[{{-2 + 2^(1 + m) - m, m >= 0}}, 0] In[2]:= Sum[2 ^ n (m - n), {n, 0, m}] Out[2]= -2 + 2^1 + m - m ``` ### Options (2) #### Assumptions (1) Specify assumptions on a variable or parameter: ```wl In[1]:= DiscreteConvolve[UnitStep[n] / 3 ^ n, 2 ^ n UnitStep[-n], n, m, Assumptions -> m > 0] Out[1]= (2 3^1 - m/5) In[2]:= DiscreteConvolve[UnitStep[n] / 3 ^ n, 2 ^ n UnitStep[-n], n, m, Assumptions -> m < 0] Out[2]= (3 2^1 + m/5) ``` #### GenerateConditions (1) Generate conditions for the range of a parameter: ```wl In[1]:= DiscreteConvolve[E ^ (-a Abs[n]), 1, n, m, GenerateConditions -> True] Out[1]= ConditionalExpression[(1 + E^a)/(-1 + E^a), E^Re[a] > 1] ``` ### Applications (2) Obtain a particular solution for a linear difference equation: ```wl In[1]:= y[n] /. RSolve[{y[n] - 2y[n - 1] == n, y[0] == 0}, y, n][[1]] Out[1]= -2 + 2^1 + n - n In[2]:= DiscreteConvolve[2 ^ k UnitStep[k], k UnitStep[k], k, n, Assumptions -> n > 0] Out[2]= -2 + 2^1 + n - n ``` --- Obtain the step response of a linear, time-invariant system given its impulse response ``h``: ```wl In[1]:= h = (4 / 5) ^ n UnitStep[n]; In[2]:= DiscretePlot[h, {n, 0, 20}] Out[2]= [image] ``` The step response corresponding to this system: ```wl In[3]:= DiscreteConvolve[h, UnitStep[n], n, m] Out[3]= Piecewise[{{5 - 4^(1 + m)/5^m, m >= 0}}, 0] In[4]:= DiscretePlot[%, {m, -5, 20}] Out[4]= [image] ``` ### Properties & Relations (7) ``DiscreteConvolve`` computes a sum over the set of integers: ```wl In[1]:= DiscreteConvolve[1 / (3n + 1) ^ 2, UnitStep[n], n, m, Assumptions -> m > 0] Out[1]= (1/27) (4 π^2 - 3 PolyGamma[1, (4/3) + m]) In[2]:= Sum[UnitStep[m - n] / (3n + 1) ^ 2, {n, -Infinity, Infinity}, Assumptions -> Element[m, Integers] && m > 0] Out[2]= (1/27) (4 π^2 - 3 PolyGamma[1, (4/3) + m]) ``` --- Convolution with ``DiscreteDelta`` gives the value of a sequence at ``m`` : ```wl In[1]:= DiscreteConvolve[f[n], DiscreteDelta[n], n, m] Out[1]= f[m] ``` --- Scaling: ```wl In[1]:= DiscreteConvolve[a r[n], s[n], n, m] Out[1]= a DiscreteConvolve[r[n], s[n], n, m] In[2]:= DiscreteConvolve[r[n], a s[n], n, m] Out[2]= a DiscreteConvolve[r[n], s[n], n, m] ``` --- Commutativity: ```wl In[1]:= f[n_] := 2 ^ n UnitStep[n] In[2]:= g[n_] := UnitStep[n] In[3]:= DiscreteConvolve[f[n], g[n], n, m] Out[3]= Piecewise[{{-1 + 2^(1 + m), m >= 0}}, 0] In[4]:= DiscreteConvolve[g[n], f[n], n, m] Out[4]= Piecewise[{{-1 + 2^(1 + m), m >= 0}}, 0] ``` --- Distributivity: ```wl In[1]:= DiscreteConvolve[h[n] + i[n], j[n], n, m] Out[1]= DiscreteConvolve[h[n], j[n], n, m] + DiscreteConvolve[i[n], j[n], n, m] In[2]:= DiscreteConvolve[h[n], i[n] + j[n], n, m] Out[2]= DiscreteConvolve[h[n], i[n], n, m] + DiscreteConvolve[h[n], j[n], n, m] ``` --- The ``ZTransform`` of a causal convolution is the product of the individual transforms: ```wl In[1]:= f[n_] := 2 ^ n UnitStep[n] In[2]:= g[n_] := UnitStep[n] In[3]:= ZTransform[DiscreteConvolve[f[n], g[n], n, m], m, z] Out[3]= (z^2/2 - 3 z + z^2) In[4]:= Simplify[ZTransform[f[n], n, z]ZTransform[g[n], n, z]] Out[4]= (z^2/2 - 3 z + z^2) ``` Similarly for ``GeneratingFunction``: ```wl In[5]:= GeneratingFunction[DiscreteConvolve[f[n], g[n], n, m], m, z] Out[5]= (1/1 - 3 z + 2 z^2) In[6]:= GeneratingFunction[f[n], n, z]GeneratingFunction[g[n], n, z] Out[6]= (1/(1 - 2 z) (1 - z)) In[7]:= %% - %//Simplify Out[7]= 0 ``` --- The ``FourierSequenceTransform`` of a convolution is the product of the individual transforms: ```wl In[1]:= f[n_] := 3 ^ (-n) UnitStep[n] In[2]:= g[n_] := 2 ^ (n)UnitStep[-n] In[3]:= DiscreteConvolve[f[n], g[n], n, m] Out[3]= 2^m (Piecewise[{{6/5, m <= 0}}, 6^(1 - m)/5]) In[4]:= Together[FourierSequenceTransform[%, m, w]] Out[4]= -(6 E^I w/2 - 7 E^I w + 3 E^2 I w) In[5]:= Simplify[FourierSequenceTransform[f[n], n, w] FourierSequenceTransform[g[n], n, w]] Out[5]= -(6 E^I w/2 - 7 E^I w + 3 E^2 I w) ``` ### Interactive Examples (1) This demonstrates the discrete-time convolution operation $(f* g) (y)$ : ```wl In[1]:= DynamicModule[{f, g, h}, f[n_] := (3 / 4) ^ n UnitStep[n]; g[n_] := UnitBox[n / 5]; h[n_] = DiscreteConvolve[f[m], g[m], m, n]; Manipulate[GraphicsRow[{DiscretePlot[{f[m], g[n - m]}, {m, -5, 12}, ...], DiscretePlot[f[m]g[n - m], {m, -5, 12}, ...], DiscretePlot[h[m], {m, -5, n}, ...]}, ImageSize -> 480], {{n, 1}, -4, 11, 1}]] Out[1]= DynamicModule[«3»] ``` ## See Also * [`Sum`](https://reference.wolfram.com/language/ref/Sum.en.md) * [`Convolve`](https://reference.wolfram.com/language/ref/Convolve.en.md) * [`ListConvolve`](https://reference.wolfram.com/language/ref/ListConvolve.en.md) * [`ZTransform`](https://reference.wolfram.com/language/ref/ZTransform.en.md) * [`GeneratingFunction`](https://reference.wolfram.com/language/ref/GeneratingFunction.en.md) * [`FourierSequenceTransform`](https://reference.wolfram.com/language/ref/FourierSequenceTransform.en.md) * [`DirichletConvolve`](https://reference.wolfram.com/language/ref/DirichletConvolve.en.md) ## Related Guides * [Summation Transforms](https://reference.wolfram.com/language/guide/SummationTransforms.en.md) * [Fourier Analysis](https://reference.wolfram.com/language/guide/FourierAnalysis.en.md) * [Additive Number Theory](https://reference.wolfram.com/language/guide/AdditiveNumberTheory.en.md) ## Related Links * [MathWorld](https://mathworld.wolfram.com/Convolution.html) ## History * [Introduced in 2008 (7.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn70.en.md)