Konvoluční věta - Convolution theorem - Wikipedia

v matematika, konvoluční věta uvádí, že za vhodných podmínek Fourierova transformace a konvoluce ze dvou signály je bodový produkt jejich Fourierových transformací. Jinými slovy, konvoluce v jedné doméně (např. časová doména ) rovná se bodové násobení v jiné doméně (např. frekvenční doména ). Verze věty o konvoluci platí pro různé Fourierovy transformace. Nechat ${ displaystyle f}$ a ${ displaystyle g}$ být dva funkce s konvoluce ${ displaystyle f * g}$ . (Všimněte si, že hvězdička označuje v tomto kontextu konvoluci, nikoli standardní násobení. The tenzorový produkt symbol ${ displaystyle otimes}$ místo toho se někdy používá.)

Li ${ displaystyle { mathcal {F}}}$ označuje Fourierovu transformaci operátor, pak ${ displaystyle { mathcal {F}} {f }}$ a ${ displaystyle { mathcal {F}} {g }}$ jsou Fourierovy transformace ${ displaystyle f}$ a ${ displaystyle g}$ , resp. Pak

{ displaystyle { mathcal {F}} {f * g } = { mathcal {F}} {f } cdot { mathcal {F}} {g }}

^[1]

kde ${ displaystyle cdot}$ označuje bodové násobení. Funguje to i opačně:

{ displaystyle { mathcal {F}} {f cdot g } = { mathcal {F}} {f } * { mathcal {F}} {g }}

Aplikováním inverzní Fourierovy transformace ${ displaystyle { mathcal {F}} ^ {- 1}}$ , můžeme psát:

{ displaystyle f * g = { mathcal {F}} ^ {- 1} { big {} { mathcal {F}} {f } cdot { mathcal {F}} {g } { velký }}}

a:

{ displaystyle f cdot g = { mathcal {F}} ^ {- 1} { big {} { mathcal {F}} {f } * { mathcal {F}} {g } { velký }}}

Vztahy výše jsou platné pouze pro formu Fourierovy transformace zobrazené v Důkaz níže. Transformace může být normalizována jinými způsoby, v takovém případě jsou faktory konstantního měřítka (obvykle ${ displaystyle 2 pi}$ nebo ${ displaystyle { sqrt {2 pi}}}$ ) se objeví ve výše uvedených vztazích.

Tato věta platí také pro Laplaceova transformace, oboustranná Laplaceova transformace a pokud jsou vhodně upraveny, pro Mellinova transformace a Hartleyova transformace (vidět Mellinova věta o inverzi ). Může být rozšířena na Fourierovu transformaci abstraktní harmonická analýza definováno přes místně kompaktní abelianské skupiny.

Tato formulace je zvláště užitečná pro implementaci numerické konvoluce na a počítač: Standardní konvoluční algoritmus má kvadratický výpočetní složitost. S pomocí věty o konvoluci a rychlá Fourierova transformace, lze složitost konvoluce snížit z ${ displaystyle O left (n ^ {2} right)}$ na ${ displaystyle O left (n log n right)}$ , použitím velká O notace. To lze využít k rychlé konstrukci multiplikační algoritmy, jako v Algoritmus násobení § Metody Fourierovy transformace.

Důkaz

Důkaz se zde zobrazuje pro konkrétní normalizace Fourierovy transformace. Jak bylo uvedeno výše, pokud je transformace normalizována odlišně, pak konstantní faktory měřítka se objeví v derivaci.

Nechat ${ displaystyle f, g}$ patří k L^str -prostor ${ displaystyle L ^ {1} ( mathbb {R} ^ {n})}$ . Nechat ${ displaystyle F}$ být Fourierovou transformací ${ displaystyle f}$ a ${ displaystyle G}$ být Fourierovou transformací ${ displaystyle g}$ :

{ displaystyle { begin {zarovnáno} F ( nu) & = { mathcal {F}} {f } ( nu) = int _ { mathbb {R} ^ {n}} f (x ) e ^ {- 2 pi ix cdot nu} , dx, G ( nu) & = { mathcal {F}} {g } ( nu) = int _ { mathbb {R} ^ {n}} g (x) e ^ {- 2 pi ix cdot nu} , dx, end {zarovnáno}}}

Kde tečka mezi ${ displaystyle x}$ a ${ displaystyle nu}$ označuje vnitřní produkt z ${ displaystyle mathbb {R} ^ {n}}$ . Nechat ${ displaystyle h}$ být konvoluce z ${ displaystyle f}$ a ${ displaystyle g}$

{ displaystyle h (z) = int _ { mathbb {R} ^ {n}} f (x) g (z-x) , dx.}

