Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

MedieninformatikMedieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik

 

 

Transformationen

Schnelle Fourier­trans­formation (FFT)

 aufwärts

Die Fourier­trans­formation ist ein fundamentales Verfahren in der Signal­verarbeitung. Durch die Fourier­trans­formation lassen sich Signale von der Darstellung {(Zeitpunkt, Abtastwert)} in die Darstellung {(Frequenzanteil, Amplitude, Phase)} überführen. Viele Operationen, z.B. Filter, lassen sich im Frequenzraum leichter durchführen. Anschließend wird das Signal mit der inversen Fourier­trans­formation wieder zurück transformiert. [Beispiel]

Außerdem hat die Fourier­trans­formation Anwendungen in der Numerik; z.B. lässt sich eine Polynom­multiplikation schneller durchführen, wenn die Polynome in Stützstellen­darstellung statt in Koeffizienten­darstellung vorliegen.

Das Verfahren der schnellen Fourier­trans­formation (engl.: Fast Fourier TransformFFT) hat eine Zeit­komplexität von O(n log(n)). Dadurch ist die Polynom­multiplikation sogar einschließlich Transformation in Stützstellen­darstellung und Rücktrans­formation noch schneller als die direkte Multiplikation in Koeffizienten­darstellung.

 

Grundlagen

Definition:  Sei komplexe Zahlen der Körper der komplexen Zahlen. Ein Element w Element komplexe Zahlen heißt n-te Einheits­wurzel, wenn wn = 1 ist, und w heißt primitive n-te Einheits­wurzel, wenn wn = 1 ist, aber wkungleich1 für alle k Element {1, ..., n-1}.

Beispiel:  Sei n = 4. Dann ist i primitive 4-te Einheits­wurzel1). Alle 4-ten Einheits­wurzeln sind:

i0 = 1,     i1 = i,     i2 = -1,     i3 = -i.

Für n = 6 ist  cos(2π/6) + i sin(2π/6)  primitive 6-te Einheits­wurzel (Bild 1).

Allgemein gilt in komplexe Zahlen:

w  =  cos(k·2π/n) + i sin(k·2π/n)     mit   k Element {0, ..., n-1}

ist n-te Einheits­wurzel; ist k teilerfremd zu n, so ist w primitiv.

In der eulerschen Schreibweise lässt sich eine n-te Einheits­wurzeln w auch ausdrücken als

w  =  eik2π/n     mit   k Element {0, ..., n-1}.

Einheitskreis in der gaußschen Zahlenebene mit 4-ten und 6-ten Einheitswurzeln
Bild 1:  Einheitskreis in der gaußschen Zahlenebene mit 4-ten und 6-ten Einheits­wurzeln
Eigenschaften von n-ten Einheits­wurzeln
  1. Es gibt in komplexe Zahlen genau n verschiedene n-te Einheits­wurzeln, diese sind darstellbar als die Potenzen einer primitiven n-ten Einheits­wurzel w:

    w0, w1, w2, ..., wn-1.

     

  2. Jede ganzzahlige Potenz wk einer n-ten Einheits­wurzel w ist wieder n-te Einheits­wurzel, denn

    (wk)n  =  wk·n   =  (wn)k  =  1k  =  1.

    Dies gilt auch für negative k.

     

  3. Ist n gerade, so gilt für jede primitive n-te Einheits­wurzel w:

    wn/2  =  -1,

    denn (wn/2)2 = wn = 1, d.h. wn/2 ist 2-te Einheits­wurzel, also 1 oder -1. Da aber  wn/2ungleich1 ist, da w primitiv ist, gilt wn/2 = -1.

     

  4. Das Quadrat w2 einer primitiven n-ten Einheits­wurzel (n gerade) ist primitive n/2-te Einheits­wurzel, denn
    1. (w2)n/2  =  wn  =  1.
    2. Angenommen, w2 sei nicht primitiv, dann existiert ein k Element {1, ..., n/2-1}  mit  (w2)k = 1. Dann ist aber w2k = 1 mit 2k < n, im Widerspruch dazu, dass w primitiv ist.

     

  5. Ist w primitive n-te Einheits­wurzel, so ist w-1 ebenfalls primitive n-te Einheits­wurzel, denn
    1. (w-1)n  =  w-n  =  1/wn  =  1/1  =  1.
    2. Angenommen, w-1 sei nicht primitiv, dann existiert ein k Element {1, ..., n-1} mit (w-1)k = w-k = 1. Dann ist aber wk = 1/w-k = 1/1 = 1, im Widerspruch dazu, dass w primitiv ist.

     

  6. In komplexe Zahlen gilt für die zu einer n-ten Einheits­wurzel w konjugierte Zahl w

    w  =  w-1

    denn es ist

    w · w = (cos(k·2π/n) + i sin(k·2π/n)) · (cos(k·2π/n) – i sin(k·2π/n))
     = cos(k·2π/n)2 + sin(k·2π/n)2
     = 1.

 

