Convolution theorem

Convolution theorem In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms. Più generalmente, convolution in one domain (per esempio., time domain) equals point-wise multiplication in the other domain (per esempio., frequency domain). Other versions of the convolution theorem are applicable to various Fourier-related transforms.

Contenuti 1 Functions of a continuous variable 1.1 Periodic convolution (Fourier series coefficients) 2 Functions of a discrete variable (sequenze) 2.1 Periodic convolution 3 Convolution theorem for inverse Fourier transform 4 Convolution theorem for tempered distributions 5 Guarda anche 6 Appunti 7 Riferimenti 8 Ulteriori letture 9 Additional resources Functions of a continuous variable Consider two functions {stile di visualizzazione g(X)} e {stile di visualizzazione h(X)} with Fourier transforms {stile di visualizzazione G} e {stile di visualizzazione H} : {stile di visualizzazione {inizio{allineato}G(f)&triangleq {matematico {F}}{g}(f)=int _{-infty }^{infty }g(X)e^{-i2pi fx},dx,quad fin mathbb {R} \H(f)&triangleq {matematico {F}}{h}(f)=int _{-infty }^{infty }h(X)e^{-i2pi fx},dx,quad fin mathbb {R} fine{allineato}}} dove {stile di visualizzazione {matematico {F}}} denotes the Fourier transform operator. The transform may be normalized in other ways, in which case constant scaling factors (typically {displaystyle 2pi } o {stile di visualizzazione {mq {2pi }}} ) will appear in the convolution theorem below. The convolution of {stile di visualizzazione g} e {stile di visualizzazione h} è definito da: {stile di visualizzazione r(X)={g*h}(X)triangleq int _{-infty }^{infty }g(sì )h(x-tau ),dtau =int _{-infty }^{infty }g(x-tau )h(sì ),dtau .} In this context the asterisk denotes convolution, instead of standard multiplication. The tensor product symbol {stile di visualizzazione a volte } is sometimes used instead.

The convolution theorem states that:[1][2]: eq.8  {stile di visualizzazione R(f)triangleq {matematico {F}}{r}(f)=G(f)H(f).quad fin mathbb {R} } (Eq.1a) Applying the inverse Fourier transform {stile di visualizzazione {matematico {F}}^{-1}} , produces the corollary:[2]: eqs.7, 10  Convolution theorem {stile di visualizzazione r(X)={g*h}(X)={matematico {F}}^{-1}{Gcdot H},} (Eq.1b) dove {stile di visualizzazione cdot } denotes point-wise multiplication The theorem also generally applies to multi-dimensional functions.

Multi-dimensional derivation of Eq.1 Consider functions {stile di visualizzazione g,h} in Lp-space {stile di visualizzazione L^{1}(mathbb {R} ^{n})} , with Fourier transforms {stile di visualizzazione G,H} : {stile di visualizzazione {inizio{allineato}G(f)&triangleq {matematico {F}}{g}(f)=int _{mathbb {R} ^{n}}g(X)e^{-i2pi fcdot x},dx,quad fin mathbb {R} ^{n}\H(f)&triangleq {matematico {F}}{h}(f)=int _{mathbb {R} ^{n}}h(X)e^{-i2pi fcdot x},dx,fine{allineato}}} dove {displaystyle fcdot x} indicates the inner product of {displaystyle mathbb {R} ^{n}} : {displaystyle fcdot x=sum _{j=1}^{n}{f}_{j}X_{j},} e {displaystyle dx=prod _{j=1}^{n}dx_{j}.} The convolution of {stile di visualizzazione g} e {stile di visualizzazione h} è definito da: {stile di visualizzazione r(X)triangleq int _{mathbb {R} ^{n}}g(sì )h(x-tau ),dtau .} Anche: {displaystyle iint |g(sì )h(x-tau )|,dx,dtau =int left(|g(sì )|int |h(x-tau )|,dxright),dtau =int |g(sì )|,|h|_{1},dtau =|g|_{1}|h|_{1}.} Hence by Fubini's theorem we have that {displaystyle rin L^{1}(mathbb {R} ^{n})} so its Fourier transform {stile di visualizzazione R} is defined by the integral formula: {stile di visualizzazione {inizio{allineato}R(f)triangleq {matematico {F}}{r}(f)&=int _{mathbb {R} ^{n}}r(X)e^{-i2pi fcdot x},dx\&=int _{mathbb {R} ^{n}}sinistra(int _{mathbb {R} ^{n}}g(sì )h(x-tau ),dtau right),e^{-i2pi fcdot x},dx.end{allineato}}} Notare che {stile di visualizzazione |g(sì )h(x-tau )e^{-i2pi fcdot x}|=|g(sì )h(x-tau )|} and hence by the argument above we may apply Fubini's theorem again (cioè. interchange the order of integration): {stile di visualizzazione {inizio{allineato}R(f)&=int _{mathbb {R} ^{n}}g(sì )underbrace {sinistra(int _{mathbb {R} ^{n}}h(x-tau ) e^{-i2pi fcdot x},dxright)} _{H(f) e^{-i2pi fcdot tau }},dtau \&=underbrace {sinistra(int _{mathbb {R} ^{n}}g(sì ) e^{-i2pi fcdot tau },dtau right)} _{G(f)} H(f).fine{allineato}}} This theorem also holds for the Laplace transform, the two-sided Laplace transform and, when suitably modified, for the Mellin transform and Hartley transform (see Mellin inversion theorem). It can be extended to the Fourier transform of abstract harmonic analysis defined over locally compact abelian groups.

