GELE2511 Chapitre 7 : Transformée de Fourier discrète€¦ · GELE2511 Chapitre 7 : Transform ee de Fourier discr ete Gabriel Cormier, Ph.D., ing. Universit e de Moncton Hiver 2013

GELE2511 Chapitre 7 :Transformee de Fourier discrete

Gabriel Cormier, Ph.D., ing.

Universite de Moncton

Hiver 2013

Gabriel Cormier (UdeM) GELE2511 Chapitre 7 Hiver 2013 1 / 79

Introduction

Contenu

Contenu

Serie de Fourier discrete

Transformee de Fourier discrete

Applications

Transformee de Fourier rapide


Introduction

Introduction

La transformee de Fourier discrete est une methode qui permet dedecrire un signal discret en fonction de la frequence.

On verra ici comment se servir de la transformee de Fourier discrete(DFT) pour analyser le contenu frequentiel d’un signal.


Introduction

Introduction

Il existe plusieurs termes pour definir la transformee de Fourier de signauxcontinus et discrets.

Transformee de Fourier : s’applique aux signaux continusaperiodiques. Produit un spectre aperiodique.

Serie de Fourier : s’applique aux signaux continus periodiques.Produit un spectre discret.

Transformee de Fourier a temps discret (DTFT) : s’applique auxsignaux discrets aperiodiques. Produit un spectre continu periodique.

Transformee de Fourier discrete (DFT) : s’applique aux signauxdiscrets periodiques. Produit un spectre discret.

Serie de Fourier discrete (DFS) : sert d’approximation auxcoefficients de la serie de Fourier.


Introduction

Introduction

La seule transformee qui s’applique aux problemes de traitement designaux est la transformee de Fourier discrete (DFT).

Les transformees qui s’appliquent aux signaux continus ne peuventpas etre utilisees pour des signaux discrets.

Quant a la DTFT, elle s’applique aux signaux de duree infinie : on nepeut pas s’en servir pour des signaux reels (qui auront une dureefinie).

Meme si les signaux discrets ne sont pas necessairement periodiques,la DFT est la seule transformee applicable.




La serie de Fourier discrete est tres semblable a la serie de Fourier.

Pour le cas discret, le nombre de sinusoıdes qui constituent un signalest fini.

On peut utiliser 3 formes, comme la serie de Fourier : forme reelle,forme complexe, forme polaire.

Tout comme le cas a temps continu, on utilise une minuscule pourrepresenter un signal en fonction du temps (x[n]) et une majusculepour representer un signal en fonction de la frequence (X[n]).




La serie de Fourier discrete est obtenue a partir de la serie de Fouriercontinue :

f(t) =

∞∑n=−∞

Cnejnω0t

ou les coefficients de la serie de Fourier sont :

Cn =1

T

∫ T

0f(t)e−jnω0t dt




On peut transformer les coefficients de la serie de Fourier continueaux coefficients de la serie de Fourier discrete en faisant lessubstitutions suivantes :

f(t)→ x[n] (le signal est echantillonne)ω0 → 2πft→ ntsdt→ ts

On obtient :

XDFS [k] =1

N

N−1∑n=0

x[n]e−j2πkn/N



Exemple

Soit un signal continu x(t) = 4 cos(100πt), echantillonne a 2 fois le tauxde Nyquist, pour 3 periodes. Puisque f = 50Hz, fN = 100Hz, et doncfs = 200Hz.

0 2 4 6 8 10 12

−4

−2

0

2

4

n

Le signal echantillonne est x[n] = {4, 0,−4, 0, 4, 0,−4, 0, 4, 0,−4, 0}.



Exemple (2)

On applique l’equation de la DFS pour calculer le spectre.

0 2 4 6 8 10 12

0

1

2

k

Cependant, on a 2 pics dans le spectre, alors qu’il n’y a qu’un seul cosinus.



Exemple (3)

On a un pic a k = 3 et k = 9.

F =f

fs=

50

200=

1

4=

1

4· 33=

3

12=

k

N

A cause de 3 periodes

Est-ce que ca implique qu’on a 2 cosinus dans le signal ?

Il faut considerer la composante negative :

