16. L ES TRANSFORMÉES DE F OURIER
Comme cela est sans intérêt, on préfère travailler sur une transformée de Fourier normalisée,
c’est-à-dire que l’on va effectuer une transformation linéaire des abscisses de tcllc sorte que
l’intervalle arbitraire (-a/2, +a/2) soit transformé en un intervalle dc longueur unité: soit
l’intervalle (-1/2, +1/2). Il faudra se souvenir de cette opération lorsque l’on désirera effectuer
une interpolation dans les transformées de Fourier.
9.2. Normalisation de la transformée de Fourier
Pour obtenir la normalisation, il suffit donc de poser :
n = 2nh = 1, N = 2n,
et pi = p2 = 0.
Il s’ensuit que :
h = l/N, T = 1: T = N = l/h.
Rappelons que T est la période de la transformée F(t). Puisqu’on ne calcule qu’un nombre
fini de points de la transformée, il est plus commode d’écrire en indice lc numcro du point
c’est-à-dire que l’on notera désormais : F(mr) = F,,, et f(kh>) = fi;
Comme dans le cas du calcul des fonctions trigonomctriqucs, II~IE poserons : WN =
exp(2nj/N). Par ce procédé, les transformées de Fourier discrctes normalisées s’tcrivent sinplement :
(16.22)
Il faut bien reconnaître que, jusqu’à présent, nous n’avons pas amélioré la technique de calcul,
et nous avons toujours besoin de N operations complexes pour mener à bien les calculs.
Maintenant, nous allons étudier un algorithme qui rend le temps de calcul non plus proportionnel à N2 rnais à N log, (N). P our des raisons qui deviendront évidentes par la suite, on
choisira un nombre N de données qui est une puissance de deux, et l’on posera N = 2’“.
9.3. Calcul de la transformée de Fourier au moyen de la technique de partage
Théorème - La transformée de Fourier d’une fonction quelconque cormue en N points est une
combinaison linéaire d’une transformée de Fourier de deux fonctions issues de la première et ne
comportant que N/2 points chacune.
Pour démontrer cette proposition, nous allons décomposer la fonction f(z) en deux fonctions,
l’une constituée des indices irnpairs fzk+i et l’autre des indices pairs fzk. Il est bien entendu que
l’on conserve l’ordre des échantillons dans la fonction f (cc).
On designe par u la fonction constituée par les échantillons d’indice pair et par v la fonction
constituée par les échantillons d’indice impair, chacune de ces fonctions comprenant N/2 points.
Les transformées de Fourier respectives de u et ‘ v sont désignées par U et V; on obtient leurs
263
Comme cela est sans intérêt, on préfère travailler sur une transformée de Fourier normalisée,
c’est-à-dire que l’on va effectuer une transformation linéaire des abscisses de tcllc sorte que
l’intervalle arbitraire (-a/2, +a/2) soit transformé en un intervalle dc longueur unité: soit
l’intervalle (-1/2, +1/2). Il faudra se souvenir de cette opération lorsque l’on désirera effectuer
une interpolation dans les transformées de Fourier.
9.2. Normalisation de la transformée de Fourier
Pour obtenir la normalisation, il suffit donc de poser :
n = 2nh = 1, N = 2n,
et pi = p2 = 0.
Il s’ensuit que :
h = l/N, T = 1: T = N = l/h.
Rappelons que T est la période de la transformée F(t). Puisqu’on ne calcule qu’un nombre
fini de points de la transformée, il est plus commode d’écrire en indice lc numcro du point
c’est-à-dire que l’on notera désormais : F(mr) = F,,, et f(kh>) = fi;
Comme dans le cas du calcul des fonctions trigonomctriqucs, II~IE poserons : WN =
exp(2nj/N). Par ce procédé, les transformées de Fourier discrctes normalisées s’tcrivent sinplement :
(16.22)
Il faut bien reconnaître que, jusqu’à présent, nous n’avons pas amélioré la technique de calcul,
et nous avons toujours besoin de N operations complexes pour mener à bien les calculs.
Maintenant, nous allons étudier un algorithme qui rend le temps de calcul non plus proportionnel à N2 rnais à N log, (N). P our des raisons qui deviendront évidentes par la suite, on
choisira un nombre N de données qui est une puissance de deux, et l’on posera N = 2’“.
9.3. Calcul de la transformée de Fourier au moyen de la technique de partage
Théorème - La transformée de Fourier d’une fonction quelconque cormue en N points est une
combinaison linéaire d’une transformée de Fourier de deux fonctions issues de la première et ne
comportant que N/2 points chacune.
Pour démontrer cette proposition, nous allons décomposer la fonction f(z) en deux fonctions,
l’une constituée des indices irnpairs fzk+i et l’autre des indices pairs fzk. Il est bien entendu que
l’on conserve l’ordre des échantillons dans la fonction f (cc).
On designe par u la fonction constituée par les échantillons d’indice pair et par v la fonction
constituée par les échantillons d’indice impair, chacune de ces fonctions comprenant N/2 points.
Les transformées de Fourier respectives de u et ‘ v sont désignées par U et V; on obtient leurs
263