Français
Menu

Qu'est-ce que Transformée de Fourier rapide (FFT) ?

Famille d'algorithmes qui calculent exactement la transformée de Fourier discrète (DFT) avec peu d'opérations. L'approche la plus connue (l'algorithme de Cooley-Tukey) divise de façon répétée une DFT sur N points en DFT de taille moitié et met en commun les calculs partagés, ce qui ramène le nombre d'opérations d'environ N² pour la définition à environ N log₂N. Pour N = 1024, cela représente environ 1/100. L'algorithme est le plus simple quand le nombre de points est une puissance de deux, mais il existe des méthodes pour les autres tailles. Outre l'analyse spectrale, il sert à la modulation et à la démodulation OFDM ainsi qu'au calcul rapide de longues convolutions.

Nom japonais: 高速フーリエ変換(FFT)

« Transformée de Fourier rapide (FFT) » apparaît dans 4 questions d'entraînement réparties sur 2 thèmes, dont Bases du traitement numérique du signal, Bases des communications sans fil.

Domaine: Bases du traitement numérique du signal

Pourquoi c'est rapide

Diviser une DFT sur N points en deux DFT sur N/2 points, l'une des échantillons de rang pair et l'autre des échantillons de rang impair, permet de reconstituer le résultat d'origine simplement en multipliant par des facteurs de rotation (twiddle factors) e^(−j2πk/N), puis en additionnant et en soustrayant. En répétant l'opération, on obtient log₂N étages d'environ N opérations chacun : le total est de l'ordre de N log₂N. En raison de sa forme, cette paire addition-soustraction s'appelle un papillon (butterfly).

Le gain de vitesse

Le rapport vaut N/log₂N : 1024 ÷ 10 = 102,4 pour N = 1024 et 65 536 ÷ 16 = 4096 pour N = 65 536. Plus le nombre de points est grand, plus le gain est important, ce qui rend la FFT indispensable pour les affichages de spectre en temps réel et pour des usages comme les récepteurs de communication, qui calculent de nombreuses DFT à la suite.

Convolution par la FFT

La convolution de deux suites devient une multiplication dans le domaine fréquentiel. Transformer les deux suites par FFT, les multiplier, puis revenir par FFT inverse permet donc de calculer la convolution d'un long filtre FIR avec moins d'opérations que le calcul direct. La multiplication de DFT correspond toutefois à une convolution circulaire : il faut donc égaliser les longueurs par remplissage par des zéros pour éviter le recouvrement circulaire aux extrémités.

S'entraîner : questions sur Transformée de Fourier rapide (FFT)

On suppose qu'une DFT sur N points demande environ N² opérations lorsqu'elle est calculée d'après sa définition, et environ N log₂N opérations avec la FFT (transformée de Fourier rapide). Pour N = 1024, quelle valeur est la plus proche de la réduction du nombre d'opérations obtenue par la FFT ?

  1. AEnviron 1/10
  2. BEnviron 1/100
  3. CEnviron 1/1000
Afficher la réponse et l'explication

Réponse : B. Environ 1/100

N² = 1024² ≈ 1,05 million et N log₂N = 1024 × 10 = 10 240 : le rapport vaut N/log₂N = 1024 ÷ 10 = 102,4, soit environ 1/100. L'écart se creuse quand N augmente ; pour N = 65 536, la réduction est d'environ 1/4096. La FFT réduit le travail en divisant de façon répétée une DFT en DFT de taille moitié et en mettant en commun les calculs partagés.

Questions fréquentes

Le nombre de points d'une FFT doit-il être une puissance de deux ?

Non. Une puissance de deux est souvent le cas le plus simple et le plus rapide, mais il existe des FFT à base mixte, qui décomposent la taille en facteurs 3, 5, etc., ainsi que des méthodes pour les tailles premières, et les bibliothèques courantes calculent n'importe quelle taille. Lorsqu'on préfère une puissance de deux, on peut augmenter le nombre de points par remplissage par des zéros.

Les résultats de la FFT sont-ils les mêmes que ceux de la DFT ?

Les deux calculent les mêmes valeurs : elles concordent donc aux erreurs d'arrondi près. La FFT n'est pas une approximation, mais un algorithme qui réorganise le calcul pour obtenir plus vite le même résultat.

« Transformée de Fourier rapide (FFT) » dans les explications

Questions mentionnant « Transformée de Fourier rapide (FFT) » (4)

  1. On suppose qu'une DFT sur N points demande environ N² opérations lorsqu'elle est calculée d'après sa définition, et environ N log₂N opérations avec la FFT (transformée de Fourier rapide). Pour N = 1024, quelle valeur est la plus proche de la réduction du nombre d'opérations obtenue par la FFT ?
  2. Un signal de 256 points est suivi de 768 zéros (remplissage par des zéros, ou zero padding), puis on calcule une DFT sur 1024 points. Par rapport au calcul de la DFT sur les 256 points tels quels, quelle affirmation est correcte ?
  3. Quelle description de l'OFDM (multiplexage par répartition orthogonale de la fréquence) est correcte ?
  4. En OFDM, quel est le but principal du préfixe cyclique (CP), qui copie une partie de la fin de chaque symbole au début de celui-ci ?

Termes associés

OFDM (multiplexage par répartition orthogonale de la fréquence) Résolution fréquentielle Convolution Décimation Équation aux différences Filtre à moyenne mobile Filtre FIR Filtre IIR Fonction de fenêtrage Fuite spectrale

Retour au glossaire