2 cos(−2π50t) + 2 cos(2π50t) = 4 cos(2π50t)

La DFS a la propriete d’etre symetrique conjugue :

X[k] = X∗[N − k]



Exemple (4)

On rearrange l’abscisse pour identifier les composantes negatives.

−6 −4 −2 0 2 4 6

0

1

2

k

Les pics sont a k = −3 et k = 3, qui sont donc a la meme frequence.



Exemple (5)

Les points de N/2 + 1 a N − 1 sont le conjugue des points de N/2 a0.

Si on veut un graphe ou il y a seulement des frequences positives, ilfaudra multiplier les amplitudes des coefficients 1 a N/2 (le DC est ala bonne amplitude).



Exemple (6)

Comment interpreter l’abscisse ?

L’abscisse fait seulement du sens en fonction du tauxd’echantillonnage.

Les points de k = 0 a N − 1 peuvent etre remplaces par F = k/N ;l’abscisse variera de 0 a 1.

Les points k = 0 a N − 1 peuvent etre remplaces par f = (k/N)fs ;l’abscisse variera de 0 a fs.

On peut aussi representer les frequences de facon radiale : onmultiplie par 2π.



Exemple (7)

On peut retracer le spectre en fonction de F ou fs.

0 0.2 0.4

0

1

2

F

0 20 40 60 80 100

0

1

2

f (Hz)

Le pic est bien a la bonne frequence : 50Hz.


Fuite spectrale

Problemes de la DFS

On verra qu’on peut avoir des erreurs dans le spectre sil’echantillonnage n’est pas fait correctement.

On verra qu’il y a des erreurs si on n’echantillonne pas pour unnombre entier de points par periode.

On reprend l’exemple precedent, mais cette fois on echantillonne a240Hz au lieu de 200Hz.


Fuite spectrale

Problemes de la DFS

On echantillonne a 240Hz : on a 240/50 = 4.8 echantillons par periode.

0 2 4 6 8 10 12 14

−4

−2

0

2

4

n


Fuite spectrale

Problemes de la DFS

On calcule la DFS de ce signal.

0 10 20 30 40 50 60 70 80 90 100 110 120

0

1

2

f (Hz)

Il y a erreur dans la frequence : c’est 51.5 Hz environ, une erreur de 3%.


Fuite spectrale

Problemes de la DFS

On peut aussi comprendre ce phenomene si on considere que de 0 a120 Hz, il y a 8 points (incluant le DC). L’intervalle de 0 a 120 Hz estdivise en 7 : 17.14 Hz par pas.

Le point le plus pres de 50 Hz est 3×17.14, ou 51.4 Hz.

Dans ce cas-ci, on n’a pas assez de points pour representercorrectement le 50 Hz.

L’intervalle entre les points est appele l’espacement spectral, etcorrespond a S/N .


Fuite spectrale

Fuite spectrale

Si on n’echantillonne pas un signal pour un nombre entier de pointspar periode, il y aura une erreur dans les coefficients de la serie deFourier.

On appelle ce phenomene la fuite spectrale.

La serie de Fourier discrete calculee donnera des frequences autresque celles dans le signal (mais quand meme pres de la vraie valeur).


Fuite spectrale

Effets de la fuite spectrale

La fuite spectrale est presente si on n’echantillonne pas pour unnombre entier de points par periode.

La transformee de Fourier aura des composantes non nulles a desfrequences autres que celles du signal.

Il peut aussi avoir du repliement si le signal continu contient desharmoniques de frequence plus elevee que le taux d’echantillonnage.


Fuite spectrale

Minimiser la fuite spectrale

On peut minimiser les effets de la fuite spectrale si on echantillonne aun taux plus eleve que le taux de Nyquist.

De facon pratique, pour avoir une erreur plus petite que 5% dans lesM premieres harmoniques, il faut echantillonner a fs = 8fM , ou fMest la frequence de la M ieme harmonique.


Fuite spectrale

Minimiser la fuite spectrale

On devrait idealement echantillonner pour un nombre entier de pointspar periode.

Pratiquement, ceci est rarement possible, puisqu’on ne connaıt pas apriori les frequences d’un signal.

On doit donc echantillonner le plus longtemps possible, pour reduirel’espacement spectral.


