Fast Fourier Transformation
Dimitri Litke
2
1. Einleitung2. Grundlagen
2.1 Komplexe Zahlen2.2 Einheitswurzel
3. Fourier Transformation3.1 Diskrete Fourier Transformation3.2 Inverse Fourier Transformation
4. Schnelle Fourier Transformation4.1 FFT4.2 Parallele Implementierung
5. Fazit
Gliederung
3
• Anwendungsgebiete– Signalverarbeitung– Bildverarbeitung– Grundlegende mathematische Berechnungen,
wie z.B. Polynommultiplikation
1. Einleitung
4
1. Einleitung
Koeffizienten -darstellung
Koeffizienten -darstellung
Stützstellen -darstellung
Stützstellen -darstellung
Transformation Transformation
direkte Multiplikation
Multiplikation
Polynommultiplikation
5
1. Einleitung2. Grundlagen
2.1 Komplexe Zahlen2.2 Einheitswurzel
3. Fourier Transformation3.1 Diskrete Fourier Transformation3.2 Inverse Fourier Transformation
4. Schnelle Fourier Transformation4.1 FFT4.2 Parallele Implementierung
5. Fazit
Gliederung
6
Im Bereich der reellen Zahlen gibt es keine Lösung für x²=-1
=> Erweiterung des Zahlenbereiches um die imaginären Zahlen
Die wichtigste von diesen ist i: die Lösung der Gleichung x²=-1
Die reellen und die imaginären Zahlen vereinigt nennt man komplexe Zahlen
Eine Komplexe Zahl z: z = a + i*b , wobei a und b reell sind
2.1 Komplexe Zahlen
7
Darstellung von z = a + i*b im Koordinatensystem
2.1 Komplexe Zahlen
Imaginäre Achse
Reelle Achse
Imaginärteil i*b
Reallteil az
r
Andere Darstellungsform: ))sin()(cos( irerz i
8
• Sei C der Körper der komplexen Zahlen. Ein Element ω C heißt n-te Einheitswurzel, wenn
• Für jedes n gibt genau n solche Einheitswurzeln ,
die die Bedingung erfüllen.
• Haupteinheitswurzel:
• Alle anderen:
2.2 Einheitswurzel
9
Imaginäre Achse
Reelle Achse
Einheitskreis:
2.2 Einheitswurzel
i
1
)0,1(0
),0(1 i
)0,1(2
),0(3 i
10
Einheitskreis:
2.2 Einheitswurzel
Imaginäre Achse
Reelle Achse
i
1
)0,1(0
11
1. Einleitung2. Grundlagen
2.1 Komplexe Zahlen2.2 Einheitswurzel
3. Fourier Transformation3.1 Diskrete Fourier Transformation3.2 Inverse Fourier Transformation
4. Schnelle Fourier Transformation4.1 FFT4.2 Parallele Implementierung
5. Fazit
Gliederung
12
Sei n N und primitive n-te Einheitswurzel in C
Die Fouriermatrix:
für alle i, j {0,…,n-1}
Für n=4:
3.1 Diskrete Fourier Transformation
ii
iiF
111111
111111
4
jijiF ,
1)1( 36323,2 F
13
Die DFT eines Vektors x = (x0,…xn-1):
d.h. die j-te Komponente des Ergebnisvektors f(x):
Für n=4:
3.1 Diskrete Fourier Transformation
xFxf n)(
1
0)(
n
kk
jkj xxf
32100 )( xxxxxf
32101 )( ixxixxxf
32102 )( xxxxxf
32103 )( ixxixxxf
14
Beispiel:Multiplikation von zwei Polynomen: und
Hier und
Eingabevektor von p(x): von q(x):
3.1 Diskrete Fourier Transformation
1
0
)(n
i
ii xaxp
1
0
)(n
i
ii xbxq
1542)( 23 xxxxp 232)( 23 xxxxq
00002451
00001232
15
Die DFT des Eingabevektors von p(x):
3.1 Diskrete Fourier Transformation
ii
i
iii
95.012.13395.812.3
1295.812.3
3395.012.1
2
00002451
111
11111
111
111111111
1234567
246246
3614725
4444
5274163
642642
7654321
16
Multiplikation von transformierten Vektoren
3.1 Diskrete Fourier Transformation
iii
iii
ii
i
ii
i
ii
i
iii
66.876.06666.225.9
066.225.96666.876.0
16
83.441.03283.059.0
083.059.0
283.441.3
8
95.012.13395.812.3
1295.812.3
3395.012.1
2
17
Einträge der inversen Fouriermatrix:
für alle i, j {0, …, n-1}.
z.B. für n=4:
3.2 Inverse Fourier Transformation
nF jiji /1,
ii
iiF
ii
ii
111111
111111
4
1
441
441
41
41
41
41
441
441
41
41
41
41
14
18
Beispiel (fortgesetzt):
3.2 Inverse Fourier Transformation
02031572
66.876.06666.225.9
066.225.96666.876.0
16
111
11111
111
111111111
8
1
1234567
246246
3614725
4444
5274163
642642
7654321
iii
iii
19
Dieser Vektor beinhaltet nun die Koeffizienten des
Ergebnispolynoms:
27532)()( 2346 xxxxxxqxp
02031572
3.2 Inverse Fourier Transformation
20
Koeffizienten -darstellung
Koeffizienten -darstellung
Stützstellen -darstellung
Stützstellen -darstellung
Transformation
)(n2
direkte Multiplikation
)(n 2
)(n
Multiplikation
Komplexität
Transformation
)(n2
21
1. Einleitung2. Grundlagen
2.1 Komplexe Zahlen2.2 Einheitswurzel
3. Fourier Transformation3.1 Diskrete Fourier Transformation3.2 Inverse Fourier Transformation
4. Schnelle Fourier Transformation4.1 FFT4.2 Parallele Implementierung
5. Fazit
Gliederung
22
Die Idee:
Die Matrix-Vektor-Multiplikation soll so ausgeführt werden, dass auf die schon vorhandenen Zwischenergebnisse zurückgegriffen werden kann
Hier werden folgende Eigenschaften der primitiven
Einheitswurzeln genutzt
und
4.1 Fast Fourier Transformation
2
2nn
23
Das Ziel ist hier die FT des Vektors a zu berechnen:
Aufteilung des Polynoms in
und
11
44
33
2210 ...)(
nn xaxaxaxaxaaxf
12
36
2420
0 2...)(
n
xaxaxaxaaxf n
1
13
72
5311 2...)(
n
xaxaxaxaaxf n
4.1 Fast Fourier Transformation
24
Die schnelle Fourier Transformation:
Aufteilung der Polynome
und
solange bis nur noch Paare von Polynomen mit jeweilseinem Koeffizienten vorhanden
)()()( 2120 xxfxfxf
)(0 xf )(1 xf
4.1 Fast Fourier Transformation
25
4.1 Fast Fourier Transformation
)( 7a)( 5a )( 3a)( 1a)( 0a )( 4a )( 2a )( 6a
),( 73 aa),( 51 aa),( 62 aa),( 40 aa
),,,( 7531 aaaa),,,( 6420 aaaa
),,,,,,,( 76543210 aaaaaaaa
Rekursive Aufteilung des Inputvektors
26
Aufgabe: Berechnung der FT von einem Vektor mit n Elementen auf einem Rechner mit p
Prozessoren
Drei Phasen
1. Austausch von Inputelementen zwischen den Prozessoren
2. Die ersten log(n)-log(p) Iterationsschritte der FFT (parallele Ausführung)
3. Die letzten log(p) Schritte der FFT (Kommunikation zwischen den Prozessoren erforderlich)
4.2 Parallele Implementierung
27
Folgende zwei Operationen werden wiederholt:
und
Graphische Darstellung als „Butterfly“-Operation:
4.2 Parallele Implementierung
]1[]0[kkk yyy ]1[]0[
2/ kknk yyy
kn
]1[]0[k
knk yy
]1[]0[k
knk yy
]1[ky
]0[ky
28
4.2 Parallele Implementierung
0818
28
38
04
14
04
14
7y
0y
1y
2y
3y
4y
5y
6y
0a
1a
2a
3a
4a
5a
6a
7a
1s 2s 3s
P0
P1
29
4.2 Parallele Implementierung
08
38
04
14
04
14
1s 2s 3s
P0
P1
18
28
-5
-1-4i
3
-1+4i
7
5+2i
3
5-2i
5
5
2
2
-1
-1
-4
-4
5
0
0
0
0
-4
-1-1
-4
5
2
2
0
0
0
0
2
1,12+0,95i
3+3i
-3,12+8,95i
-12
1,12-0,95i
-3,12-8,95i
3-3i
30
Koeffizienten -darstellung
Koeffizienten -darstellung
Stützstellen -darstellung
Stützstellen -darstellung
direkte Multiplikation
)(n 2
)(n
Multiplikation
Komplexität
Transformation
)log( pn
p
nO
Transformation
)log( pn
p
nO
4.2 Parallele Implementierung
31
1. Einleitung2. Grundlagen
2.1 Komplexe Zahlen2.2 Einheitswurzel
3. Fourier Transformation3.1 Diskrete Fourier Transformation3.2 Inverse Fourier Transformation
4. Schnelle Fourier Transformation4.1 FFT4.2 Parallele Implementierung
5. Fazit
Gliederung
32
• Die Anwendungsmöglichkeiten sind weit größer als hier beschrieben wurde. Aber die prinzipielle Vorgehensweise bleibt die gleiche
• Fourier Transformation ist ein sehr wichtiges Werkzeug, das auf vielen Gebieten für die Berechnung verschiedener Operationen auf großen Datensätzen eingesetzt wird
• Deswegen ist es wichtig einen effizienten Algorithmus verwenden zu können. Die FFT kann den Aufwand erheblich reduzieren
• Die FFT eignet sich sehr gut zur Implementierung auf Rechnern mit mehreren Prozessoren
5. Fazit