TRANSFORMÉE DE FOURIER DISCRÈTE

N−1

∑

k=0

N−1

∑

i=0

N−1

∑

k=0

N−1

∑

k=0

X(k)e j2π n k

(cid:2)

N = 1

N

N−1

∑

k=0

(cid:3)

x(i)

N

e j2π (n−i) k

N−1

∑

k=0

N = 1 − ei2π(n−i)

e j2π (n−i) k

1 − ei2π n−i

N−1

∑

k=0

e j2π (n−i) k

e j2π (n−i) k

(cid:2)

1 = N

(cid:3)

N =

N

N

= 1

N

N−1

∑

k=0

A = x(n)

c.q.f.d.

= 0

x(n)N

A = 1

N

N−1

∑

i=0

x(i)

1.3 Lien entre la transformée de Fourier et la TFD

Soit x(t) un signal analogique continu.

1. On échantillonne x(t) à fe = 1/Te.

x(t) → xe(t) =

+∞

∑

n=−∞

x(nTe)δ(t − nTe) = x(t)P(t)

où P(t) est la « fonction peigne »:

P(t) =

+∞

∑

n=−∞

δ(t − nTe)

T F(cid:1)(cid:2) P( f ) = 1

Te

+∞

∑

n=−∞

δ

(cid:4)

(cid:5)

f − n

Te

L’échantillonnage rend le spectre périodique et peut entraîner un phénomène de « recouvrement de spectre »

ou aliasing.

x(t)

xe(t)

|X(f)|

1

t

f

|Xe(f)|

1/Te

t

-1/Te

1/Te

f

2. On tronque la suite xe(nTe) en ne conservant qu’un nombre fini N de termes pour obtenir le signal xtr

formé des échantillons: x(0) . . . x((N − 1)Te):

(t)

xtr

(t) = xe(t)F(t) =

N−1

∑

n=0

x(nTe)δ (t − nTe)

(t) = x(t)P(t)F(t)

xtr

1. Transformée deFourierDiscrète: TFD

Page7

où F(t) est une fonction fenêtre de durée NTe

(cid:6)

où T0

= NTe.

F(t) =

F(t)

1

(cid:7)

− Te

2

, T0

− Te

2

(cid:8)

1

0

t ∈

si

sinon

-Te/2

T0-Te/2

xtr(t)

|F(f)|

T0

f

|Xtr(f)|

f

t

t

La convolution avec un sinus cardinal introduit des ondulations sur le spectre. Elles sont appelés « ripples » en

anglais.

Xtr

( f ) =

x(nTe)e− j2π f nTe

N−1

∑

n=0

3. On échantillonne Xtr

( f ) à 1/T0

On obtient alors N valeurs différentes espacées de 1/T0 entre 0 et 1/Te, car T0

opération rend périodique la « fonction » dans le temps. Appelons xc(t) la fonction résultante.

(cid:4)

(cid:4)

(cid:5)

(cid:4)

(cid:5)

(cid:5)

= NTe. Cette dernière

Xc( f ) = Xtr

+∞

∑

( f )

n=−∞

(cid:2)

N−1

∑

k=0

+∞

∑

n=−∞

Xc( f ) =

x(kTe)e− j2π nk

N

δ

δ

f − n

T0

+∞

∑

n=−∞

(cid:4)

=

(cid:3)

Xtr

n

T0

(cid:5)

δ

f − n

T0

f − n

T0

(cid:10)

xc(t) = T0

+∞

∑

n=−∞

xtr

(cid:9)

t − nT0

xc(t) et Xc( f ) sont deux distributions échantillonnées reliées par la transformation de Fourier.

xc(t)

Te

|Xc(f)|

1/NTe

T0=NTe

t

fe=1/Te

f

On obtient donc une correspondance entre N points dans le domaine temporel xc(nTe) et N points dans le

domaine fréquentiel Xc(n/T0

), pour n entre 0 et N − 1. De plus:

xc(nTe) = T0 x(nTe) pour

(cid:4)

N−1

∑

n=0

x(nTe)e

k

T0

Xc

=

(cid:5)

− j2π nk

N

n ∈ [0, N − 1]

Page 8

ChapterI. Transformée deFourierdiscrète: TFDetTFR

c’est-à-dire que la suite Xc(k) = Xc(k/T0

) est précisément la TFD de la suite x(n) = x(nTe).

1.4 Comparaison entre la transformée de Fourier et la TFD

Soit un signal x(t) et sa transformée de Fourier X( f ) .