Fuite spectrale

Exemple

Soit une onde carree de 50 Hz echantillonnee a 1 kHz : 20 echantillons parperiode.

0 2 4 6 8 10 12 14 16 18 20

−1

0

1

Temps (ms)


Fuite spectrale

Exemple (2)

Le spectre :

0 100 200 300 400 500

0

0.2

0.4

0.6

Frequence (Hz)


Fuite spectrale

Exemple (3)

On compare les coefficients de la serie de Fourier a ceux de la DFS :

|C(k)| |X[k]| ErreurDC 0 0 0Fondamentale 0.6366 0.6346 0.3%2e harmonique 0 0 03e harmonique 0.212 0.206 2.9%4e harmonique 0 0 05e harmonique 0.1273 0.1169 8.2%

La fondamentale et la 3e harmonique ont moins de 5% d’erreur :S < 8(3f0)




On peut obtenir la transformee de Fourier discrete a partir de la serie deFourier discrete.


XDFT [k] =

N−1∑n=0

x[n]e−j2πkn/N = NXDFS



Transformee de Fourier discrete inverse

La transformee inverse (IDFT) est :

Transformee de Fourier discrete inverse

x[n] =1

N

N−1∑k=0

XDFT [k]ej2πkn/N



Exemple

Calculer la DFT du signal suivant : x[n] = {1, 2, 1, 0}

Dans ce cas-ci, on a N = 4, et donc selon la definition de la DFT,e−j2πkn/N = e−jπkn/2. On calcule les valeurs :

k = 0 : XDFT [0] =

3∑n=0

x[n]e0 = 1 + 2 + 1 + 0 = 4

k = 1 : XDFT [1] =

3∑n=0

x[n]e−jπn/2 = 1 + 2e−jπ/2 + e−jπ + 0 = −j2

k = 2 : XDFT [2] =3∑

n=0

x[n]e−jπn = 1 + 2e−jπ + e−j2π + 0 = 0

k = 3 : XDFT [3] =3∑

n=0

x[n]e−j3πn/2 = 1 + 2e−j3π/2 + e−j3π + 0 = j2

XDFT = {4,−j2, 0, j2}



Quelques proprietes

Quelques transformees utiles :

{1, 0, 0, 0, . . . , 0} impulsion⇐⇒ {1, 1, 1, 1, . . . , 1} constante

{1, 1, 1, 1, . . . , 1} constante⇐⇒ {N, 0, 0, 0, . . . , 0} impulsion

cos(2πnk0/N) sinusoıde⇐⇒ 0.5N(δ[k − k0] + δ[k − (N − k0)])

Remarquer qu’un signal qui est court dans le temps est long en frequence,et vice-versa.


Applications

Applications

On verra quelques applications de la transformee de Fourier discrete :

Analyse spectrale d’un signal

Reponse en frequence d’un systeme

Convolution


Applications Analyse spectrale

Analyse spectrale

Il existe plusieurs signaux dont l’information est codee dans des sinusoıdes.

La voix est un bon exemple : les humains peuvent distinguer des sonsde 20Hz a 20kHz environ.

La musique n’est qu’une suite de notes de frequence fixe (ex : A4 est440Hz).

Les pales d’un sous-marin tournent a une frequence qui peut etredetectee.



Exemple 1

Supposons qu’on veut caracteriser les sons enregistres dans l’ocean.

On place un microphone dans l’eau pour enregistrer les sons, puis onamplifie le signal.

On utilise un filtre passe-bas pour couper les sons au-dessus de 80Hz.On echantillonne a 160Hz.

On procede ensuite a l’analyse du spectre.



Exemple 1

On observe le signal en fonction du temps pour voir si on peut deduire del’information.

0 0.5 1 1.5−0.2

−0.1

0

0.1

0.2

0.3

temps (s)



Exemple 1

On observe maintenant le spectre.

0 10 20 30 40 50 60 70 800

0.2

0.4

0.6

0.8

Fréquence (Hz)



Exemple 1

On analyse le contenu spectral :

Si on ignore les pics, on voit qu’entre 10Hz et 70Hz le spectre estconstant ; c’est le bruit blanc gaussien.