Periodic convolution (Fourier series coefficients) Ritenere {stile di visualizzazione P} -periodic functions {stile di visualizzazione g_{_{P}}} e {stile di visualizzazione h_{_{P}},} which can be expressed as periodic summations: {stile di visualizzazione g_{_{P}}(X) triangleq sum _{m=-infty }^{infty }g(x-mP)} e {stile di visualizzazione h_{_{P}}(X) triangleq sum _{m=-infty }^{infty }h(x-mP).} In practice the non-zero portion of components {stile di visualizzazione g} e {stile di visualizzazione h} are often limited to duration {stile di visualizzazione P,} but nothing in the theorem requires that. The Fourier series coefficients are: {stile di visualizzazione {inizio{allineato}G[K]&triangleq {matematico {F}}{g_{_{P}}}[K]={frac {1}{P}}int _{P}g_{_{P}}(X)e^{-i2pi kx/P},dx,quad kin mathbb {Z} ;quad quad scriptstyle {testo{integration over any interval of length }}P\H[K]&triangleq {matematico {F}}{h_{_{P}}}[K]={frac {1}{P}}int _{P}h_{_{P}}(X)e^{-i2pi kx/P},dx,quad kin mathbb {Z} fine{allineato}}} dove {stile di visualizzazione {matematico {F}}} denotes the Fourier series integral.