Diskrete Fourier­trans­formation

Definition:  Sei n Element natürliche Zahlen und w primitive n-te Einheits­wurzel in komplexe Zahlen. Eine nkreuzn-Matrix F mit

Fi,j  =  wi·j

für alle i, j Element {0, ..., n-1} heißt Fourier­matrix.2)

Die lineare Abbildung  f : komplexe Zahlenn Pfeil komplexe Zahlenn  mit

f(a)  =  a·F

für alle (Zeilen-)vektoren a Element komplexe Zahlenn heißt diskrete Fourier­trans­formation (DFT).3)

Beispiel:  Sei n = 4. Dann ist i primitive n-te Einheits­wurzel. Die zugehörige Fourier­matrix ist

F  =   eckige Klammer auf
1111
1i-1-i
1-11-1
1-i-1i
eckige Klammer zu

So ist etwa die -1 in der letzten Zeile der Matrix das Element

F3,2 = w3·2 = w6 = (-1)3 = -1

(die Elemente der Matrix werden von 0 bis n-1 indiziert).

Die Fourier­trans­formation des Vektors a = [1 1 1 0] ergibt

y = a·F =  [3 i 1 -i]

Offenbar ist die Fourier­matrix F die Vandermonde-Matrix des Vektors w0, ..., wn-1. Die Matrix-Vektor-Multiplikation y = a·F lässt sich somit als Polynom­auswertung an den Stellen w0, ..., wn-1 auffassen, wobei der Vektor a die Koeffizienten des Polynoms enthält. Das Ergebnis y0, ..., yn-1 ist die Stützstellen­darstellung des Polynoms.

Satz:  Die inverse Fourier­matrix F -1 existiert und ist gleich

F -1i,j  =  1/n · w-i·j

für alle i, j Element {0, ..., n-1}. Die inverse Fourier­matrix enthält also die zu den Elementen der Fourier­matrix inversen Elemente, dividiert durch n.

Definition:  Die lineare Abbildung  f -1 : komplexe Zahlenn Pfeil komplexe Zahlenn  mit

f -1(a)  =  a·F -1

für alle a Element komplexe Zahlenn heißt inverse Fourier­trans­formation.

Beispiel:  Sei n = 4. Die inverse Fourier­matrix ist

F -1  =  1/4 · eckige Klammer auf
1111
1-i-1i
1-11-1
1i-1-i
eckige Klammer zu

Die inverse Fourier­trans­formation des Vektors y = [3 i 1 -i] ergibt

a  =  y·F -1  =  [1 1 1 0].

In dieser Form ist die Fourier­trans­formation eine Matrix-Vektor-Multiplikation mit der Komplexität O(n2). Durch Ausnutzung der Symmetrie der n-ten Einheits­wurzeln lässt sich die Berechnung auf O(n log(n)) beschleunigen. Dieses Verfahren heißt schnelle Fourier­trans­formation (Fast Fourier TransformFFT) [CT 65].

 

Schnelle Fourier­trans­formation (FFT)

Die Idee des Verfahrens der schnellen Fourier­trans­formation ist, die einzelnen Berechnungen der Matrix-Vektor-Multiplikation y = a·F in einer speziellen Reihenfolge auszuführen, so dass jeweils auf schon berechnete Zwischen­ergebnisse zurück­gegriffen werden kann. Dabei werden die o.a. Eigenschaften (3) und (4) ausgenutzt, nämlich dass wn/2 = -1 ist und dass das Quadrat w2 der primitiven n-ten Einheits­wurzel w primitive n/2-te Einheits­wurzel ist. Das Verfahren setzt voraus, dass n eine Zweierpotenz ist.

 

Gegeben ist ein Vektor a = [a0 ... an-1]. Berechnet werden soll y = a·F, d.h. gesucht ist der Vektor

y  =  [y0 ... yn-1]

Der Vektor y wird nun durch zwei ineinander verschränkte Vektoren y' und y'' halber Länge dargestellt:

y  =  [y'0 y''0  ...  y'n/2-1 y''n/2-1].