Le bruit blanc gaussien est appele ainsi parce qu’il est constant surtoutes les frequences.

Le bruit blanc est cause par plusieurs choses : ici, ca peut etre lemicrophone, ou meme l’ocean.



Exemple 1

Analyse du contenu spectral (suite) :

Pour les frequences tres faibles, on remarque que le bruit augmentetres rapidement, avec une forme qui ressemble a 1/f : c’est le bruitrose (flicker noise).

Ce type de bruit apparaıt dans pratiquement tous les systemesphysiques, que ce soit electrique, mecanique, etc. Aucune theorie nepermet d’expliquer tous les cas ou se trouve ce type de bruit.

Pour les systemes electriques courants, c’est generalement en-dessousde 100Hz qu’on retrouve ce type de bruit.



Exemple 1

Analyse du contenu spectral (suite) : les pics

A 60Hz, il y a generalement pollution causee par l’equipementelectronique. On peut observer des harmoniques a 120Hz, 180Hz, etc.

Il y a souvent des pics entre 25kHz et 40kHz qui sont causes parcertains types d’alimentations a decoupage.

Les appareils mecaniques rotatifs causent aussi des frequences faibles :un moteur qui tourne a 1800rpm cause des vibrations a 30Hz.



Exemple 1

Analyse du contenu spectral (suite) : les pics

Il y a un pic important a 13Hz, et un pic plus faible a 26Hz, qui estprobablement une harmonique de celui de 13Hz.

Ce signal pourrait etre cause par les pales triples d’un sous-marin quitournent a 4.33 tours/seconde.

Cette technique est la base du sonar passif.


Obtention du spectre


Pour obtenir le spectre d’un signal a l’aide de la DFT, il suffitd’appliquer l’equation de la DFT aux echantillons.

Cependant, il faut bien savoir interpreter les resultats.

On prend donc un exemple simple pour demontrer commentinterpreter correctement la DFT.


Obtention du spectre Exemple


Le signal :

x(t) = 0.5 cos(2π44t) + 0.4 sin(2π232t) + 0.5 cos(2π415t)

On va ajouter du bruit blanc gaussien a ce signal en utilisant la commandeawgn dans Matlab.

Le signal sera echantillonne a 3kHz, et on utilisera 256 echantillons.




Le signal est le suivant :

0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09−1.5

−1

−0.5

0

0.5

1

1.5

Code Matlab :N = 256;

S = 3000;

t = 0 : 1/S : (N-1)/S;

x = 0.5*cos(2*pi*t*44)+0.4*sin(2*pi*t*322)+0.5*cos(2*pi*t*415);

x = awgn(x,15);




A l’aide de la DFT, on obtient le spectre suivant :

0 20 40 60 80 100 120 1400

10

20

30

40

50

60

k

Code Matlab :X = fft(x);

k = 1:N;

plot(k,abs(X));




Quelques remarques sur la figure precedente :

L’abscisse est en fonction de k, et pas en fonction de la frequence.

Il faut transformer l’abscisse de sorte qu’elle soit en fonction de lafrequence d’echantillonnage, si on veut que le graphe fasse du sens ducote pratique.

Les points de 0 a 128 doivent en fait varier de 0 a 1500Hz (0 a fs/2).




En fonction de la frequence :

0 500 1000 15000

10

20

30

40

50

60

f (Hz)

Code Matlab :f = 0: S/N : 0.5*S;

stem(f,abs(X(0:129))); xlabel(’f (Hz)’);




Il y a peu d’information utile apres 500Hz, donc on fait un zoom sur cettepartie du spectre a l’aide de la commande xlim.

0 50 100 150 200 250 300 350 400 450 5000

20

40

60

f (Hz)

Cependant, la resolution spectrale (S/N) est de 11.72Hz, ce qui ne permetpas de bien determiner les frequences. Il faudrait utiliser plus de points.




Avec 1024 points, la resolution est bien meilleure.

0 50 100 150 200 250 300 350 400 450 5000

100

200

300

f (Hz)

Cependant, plus on a de points, plus le temps de calcul est eleve.


Obtention du spectre Fenetre de Hamming

Fenetre de Hamming