The pointwise product: {stile di visualizzazione g_{_{P}}(X)cdot h_{_{P}}(X)} è anche {stile di visualizzazione P} -periodic, and its Fourier series coefficients are given by the discrete convolution of the {stile di visualizzazione G} e {stile di visualizzazione H} sequenze: {stile di visualizzazione {matematico {F}}{g_{_{P}}cdot h_{_{P}}}[K]={G*H}[K].} The convolution: {stile di visualizzazione {inizio{allineato}{g_{_{P}}*h}(X) &triangleq int _{-infty }^{infty }g_{_{P}}(x-tau )cdot h(sì ) dtau \&equiv int _{P}g_{_{P}}(x-tau )cdot h_{_{P}}(sì ) dtau ;quad quad scriptstyle {testo{integration over any interval of length }}Pend{allineato}}} è anche {stile di visualizzazione P} -periodic,[UN] and is called a periodic convolution. The corresponding convolution theorem is: {stile di visualizzazione {matematico {F}}{g_{_{P}}*h}[K]= Pcdot G[K] H[K].} (Eq.2) Derivation of Eq.2 {stile di visualizzazione {inizio{allineato}{matematico {F}}{g_{_{P}}*h}[K]&triangleq {frac {1}{P}}int _{P}sinistra(int _{P}g_{_{P}}(sì )cdot h_{_{P}}(x-tau ) dtau right)e^{-i2pi kx/P},dx\&=int _{P}g_{_{P}}(sì )sinistra({frac {1}{P}}int _{P}h_{_{P}}(x-tau ) e^{-i2pi kx/P}dxright),dtau \&=int _{P}g_{_{P}}(sì ) e^{-i2pi ktau /P}underbrace {sinistra({frac {1}{P}}int _{P}h_{_{P}}(x-tau ) e^{-i2pi k(x-tau )/P}dxright)} _{H[K],quad {testo{due to periodicity}}},dtau \&=underbrace {sinistra(int _{P} g_{_{P}}(sì ) e^{-i2pi ktau /P}dtau right)} _{Pcdot G[K]} H[K].fine{allineato}}} Functions of a discrete variable (sequenze) By a derivation similar to Eq.1, there is an analogous theorem for sequences, such as samples of two continuous functions, where now {stile di visualizzazione {matematico {F}}} denotes the discrete-time Fourier transform (DTFT) operatore. Consider two sequences {stile di visualizzazione g[n]} e {stile di visualizzazione h[n]} with transforms {stile di visualizzazione G} e {stile di visualizzazione H} : {stile di visualizzazione {inizio{allineato}G(f)&triangleq {matematico {F}}{g}(f)=somma _{n=-infty }^{infty }g[n]cdot e^{-i2pi fn};,quad fin mathbb {R} \H(f)&triangleq {matematico {F}}{h}(f)=somma _{n=-infty }^{infty }h[n]cdot e^{-i2pi fn};.quad fin mathbb {R} fine{allineato}}} The § Discrete convolution of {stile di visualizzazione g} e {stile di visualizzazione h} è definito da: {stile di visualizzazione r[n]triangleq (g*h)[n]=somma _{m=-infty }^{infty }g[m]cdot h[n-m]=somma _{m=-infty }^{infty }g[n-m]cdot h[m].} The convolution theorem for discrete sequences is:[3][4]: p.60 (2.169)  {stile di visualizzazione R(f)={matematico {F}}{g*h}(f)= G(f)H(f).} (Eq.3) Periodic convolution {stile di visualizzazione G(f)} e {stile di visualizzazione H(f),} come sopra definito, are periodic, with a period of 1. Ritenere {stile di visualizzazione N} -periodic sequences {stile di visualizzazione g_{_{N}}} e {stile di visualizzazione h_{_{N}}} : {stile di visualizzazione g_{_{N}}[n] triangleq sum _{m=-infty }^{infty }g[n-mN]} e {stile di visualizzazione h_{_{N}}[n] triangleq sum _{m=-infty }^{infty }h[n-mN],quad nin mathbb {Z} .} These functions occur as the result of sampling {stile di visualizzazione G} e {stile di visualizzazione H} at intervals of {displaystyle 1/N} and performing an inverse discrete Fourier transform (DFT) Su {stile di visualizzazione N} samples (see § Sampling the DTFT). The discrete convolution: {stile di visualizzazione {g_{_{N}}*h}[n] triangleq sum _{m=-infty }^{infty }g_{_{N}}[m]cdot h[n-m]equiv sum _{m=0}^{N-1}g_{_{N}}[m]cdot h_{_{N}}[n-m]} è anche {stile di visualizzazione N} -periodic, and is called a periodic convolution. Redefining the {stile di visualizzazione {matematico {F}}} operator as the {stile di visualizzazione N} -length DFT, the corresponding theorem is:[5][4]: p.548  {stile di visualizzazione {matematico {F}}{g_{_{N}}*h}[K]= underbrace {{matematico {F}}{g_{_{N}}}[K]} _{G(k/N)}cdot underbrace {{matematico {F}}{h_{_{N}}}[K]} _{H(k/N)},quad kin mathbb {Z} .} (Eq.4a) And therefore: {stile di visualizzazione {g_{_{N}}*h}[n]= {matematico {F}}^{-1}{{matematico {F}}{g_{_{N}}}cdot {matematico {F}}{h_{_{N}}}}.} (Eq.4b) Under the right conditions, it is possible for this N-length sequence to contain a distortion-free segment of a {displaystyle g*h} convolution. But when the non-zero portion of the {stile di visualizzazione g(n)} o {stile di visualizzazione h(n)} sequence is equal or longer than {stile di visualizzazione N,} some distortion is inevitable. Such is the case when the {stile di visualizzazione H(k/N)} sequence is obtained by directly sampling the DTFT of the infinitely long § Discrete Hilbert transform impulse response.[B] Per {stile di visualizzazione g} e {stile di visualizzazione h} sequences whose non-zero duration is less than or equal to {stile di visualizzazione N,} a final simplification is: Circular convolution {stile di visualizzazione {g_{_{N}}*h}[n]= {matematico {F}}^{-1}{{matematico {F}}{g}cdot {matematico {F}}{h}}.} (Eq.4c) This form is often used to efficiently implement numerical convolution by computer. (see § Fast convolution algorithms and § Example) As a partial reciprocal, it has been shown [6] that any linear transform that turns convolution into pointwise product is the DFT (up to a permutation of coefficients).