D.h. die Komponenten von y an geraden Indexpositionen bilden den Vektor y' und diejenigen an ungeraden Indexpositionen den Vektor y''.

 

Die Vektoren y' und y'' werden getrennt voneinander berechnet. Zunächst werden die Komponenten von y' berechnet, indem die entsprechenden Komponenten des Vektors a mit den entsprechenden Spalten der Fourier­matrix multipliziert werden.

Im Folgenden sei m = n/2.

Zunächst werden die Komponenten von y mit geradem Index berechnet. Es gilt für alle k Element {0, ..., m-1}:

yk'   =   y2k   =    Summe i = 0, ..., n-1     ai wi·2k.

Die Summe wird in zwei Hälften zerlegt:

yk'   =    Summe i = 0, ..., m-1   ai wi·2k   +    Summe i = 0, ..., m-1   ai+m w(i+m)·2k.

Nun ist aber

w(i+m)·2k   =   wi·2k + m·2k   =   wi·2k·wm·2k   =   wi·2k·wnk   =   wi·2k,

da wnk = 1 ist, und damit

yk'   =    Summe i = 0, ..., m-1     (ai + ai+m) wi·2k.

Mit v = w2, v primitive m-te Einheits­wurzel, gilt:

yk'   =    Summe i = 0, ..., m-1     (ai + ai+m) vi·k,

d.h. yk' ist nichts anderes als die k-te Komponente der Fourier­trans­formation des Vektors

[ai + ai+m] i = 0, ..., m-1

der Länge m.

 

 

Ähnlich werden die Komponenten von y mit ungeradem Index berechnet. Es gilt für alle k Element {0, ..., m-1} :

yk''   =   y2k+1   =    Summe i = 0, ..., n-1     ai wi·(2k+1).

Wiederum wird die Summe in zwei Hälften zerlegt:

yk''   =    Summe i = 0, ..., m-1   ai wi·(2k+1)   +    Summe i = 0, ..., n/2-1   ai+m w(i+m)·(2k+1).

Nun ist aber

w(i+m)·(2k+1)   =   wi·2k + m·2k + i + m   =   wi·2k · wnk · wi · wn/2   =   – wi·wi·2k,

da wnk = 1 und wn/2 = -1 ist.

Somit gilt:

yk''   =    Summe i = 0, ..., m-1   ai wi·wi·2k   +    Summe i = 0, ..., m-1   – ai+m wi·wi·2k

  =   Summe i = 0, ..., m-1     wi·(ai – ai+m) wi·2k.

Mit m = n/2 sowie v = w2 gilt wiederum:

yk''   =    Summe i = 0, ..., m-1     wi·(ai – ai+m) vi·k,

d.h. yk'' ist nichts anderes als die k-te Komponente der Fourier­trans­formation des Vektors

wi·[ai – ai+m] i = 0, ..., m-1.

 

Durch rekursive Anwendung dieses Verfahrens auf Vektoren jeweils halber Länge wird im Ergebnis die Fourier­trans­formation berechnet. Bild 2 zeigt schematisch den Ablauf der Berechnung für n = 8.

Datenfluss der schnellen Fouriertransformation
Bild 2:  Datenfluss der schnellen Fourier­trans­formation

 

Analyse

Um die Fourier­trans­formation eines Vektors a zu berechnen, ist zunächst ein Vektor a' zu berechnen, dessen Komponenten ai' für i = 0, ..., m-1 wie oben gesehen folgende Werte haben:

ai'  =  ai + ai+m     sowie

ai+m'  =  wi·(ai – ai+m).

Hierfür sind m Additionen, m Subtraktionen und m Multiplikationen erforderlich sowie nochmals m Multiplikationen, um jeweils wi aus wi-1 zu berechnen. Insgesamt ergibt dies also 2m = n Additionen und 2m = n Multiplikationen.

Anschließend ist rekursiv auf die beiden Hälften von a' die Fourier­trans­formation anzuwenden.

Die Ergebnis­vektoren y' und y'' stellen die geraden und die ungeraden Komponenten von y dar; sie sind noch ineinander zu verschränken (perfect shuffle), um den gewünschten Vektor y zu erhalten. Die Permutation perfect shuffle lässt sich, etwa mit der unten angegebenen Prozedur, in 3/2 n Schritten durchführen.

Die Zeit­komplexität T(n) der FFT ergibt sich somit als

T(n) = 3.5n + 2·T(n/2)  sowie

T(1) = 0.

Die Auf­lösung dieser Rekursion ergibt

