WikiDer > Schnelle Fourier-Transformation

FFT-Schmetterlingsberechnung

In dem numerische Mathematik ist ein Schnelle Fourier-Transformation (Schnelle Fourier-Transformation, abgekürzt FFT) ein Algorithmus zur effizienten Berechnung des diskrete Fourier-Transformation (DFT) eines diskreten Signals, dessen Werte in endlicher Zahl bekannt sind ${Displaystil N}$ äquidistante Punkte. Während die direkte Berechnung eine Effizienz von ${Anzeigestil O(N^{2})}$, ist die Effizienz einer FFT ${displaystyle O(Nlog _{2}N)}$. Die damit verbundene Zeitersparnis ist insbesondere bei großen ${Displaystil N}$.

Der Algorithmus wurde entwickelt von James Cooley und John Tukey im Jahr 1965 und beträgt in seiner ursprünglichen Form a Fourier-Transformation mit Länge ${Displaystil N}$ zerfällt in zwei Transformationen mit Länge ${Anzeigestil N/2}$, unter Ausnutzung der Periodizität und Symmetrie im Sinus und Cosinus. Aufgrund dieser Spaltung rekursiv zu beantragen, ergibt sich eine Verbesserung der Bestellung ${displaystyle N/log_{2}N}$. Beispielsweise ${Anzeigestil N=8192}$ ist das schon ein Faktor von 630.

Die Anwendung einer solchen Rekursion erfordert, dass ${Displaystil N}$ ist eine Potenz von 2. Später wurde diese Methode auf eine Zerlegung in beliebige . verallgemeinert Primfaktoren, was zu einer allgemeineren Anwendbarkeit führt. Die Verwendung großer Primfaktoren kann sich jedoch sehr negativ auf die Rechenzeit auswirken. Für die praktische Anwendung wie in Signalanalyse die Beschränkung auf Zweierpotenzen hat kaum Wirkung. Wenn eine 3-dimensionale FFT verwendet wird, wie in der Kristallographie, kann jedoch zu fast 8-mal mehr Speicherverbrauch und 24-mal mehr Rechenzeit als unbedingt erforderlich führen.

Cooley und Tukeys Algorithmuskey

Der Algorithmus von Cooley und Tukey zeigt, wie eine diskrete Fourier-Transformation der Dimension 2n auf 2 Transformationen der Dimension n reduziert werden kann.

spät ${displaystyle (x_{0},ldots ,x_{2n-1})}$ ein diskretes Signal der Dimension 2n sein. Die DFT dieses Signals ist:

${displaystyle X_{m}=Summe _{k=0}^{2n-1}x_{k},e^{-{frac {2pi i}{2n}}mk}=Summe _{k=0}^ {2n-1}x_{k}w_{km}(2n),Quad m=0,ldots,2n-1}$

Benennen Sie die Eingabedaten mit geradem Index:

${displaystyle x'_{r}=x_{2r},quad r=0,ldots,n-1}$

mit DFT ${Anzeigestil X'}$,

und solche mit ungeradem Index

${displaystyle x''_{r}=x_{2r 1},quad r=0,ldots ,n-1}$

mit DFT ${Anzeigestil X''}$.

Dann ist:

${displaystyle { egin{aligned}X_{m}&=summe _{r=0}^{n-1}x_{2r}w_{2r,m}(2n) Summe _{r=0}^{n- 1}x_{2r 1}w_{2r 1,m}(2n)/&=Summe _{r=0}^{n-1}x'_{r}w_{r,m}(n) w_{ 1,m}(n)summe _{r=0}^{n-1}x''_{r}w_{r,m}(n)/&={ egin{cases}X'_{m} w_{1,m}(n)X''_{m}&{ ext{ if }}m$

Beachten Sie auch, dass die Gewichtungsfaktoren ${displaystyle w_{r,m}(n)}$ müssen für beide n-dimensionalen Transformationen nur einmal berechnet werden.

Siehe auch

• Fourier-Analyse