Derivations of Eq.4 A time-domain derivation proceeds as follows: {stile di visualizzazione {inizio{allineato}{stile di sceneggiatura {rm {DFT}}}{g_{_{N}}*h}[K]&triangleq sum _{n=0}^{N-1}sinistra(somma _{m=0}^{N-1}g_{_{N}}[m]cdot h_{_{N}}[n-m]Giusto)e^{-i2pi kn/N}\&=sum _{m=0}^{N-1}g_{_{N}}[m]sinistra(somma _{n=0}^{N-1}h_{_{N}}[n-m]cdot e^{-i2pi kn/N}Giusto)\&=sum _{m=0}^{N-1}g_{_{N}}[m]cdot e^{-i2pi km/N}underbrace {sinistra(somma _{n=0}^{N-1}h_{_{N}}[n-m]cdot e^{-i2pi k(n-m)/N}Giusto)} _{{stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]quad scriptstyle {testo{due to periodicity}}}\&=underbrace {sinistra(somma _{m=0}^{N-1}g_{_{N}}[m]cdot e^{-i2pi km/N}Giusto)} _{{stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]}sinistra({stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]Giusto).fine{allineato}}} A frequency-domain derivation follows from § Periodic data, which indicates that the DTFTs can be written as: {stile di visualizzazione {matematico {F}}{g_{_{N}}*h}(f)={frac {1}{N}}somma _{k=-infty }^{infty }sinistra({stile di sceneggiatura {rm {DFT}}}{g_{_{N}}*h}[K]Giusto)cdot delta left(f-k/Nright).} (5un) {stile di visualizzazione {matematico {F}}{g_{_{N}}}(f)={frac {1}{N}}somma _{k=-infty }^{infty }sinistra({stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]Giusto)cdot delta left(f-k/Nright).} The product with {stile di visualizzazione H(f)} is thereby reduced to a discrete-frequency function: {stile di visualizzazione {inizio{allineato}{matematico {F}}{g_{_{N}}*h}(f)&=G_{_{N}}(f)H(f)\&={frac {1}{N}}somma _{k=-infty }^{infty }sinistra({stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]Giusto)cdot H(f)cdot delta left(f-k/Nright)\&={frac {1}{N}}somma _{k=-infty }^{infty }sinistra({stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]Giusto)cdot H(k/N)cdot delta left(f-k/Nright)\&={frac {1}{N}}somma _{k=-infty }^{infty }sinistra({stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]Giusto)cdot a sinistra({stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]Giusto)cdot delta left(f-k/Nright),quad scriptstyle {matematica {(Eq.5b)}}fine{allineato}}} where the equivalence of {stile di visualizzazione H(k/N)} e {stile di visualizzazione a sinistra({stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]Giusto)} follows from § Sampling the DTFT. Perciò, the equivalence of (5un) e (5b) requires: {stile di visualizzazione {stile di sceneggiatura {rm {DFT}}}{{g_{_{N}}*h}[K]}= sinistra({stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]Giusto)cdot a sinistra({stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]Giusto).} We can also verify the inverse DTFT of (5b): {stile di visualizzazione {inizio{allineato}(g_{_{N}}*h)[n]&=int _{0}^{1}sinistra({frac {1}{N}}somma _{k=-infty }^{infty }{stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]cdot {stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]cdot delta left(f-k/Nright)Giusto)cdot e^{i2pi fn}df\&={frac {1}{N}}somma _{k=-infty }^{infty }{stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]cdot {stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]cdot underbrace {sinistra(int _{0}^{1}delta left(f-k/Nright)cdot e^{i2pi fn}dfright)} _{{testo{0, per}} k notin [0, N)}\&={frac {1}{N}}somma _{k=0}^{N-1}{bigg (}{stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}[K]cdot {stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}[K]{bigg )}cdot e^{i2pi {frac {n}{N}}K}\&= {stile di sceneggiatura {rm {DFT}}^{-1}}{bigg (}{stile di sceneggiatura {rm {DFT}}}{g_{_{N}}}cdot {stile di sceneggiatura {rm {DFT}}}{h_{_{N}}}{bigg )}.fine{allineato}}} Convolution theorem for inverse Fourier transform There is also a convolution theorem for the inverse Fourier transform: {stile di visualizzazione {matematico {F}}{g*h}={matematico {F}}{g}cdot {matematico {F}}{h}} {stile di visualizzazione {matematico {F}}{gcdot h}={matematico {F}}{g}*{matematico {F}}{h}} affinché {displaystyle g*h={matematico {F}}^{-1}sinistra{{matematico {F}}{g}cdot {matematico {F}}{h}Giusto}} {displaystyle gcdot h={matematico {F}}^{-1}sinistra{{matematico {F}}{g}*{matematico {F}}{h}Giusto}} Convolution theorem for tempered distributions The convolution theorem extends to tempered distributions. Qui, {stile di visualizzazione g} is an arbitrary tempered distribution (per esempio. the Dirac comb) {stile di visualizzazione {matematico {F}}{f*g}={matematico {F}}{f}cdot {matematico {F}}{g}} {stile di visualizzazione {matematico {F}}{alpha cdot g}={matematico {F}}{alfa }*{matematico {F}}{g}} ma {displaystyle f=F{alfa }} must be "rapidly decreasing" towards {displaystyle -infty } e {displaystyle +infty } in order to guarantee the existence of both, convolution and multiplication product. Equivalentemente, Se {displaystyle alpha =F^{-1}{f}} è un liscio "slowly growing" ordinary function, it guarantees the existence of both, multiplication and convolution product.[7][8][9] In particolare, every compactly supported tempered distribution, such as the Dirac Delta, è "rapidly decreasing". Equivalentemente, bandlimited functions, such as the function that is constantly {stile di visualizzazione 1} are smooth "slowly growing" ordinary functions. Se, Per esempio, {displaystyle gequiv operatorname {III} } is the Dirac comb both equations yield the Poisson summation formula and if, furthermore, {displaystyle fequiv delta } is the Dirac delta then {displaystyle alfa equiv 1} is constantly one and these equations yield the Dirac comb identity.

