Histoire des mathématiques Algorithme

algorithme de Cooley et Tukey

Algorithme

algorithme de transformation de Fourier rapide

Traduit de l’anglais automatiquement — non relu. « fast Fourier Transform algorithm »

Pour comprendre

rédaction

Décomposer un signal

La transformée de Fourier rapide, ou FFT, décompose un signal en fréquences qui le composent. Au lieu d'effectuer un calcul direct demandant environ \(n^2\) opérations, elle organise le travail pour en demander de l'ordre de \(n \log n\). Elle coupe récursivement le problème en deux calculs plus petits, puis combine leurs résultats.

Rendre le numérique praticable

Ce gain de calcul a rendu praticable l'analyse de nombreux signaux numériques. Il intervient dans le traitement du son, des images et de données où l'on cherche les composantes périodiques d'une évolution. La FFT ne change pas le signal étudié : elle fournit une autre description, qui met en évidence les fréquences présentes et leur rôle dans la forme observée.

Repères historiques

  • algorithme déjà esquissé par Gauss vers 1805 dans un manuscrit resté inédit
  • redécouvert et publié par James Cooley et John Tukey en 1965

La figure superpose un signal composé en courbe épaisse et les trois fréquences pures pointillées que la FFT retrouve.

{ "boundingBox": [ -0.4, 2.1, 6.8, -2.1 ], "axis": true, "functions": [ { "expression": "sin(x)+0.5*sin(3*x)+0.3*sin(5*x)", "range": [ 0, 6.3 ], "color": "#2563eb", "width": 3, "label": "signal" }, { "expression": "sin(x)", "range": [ 0, 6.3 ], "color": "#dc2626", "width": 1, "dash": "dashed", "label": "fréquence 1" }, { "expression": "0.5*sin(3*x)", "range": [ 0, 6.3 ], "color": "#16a34a", "width": 1, "dash": "dashed", "label": "fréquence 3" }, { "expression": "0.3*sin(5*x)", "range": [ 0, 6.3 ], "color": "#9333ea", "width": 1, "dash": "dashed", "label": "fréquence 5" } ] }

Dates

premiere trace
esquissé par Gauss, manuscrit inédit approximative
publication
publié par Cooley et Tukey

Sources