Fast Fourier Transformation

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


Stützstellen -darstellung


Transformation Transformation

direkte Multiplikation

Multiplikation

Polynommultiplikation

5





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





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:


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):


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):


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


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):


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


20





Transformation

)(n2


)(n 2

)(n

Multiplikation

Komplexität

Transformation

)(n2

21





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


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


25


)( 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:


]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


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


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






)(n 2

)(n

Multiplikation

Komplexität

Transformation

)log( pn

p

nO

Transformation

)log( pn

p

nO


31





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

Documents

Fast Fourier Transformation