T(n) = 3.5n·log(n),   d.h.

T(nElement O(n log(n)).

 

Programm

Die folgende Prozedur berechnet die Fourier­trans­formation eines komplexen Vektors a, beginnend beim Index lo und der Länge n. Der Parameter w steht für die primitive n-te Einheits­wurzel. Rechen­operationen mit komplexen Zahlen sind der Über­sichtlich­keit halber mit normalen Rechenzeichen (+, -, *) dargestellt, obwohl diese in Java eigentlich nicht zur Verfügung stehen.

void fft(Complex[] a, int n, int lo, Complex w)
{
    int i, m;
    Complex z, v, h;

    if (n>1)
    {
        m=n/2;
        z=1;
        for (i=lo; i<lo+m; i++)
        {
            h=a[i]-a[i+m];
            a[i]=a[i]+a[i+m];
            a[i+m]=h*z;
            z=z*w;
        }
        v=w*w;
        fft(a, m, lo, v);
        fft(a, m, lo+m, v);
        shuffle (a, n, lo);
    }
}

 

Die Prozedur shuffle verschränkt die beiden, von den rekursiven Aufrufen von fft erzeugten Hälften reiß­verschluss­artig ineinander. Die entsprechende Permutation für n = 8 lautet

0 1 2 3 4 5 6 7
0 4 1 5 2 6 3 7

Zur Ausführung der Permutation wird ein Hilfsarray b verwendet, in das zunächst die eine Hälfte der Folge ausgelagert wird.

void shuffle(Complex[] a, int n, int lo)
{
    int i, m=n/2;
    Complex[] b=new Complex[m];

    for (i=0; i<m; i++)
        b[i]=a[lo+i];
    for (i=0; i<m; i++)
        a[lo+i+i+1]=a[lo+i+m];
    for (i=0; i<m; i++)
        a[lo+i+i]=b[i];
}

 

Inverse Fourier­trans­formation

Die inverse Fourier­trans­formation lässt sich mit demselben Verfahren durchführen. Aufgrund der Definition der inversen Fourier­matrix F -1 wird jedoch statt mit der primitiven n-ten Einheits­wurzel w mit der inversen n-ten Einheits­wurzel w-1 gearbeitet. In komplexe Zahlen ist dies die konjugiert komplexe n-te Einheits­wurzel w (vgl. o.a. Eigenschaften (5) und (6)). Ferner werden die Elemente der invers zu trans­formierenden Folge zunächst durch n geteilt.

 

Zusammenfassung

Die diskrete Fourier­trans­formation lässt sich interpretieren als Transformation eines Polynoms vom Grad n-1 von der Koeffizienten­darstellung in die Stützstellen­darstellung. Als Stützstellen werden die n-ten Einheits­wurzeln w0, w1, ..., wn-1 verwendet. Im Körper komplexe Zahlen der komplexen Zahlen sind die Werte

wk  =  cos(k·2π/n) + i sin(k·2π/n)  =  eik2π/n     mit   k Element {0, ..., n-1}

die n-ten Einheits­wurzeln.

Durch Ausnutzung der Symmetrien der n-ten Einheits­wurzeln lässt sich die Fourier­trans­formation beschleunigen; das Verfahren ist die schnelle Fourier­trans­formation FFT.

Mit Hilfe der FFT lässt sich die Zeit­komplexität der Polynom­multiplikation von Θ(n2) auf Θ(n log(n)) verbessern.

 

Literatur

[AHU 74]A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)
[CT 65]J.M. Cooley, J.W. Tukey: An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Comp. 19, 297-301 (1965)
[Sed 88]R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)
[Lan 06]H.W. Lang: Algorithmen in Java. 2. Auflage, Oldenbourg (2006)

Den FFT-Algorithmus finden Sie auch in meinem Buch über Algorithmen.
Weiterevertikaler Abstand Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphen­algorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortier­algorithmen.
[Weitere Informationen]   [Bestellen]

Buch  

 


1)  Die Zahl i ist die imaginäre Einheit i = Wurzel-1

2)  Da es für n>2 stets mehrere primitive n-te Einheits­wurzeln gibt, ist die Fourier­matrix insofern nicht eindeutig festgelegt.

3)  Da die Fourier­matrix symmetrisch ist, lässt sich die Fourier­trans­formation auch als f(a) = F·a für Spalten­vektoren a definieren.

 

Weiter mit:  [Diskrete Kosinus-Transformation]  oder up

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 05.03.1997   Updated: 20.04.2011
Valid HTML 4.01 Transitional