Faltung auf FFT zurückführen

Wissenschaft Physik
1

Hallo,

ich möchte in einem Programm effizient die Faltung von zwei Sequenzen reeller Zahlen berechnen. Dazu will ich sie auf die Fouriertransformation zurückführen, die mit der Laufzeit n*log(n) schneller ist, als wenn ich das ganze einfach Elementweise berechne.
Ich habe also conv(a, b) = F(prod(f(a), f(b)), wenn F die Fourier-Rücktransformation, f die Fouriertransformation und prod das elementweise Produkt ist.

Aber was mache ich, wenn a und b unterschiedlich viele Elemente haben? Dann klappt ja das Elementweise Produkt nicht. Wie mache ich das dann am besten?

Grüße,
Moritz

2

Mit Nullen auffüllen!
Hallo Moritz,
füll (vor der FFT) einfach mit Nullen auf. Der „Faltungskern“ ist ja i.d.R. die Auflösungsfunktion eines Messgeräts, eine Punktbildfunktion bei opt. Abbildungen oder eine Wahscheinlichkeitsdichte. DIe haben sowieso die Eigenschaft, dass sie für x gegen ± unendl. verschwinden.

Siehe auch Wikipedia: http://de.wikipedia.org/wiki/Faltung_%28Mathematik%29

„Im Fall eines beschränkten Definitionsbereichs werden f und g meist durch Null fortgesetzt.“

Gruß Kurt