Un facon d’ameliorer les pics sans utiliser plus de points est demultiplier le signal en fonction du temps par une composante appeleeune fenetre de Hamming.

La fenetre de Hamming va attenuer les bouts du signal. En termes despectre, la fenetre de Hamming va rendre les pics plus grands parrapport au bruit, mais ca va aussi les elargir.

Il existe plusieurs autres fenetres.



Fenetre de Hamming

Effet de la fenetre de Hamming :

0 50 100 150 200 2500

0.2

0.4

0.6

0.8

1

n

Fenêtre de Hamming

0 0.02 0.04 0.06 0.08−2

−1

0

1

2

t

Signal multiplié par la fenêtre

Code Matlab :x = x.*hamming(N)’;



Fenetre de Hamming

On peut voir l’effet de la fenetre de Hamming sur le spectre.

0 100 200 300 400 5000

20

40

60

80

f (Hz)

Sans fenêtre de Hamming

0 100 200 300 400 5000

10

20

30

40

f (Hz)

Avec la fenêtre de Hamming


Reponse en frequence


Une autre application de la DFT est la reponse en frequence d’unsysteme, qui permet de voir le comportement en termes de frequence.

La reponse en frequence d’un systeme est la transformee de Fourierde la reponse impulsionnelle.

Dans certains cas, la reponse en frequence donne beaucoup plusd’information sur la fonction d’un systeme que sa reponseimpulsionnelle.




Exemple : reponse impulsionnelle d’un systeme quelconque. Il est difficilede determiner la fonction du systeme.

0 10 20 30 40 50 60−0.4

−0.2

0

0.2

0.4

n




En faisant la DFT de ce signal, la fonction est plus claire : c’est un filtrepasse-bande.

0 0.1 0.2 0.3 0.4 0.50

0.5

1

1.5

F




Pour obtenir plus de resolution, on va effectuer la DFT avec plus depoints. On ajoute des zeros a la fin du signal.

0 100 200 300 400 500−0.4

−0.2

0

0.2

0.4

n

signal additioné de zéros

0 0.1 0.2 0.3 0.4 0.50

0.5

1

1.5

F

DFT

On n’a pas augmente la precision du spectre, seulement sa resolution.


Convolution

Convolution par la DFT

Une autre application de la DFT est pour faire la convolution de deuxsignaux.

Dans le domaine du temps, on utilise la convolution pour calculer lasortie d’un systeme.

Dans le domaine de frequence, on fait la multiplication.

x[n]h[n]⇐⇒ X[k]H[k]


Convolution


Bien qu’il y ait des etapes supplementaires, c’est plus rapide de passerpar la DFT pour faire la convolution.

Etapes : DFT de x[n], DFT de h[n], multiplication, transformeeinverse.


Convolution


Certains problemes :

La longueur de la convolution n’est pas la meme que la DFT.

Pour un signal x[n] de longueur N et h[n] de longueur M , lalongueur de la convolution est N +M − 1.

La longueur de la DFT est N (si N > M).

Il manque des points.

Il faut donc ajouter des zeros aux signaux pour qu’ils soient delongueur N +M − 1, avant de faire la DFT.


Convolution

Exemple

Soit x[n] = {1,−3, 1, 5} et h[n] = {4, 3, 2, 1}. Effectuer la convolution parla DFT.

La convolution serait de longueur 4 + 4− 1 = 7. Il faut ajouter 3 zeros achaque sequence.

X[k] = {4.0,−5.60− j0.80, 3.88 + j7.27, 3.21− j2.79, 3.21 + j2.79,

3.88− j7.27,−5.60 + j0.80}H[k] = {10, 4.52− j4.73, 2.15− j1.28, 2.32− j0.72, 2.32 + j0.72,

2.15 + j1.28, 4.52 + j4.73}

On multiplie point par point :

Y [k] = {40,−29.11 + j22.86, 17.63 + j10.72, 5.47− j8.77, 5.47 + j8.77,

17.63− j10.70,−29.11− j22.86}

Puis la transformee inverse :

y[n] = {4,−9,−3, 18, 14, 11, 5}


Convolution

Deconvolution

Si on connaıt la sortie d’un systeme et la reponse impulsionnelle, on peutcalculer l’entree a l’aide de la deconvolution.