à la suite x(nTe) pour n ∈ [0, (N − 1)] correspond la suite TFD X(k) pour k ∈ [0, (N − 1)] avec:

X (k) =

N−1

∑

n=0

x(nTe)e− j2π nk

N

Quel est le lien entre X( f ) et X(k) pour k ∈ [0, (N − 1)] ?

On pose T0

= NTe.

Dans le cas où:

• x(t) est périodique de période τ,

• x(t) est à bande limitée [− fmax, fmax],

• la largeur de la fenêtre F(t) est égale à un multiple de τ, T0

• et la fréquence d’échantillonnage fe = 1/Te est supérieure à 2 fmax.

= kτ,

Il y a coïncidence à un facteur multiplicatif près entre X(k) et X( f = k/T0

):

(cid:4)

(cid:5)

(cid:4)

(cid:5)

X(k) = T0

Te

X

k

T0

= N X

k

T0

En effet, x(t) étant périodique de période τ a un spectre formé de raies distantes de 1/τ. De plus, ce spectre est

limité à fmax.

|X(f)|

1

1/τ

-fmax

fmax

f

Les trois opérations qui conduisent à la suite X(k) auront les conséquences suivantes:

1. L’échantillonnage de x(t) à fe rend périodique le spectre et le multiplie par 1/Te.

|Xe(f)|

1/Te

1/τ

-fmax

fmax

fe

f

1. Transformée deFourierDiscrète: TFD

Page9

2. La troncation de xe(t) par une fenêtre de largeur T0 a pour effet de convoluer le spectre avec un sinus

cardinal qui s’annule tous les 1/T0 avec T0

= kτ.

|Xtr(f)|

T0/Te

fe

f

3. L’échantillonnage du spectre à la fréquence 1/T0 a pour effet de ne conserver que des valeurs où Xtr et X

/Te = N près. C’est le seul cas où il y a identité entre la TFD et la TF au facteur

coïncident au facteur T0

N près, aux N points de calcul k/T0 avec k ∈ [0, (N − 1)].

Dans tous les autres cas, la TFD diffère de la TF aux points k/T0. L’erreur est introduite:

• par recouvrement de spectre si X( f ) n’est pas à support limité, erreur que l’on minimise en augmentant

fe.

• par les ondulations dues à la troncature par la fonction fenêtre si x(t) n’est pas périodique ou à durée lim-

itée: erreur que l’on peut chercher à atténuer en choisissant une fenêtre autre que la fenêtre rectangulaire

(fenêtre de Hanning par exemple) et en augmentant autant que possible la largeur de la fenêtre.

• pour les deux premières raisons à la fois si x(t) n’est ni à durée limitée ni à bande limitée

• même si x(t) est périodique et à bande limitée, on introduit une erreur si la fenêtre de troncature n’a pas

une durée égale à un multiple de la période car la troncature introduit alors de fortes discontinuités (voir

la figure suivante).

x(t)

xc(t)

t

t

1.5 Fenêtres de pondération

De nombreuses fenêtres de pondération ont été proposées pour l’analyse spectrale. Ces fenêtres sont utilisées

pour limiter (tronquer) la durée temporelle du signal x(t) à analyser. En notant x(t) le signal, F(t) la fenêtre, et

xtr

(t) le signal tronqué, on obtient la relation suivante:

et dans le domaine fréquentiel:

(t) = x(t)F(t)

xtr

Xtr

( f ) = X( f ) (cid:3) F( f )

Page 10

ChapterI. Transformée deFourierdiscrète: TFDetTFR

Pour une même durée temporelle NTe, on compare les différentes fenêtres essentiellement par leurs propiétés

fréquentielles. Idéalement, on aimerait que la troncation du signal en temps ne modifie pas son contenu fréquen-

( f ), ce qui suppose que F( f ) = δ( f = 0). En pratique, ce n’est pas possible

tiel, c’est- à-dire que X( f ) = Xtr

et les fenêtres F( f ) présentent un lobe principal de largeur non nulle centré autour de la fréquence nulle et en

général des lobes secondaires de hauteur non nulle. On peut caractériser une fenêtre par des paramètres tels

que:

• La largeur du lobe principal, mesurée à 3 dB d’atténuation par rapport à l’amplitude en f = 0, ou bien à

mi-hauteur.

• La hauteur maximale des lobes seconadaires (quand ils existent).

Ces paramètres influencent respectivement la résolution et la dynamique de l’analyse spectrale.

La résolution est la capacité à distinguer 2 fréquences proches. La dynamique est la capacité à mesurer des

composantes fréquentielles d’amplitudes très différentes sans que la plus forte ne masque la plus faible.

