Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Analyse numérique

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/

Cette page vous a-t-elle été utile ? Notez-la :
moyenne 5,0 sur 1 vote

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 N é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 N échantillons x_0, x_1, \dots, x_{N-1}, pris à la fréquence d’échantillonnage f_s, la DFT est

    \[ X_k = \sum_{n=0}^{N-1}x_n\,e^{-2\pi i\,kn/N},\qquad k = 0, 1, \dots, N - 1 \]

et la transformée inverse

    \[ x_n = \frac1N\sum_{k=0}^{N-1}X_k\,e^{2\pi i\,kn/N} \]

Le coefficient X_k mesure à quel point le signal ressemble à une sinusoïde qui fait k périodes dans la fenêtre de N échantillons, c’est-à-dire à la fréquence f_k = k\,f_s/N. La résolution en fréquence est f_s/N : distinguer deux fréquences proches demande de longues fenêtres.

Un signal échantillonné fait de deux sinusoïdes et le module de sa DFT avec deux paires de raies
À gauche, 32 échantillons d’un signal fait de deux sinusoïdes, avec 3 et 7 périodes dans la fenêtre et la seconde d’amplitude moitié. À droite, le module de la DFT : deux raies en k = 3 et k = 7, de hauteurs proportionnelles aux amplitudes, et leurs images symétriques en N − 3 et N − 7.

Deux propriétés à retenir.

  • Pour un signal réel X_{N-k} = \overline{X_k} : la seconde moitié du spectre est le miroir de la première, et les fréquences utiles vont de 0 à f_s/2 (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 N. 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 N sommes de N termes : N^2 multiplications complexes. Avec N = 10^6 cela fait 10^{12} opérations.

La FFT exploite la structure des exponentielles. Avec N pair, on sépare les échantillons d’indice pair et impair :

    \[ 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 \]

E_k et O_k sont les DFT, de longueur N/2, des échantillons pairs et impairs, et W = e^{-2\pi i/N}. De plus, comme E et O ont la période N/2 et que W^{k + N/2} = -W^k :

    \[ X_k = E_k + W^kO_k,\qquad X_{k + N/2} = E_k - W^kO_k \]

Une multiplication donne deux coefficients (le « papillon »). Une DFT de longueur N devient deux DFT de longueur N/2 plus N/2 multiplications ; en répétant jusqu’à la longueur 1, avec N = 2^p il y a p = \log_2 N niveaux. Le coût total est

    \[ \frac N2\log_2 N \]

multiplications. Avec N = 10^6 (environ 2^{20}) : environ 10^7 au lieu de 10^{12}, 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 N coûte N^2 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 à N\log N. 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 f_s/N, avec N 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.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x