Deconvolution est beaucoup plus complexe que la convolution.

Beaucoup plus facile dans le domaine de frequence.

Division simple dans le domaine de frequence.


Proprietes

Proprietes de la DFT

Si XDFT est la DFT d’un signal discret x[n], alors :

kx[n]⇐⇒ kXDFT [k] linearite

x1[n] + x2[n]⇐⇒ X1[k] +X2[k] additivite

x[−n]⇐⇒ XDFT [−k] = X∗DFT [k] repliement

x[n− s]⇐⇒ e−j2πsk/NXDFT [k] dephasage

x[n]y[n]⇐⇒ 1

NXDFT [k]~ YDFT [k] multiplication

x[n]~ y[n]⇐⇒ XDFT [k]YDFT [k] convolution periodique


Proprietes

Proprietes de la DFT

Si XDFT [k] est la DFT d’une sequence x[n], alors :

1 Si un signal est repete M fois, la DFT de ce signal est l’interpolationzero de XDFT et multipliee par M .

{x[n], x[n], x[n], . . . , x[n]︸︷︷︸M fois

} ⇐⇒MXDFT [k/M ]

2 Si un signal subit une interpolation zero de M , alors la DFT estrepetee M fois :

x[n/M ]⇐⇒ {XDFT [k], XDFT [k], XDFT [k], . . . , XDFT [k]︸︷︷︸M fois

}


Proprietes

Theoreme de Parseval

Puisque le temps et la frequence sont deux domaines equivalents pourrepresenter un signal, ils doivent avoir la meme energie.

C’est le theoreme de Parseval :

N−1∑i=0

x2[n] =1

N

N/2∑k=−N/2

|X[k]|2


Proprietes

Formulation matricielle

On peut exprimer la DFT sous forme matricielle. Soit WN = e−j2π/N ,

XDFT [k] =

N−1∑n=0

x[n]WnkN , k = 0, 1, . . . , N − 1

ce qui donne :X = WNx

ou

WN =

W 0N W 0

N W 0N · · · W 0

N

W 0N W 1

N W 2N · · · WN−1

N

W 0N W 2

N W 4N · · · W

2(N−1)N

......

.... . .

...

W 0N WN−1

N W2(N−1)N · · · W

(N−1)(N−1)N


Detection de signaux


On peut utiliser la DFT pour detecter la frequence de signaux.

On utilise les effets du repliement.

L’emplacement des composantes spectrales peut changer a cause durepliement.

Si on peut echantillonner a des taux differents, on peut trouver lescomposantes spectrales d’un signal.




Pour S = 100, 200 et 500Hz, les pics changent de frequence. Mais aS = 1kHz, les pics sont au meme endroit que S = 500Hz.

0 10 20 30 40 500

0.1

0.2

0.3

0.4

f (Hz)

S = 100Hz

0 50 1000

0.1

0.2

0.3

0.4

f (Hz)

S = 200Hz

0 50 100 150 200 2500

0.1

0.2

0.3

0.4

f (Hz)

S = 500Hz

0 100 200 300 400 5000

0.1

0.2

0.3

0.4

f (Hz)

S = 1000Hz


DTFT

DTFT

La DTFT (Transformee de Fourier a temps discret) est une methodepour decrire un signal discret comme une somme d’exponentielscomplexes.

La DTFT produit un spectre continu.

La DFT est la version echantillonnee de la DTFT.


DTFT

DFT

Par definition, la DTFT est :

X(F ) =

∞∑m=−∞

x[m]e−j2πmF

ou F est une variable continue.

La DTFT est periodique, avec une periode de 1. L’intervalle−0.5 < F < 0.5 est la periode principale.

La DTFT inverse est :

x[n] =

∫ 0.5

−0.5X(F )ej2πnFdF


DTFT

Exemple

Calculer la DTFT de la sequence x[n] = {1, 0, 3,−2}.

A partir de la definition,

X(F ) =

∞∑m=−∞

x[m]e−j2πmF = 1 + 3e−j4πF − 2e−j6πF

L’amplitude du spectre est montre a la figure suivante.

−0.5 0 0.5 10

2

4

6