De manière générale, la largeur du lobe principal est inversement proportionnelle à la durée temporelle de

la fenêtre.

1.5.1 Fenêtres rectangulaires, triangulaires et paraboliques

• Fenêtre rectangulaire Fr(t)

Une fenêtre rectangulaire Fr(t) centrée de durée NTe s’écrit en temps et en fréquence:

Fr(t) = rectNTe

Fr( f ) = sin 2πf N Te/2

(t)

2πf N Te

2

La transformé de Fourier de la fenêtre rectangulaire, présente des lobes secondaires importants qui ne

décroissent qu’en 1

f . Le lobe secondaire le plus haut n’est qu’à -13 dB en dessous de l’amplitude en

f = 0.

• Fenêtre triangulaire Ft

(t) et fenêtre parabolique Fp(t)

(t) (appelée aussi fenˆtre de Bartlett) et la fenêtre parabolique Fp(t) se déduisent

La fenêtre triangulaire Ft

simplement de la fenêtre rectangulaire par élévation au carré ou au cube de Fr( f ). Les transformées de

Fourier ainsi obtenues décroissent donc en 1

2

f 3 . elles sont respectivement égales à:

f 2 et en 1

(cid:5)

(cid:5)

(cid:4)

(cid:4)

3

(ω) =

Ft

sin NωT

4

NωTe

4

ou à Fp(ω) =

sin EωTe

6

NωTe

6

De plus, l’amplitude maximum des lobes secondaires est à -26 db en dessous du lobe principal dans le

(ω), et à -39 db dans le cas de Fp(ω). Par contre, le lobe principal est, dans les 2 cas, plus large

cas de Ft

que pour la fenêtre rectangulaire.

Déterminons les expressions temporelles de Ft

(ω) et de Fp(ω):

donc

et

donc

(ω) = Fr(ω) × Fr(ω)

Ft

(t) = Fr(t) ∗ Fr(t) = 1 −

Ft

(cid:4)

(cid:5)

2 | t |

NTe

Fp(ω) = Ft

(ω) × Fr(ω)

Fp(t) = Ft

(t) ∗ Fr(t) = 1 −

(cid:5)

2

(cid:4)

t

NTe

La figure suivante représente la fenêtre triangulaire.

1. Transformée deFourierDiscrète: TFD

Page11

F(t)

|F(f)|

NTe

t

f

La figure suivante représente la fenêtre parabolique.

F(t)

|F(f)|

NTe

t

f

1.5.2 Fenêtres Fenêtres détruisant par addition algébrique, les lobes secondaires de la fenêtre rectan-

gulaire

D’autres fenêtres intéressantes s’obtiennent en détruisant les lobes secondaires de la fenêtre rectangulaire, par

addition algébrique. On peut citer dans cette catégorie la fenêtre cosinusoïdale, les fenêtres de Hanning, de

Hamming, de Blackman.

• Fenêtre cosinusoïde Fc(t)

L’expression algébrique de la fenêtre cosinusoïde est:

(cid:4)

(cid:4)

Fc( f ) = 1

2

FR

f − 1

2NTe

(cid:4)

(cid:5)

(cid:5)

(cid:5)(cid:5)

(cid:4)

+ FR

f + 1

NTe

Fc(t) = Fr(t) cos

π t

NTe

Les lobes secondaires de Fc( f ) sont plus faibles que ceux de Fr( f ); ainsi l’amplitude maximum de ces

lobes est 34 db en dessous de l’amplitude en f = 0 et leur décroissance est en 1/ f2. Par contre, le lobe

principal est plus large.

• Fenêtre de Hanning FH

Nous avons vu précédemment comment, par une combinaison algébrique de deux fonctions déduites

de Fr( f ) par des décalages en fréquence, on pouvait diminuer l’amplitude des lobes secondaires mais

en augmentant la bande de transition. On peut encore diminuer l’amplitude des lobes secondaires en

augmentant le nombre de fonctions combinées algébriquement. C’est le cas pour la fenêtre de Hanning

(voir la figure suivante).

F(t)

|F(f)|

NTe

t

f

= NTe):

