DFT et FFT : la transformée de Fourier sur ordinateur
Définition de la DFT, résolution et fuite spectrale, fenêtres, l'algorithme FFT avec le papillon et son coût, convolution rapide, OFDM, compression et radar.
https://www.electronics-engineering.com/fr/dft-fft-transformee-de-fourier-rapide/
La transformée de Fourier de la leçon de Méthodes mathématiques est une intégrale sur un signal continu et infini. Sur un ordinateur on dispose de
échantillons. La transformée de Fourier discrète (DFT) est la version pour les signaux échantillonnés, et la FFT (Fast Fourier Transform, transformée de Fourier rapide) est l’algorithme qui la calcule efficacement. Introduite sous sa forme moderne par Cooley et Tukey en 1965, elle est considérée comme l’un des algorithmes les plus importants du XXe siècle : elle se trouve dans tout oscilloscope numérique, dans le Wi-Fi, la 4G et la 5G, dans la compression MP3 et JPEG, dans le radar.
La DFT
Étant donnés
échantillons
, pris à la fréquence d’échantillonnage
, la DFT est
![Rendered by QuickLaTeX.com \[ X_k = \sum_{n=0}^{N-1}x_n\,e^{-2\pi i\,kn/N},\qquad k = 0, 1, \dots, N - 1 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-ef54ed75e73cbd6808048499764edd7a_l3.png)
et la transformée inverse
![Rendered by QuickLaTeX.com \[ x_n = \frac1N\sum_{k=0}^{N-1}X_k\,e^{2\pi i\,kn/N} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-3bf57ea528dda71f864307e7612fdbc0_l3.png)
Le coefficient
mesure à quel point le signal ressemble à une sinusoïde qui fait
périodes dans la fenêtre de
échantillons, c’est-à-dire à la fréquence
. La résolution en fréquence est
: distinguer deux fréquences proches demande de longues fenêtres.

Deux propriétés à retenir.
- Pour un signal réel
: la seconde moitié du spectre est le miroir de la première, et les fréquences utiles vont de 0 à
(la fréquence de Nyquist). C’est le même phénomène que le repliement. - La DFT traite le signal comme s’il était périodique de période
. Si la fenêtre ne contient pas un nombre entier de périodes, le début et la fin ne se raccordent pas et le spectre « s’étale » sur les cases voisines (fuite spectrale). On la réduit en multipliant le signal par une fenêtre qui tombe en douceur à zéro sur les bords (Hann, Hamming, Blackman) : l’option « fenêtre » des analyseurs de spectre et des oscilloscopes.
Le coût et l’idée de la FFT
Calculée directement, la DFT demande
sommes de
termes :
multiplications complexes. Avec
cela fait
opérations.
La FFT exploite la structure des exponentielles. Avec
pair, on sépare les échantillons d’indice pair et impair :
![Rendered by QuickLaTeX.com \[ X_k = \sum_{m=0}^{N/2-1}x_{2m}\,e^{-2\pi i\,km/(N/2)} + e^{-2\pi i\,k/N}\sum_{m=0}^{N/2-1}x_{2m+1}\,e^{-2\pi i\,km/(N/2)} = E_k + W^k\,O_k \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-aa5006f9a093564b879eace99cd69fea_l3.png)
et
sont les DFT, de longueur
, des échantillons pairs et impairs, et
. De plus, comme
et
ont la période
et que
:
![]()
Une multiplication donne deux coefficients (le « papillon »). Une DFT de longueur
devient deux DFT de longueur
plus
multiplications ; en répétant jusqu’à la longueur 1, avec
il y a
niveaux. Le coût total est
![]()
multiplications. Avec
(environ
) : environ
au lieu de
, cent mille fois moins. C’est la différence entre un calcul de quelques millisecondes et un calcul de plusieurs heures.
La convolution rapide
Convoluer directement deux suites de longueur
coûte
opérations. Avec le théorème de convolution (leçon sur la transformée de Fourier), on prend la FFT des deux, on multiplie les spectres et on prend la FFT inverse : un coût proportionnel à
. C’est ainsi qu’on applique des filtres FIR très longs, qu’on obtient les effets de réverbération à partir d’une réponse impulsionnelle, et qu’on multiplie des entiers énormes.
Applications
- Analyse spectrale. La fonction FFT des oscilloscopes numériques montre les harmoniques d’un signal : la distorsion d’un amplificateur ou les perturbations du secteur à 50/60 Hz se voient tout de suite.
- OFDM. Le Wi-Fi, la 4G, la 5G et la télévision numérique transmettent des données sur des centaines ou des milliers de sous-porteuses orthogonales. L’émetteur construit le signal avec une FFT inverse, le récepteur le sépare avec une FFT. Sans algorithme rapide ces techniques ne pourraient pas tenir dans un téléphone.
- Compression. MP3 et AAC travaillent sur une transformée apparentée (la MDCT) et éliminent les composantes que l’oreille n’entend pas ; JPEG utilise la transformée en cosinus discrète sur des blocs de 8×8 pixels.
- Radar et sonar. La distance et la vitesse des cibles se trouvent à partir des fréquences du signal reçu, calculées avec la FFT : c’est ainsi que fonctionnent les radars automobiles à 77 GHz.
Complétion par des zéros et résolution
Ajouter des zéros aux échantillons avant la FFT (zero padding) rend le spectre plus dense et plus agréable à regarder, mais n’augmente pas la résolution : deux fréquences plus proches que
, avec
le nombre d’échantillons réels, restent indiscernables. Pour les séparer il faut une fenêtre d’observation plus longue. C’est le même principe d’incertitude temps-fréquence vu pour la transformée continue.





Ciao, sono l'autore di «DFT e FFT: la trasformata di Fourier al computer». Domande, dubbi, segnalazioni di errori o richieste di approfondimento sono benvenuti: scriveteli qui sotto e vi rispondo io. Potete anche votare la pagina con le stelle all'inizio dell'articolo.Hi, I am the author of “DFT and FFT: the Fourier transform on a computer”. Questions, doubts, error reports and requests for more detail are all welcome: write them below and I will answer. You can also rate the page with the stars at the top of the article.