8

F

Am

plitu

de


FFT

FFT

Il existe plusieurs methodes pour calculer la DFT, mais la plus rapideest la FFT.

Cet algorithme est tres efficace, jusqu’a des centaines de fois plusrapide que les methodes conventionnelles.

Sans la FFT, plusieurs techniques de traitement de signal ne seraientpas pratique.


FFT

FFT

J.W. Cooley et J.W. Tukey sont les 2 ingenieurs credites pourl’invention de la FFT, dans un article paru en 1965.

Bien que la technique elle-meme n’etaient pas recente, les auteursetaient les premiers a realiser que les methodes mathematiques deGauss pouvaient etre utilisees avec des ordinateurs.

La FFT est comme le transistor du traitement de signal.


FFT

Problemes de la DFT

L’algorithme de la DFT a quelques problemes :

Inefficace

N’utilise pas les proprietes de la DFT (symetrie conjuguee, etc.)

On optimise la DFT en exploitant certaines proprietes.


FFT

Optimiser la DFT

On peut exploiter la symetrie et periodicite de WN .

Wn+NN = e−j2π(n+N)/N = e−j2πn/Ne−j2πN/N = e−j2πn/N =Wn

N

Wn+N/2N = e−j2π(n+N/2)/N = e−j2πn/Ne−jπ = −e−j2π/N = −Wn

N

WNkN = e−j2πNk/N = e−j2πk = 1, ou k est un entier

W 2N = e−j2π2/N = e−j2π/(N/2) = e−j2π/N =WN/2


FFT

Optimiser la DFT

Choisir une valeur de N qui est le produit de plusieurs petits chiffres.

On veut que N = r1r2 · · · rm. Il est utile de choisir la meme valeur der, de sorte que N = rm. Le plus commun est r = 2.

Decimation des indices

On accelere le calcul si on separe le signal en composantes paires etimpaires.

Utilisation efficace de la memoire

Ce aspect touche plutot le cote pratique : on enregistre les resultats descalculs dans les memes adresses qui contenaient les donnees.


FFT

Optimiser la DFT

Quelques resultats simples mais fondamentaux peuvent simplifier lescalculs :

La DFT d’un seul echantillon est l’echantillon lui-meme :

XDFT [0] = x[0]W 01 = x[0]

La DFT de deux echantillons est une operation simple :

X2[0] = x[0]W 02 + x[1]W 0

2 = x[0] + x[1]

X2[1] = x[0]W 02 + x[1]W 1

2 = x[0]− x[1]


FFT

FFT

Le calcul de la DFT est une operation d’ordre N2. Selon l’equation dela DFT,

X[k] =

N−1∑n=0

x[n]WnkN

on remarque qu’il faut :

N2 multiplications complexesN(N − 1) additions complexes

Il y a beaucoup d’operations a effectuer.


FFT

FFT

A l’aide des proprietes vues auparavant, on peut grandement accelererle calcul de la DFT.

On passe d’un calcul ayant N2 multiplications a un calcul ayantlog2(N) multiplications.

Pour des signaux a plusieurs echantillons, la FFT est beaucoup plusrapide.


FFT

FFT

L’implantation pratique de la FFT necessite un nombre de points quiest une puissance de 2.

Si le nombre de points n’est pas une puissance de 2, on doit ajouterdes zeros a la fin de la sequence.


FFT

IFFT

Pour calculer la transformee inverse, on utilise la formulationmatricielle :

X = WMx⇒ x = W−1M X =

1

M[W∗

M ]T X

C’est pratiquement le meme calcul que la FFT, sauf qu’on utilise leconjugue de WM transpose.


Conclusion

Conclusion

Les points cles de ce chapitre sont :

Calculer la DFT (FFT) d’un signal.

Savoir appliquer l’axe de frequence a la DFT.

Utiliser la fenetre de Hamming.

Utiliser la DFT pour faire la convolution, la detection de signaux et lareponse en frequence.


Documents

GELE2511 Chapitre 7 : Transformée de Fourier discrète€¦ · GELE2511 Chapitre 7 : Transform ee de Fourier discr ete Gabriel Cormier, Ph.D., ing. Universit e de Moncton Hiver 2013