L’expression algébrique de la fenêtre de Hanning est (en notant T0

(cid:5)

(cid:4)

(cid:4)

(cid:5)

FH

( f ) = 1

2

FR

( f ) + 1

4

FR

f − 1

T0

+ 1

4

FR

f + 1

T0

Page 12

ChapterI. Transformée deFourierdiscrète: TFDetTFR

(t) = 1

2

(t) = 0

FH

FH

(cid:5)(cid:5)

(cid:4)

(cid:4)

1 + cos

2π t

T0

ailleurs.

pour

t ∈

(cid:7)

−T0

/2, T0

(cid:8)

/2

L’amplitude maximum des lobes secondaires est alors égale à -44 db (en dessous du lobe principal); ils

décroissent en 1

f 3 . Le lobe principal est presque 2 fois plus large que pour la fenêtre rectangulaire.

• Fenˆtre de Hamming Fhm

On peut améliorer les résultats obtenus par la fenêtre précédente en modifiant les pondérations de Fr( f ),

Fr( f − 1/NTe) et Fr( f + 1/NTe):

Fhm

( f ) = 0.56 Fr( f ) + 0.22 [Fr( f − 1/NTe) + Fr( f + 1/NTe)]

Dans ce cas, la décroissance des lobes secondaires est toujours en 1/ f3 mais l’amplitude maximum de

ces lobes est à -60 db sous le lobe principal.

L’expression temporelle Fhm

(t)de la fenêtre de Hamming s’écrit:

Fhm

(t) = 0, 56 + 0, 44 × cos(2πt/NTe) − NTe

2

= 0 ailleurs

< t < NTe

2

• Fenêtre de Blackman FB

(t)

Pour diminuer encore l’amplitude des lobes secondaires, on peut combiner:

Fr( f ), Fr( f − 1/NTe), Fr( f − 2/NTe), Fr( f + 2/NTe), Fr( f + 1/NTe) selon la loi suivante:

FB

( f ) = 0, 42 Fr( f ) + 0, 25 [Fr( f − 1/NTe) + Fr( f + 1/NTe)]

+ 0, 08 [Fr( f − 2/NTe) + Fr( f + 2/NTe)]

La décroissance des lobes secondaires est en 1

f 5 ; l’amplitude maximum des lobes secondaires est -87

db en dessous du lobe principal; Le lobe principal est 2 fois plus large que pour la fenêtre rectangulaire.

L’expression temporelle de la fenêtre est:

(t) = 0, 42 + 0, 5 cos(2πt/NTe) + 0, 08 cos(4πt/NTe)

FB

ou 0 ailleurs

− NTe

2

< t < NTe

2

1.5.3 Autres fenêtres: Gauss, Kaiser, Dolph-Chebychev

• Fenêtre de Gauss Fg(t)

Pour supprimer totalement les lobes de la transformée de Fourier de la fenêtre rectangulaire, on peut

utiliser une fenêtre telle que sa transformée de Fourier Fg( f ) soit une exponentielle

(cid:11)

Fg(ω) = exp

−

(cid:12)

(NωTe/2)2

4k

√

Le paramètre k est lié à la dispersion σ de l’exponentielle en prenant comme variable réduite u =

2k. On pourra donc régler la dispersion de Fg( f ), c’est-à-dire la largeur de

NωTe/2. σ est alors égal à

la bande de transition en faisant varier k.

Cherchons l’expression temporelle de cette fonction: Fg(t) = exp

puisque la transformée de Fourier conserve la loi gaussienne:

(cid:8)

, à une constante près

−4k(t/NTe)2

(cid:7)

(cid:11)

exp (−t2

2

) −→ exp (

(cid:12)

)

−ω2

2

La fenêtre gaussienne a donc pour expression:

1. Transformée deFourierDiscrète: TFD

Page13

Fg(t) = exp

(cid:7)

−4k(t/MT )2

(cid:8)

si | t | < NTe/2

Fg(t) = 0 si | t | > NTe/2

Le paramètre k permet de réaliser un compromis entre l’ondulation en bande atténuée et la largeur de la

bande de transition, ce que ne permettaient pas de faire les fenêtres décrites précédemment.

• Fenêtre de Kaiser FK

(t)

Cette fenêtre est une des plus efficaces: sa transformée de Fourier FK

(V ) =

FK

2

(πVa)

I0

(cid:13)

sin

(cid:14)

π

(cid:14)

V 2 − V 2

a

π

V 2 − V 2

a

( f ) a pour expression

(cid:15)

où V = f NTr, Va = faNTe,

première espèce.

(cid:14)

V 2 −V 2

a peut être complexe et I0

(x) est la fonction de Bessel modifiée de

Cette fonction dépend d’un paramètre Va qui permet de diminuer l’amplitude des lobes secondaires mais

qui augmente la largeur du lobe principal. Dans la plupart des applications, une valeur de Va comprise

entre 4/π et 9/π conviendra.

L’expression temporelle de la fenêtre de Kaiser, transformée de Fourier inverse de FK

( f ) est

4/π < Va < 9/π

(cid:13)

πVa

I0

(t) =

FK

(cid:14)

I0

1 − (2t/NTe)2

(πVa)

(cid:15)

si | t | < NTe/2

(t) = 0

FK

ailleurs

( f ) corresponde à V = 2, c’est-à-dire d’imposer que Va =

Comparaison avec la fenêtre de Hamming:

Pour obtenir une bande de transition égale à celle de la fenêtre de Hamming, il suffit d’imposer que le

3 puisque le

premier zéro de la fonction FK

= 1. Dans ces conditions, la fenêtre de Kaiser a 99,8

premier zéro est solution de l’équation V2 − V 2

a

% de son énergie dans le lobe principal alors que la fenêtre de Hamming n’a que 96,3 % de son énergie

dans ce lobe ; par conséquent, l’ondulation en bande atténuée sera meilleure dans le cas de la fenêtre de

Kaiser.

Comparaison avec la fenêtre de Blackman:

On peut obtenir la même largeur de lobe principal avec la fenêtre de Kaiser, en positionnant le premier

zéro à‘V = 3, c’est-à-dire en faisant Va = 2

2. A nouveau, l’ondulation en bande atténuée est inférieure

dans le cas de la fenêtre de Kaiser.

√

√

• Fenêtre de Dolph-Chebychev FD

La fenêtre de Doph-Tchebychev est celle qui est réalise le meilleur compromis largeur du lobe principal,

hauteur des lobes secondaires.

L’expression mathématique de cette fenêtre exprimée dans le domaine fréquentiel est:

( f ) =

FD

cos

(cid:7)

(cid:8)

Pcos−1(λcos πf Te)

ch [P arg ch(λ)]

où P = N-1, N impair.

Le paramètre λ permet de régler l’amplitude des ondulations.

les fonctions cos(x) et cos−1(x) sont des fonctions complexes.

Page 14

ChapterI. Transformée deFourierdiscrète: TFDetTFR

L’amplitude maximum δ des ondulations est liée au paramètre λ par la relation

δ =

1

ch [ P arg ch(λ) ]

L’expression temporelle de cette fenêtre n’a pas une forme simple ; la meilleure façon de l’obtenir étant

de calculer la transformée de Fourier inverse de FD

( f ) en utilisant la transformée de Fourier discrète.

Dans tous les cas, à nombre N de coefficients constant, on devra réaliser un compromis entre l’amplitude

Il faudra choisir entre une moins grande dispersion ou une

des ondulations et la largeur du lobe principal.

meilleure résolution.

1.6 Problèmes de visualisation de la TFD

Quand on lui présente un graphe discret, l’œil réalise une interpolation entre les points du dessin. Cette inter-

polation est d’autant plus réussie que les points sont rapprochés.

Pour observer à la fois un « beau » signal x(n) et un « beau » spectre, on ne peut visualiser le même « buffer

».

Pour le graphe temporel, on a intérêt à ce que Te << T0 mais si Te << T0 alors 1/Te sera trop grand par

rapport à 1/T0 et l’œil aura du mal à interpoler le graphe fréquentiel

. Pour améliorer le graphe fréquentiel on peut rajouter des 0 à la suite x(n), on ne change rien au résultat

/Te.

mais on augmente T0

On appelle cette opération « zero-padding » en anglais.

Exemple: soit x(t) dont la fréquence de Shannon (2 fmax) est 128 Hz = fSH

1. pour visualiser en « temps », on échantillonne une durée T à 1024 Hz = 8 fSH

2. pour visualiser le spectre, on échantillonne à 128 Hz une durée égale à 8 T en rajoutant des 0 à la suite

x(n).

On aura alors le même nombre de points sur une période de signal et de spectre et les deux graphes seront

bien visualisés.

1.7 Propriétés de la TFD et convolution circulaire

Elles sont analogues à celles de la Transformée de Fourier, mais il faut prendre en compte une notion de

périodicité des séquences.

1.7.1 Théorème de Parseval

Le théorème de Parseval, sous sa forme discrète, s’écrit:

N−1

∑

n=0

|x(nTe)|2 = 1

N

N−1

∑

k=0

|X(k)|2

Démonstration:

N−1

∑

n=0

N−1

∑

n=0

|x(nTe)|2 = 1

N2

|x(nTe)|2 = 1

N2

N−1

∑

n=0

N−1

∑

k=0

(cid:2)

N−1

∑

k=0

(cid:16)

N

Xke2 jπnk

(cid:2)

N−1

∑

l=0

(cid:3)

N

l e2 jπ−nl

X ∗

(cid:3)(cid:17)

N−1

∑

l=0

XkX ∗

l

N−1

∑

n=0

e2 jπn(k−l)

N

Or:

Si

k (cid:2)= l

N−1

∑

n=0

e2 jπn(k−l)

N = 1 − e2 jπ(k−l)

e2 jπ(k−l)/N

= 0

1. Transformée deFourierDiscrète: TFD

Page15

Et si

k = l

e2 jπn(k−l)

N = N

N−1

∑

n=0

(cid:2)

XkX ∗

l

(cid:3)(cid:17)

e2 jπn(k−l)

N

= 1

N

N−1

∑

k=0

|2

|Xk

N−1

∑

n=0

On en déduit:

(cid:16)

N−1

∑

n=0

|x(nTe)|2 = 1

N2

N−1

∑

k=0

N−1

∑

l=0

1.7.2 Théorème de la convolution discrète

Avant de présenter les résultats concernant la convolution discrète, on a besoin de définir les notions de convo-

lution circulaire et de convolution linéaire.

Convolution circulaire:

Soit 2 suites périodiques (x(n)) et (y(n)) de période N. La convolution circulaire de ces 2 suites donne la suite

(z(n)) de période N définie par:

(z(n)) = (x(n)) ⊗ (y(n)) =

x(i)y((cid:8)n − i(cid:8))

pour

n ∈ [0, N − 1] ,

(cid:3)

(cid:2)

N−1

∑

i=0

où la notation ||n − i|| signifie (n − i) modulo N.

Convolution linéaire:

La convolution linéaire d’une période de (x(n)) et d’une période de (y(n)) conduit quant-à-elle à une suite

(u(n)) de longueur 2N − 1 valant:

(u(n)) = (x(n)) ∗ (y(n)) =

(cid:3)

x(i)y(n − i)

pour

n ∈ [0, 2N − 1]

(cid:2)

N−1

∑

i=0

EXEMPLE:

Soit les suites (x(n)) et (y(n)) périodiques de période N = 3, telles que

x(n) = y(n) = 1

pour n entre 0 et 2.

La suite (z(n)), convolution circulaire des suites (x(n)) et (y(n)) est périodique de période N = 3, et vaut

z(n) = 3 pour n entre 0 et 2. La suite (u(n)), convolution linéaire des suites (x(n)) et (y(n)) est de durée

2N − 1 = 5, et vaut:

z(0) = 1, z(1) = 2, z(2) = 3, z(3) = 2, z(4) = 1.

La suite (z(n)) peut s’obtenir en répétant périodiquement la suite (u(n)) avec la période N.

Une période de xn

Une période yn

Une période zn

Suite un

Suite zn obtenue en rendant un périodique

Page 16

ChapterI. Transformée deFourierdiscrète: TFDetTFR

Théorème de la convolution discrète circulaire La TFD de la suite (z(n)) convolution circulaire de 2 suites

périodique (x(n)) et (y(n)) de période N, est le produit des TFD des suites (x(n)) et (y(n)):

z(n) = x(n) ⊗ y(n) ⇒ T FD(z(n)) = T FD(x(n))T FD(y(n))

(I.1)

où le symbole ⊗ représente la convolution circulaire.

Réciproquement, la suite p(n) produit des suites x(n) et y(n), a pour TFD une suite P(k) qui est la convo-

lution circulaire des suites X(k) et Y (k):

avec P(k) = T FD(p(n)), X(k) = T FD(x(n)),Y (k) = T FD(y(n)).

p(n) = x(n)y(n) ⇒ P(k) = X(k) ⊗Y (k)

Démonstration de (I.1)

(cid:2)

(z(n)) = (x(n)) ⊗ (y(n)) =

(cid:3)

x(i)y((cid:8)n − i(cid:8))

N−1

∑

i=0

(cid:2)

n ∈ [0, N − 1]

pour

(cid:3)

Z(n) =

Z(n) =

Z(n) =

N−1

∑

i=0

N−1

∑

i=0

(cid:2)

z(i)e

(cid:2)

N−1

∑

k=0

N−1

∑

k=0

− j2πni

N =

N−1

∑

i=0

N−1

∑

k=0

x(k)y((cid:8)i − k(cid:8))

(cid:3)

x(k)e

− j2πnk

N y((cid:8)i − k(cid:8))e

− j2πn(i−k)

N

(cid:3)

− j2πni

e

N

(cid:2)

N−1

∑

k=0

=

N−1

∑

i=0

x(k)e

− j2πnk

N y((cid:8)i − k(cid:8))e

− j2πn(cid:8)i−k(cid:8)

N

(cid:3)

x(k)e

− j2πnk

N

y(k)e

− j2πnk

N

= X(n)Y (n)

(cid:3) (cid:2)

N−1

∑

k=0

Relation entre convolution discrète linéaire et convolution continue

Soit x(t) et y(t) de durées finies. La convolution de x(t) avec y(t) s’écrit u(t):

+∞(cid:1)

u(t) =

x(τ)y(t − τ)dτ

−∞

Échantillonnons x(t) et y(t) à fe = 1/Te. On obtient alors P échantillons pour x et Q échantillons pour y.

On peut approcher l’intégrale u(t) par la méthode de l’intégration rectangulaire (de pas Te). La suite vn

ainsi obtenue (au terme multiplicatif Te près) correspond à une convolution discrète linéaire (et non circulaire)

des suites x(n) et y(n).

v(n) =

1.7.3 Théorème du retard circulaire

Soit la suite x(n) périodique, de période N.

P+Q−1

∑

k=0

x(k)y(n − k)

Soit la suite yn obtenue en retardant x(n) de ko échantillons. La suite y(n) est périodique de période N et

sa TFD Y (k) se déduit de celle de x(n) par:

où Y (k) et X(k) sont les TFD de x(n) et y(n).

Y (k) = X(k)e− j2πkko/N

2 Transformée de Fourier Rapide TFR, Fast Fourier transform FFT

La Transformée de Fourier Rapide (notée par la suite FFT) est simplement une TFD calculée selon un algo-

rithme permettant de réduire le nombre d’opérations et, en particulier, le nombre de multiplications à effectuer.

Il faut noter cependant, que la réduction du nombre d’opérations arithmétiques à effectuer, n’est pas synonyme

de réduction du temps d’exécution. Tout dépend de l’architecture du processeur qui exécute le traitement.

Pour calculer une TFD, on doit calculer N valeurs X(k):

X(k) =

N−1

∑

n=0

x(n)e

− j2π n k

N

et ceci pour k ∈ [0, N − 1].

Si on effectue le calcul directement sans algorithme efficace, on doit effectuer:

(cid:6)

N2

N(N − 1)

multiplications complexes

additions complexes

Il existe différents algorithmes de FFT. Le plus connu est sûrement celui de Cooley-Tukey (appelé aussi à

entrelacement temporel ou à « decimation in time ») qui réduit à

N

2

log2

(N)

le nombre de multiplications.

Il existe deux versions de l’algorithme:

• FFT avec entrelacement temporel,

• FFT avec entrelacement fréquentiel.

L’algorithme nécessite que N soit une puissance de 2. Le principe de l’algorithme consiste à décomposer le

calcul de la TFD d’ordre N = 2l en l étapes successives.

2.1 FFT avec entrelacement temporel

Illustrons tout d’abord la méthode par un exemple pour N = 4.

Les données sont notées x(n) et la suite TFD X(n).

La notation w représente e− j2π/N, c’est-à- dire e− j2π/4. On peut remarquer que wN = 1 et wN/2 = −1.

Pour N = 4, w4 = 1

et w2 = −1.

la suite TFD s’écrit:

X(0) = x(0) + x(1) + x(2) + x(3) = (x(0) + x(2)) + (x(1) + x(3))

X(1) = x(0) + w1x(1) + w2x(2) + w3x(3) = (x(0) − x(2)) + w1 (x(1) − x(3))

X(2) = x(0) + w2x(1) + w4x(2) + w6x(3) = (x(0) + x(2)) − (x(1) + x(3))

X(3) = x(0) + w3x(1) + w6x(2) + w9x(3) = (x(0) − x(2)) − w1 (x(1) − x(3))

Les données (x(0), x(1), . . . , x(N − 1)) sont regroupées en 2 paquets: un paquet formé des données d’indices

pairs (x(0), x(2), . . . , x(N − 2)) et un paquet formé des données d’indices impairs (x(1), x(3), . . . , x(N − 1)).

Soit pour N = 4, un paquet (x(0), x(2)) et un paquet (x(1), x(3)).

Puis sur chaque paquet on effectue une DFT d’ordre N/2 et on combine les résultats de ces 2 DFT pour obtenir

celle d’ordre N. Ce qui donne, toujours pour N = 4:

Page 18

ChapterI. Transformée deFourierdiscrète: TFDetTFR

x0

x2

x1

x3

TFD

ordre

N/2=2

TFD

ordre

N/2=2

Y0 = x0+x2

Y1 = x0 - x2

X0=Y0+Z0=x0+x1+x2+x3

X1=Y1+w1Z1=x0+w1x1-x2-w1x3

w1

Z0 = x1+x3

Z1 = x1 - x3

w1

X2=Y0 - Z0=x0 - x1+x2 - x3

X3=Y1 - w1Z1=x0 - w1x1 - x2 +w1x3

Pour obtenir les 4 valeurs X(k), il suffit donc de calculer 2 DFT d’ordre N/2 = 2 et de combiner les résultats

2 à 2 à l’aide d’une addition et d’une multiplication au maximum, pour chaque valeur X(k). Cette étape est

appelée étage de « papillons », pour des raisons évidentes liées à la forme du schéma de calcul. Ce résultat se

généralise à toute valeur valeur de N multiple de 2. En effet:

x(n)e

− j2π nk

N

X(k) =

X(k) =

X(k) =

X(k) =

N−1

∑

n=0

N/2−1

∑

i=0

N/2−1

∑

i=0

N/2−1

∑

i=0

x(2i)e

− j2π2ik

N +

N/2−1

∑

i=0

x(2i + 1)e

− j2π2(i+1)k

N

x(2i)e

− j2π ik

N/2 + e− j2π k

N

N/2−1

∑

i=0

x(2i + 1)e

− j2π ik

N/2

y(i)e

− j2π ik

N/2 + wk

N/2−1

∑

i=0

z(i)e

− j2π ik

N/2

On note y(i) = x(2i) et z(i) = x(2i + 1), pour i ∈ [0, (N/2 − 1)]. On remarque que les 2 termes de la somme

donnant X(k) se déduisent directement des 2 TFD d’ordre N/2 des suites y(i) et z(i) de N/2 points. On note

ces TFD Y (k) et Z(k).

Ainsi pour k ≤ N/2 − 1, les 2 termes de la somme se déduisent des termes de rang k de Y (k) et Z(k):

X(k) =

N/2−1

∑

i=0

Pour k ∈ [N/2, (N − 1)], on peut écrire k = k(cid:11) + N/2, avec k(cid:11) ∈ [0, (N/2 − 1)]. De plus, comme quelque soit i

entier e− j2πi = 1, on peut déduire X(k) des termes de rang k − N/2 des 2 TFD Y (k) et Z(k):

N/2 = Y (k) + wkZ(k)

N/2−1

∑

i=0

N/2 + wk

y(i)e

− j2π ik

− j2π ik

z(i)e

X(k) =

X(k) =

y(i)e

− j2π ik

N/2 + wk

N/2−1

∑

i=0

z(i)e

− j2π ik

N/2

y(i)e

− j2π i(k +N/2)

N/2 + wk

N/2−1

∑

i=0

− j2π i(k +N/2)

N/2

z(i)e

X(k) =

N/2−1

∑

i=0

X(k) = Y (k − N/2) + wkZ(k − N/2)

N/2 + wk

y(i)e

− j2π ik

z(i)e

− j2π ik

N/2

N/2−1

∑

i=0

N/2−1

∑

i=0

N/2−1

∑

i=0

En conclusion, pour tout N multiple de 2, on peut calculer chaque terme X(k) de la TFD d’ordre N en com-

binant, à l’aide d’au plus 1 multiplication et 1 addition, 2 termes des TFD d’ordre N/2 des 2 suites y(i) et z(i)

de longueur N/2, formées respectivement des termes d’indices pairs et des termes d’indices impairs de la suite

x(n). En notant Y (k) et Z(k) les TFD d’ordre N/2 de ces suites on peut écrire:

(cid:11)

Pour

k ∈

X(k) = Y (k) + wkZ(k)

(cid:12)

− 1

0, N

2

2. Transformée deFourierRapideTFR,FastFouriertransform FFT

Page19

Pour

k ∈

(cid:12)

, N − 1

(cid:11)

N

2

X(k) = Y (k − N/2) + wkZ(k − N/2)

On appelle « papillon », l’étape de calcul consistant à calculer 2 points de la TFD d’indices distants de N/2,

par exemple X(k) et X(k + N/2) avec k ∈ [0, N/2 − 1]. Le calcul de ce couple de valeurs de la TFD d’ordre N

utilise le couple de valeurs Y (k) et Z(k) des TFD d’ordre N/2:

Pour

k ∈

(cid:11)

0, N

2

(cid:12) (cid:6)

− 1

X(k) = Y (k) + wkZ(k)

X(k + N/2) = Yk

<...