Taky

{ Displaystyle iint | f (x) g (zx) | , dz , dx = int vlevo (| f (x) | int | g (zx) | , dz vpravo) , dx = int | f (x) | , | g | _ {1} , dx = | f | _ {1} | g | _ {1}.}

Proto Fubiniho věta máme to ${ displaystyle h in L ^ {1} ( mathbb {R} ^ {n})}$ takže jeho Fourierova transformace ${ displaystyle H}$ je definován integrálním vzorcem

{ displaystyle { begin {aligned} H ( nu) = { mathcal {F}} {h } & = int _ { mathbb {R} ^ {n}} h (z) e ^ { -2 pi iz cdot nu} , dz & = int _ { mathbb {R} ^ {n}} int _ { mathbb {R} ^ {n}} f (x) g (zx) , dx , e ^ {- 2 pi iz cdot nu} , dz. end {zarovnáno}}}

Všimněte si, že ${ displaystyle | f (x) g (z-x) e ^ {- 2 pi iz cdot nu} | = | f (x) g (z-x) |}$ a tedy výše uvedeným argumentem můžeme znovu použít Fubiniho teorém (tj. vyměnit pořadí integrace):

{ displaystyle H ( nu) = int _ { mathbb {R} ^ {n}} f (x) left ( int _ { mathbb {R} ^ {n}} g (zx) e ^ {-2 pi iz cdot nu} , dz right) , dx.}

Střídání ${ displaystyle y = z-x}$ výnosy ${ displaystyle dy = dz}$ . Proto

{ displaystyle H ( nu) = int _ { mathbb {R} ^ {n}} f (x) left ( int _ { mathbb {R} ^ {n}} g (y) e ^ {-2 pi i (y + x) cdot nu} , dy right) , dx}

{ displaystyle = int _ { mathbb {R} ^ {n}} f (x) e ^ {- 2 pi ix cdot nu} left ( int _ { mathbb {R} ^ {n }} g (y) e ^ {- 2 pi iy cdot nu} , dy right) , dx}

{ displaystyle = int _ { mathbb {R} ^ {n}} f (x) e ^ {- 2 pi ix cdot nu} , dx int _ { mathbb {R} ^ {n }} g (y) e ^ {- 2 pi iy cdot nu} , dy.}

Tyto dva integrály jsou definicemi ${ displaystyle F ( nu)}$ a ${ displaystyle G ( nu)}$ , tak:

{ displaystyle H ( nu) = F ( nu) cdot G ( nu),}

QED.

Věta o konvoluci pro inverzní Fourierovu transformaci

Podobný argument, jako výše uvedený důkaz, lze použít na konvoluční teorém pro inverzní Fourierovu transformaci;

{ displaystyle { mathcal {F}} ^ {- 1} {f * g } = { mathcal {F}} ^ {- 1} {f } cdot { mathcal {F}} ^ {-1} {g }}

{ displaystyle { mathcal {F}} ^ {- 1} {f cdot g } = { mathcal {F}} ^ {- 1} {f } * { mathcal {F}} ^ {-1} {g }}

aby

{ displaystyle f * g = { mathcal {F}} { velký {} { mathcal {F}} ^ {- 1} {f } cdot { mathcal {F}} ^ {- 1 } {g } { velký }}}

{ displaystyle f cdot g = { mathcal {F}} { big {} { mathcal {F}} ^ {- 1} {f } * { mathcal {F}} ^ {- 1 } {g } { velký }}}

Věta o konvoluci pro temperované distribuce

Věta o konvoluci se rozšiřuje na temperované distribuce. Tady, ${ displaystyle g}$ je libovolné temperované rozdělení (např Dirac hřeben )

{ displaystyle { mathcal {F}} {f * g } = { mathcal {F}} {f } cdot { mathcal {F}} {g }}

{ displaystyle { mathcal {F}} { alpha cdot g } = { mathcal {F}} { alpha } * { mathcal {F}} {g }}

ale ${ displaystyle f = F { alpha }}$ musí „rychle klesat“ směrem k ${ displaystyle - infty}$ a ${ displaystyle + infty}$ aby byla zaručena existence konvolučního i multiplikačního produktu. Ekvivalentně, pokud ${ displaystyle alpha = F ^ {- 1} {f }}$ je plynulá „pomalu rostoucí“ běžná funkce, zaručuje existenci produktu množení i konvoluce.^[2]^[3]^[4]

