L'algorithme de calcul de transformée de Fourier rapide

Cet algorithme célèbre a été inventé par Cooley et Tukey, ingénieurs dans le centre de recherche d'IBM au début des années 1960. Il a eu, du fait de son efficacité, un impact considérable sur le développement des applications en traitement numérique des signaux. Un calcul de transformée de Fourier discrète est un calcul de produit d'une matrice par un vecteur. Il nécessite donc multiplications/additions de nombres complexes. Si on suppose qu'un calculateur effectue opérations par seconde, un calcul de transformée sur un signal de échantillons nécessitera s. Un calcul sur une image de taille nécessitera soit opérations et une quinzaine de minutes de calcul. Si on envisage de traiter des données dans un domaine à trois dimensions (sur des vecteurs de taille ) il faudrait alors effetuer soit opérations, ce qui nécessite quelques dizaines d'années. La transformée de Fourier rapide réduit considérablement le nombre d'opérations à effectuer: au lieu d'effectuer opérations il suffira d'en faire . Dans les trois exemples précédents on aura à faire , et opérations ce qui nécessitera respectivement , et s ... Pour expliquer cet algorithme, nous utiliserons la récursivité en montrant que le calcul d'une transformée de Fourier de taille se ramène au calcul de deux transformée de Fourier de taille suivi de multiplications. On veut calculer Pour
(191)

On pose si est pair et si est impair. s'écrit alors, en posant
(192)

Nommons les séquences
(193)
(194)
(195)
(196)

Avec ces notations, l'eq. (192) devient
(197)

Dans la deuxième sommation du membre de droite de l'équation (197), le facteur ne dépend pas de . On a donc l'écriture Pour
(198)

Si
(199)

on reconnait dans les deux expressions entre crochets les transformées de Fourier discrètes des séquences des échantillons de numéro pair et des échantillons de numéro impair que nous nommons et Pour
(200)

Lorsque , on peut écrire
(201)

et remarquer que
(202)

L'équation (198) devient alors Pour
    (203)
     

et, en remarquant que
(204)

en tenant compte de (200), on a une écriture analogue à l'éq. (200) Pour
(205)

On peut changer le nom de la variable en et regrouper les deux équations (200) et (205) Pour
    (206)
    (207)

Les calculs correspondants sont représentés dans la figure 53.

Figure 53: Schéma de l'enchaînement des calculs de la transformée de Fourier rapide

Cette formulation se traduit directement par une implémentation récursive. Toutefois la programmation de la plupart des processeurs est fondée sur une implémentation différente. On commence par effectuer toutes les opérations de réarrangement des données : Pour un vecteur de longueur , construction d'un tableau de données d'adresse paire et d'un tableau de données d'adresse impaire de longueur , ce rangement étant reproduit pour les deux moitiés de tableau de taille , puis les quatre quarts de tableau de taille , etc... Ceci revient à ranger la données à l'adresse obtenue en lisant le code binaire de en sens inverse comme on peut le voir dans la table 1.

Tableau 1: Réordonnancement des données préalable dans le calcul de la transformée de Fourier rapide
abcd bcda cdba dcba
0000 0000 0000 0000
0001 0010 0100 1000
0010 0100 1000 0100
0011 0110 1100 1100
0100 1000 0010 0010
0101 1010 0110 1010
0110 1100 1010 0110
0111 1110 1110 1110
1000 0001 0001 0001
1001 0011 0101 1001
1010 0101 1001 0101
1011 0111 1101 1101
1100 1001 0011 0011
1101 1011 0111 1011
1110 1101 1011 0111
1111 1111 1111 1111

On effectue ensuite la même opération sur chacun des deux tableaux. Ensuite on effectue séquentiellement les multiplications par les nombres complexes de la forme pour calculer les transformées de Fourier de taille 2, puis les transformées de taille 4, et ainsi de suite jusqu'à obtenir les 2 transformées de Fourier de taille et finalement la transformée de Fourier de taille .

Sous-sections
[ Table des matières ]