Cooley James

Quand un son est enregistré, l'ordinateur reçoit une longue suite de mesures. Pour savoir quelles notes ou quelles fréquences la composent, il peut comparer cette suite à de nombreuses oscillations. La transformée de Fourier discrète réalise cette séparation, mais son calcul direct devient vite lourd. L'algorithme de Cooley-Tukey réorganise les mesures en petits groupes, calcule leurs contributions, puis les rassemble. Il obtient le même résultat exact avec beaucoup moins d'opérations. Cette idée, publiée par James Cooley et John Tukey en 1965, est au cœur de la FFT.

L'algorithme de Cooley-Tukey est une famille de méthodes qui accélèrent le calcul de la transformée de Fourier discrète. Cette transformée convertit une suite de n échantillons, par exemple des mesures audio prises à intervalles réguliers, en coefficients décrivant les fréquences présentes. Le calcul direct compare chaque échantillon à chaque fréquence et demande de l'ordre de n² opérations.

Le principe est de décomposer le problème en sous-problèmes plus petits. Dans la variante radix-2, n doit être une puissance de 2 : les échantillons sont séparés selon leur indice pair ou impair, puis chaque moitié est elle-même traitée de la même façon. Les résultats sont enfin combinés par des additions, des soustractions et des rotations de phase. Si n=2ᵖ, cette organisation récursive ramène le coût à l'ordre de n log₂(n), noté O(n log n).

La FFT n'est donc pas une autre transformée : elle est une manière rapide de calculer la DFT, à résultat mathématique identique dans les mêmes conventions. D'autres variantes choisissent des facteurs différents de n et s'adaptent aux tailles qui ne sont pas des puissances de 2.

Considérons huit mesures successives, sans unité : [1, 0, 1, 0, 1, 0, 1, 0]. Elles décrivent une alternance régulière entre deux niveaux. On cherche les huit coefficients de Fourier associés, indexés par k de 0 à 7.

La séparation pair-impair donne la sous-suite paire [1, 1, 1, 1] et la sous-suite impaire [0, 0, 0, 0]. Leurs sommes valent respectivement 4 et 0.

À chaque niveau, Cooley-Tukey réutilise ces calculs dans des papillons, c'est-à-dire des combinaisons d'une addition et d'une soustraction pondérées par une rotation de phase. Ici, les contributions se concentrent sur les fréquences k=0 et k=4 : X₀=4 et X₄=4, tandis que X₁, X₂, X₃, X₅, X₆ et X₇ valent 0.

Le contrôle est direct : la somme des huit mesures vaut 4, ce qui donne X₀=4, et l'alternance sur un échantillon sur deux correspond à la composante k=4. La FFT retrouve ainsi le résultat de la DFT directe, avec une organisation de calcul plus économique.

Dans le traitement audio, la FFT transforme une fenêtre d'échantillons en un spectre. Le geste consiste à observer les coefficients obtenus pour repérer les fréquences dominantes, plutôt qu'à comparer séparément chaque mesure à chaque oscillation.

Dans les télécommunications, elle aide à séparer des composantes fréquentielles et à surveiller l'occupation d'un canal. La taille de la fenêtre et le rythme d'échantillonnage déterminent les fréquences que l'analyse peut distinguer.

En imagerie et en sciences de l'ingénieur, la même organisation sert à traiter des données discrètes dans une ou plusieurs dimensions. Lorsque la taille des données est favorable à une décomposition rapide, le gain de calcul devient particulièrement important.

La FFT ne doit pas être confondue avec la transformée de Fourier discrète, ou DFT. La DFT désigne la transformation mathématique elle-même ; la FFT désigne une famille d'algorithmes qui en calcule les coefficients plus rapidement. Pour la même suite et la même convention de normalisation, les deux doivent fournir les mêmes coefficients.

La FFT ne se confond pas non plus avec la transformée de Fourier continue. La première traite un nombre fini d'échantillons ; la seconde décrit une fonction continue et ses fréquences. Une suite de mesures issue d'un capteur appelle donc une DFT ou une FFT, après le choix d'une fenêtre et d'un échantillonnage.

La variante radix-2 suppose que le nombre n d'échantillons est une puissance de 2. Pour n=8, la décomposition est régulière ; pour n=6, cette variante ne s'applique pas directement. Il faut alors compléter les données, utiliser une décomposition par facteurs de 2 et 3, ou choisir un autre algorithme.

Une FFT ne crée pas une résolution fréquentielle infinie. Une fenêtre finie observe seulement une portion du signal : une fréquence située entre deux cases peut se répartir sur plusieurs coefficients, phénomène appelé fuite spectrale. Le résultat dépend aussi de la convention de normalisation, qui peut placer le facteur d'échelle à l'aller ou au retour.

Enfin, la notation O(n log n) décrit un ordre de croissance du nombre d'opérations, pas un temps d'exécution universel. Les constantes, la mémoire, l'architecture et la précision numérique peuvent modifier le gain observé.

Pour prolonger l'étude, l'article « De la transformation de Fourier à la transformée en cosinus discrète » relie la DFT à une transformation très utilisée en traitement des images. Cette lecture permet de voir comment une analyse fréquentielle discrète change de forme selon les symétries et les applications retenues.