Zejména každá kompaktně podporovaná temperovaná distribuce, například Dirac Delta „rychle klesá“. bandband funkce, jako je funkce, která je neustále ${ displaystyle 1}$ jsou plynulé „pomalu rostoucí“ běžné funkce. Pokud například ${ displaystyle g equiv operatorname {III}}$ je Dirac hřeben obě rovnice dávají Poissonův součtový vzorec a pokud navíc ${ displaystyle f equiv delta}$ je tedy Diracova delta ${ displaystyle alpha equiv 1}$ je neustále jedna a tyto rovnice dávají Dirac hřeben identity.

Funkce diskrétních proměnných sekvencí

Analogické konvoluce věta pro diskrétní sekvence ${ displaystyle x}$ a ${ displaystyle y}$ je:

{ displaystyle scriptstyle { rm {DTFT}} displaystyle {x * y } = scriptstyle { rm {DTFT}} displaystyle {x } cdot scriptstyle { rm {DTFT} } displaystyle {y },}

^[5]^[A]

kde DTFT představuje diskrétní Fourierova transformace.

Existuje také věta pro kruhové a periodické závity:

{ displaystyle x _ {_ {N}} * y triangleq sum _ {m = - infty} ^ { infty} x _ {_ {N}} [m] cdot y [nm] ekviv součet _ {m = 0} ^ {N-1} x _ {_ {N}} [m] cdot y _ {_ {N}} [nm],}

kde ${ displaystyle x _ {_ {N}}}$ a ${ displaystyle y _ {_ {N}}}$ jsou periodické součty sekvencí ${ displaystyle x}$ a ${ displaystyle y}$ :

{ displaystyle x _ {_ {N}} [n] triangleq sum _ {m = - infty} ^ { infty} x [n-mN]}

a

{ displaystyle y _ {_ {N}} [n] triangleq sum _ {m = - infty} ^ { infty} y [n-mN].}

Věta je:

{ displaystyle scriptstyle { rm {DFT}} displaystyle {x _ {_ {N}} * y } = scriptstyle { rm {DFT}} displaystyle {x _ {_ {N}} } cdot scriptstyle { rm {DFT}} displaystyle {y _ {_ {N}} },}

^[6]^[b]

kde DFT představuje N-délku Diskrétní Fourierova transformace.

A proto:

{ displaystyle x _ {_ {N}} * y = scriptstyle { rm {DFT}} ^ {- 1} displaystyle { big [} scriptstyle { rm {DFT}} displaystyle {x_ {_ {N}} } cdot scriptstyle { rm {DFT}} displaystyle {y _ {_ {N}} } { big]}.}

Pro $X$ a $y$ sekvence, jejichž nenulové trvání je menší nebo rovno $N$ , konečné zjednodušení je:

Kruhová konvoluce

${ displaystyle x _ {_ {N}} * y = scriptstyle { rm {DFT}} ^ {- 1} displaystyle left [ scriptstyle { rm {DFT}} displaystyle {x } cdot scriptstyle { rm {DFT}} displaystyle {y } vpravo]}$

Za určitých podmínek subsekvence ${ displaystyle x _ {_ {N}} * y}$ je ekvivalentní lineární (neperiodické) konvoluci ${ displaystyle x}$ a ${ displaystyle y}$ , což je obvykle požadovaný výsledek. (vidět Příklad ) A když jsou transformace efektivně implementovány pomocí Rychlá Fourierova transformace algoritmus je tento výpočet mnohem efektivnější než lineární konvoluce.

Věta o konvoluci pro koeficienty Fourierovy řady

Pro konvoluci existují dvě věty o konvoluci Fourierova řada koeficienty periodické funkce:

První konvoluční věta uvádí, že pokud ${ displaystyle f}$ a ${ displaystyle g}$ jsou v ${ displaystyle L ^ {1} ([- pi, pi])}$ , koeficienty Fourierovy řady 2 $π$ -periodické konvoluce z ${ displaystyle f}$ a ${ displaystyle g}$ jsou dány:

{ displaystyle [{ widehat {f * _ {2 pi} g}}] (n) = 2 pi cdot { widehat {f}} (n) cdot { widehat {g}} (n ),}

^[A]

kde:

{ displaystyle { begin {zarovnané} left [f * _ {2 pi} g right] (x) & triangleq int _ {- pi} ^ { pi} f (u) cdot g [{ text {pv}} (xu)] , du, && { big (} { text {and}} underbrace {{ text {pv}} (x) triangleq arg vlevo (e ^ {ix} right)} _ { text {hlavní hodnota}} { big)} & = int _ {- pi} ^ { pi} f (u) cdot g (xu ) , du, && scriptstyle { text {when}} g (x) { text {je 2}} pi { text {-periodický.}} & = int _ {2 pi} f (u) cdot g (xu) , du, && scriptstyle { text {když jsou obě funkce 2}} pi { text {-periodické a integrál je nad jakoukoli 2}} pi { text {interval.}} end {zarovnáno}}}