See also Moment-generating function of a random variable Notes ^ Proof: {stile di visualizzazione {inizio{allineato}int _{-infty }^{infty }g_{_{P}}(x-tau )cdot h(sì ),dtau &=sum _{k=-infty }^{infty }sinistra[int _{X_{o}+kP}^{X_{o}+(k+1)P}g_{_{P}}(x-tau )cdot h(sì ) dtau right]quad x_{0}{testo{ is an arbitrary parameter}}\&=sum _{k=-infty }^{infty }sinistra[int _{X_{o}}^{X_{o}+P}underbrace {g_{_{P}}(x-tau -kP)} _{g_{_{P}}(x-tau ),{testo{ by periodicity}}}cdot h(tau +kP) dtau right]quad {testo{substituting }}tau rightarrow tau +kP\&=int _{X_{o}}^{X_{o}+P}g_{_{P}}(x-tau )cdot underbrace {sinistra[somma _{k=-infty }^{infty }h(tau +kP)Giusto]} _{triangleq h_{_{P}}(sì )} dtau end{allineato}}} ^ An example is the MATLAB function, hilbert(g,N). References ^ McGillem, Clare D.; Cooper, George R. (1984). Continuous and Discrete Signal and System Analysis (2 ed.). Holt, Rinehart and Winston. p. 118 (3-102). ISBN 0-03-061703-0. ^ Salta su: a b Weisstein, Eric W. "Convolution Theorem". Da MathWorld: una risorsa Web Wolfram. Recuperato 8 febbraio 2021. ^ Proakis, John G.; Manolakis, Dimitri G. (1996), Digital Signal Processing: Principles, Algorithms and Applications (3 ed.), New Jersey: Prentice-Hall International, p. 297, Bibcode:1996dspp.book.....P, ISBN 9780133942897, sAcfAQAAIAAJ ^ Jump up to: a b Oppenheim, Alan V.; Schafer, Ronald W.; secchio, Giovanni R. (1999). Discrete-time signal processing (2nd ed.). Upper Saddle River, N.J.: Sala dell'Apprendista. ISBN 0-13-754920-2. Also available at https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf ^ Rabiner, Lawrence R.; Oro, Bernardo (1975). Theory and application of digital signal processing. Englewood Cliffs, NJ: Prentice Hall, Inc. p. 59 (2.163). ISBN 978-0139141010. ^ Amiot, Emmanuel (2016). Music through Fourier Space. Zurigo: Springer. p. 8. ISBN 978-3-319-45581-5. ^ Horváth, John (1966). Topological Vector Spaces and Distributions. Lettura, MA: Addison-Wesley Publishing Company. ^ Barros-Neto, José (1973). An Introduction to the Theory of Distributions. New York, New York: Dekker. ^ Petersen, Bent E. (1983). Introduction to the Fourier Transform and Pseudo-Differential Operators. Boston, MA: Pitman Publishing. Further reading Katznelson, Yitzhak (1976), An introduction to Harmonic Analysis, Dover, ISBN 0-486-63331-4 Li, Bing; Babu, G. Jogesh (2019), "Convolution Theorem and Asymptotic Efficiency", A Graduate Course on Statistical Inference, New York: Springer, pp. 295–327, ISBN 978-1-4939-9759-6 Crutchfield, Steve (ottobre 9, 2010), "The Joy of Convolution", Johns Hopkins University, retrieved November 19, 2010 Additional resources For a visual representation of the use of the convolution theorem in signal processing, vedere: Johns Hopkins University's Java-aided simulation: http://www.jhu.edu/signals/convolve/index.html Categories: Theorems in Fourier analysis