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) |
si 
est pair et 
si est impair. 
s'écrit alors, en posant 
Nommons les séquences
 |
 |
 |
(193) |
 |
|
 |
(194) |
|
|
 |
(195) |
 |
|
 |
(196) |
Avec ces notations, l'eq. (192) devient
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
Si
 |
(199) |
et des échantillons de numéro impair 
que nous
nommons 
et 
Pour
Lorsque
, on peut écrire
 |
(201) |
 |
(202) |
et, en remarquant que
 |
(204) |
On peut changer le nom de la variable
en 
et regrouper
les deux équations (200) et (205)
Pour
Les calculs correspondants sont représentés dans la figure 53. 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.
| 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