Druhá teorém o konvoluci uvádí, že koeficienty Fourierovy řady produktu z ${ displaystyle f}$ a ${ displaystyle g}$ jsou dány diskrétní konvoluce z ${ displaystyle { hat {f}}}$ a ${ displaystyle { hat {g}}}$ sekvence:

{ displaystyle left [{ widehat {f cdot g}} right] (n) = left [{ widehat {f}} * { widehat {g}} right] (n).}

Viz také

Funkce generující momenty a náhodná proměnná

Poznámky

^ Faktor měřítka se vždy rovná období, 2 $π$ v tomto případě.

Citace stránky

^ Oppenheim a Schafer, str. 60 (2,169).
^ Oppenheim a Schafer, str. 548.

Reference

^ McGillem, Clare D .; Cooper, George R. (1984). Kontinuální a diskrétní analýza signálu a systému (2. vyd.). Holt, Rinehart a Winston. p. 118 (3-102). ISBN 0-03-061703-0.
^ Horváth, John (1966). Topologické vektorové prostory a distribuce. Reading, MA: Addison-Wesley Publishing Company.
^ Barros-Neto, José (1973). Úvod do teorie distribuce. New York, NY: Dekker.
^ Petersen, Bent E. (1983). Úvod do Fourierovy transformace a pseudo-diferenciálních operátorů. Boston, MA: Pitman Publishing.
^ Proakis, John G .; Manolakis, Dimitri G. (1996), Digitální zpracování signálu: Principy, algoritmy a aplikace (3. vyd.), New Jersey: Prentice-Hall International, s. 1. 297, Bibcode:1996dspp.book ..... P, ISBN 9780133942897, sAcfAQAAIAAJ
^ Rabiner, Lawrence R.; Gold, Bernard (1975). Teorie a aplikace číslicového zpracování signálu. Englewood Cliffs, NJ: Prentice-Hall, Inc. str. 59 (2,163). ISBN 978-0139141010.

Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John R. (1999). Diskrétní zpracování signálu (2. vyd.). Upper Saddle River, N.J .: Prentice Hall. ISBN 0-13-754920-2. K dispozici také na https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf

Další čtení

Katznelson, Yitzhak (1976), Úvod do harmonické analýzyDover, ISBN 0-486-63331-4
Li, Bing; Babu, G. Jogesh (2019), „Konvoluční věta a asymptotická účinnost“, Postgraduální kurz statistické inference, New York: Springer, s. 295–327, ISBN 978-1-4939-9759-6
Weisstein, Eric W. .html "Konvoluční věta" Šek | url = hodnota (Pomoc). MathWorld.
Crutchfield, Steve (9. října 2010), „Radost z konvoluce“, Univerzita Johna Hopkinse, vyvoláno 19. listopadu 2010

Dodatečné zdroje

Pro vizuální znázornění použití konvoluční věty v zpracování signálu viz:

Univerzita Johna Hopkinse je Jáva - podporovaná simulace: http://www.jhu.edu/signals/convolve/index.html

[9] Faktor měřítka se vždy rovná období, 2 $π$ v tomto případě.

[6] Oppenheim a Schafer, str. 60 (2,169).

[8] Oppenheim a Schafer, str. 548.

[McGillem-1] McGillem, Clare D .; Cooper, George R. (1984). Kontinuální a diskrétní analýza signálu a systému (2. vyd.). Holt, Rinehart a Winston. p. 118 (3-102). ISBN 0-03-061703-0.

[2] Horváth, John (1966). Topologické vektorové prostory a distribuce. Reading, MA: Addison-Wesley Publishing Company.

[3] Barros-Neto, José (1973). Úvod do teorie distribuce. New York, NY: Dekker.

[4] Petersen, Bent E. (1983). Úvod do Fourierovy transformace a pseudo-diferenciálních operátorů. Boston, MA: Pitman Publishing.

[Proakis-5] Proakis, John G .; Manolakis, Dimitri G. (1996), Digitální zpracování signálu: Principy, algoritmy a aplikace (3. vyd.), New Jersey: Prentice-Hall International, s. 1. 297, Bibcode:1996dspp.book ..... P, ISBN 9780133942897, sAcfAQAAIAAJ

[Rabiner-7] Rabiner, Lawrence R.; Gold, Bernard (1975). Teorie a aplikace číslicového zpracování signálu. Englewood Cliffs, NJ: Prentice-Hall, Inc. str. 59 (2,163). ISBN 978-0139141010.

[1]

[2]

[3]

[4]

[5]

[A]

[6]

[b]

[A]