Transformée de Fourier discrète et et transformée de Fourier rapide

Transformée de Fourier discrète

et et transformée de Fourier

rapide

Thomas LAMOTTE

2Transformée de Fourier discrète et transformée de Fourier rapide

La transformée de Fourier discrèteLa transformée de Fourier discrète

Signal analogique– La transformée de Fourier X() d ’un signal

analogique x(t) est donnée par :

t représente le temps et f les fréquences

– C ’est une opération de projection de x(t) sur l ’exponentielle.

Signal discrétisé et périodisé– Considérons une suite finie de N échantillons

d’un signal discrétisé et périodisé.

– On définit sa transformée de Fourier discrète (TFD) comme la suite

dtx(t)efX πft-2

10 Nnnx,

10 NkkX,

N

j2

N

1

0

e Wavec

N

n

nk

Nnk WxX



– De même, on définit la transformée de Fourier inverse (ITFD) par:

Interprétation vectorielle :– Les éléments de la suite peuvent

être vus comme les composantes d ’un vecteur x dans un espace à N dimensions. X est alors une combinaison linéaire de N vecteurs de base wk où les composantes de chaque vecteur wk sont donnés par la suite

– Exemple : Considérons une TFD sur 16 valeurs, on peut

tracer les parties réelles des composantes des cinq premier vecteurs de base wk

1

0

1 N

n

nk

Nkn WXN

x

10 Nnnx,

kN

N

k

N

k

NN WWWW )(,...,,, 120



– La décomposition peut alors être exprimée sous la forme matricielle :

X = WxT où xT désigne la transposée de x


La transformée de Fourier rapideLa transformée de Fourier rapide

Complexité d ’une TFD– Pour la TFD, il y a

N² multiplications complexes N(N-1) additions complexes

– Les multiplications complexes ont une durée d ’exécution beaucoup plus longue que les additions.

Algorithmes de transformée de Fourier rapide (TFR) ou Fast Fourier Transform (FFT)– Dans les algorithme de transformée de Fourier rapide, le nombre d ’opération est

considérablement réduit.– Il en existe plusieurs :

TFR avec entrelacement temporel TFR avec entralacement temporel TFR en base 4 TFR en base double

– Le plus connu est l’algorithme de Cooley-Tukey.

Algorithme de Cooley-Tuckey– Soit {X(k)}, la TFD d ’une suite {x(n)} de longueur N=2M,

– avec A(k) respectivement B(k) la transformée de Fourier de x(2n) respectivement x(2n+1)



Algorithme de Cooley-Tukey– La TFD peut s’écrire en séparant indices pairs et

impairs:

– On aboutit à deux transformées de longueur N/2. Xp correspond à la transformée des indices d’échantillons pairs et Xi à celle des indices impairs.

– Il est possible de subdiviser encore Xp en Xpp et xpi en séparant les indices pairs et impairs et de même pour les indices impairs xi en xip et xii. Il est possible de réitérer plusieurs fois cette méthode.

12

0

12

0

12

12

2

2

/ /

)(N

n

N

n

kn

n

nk

nk WxWxX

e 12212

0

12

012

22

2N

knjN

n

N

nn

N

knj

nk xexX)(/ /)(

2

212

0

12

012

2

2

2

2

2 e /

)(/ ///

)(

N

knjN

n

N

nn

N

jk

N

knj

nk xeexX

i

k

-k

N

p

kk XW XX 2/ ki-k

Nkp

Nk

XW XX 2

2

/



Exemple : – Prenons 8 échantillons, qui ont les valeurs

successives suivantes: x0,x1,x2,x3,x4,x5x6,x7,x8.

– La TFD se présente ainsi :

4

49πj

74

42πj

64

35πj

54

28πj

44

21πj

34

14πj

24

7πj

1

j0

07

4

42πj

74

36πj

64

30πj

54

24πj

44

18πj

34

12πj

24

6πj

1

j0

06

4

35πj

74

30πj

64

25πj

54

20πj

44

15πj

34

10πj

24

5πj

1

j0

05

4

28πj

74

24πj

64

20πj

54

16πj

44

12πj

34

8πj

24

4πj

1

j0

04

4

21πj

74

18πj

64

15πj

54

12πj

44

9πj

34

6πj

24

3πj

1

j0

03

4

7πj

74

6πj

64

5πj

54

4πj

44

3πj

34

2πj

24

πj

1

j0

01

j0

7

j0

6

j0

5

j0

4

j0

3

j0

2

j0

1

j0

00

exexexexexexexexX

exexexexexexexexX

exexexexexexexexX

exexexexexexexexX

exexexexexexexexX

exexexexexexexexX

exexexexexexexexX



– Prenons la ligne X1, en séparant les échantillons paires/impairs, puis en factorisant les échantillons impairs, on obtient:

– Les termes des couples x0-x1, x2-x3, x4-x5, x6-x7 sont identiques à un facteur près, donc on peut encore subdiviser :

– On peut montrer facilement,

a)

