Techniklexikon

schnelle Fourier-Transformation

Mathematische Methoden und Computereinsatz, Fast Fourier Transformation, FFT, eine besonders schnelle Variante der diskreten Fourier-Transformation

mit , die angewendet werden kann, wenn die Funktionswerte  einer Funktion , die approximativ durch ein trigonometrisches Polynom dargestellt werden soll, für eine Menge von äquidistanten Argumenten  im Intervall  mit  bekannt sind. Der Rechenaufwand der schnellen Fourier-Transformation wächst mit , im Gegensatz zur üblichen Fourier-Transformation, bei der der Aufwand mit  wächst. Die Grundidee beruht auf dem Danielson-Lanczos-Lemma, eine diskrete Fourier-Transformation der Länge  als Summe zweier diskreter Fourier-Transformationen der Länge  zu bilden, wobei die eine aus den geraden Zahlen, die andere aus den ungeraden der ursprünglichen Reihe besteht und auf die Form  führt;  () repräsentiert den -ten Koeffizienten der Fourier-Reihe mit Länge , die aus den geraden (ungeraden) Komponenten der ursprünglich  Koeffizienten  gebildet wird. Diese Teilung in gerade und ungerade Komponenten kann rekursiv fortgesetzt werden, wenn . Die Buchhaltung und Zuordnung der Komponenten im rekursiven Schema bezüglich der ursprünglichen Reihe führt auf ein Sortierproblem; daraus resultiert der mit  skalierende Rechenaufwand. Spezielle Varianten der schnellen Fourier-Transformationen existieren auch für kleine primzahlige  (Winograd-Transformation).