🎛️ Un signal et son spectre
Compose un signal de 3 sinusoïdes (fréquences f₁, f₂, f₃). La FFT calcule le spectre — les pics correspondent exactement à tes fréquences. C'est exactement ce que fait Shazam pour reconnaître une chanson.
Le signal du haut est la somme de 3 sinus. La FFT retrouve les 3 pics dans le spectre du bas. Magique.
📐 1822 : Fourier pose la question
Joseph Fourier (1768-1830) démontre dans sa « Théorie analytique de la chaleur » qu'une fonction « raisonnable » peut s'écrire comme somme infinie de sinusoïdes. C'est la série de Fourier. Sa généralisation continue est la transformée de Fourier :
F(ω) = ∫ f(t) · e^(−iωt) dt
F(ω) = amplitude complexe de la fréquence ω contenue dans f(t)
En numérique, on travaille sur N échantillons et on calcule la DFT (Discrete Fourier Transform) :
X[k] = Σ x[n] · e^(−2πi kn / N), k = 0, 1, ..., N−1
Calcul naïf : N multiplications par N échantillons = O(N²). Pour N = 1 million, cela fait 10¹² opérations — quelques heures même sur un ordinateur moderne. Inacceptable pour le temps réel.
⚡ 1965 : Cooley et Tukey trouvent l'astuce
En 1965, James Cooley (IBM Research) et John Tukey (Princeton + Bell Labs) publient un algorithme qui calcule la DFT en O(N log N). Pour N = 1 million, c'est ~20 millions d'opérations, soit 50 000 fois plus rapide.
L'idée centrale : diviser pour régner. Une DFT de taille N peut s'exprimer comme deux DFT de taille N/2 (indices pairs et impairs), combinées avec N/2 multiplications. Par récurrence :
T(N) = 2·T(N/2) + N → T(N) = O(N log N)
🕰️ Une histoire de redécouverte
En réalité, l'algorithme avait été découvert par Carl Friedrich Gauss en 1805 pour calculer les orbites des astéroïdes. Mais Gauss l'a écrit en latin, dans un cahier non publié de son vivant. Découvert seulement en 1977.
Cooley et Tukey ignoraient totalement cette préhistoire. Leur article de 1965 lance la révolution. Tukey raconte : Tukey conseillait John Kennedy sur la détection de tests nucléaires soviétiques. La détection sismique nécessitait des FFTs gigantesques. Cooley a écrit l'implémentation en quelques semaines à IBM.
📊 La FFT inverse : reconstruire le signal
Aussi vite que la FFT calcule le spectre, la FFT inverse reconstruit le signal à partir du spectre. Cela permet la boucle : signal → spectre → modifier → signal modifié.
Modifications possibles :
- Filtrer : supprimer certaines fréquences (basses = enlever le ronflement 50 Hz du secteur ; hautes = lisser le bruit).
- Compresser : garder seulement les fréquences importantes (base de MP3, JPEG).
- Égaliser : amplifier ou atténuer certaines bandes (équaliseur audio).
- Synthétiser : créer un son inexistant en mixant des fréquences.
🚀 Applications massives de la FFT
- Audio : MP3, AAC, Opus, Spotify, YouTube Music. Tous compressent en passant par la FFT pour identifier les fréquences inaudibles à supprimer.
- Image et vidéo : JPEG, MPEG, H.264, H.265, AV1 utilisent la DCT (Discrete Cosine Transform), variante de la FFT.
- Wi-Fi, 4G, 5G : la modulation OFDM (Orthogonal Frequency Division Multiplexing) utilise une FFT à chaque réception. Sans FFT, pas de connexion sans fil moderne.
- Radar : analyse Doppler (vitesse) via FFT du signal radar retourné. Météo, défense, automobile (ACC, freinage d'urgence).
- IRM (résonance magnétique) : la machine acquiert l'espace de Fourier de l'image. La reconstruction utilise une FFT inverse.
- Sismologie : détection des séismes, identification des essais nucléaires souterrains, analyse des ondes terrestres.
- Astronomie radio : radiotélescopes (FAST en Chine, ALMA au Chili) analysent les signaux par FFT pour cartographier le ciel.
- Shazam : reconnaît une chanson en quelques secondes en analysant les pics du spectre. Empreinte digitale acoustique.
- Multiplication de grands nombres : l'algorithme de Schönhage-Strassen (1971) multiplie deux entiers de N chiffres en O(N log N log log N) en passant par FFT. Utilisé dans tout calcul de précision arbitraire (RSA, cryptographie).
- Calcul scientifique : résolution d'équations aux dérivées partielles (Poisson, chaleur, ondes), simulation de fluides, prévisions météo.
- Finance quantitative : calibration de modèles, valorisation d'options.
- Génomique : alignement de séquences, motifs répétés.
🎓 La beauté mathématique
La FFT est l'archétype des algorithmes diviser-pour-régner élégants. Le code de base tient en 20 lignes :
function FFT(x):
N = length(x)
if N == 1: return x
pair = FFT(x[0::2])
impair = FFT(x[1::2])
X = array of N
for k = 0 to N/2 − 1:
t = exp(−2πi·k/N) * impair[k]
X[k] = pair[k] + t
X[k + N/2] = pair[k] − t
return X
Il y a aussi des variantes : FFT 2D pour les images, FFT sur entiers (Schönhage), FFT non équispacée pour les signaux irréguliers, Sparse FFT pour les spectres parcimonieux (qui s'exécute en O(K log N) où K est le nombre de pics, MIT 2012).
📐 Le lien avec ton programme
- Nombres complexes : e^(−2πi/N) est une racine N-ième de l'unité. Programme complexes 2BAC SM (formule de Moivre).
- Sommes : la DFT est une somme indexée. Programme 1BAC.
- Récurrence : la FFT est récursive. Algorithme « diviser pour régner ». Concept algorithmique central.
- Logarithmes : la complexité log N. Programme 2BAC SM.
- Périodicité et fréquences : sin/cos, période, fréquence. Programme trigonométrie 1BAC.
- Convolution : la FFT transforme la convolution (lente) en multiplication (rapide). Théorème de convolution. Concept fondamental en EDP et probabilités.