zum Directory-modus

Schnelle Fouriertransformation

Schnelle diskrete Fouriertransformation

Bei der Berechnung der diskreten Fouriertransformation

F ( ω n ) = 1 N m = 0 N -1 f ( t m ) e i ω n t m , n = 0 , 1 , , N -1

sind für jedes n genau 2 N Multiplikationen benötigt:

f ( t m ) cos ( ω n t m ) , m = 0 , 1 , , N -1 N Multiplikationen f ( t m ) sin ( ω n t m ) , m = 0 , 1 , , N -1 N Multiplikationen

Für alle n sind also N 2 N = 2 N 2 Multiplikationen benötigt. Man sagt, die Berechnung der Koeffizienten hat auf diese Weise eine Zeitkomplexität von O ( N 2 ) . Eigentlich hat das Verfahren der schnellen Fouriertransformation aber eine Zeitkomplexität von O ( N log 2 ( N ) ) , was wir im Folgenden demonstrieren wollen.

Führen wir die komplexe Zahl

w = e i 2 π N

ein, dann ist

e i ω n t m = e i 2 π n T m T N = e i 2 π n m N = w n m

und

F ( ω n ) = 1 N m = 0 N -1 f ( t m ) w n m , n = 0 , 1 , , N -1 .

Die diskrete Fouriertransformation lässt sich als die Summe zweier diskreter Fouriertransformationen schreiben:

F ( ω n ) = 1 N m = 0 N -1 f ( t m ) e i 2 π n m N = 1 N m = 0 N / 2 -1 f ( t 2 m ) e i 2 π n ( 2 m ) N + 1 N m = 0 N / 2 -1 f ( t 2 m +1 ) e i 2 π n ( 2 m +1 ) N = 1 2 1 N / 2 m = 0 N / 2 -1 f ( t 2 m ) e i 2 π n m N / 2 + 1 2 w n 1 N / 2 m = 0 N / 2 -1 f ( t 2 m +1 ) e i 2 π n m N / 2 = 1 2 F ( e ) ( ω n ) + 1 2 w n F ( o ) ( ω n )

wobei F ( e ) ( ω n ) bzw. F ( o ) ( ω n ) die n -te Komponente der diskreten Fouriertransformation der geraden (even) bzw. ungeraden (odd) Komponenten der originalen f ( t m ) 's bezeichnen, die jeweils der Länge N / 2 sind. Eine wichtige Eigenschaft von (auch als das Danielson-Lanczos-Lemma bekannt) ist, dass es sich rekursiv anwenden lässt. F ( e ) ( ω n ) lässt sich laut als die Summe zweier diskreter Fouriertransformationen halber Länge ( N / 4 ) schreiben, und das Gleiche gilt für F ( o ) ( ω n ) :

F ( e ) ( ω n ) = 1 2 F ( ee ) ( ω n ) + 1 2 w n F ( eo ) ( ω n ) F ( o ) ( ω n ) = 1 2 F ( oe ) ( ω n ) + 1 2 w n F ( oo ) ( ω n )

Z.B. für N = 8 berechnet man

F ( e ) ( ω n ) mit den Punkten 0 , 2 , 4 , 6 F ( ee ) ( ω n ) mit den Punkten 0 , 4 F ( eo ) ( ω n ) mit den Punkten 2 , 6 F ( eee ) ( ω n ) mit dem Punkt 0 F ( eeo ) ( ω n ) mit dem Punkt 4 F ( eoe ) ( ω n ) mit dem Punkt 2 F ( eoo ) ( ω n ) mit dem Punkt 6 F ( o ) ( ω n ) mit den Punkten 1 , 3 , 5 , 7 F ( oe ) ( ω n ) mit den Punkten 1 , 5 F ( oo ) ( ω n ) mit den Punkten 3 , 7 F ( oee ) ( ω n ) mit dem Punkt 1 F ( oeo ) ( ω n ) mit dem Punkt 5 F ( ooe ) ( ω n ) mit dem Punkt 3 F ( ooo ) ( ω n ) mit dem Punkt 7

Man unterteilt die Daten bis auf diskrete Fouriertransformationen der Länge 1, die lediglich Identitätsoperationen sind z.B.

F ( oeo ) ( ω n ) = f ( t 5 ) .

Wie weiß man, zu welchen t m eine gegebene Folge von e' s und o' s zugeordnet ist? Man invertiert die Folge und schließlich tauscht e gegen 0 und o gegen 1 aus. Die resultierende Folge ist nun die Binärdarstellung des gesuchten Werts von m , z.B.

ooe eoo 011 m = 3 .

Das Verfahren der schnellen Fouriertransformation lautet wie folgt. Man sortiert die f ( t m ) ' s nicht nach m , sondern nach der umgekehrten Binärdarstellung von m :

Tab.1
Sortierung der f ( t m ) ' s ( N = 8 )
m 0 1 2 3 4 5 6 7
Binärdarstellung 000 001 010 011 100 101 110 111
umgekehrt 000 100 010 110 001 101 011 111
m neu sortiert 0 4 2 6 1 5 3 7

Man kombiniert benachbarte Paare z.B. 0 und 4 oder 2 und 6, um Transformationen der Länge 2 zu erhalten. Dann kombiniert man die resultierenden Transformationen, um Transformationen der Länge 4 zu erhalten, usw. bis auf die Kombination der zweiten Hälfte der gesamten Daten. Das Verfahren funktioniert am Besten, wenn N eine ganzzahlige Potenz von 2 ist, d.h. N = 2 M . Man berechnet F ( ω n ) mit einer Zeitkomplexität von O ( log 2 ( N ) ) und folglich die N F ( ω n ) ' s mit einer Zeitkomplexität von O ( N log 2 ( N ) ) .

Seite 3 von 3>