Famille d'algorithmes calculant efficacement la transformée de Fourier discrète (TFD) d'une séquence en exploitant symétries, périodicités et factorisation récursive de la matrice TFD pour réduire la complexité arithmétique de O(N^2) à O(N log N) dans les cas usuels.

Principe

Utiliser la factorisation diviser-pour-régner (décompositions radix, opérations en «papillon») et les symétries des exponentielles complexes pour réutiliser les résultats intermédiaires (facteurs twiddle) et minimiser les calculs redondants de la TFD.

Démonstration

Calcul du spectre fréquentiel d'un signal échantillonné uniformément de longueur N=2^k avec une implémentation radix-2 FFT qui effectue O(N log N) opérations complexes, permettant une analyse spectrale en temps réel.

Mauvaise application

Appliquer une FFT standard à des données échantillonnées non uniformément sans rééchantillonnage ou à des séquences avec grande dynamique numérique sans mise à l'échelle, entraînant repliement spectral (aliasing) ou erreurs d'arrondi graves et des estimations spectrales trompeuses.

Conséquence

Permet la convolution rapide via multiplication dans le domaine fréquentiel, l'estimation spectrale en temps réel et le traitement d'images et de signaux à grande échelle qui serait infaisable avec une TFD naïve.

Inversion

Évaluation directe de la transformée de Fourier discrète par la somme de N^2 exponentielles complexes (TFD naïve), simple mais computationnellement impraticable pour grands N.

Limite

Suppose des données échantillonnées uniformément et nécessite typiquement des longueurs factorables (puissances de deux pour les implémentations radix optimales) ; la stabilité numérique dépend des détails d'implémentation et de l'échelle des données ; des algorithmes spécialisés (NFFT) traitent l'échantillonnage non uniforme.

Tension sémantique

Tension avec des transformées spécialisées (ondelettes, transformée de Fourier à court terme, NFFT) : la FFT est optimale pour l'analyse fréquentielle globale d'échantillons uniformes, mais moins adaptée lorsque la résolution locale temps-fréquence ou l'échantillonnage non uniforme est nécessaire.

Synthèse

Classe d'algorithmes transformant efficacement des séquences échantillonnées uniformément en coefficients fréquentiels par réutilisation récursive de la structure de la TFD, échangeant structure algorithmique contre une forte réduction du coût de calcul.