b)

– D’où l’écriture suivante :

)( 23

22

223

22

2j-

7

j-

5

j-

3

j0-

14j-

6

j-

4

j-

2

j0-

01 exexexexexexexexX

j

e

nk

NN

knj

nk

N WeW 22

22

//

nk

NN

Nknj

Nnk

N WeW

)/()(

22

2

)WxW(xWWxWxW -4

87

0

83

-2

8

-4

85

0

81

-1

8

)WxW(xWWxWxX -4

86

0

82

-2

8

-4

84

0

801

)exe(xeexexX 44π

44π j-

6

j0-

24

2πjj-

4

j0-

01

)exe(xe)exe(xe 44π

4

2πj

44π j-

7

j0-

3

j-

5

j0-

14

πj



– Le calcul de certains terme revient plusieurs fois, on peut donc diminuer le nombre d’opérations à réaliser à l’aide d’ opérations « butterfly »

– Opérations « Butterfly » ou papillon

– Le calcul « Butterfly » est le suivant :

)Wx(xWW-xxX - 0

262

1

4

0

2401 )0

273

-1

4

0

251

1

8 Wx-(xWWxx W

)Wx(xWWxxX 0

262

0

4

0

2400

)Wx(xWWxxX 0

262

0

4

0

2402

)0

273

0

4

0

251

0

8 Wx(xWWxx W

)0

273

0

4

0

251

2

8 Wx(xWWxx W

……

.

a

b

bWa n

N

bWa n

N


Application à la FFT

Remarque :– Ce schéma de calcul peut être implanté dans des

DSP

– Nombre de calculs N/2log2N


x0

x4

x2

x6

x1

x5

x3

x7

X0

X1

X2

X3

X4

X5

X6

X7c cSignal Transformée de Fourier

0

2W

0

2W

0

2W

0

2W

0

4W

1

4W

0

4W

1

4W

0

8W

3

8

W



Incrément en « reverse carry »– Les couples d’échantillons doivent être choisis

selon un ordre particulier. Cette incrémentation est appelée « reverse carry » (retenue inverse).

– L’incrémentation conssite à additionner N/2 à l’indice puis à reporter la retenue à droite plutôt qu’à gauche.

– Exemple: N= 8 N/2=4 soit 100 En retenue « non inverse » : 100 + 100 = 1000 = 8 En retenue « inverse » : 100+100 = 010 = 2

– Le 1 passe de la gauche vers la droite

– On peut aussi arranger les valeurs de fréquence selon l’incrémentation « reverse carry » :

Exemple pour 8 échantillons



X0

X4

X2

X6

X1

X5

X3

X7

x0

x1

x2

x3

x4

x5

x6

x7c cSignal

0

2W

0

2W

0

2W

0

2W

0

4W

1

4W

0

4W

1

4W

Transformée de Fourier

0

8W

3

8

W

Documents

Transformée de Fourier discrète et et transformée de Fourier rapide