FFT — transformée de Fourier rapide expliquée simplement

La FFT, ou transformée de Fourier rapide, est une méthode rapide pour calculer la transformée de Fourier discrète (DFT). Si vous partez d’échantillons régulièrement espacés, la DFT indique quelle quantité de chaque motif de fréquence discret apparaît dans ces échantillons.

Le point important est que la FFT ne change pas le résultat. Elle donne les mêmes valeurs de DFT que la formule directe, mais avec beaucoup moins de calculs répétés.

La FFT en une phrase

La FFT est un algorithme plus rapide pour obtenir les mêmes valeurs dans le domaine fréquentiel que celles déjà définies par la DFT.

Ce que mesure la DFT

Supposons que vous ayez des échantillons $x_0, x_1, \dots, x_{N-1}$. La DFT produit des nombres $X_0, X_1, \dots, X_{N-1}$ définis par

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Chaque $X_k$ mesure à quel point les données correspondent à un motif de fréquence discret.

Si les échantillons sont régulièrement espacés avec une fréquence d’échantillonnage $f_s$, alors les cases de fréquence adjacentes sont espacées de

$$\frac{f_s}{N}$$

Cette condition est importante. Sans fréquence d’échantillonnage connue, vous avez toujours des cases de DFT, mais vous ne pouvez pas les étiqueter comme des fréquences physiques telles que les hertz.

Pourquoi la FFT est plus rapide

Une FFT est une famille d’algorithmes permettant de calculer efficacement la DFT. L’idée principale consiste à réutiliser la structure des facteurs exponentiels complexes au lieu de recalculer depuis zéro des sommes presque identiques.

La version la plus facile à visualiser est la FFT radix-2. Elle fonctionne le plus naturellement quand $N$ est une puissance de $2$, et elle découpe une transformée de longueur $N$ en deux transformées de longueur $N/2$ avant de combiner les résultats.

Pour la DFT directe, la quantité de calcul croît de l’ordre de $N^2$. Pour les méthodes FFT courantes, elle tombe à environ $N \log N$.

C’est cet écart qui rend les FFT importantes en pratique. Pour de petites entrées, les deux méthodes peuvent sembler acceptables. Pour de grandes entrées, la FFT est nettement plus rapide.

Comment la FFT divise le travail

Au lieu de comparer directement chaque échantillon à chaque motif de fréquence, la FFT décompose le problème en transformées plus petites, puis les recombine avec des facteurs de phase.

Une décomposition standard est :

1. Mettre les échantillons d’indice pair dans une liste.
2. Mettre les échantillons d’indice impair dans une autre liste.
3. Calculer des transformées plus petites sur ces listes.
4. Combiner les deux moitiés.

C’est une approche diviser pour régner appliquée à l’analyse fréquentielle.

Exemple de FFT à 4 points

Prenons le signal à 4 points

$$x = [1, 0, 1, 0]$$

Ce motif alterne entre $1$ et $0$, donc on s’attend à une certaine structure fréquentielle plutôt qu’à un résultat complètement plat.

Séparons-le en indices pairs et impairs :

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

La DFT à 2 points de la partie paire est

$$E = [2, 0]$$

et la DFT à 2 points de la partie impaire est

$$O = [0, 0]$$

Pour une FFT à 4 points, l’étape de combinaison est

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

où

$$W_4 = e^{-i 2 \pi / 4}$$

Comme $O_k = 0$, la combinaison est particulièrement simple :

$$X = [2, 0, 2, 0]$$

Interprétons maintenant le résultat.

$X_0 = 2$ est le terme de fréquence nulle, donc il reflète la valeur moyenne non nulle des échantillons. La valeur non nulle en $X_2$ capture la partie alternée du motif dans ce cas à 4 points. Si vous soustrayez d’abord la moyenne, le terme $X_0$ disparaît et la composante alternée ressort plus clairement.

Cet exemple est petit, mais l’idée se généralise : on résout des transformées plus petites, puis on les combine au lieu de reconstruire toute la somme à chaque fois.

Erreurs fréquentes avec la FFT

Considérer la FFT et la DFT comme des résultats différents

Ce n’est pas le cas. La FFT est une méthode plus rapide pour calculer la DFT.

Lire les cases comme des fréquences physiques trop tôt

Les positions des cases ne deviennent des fréquences physiques que lorsque l’espacement des échantillons est connu. Si la fréquence d’échantillonnage est $f_s$, alors l’espacement des cases est $f_s/N$ pour des échantillons régulièrement espacés.

Supposer que le zero-padding ajoute de nouvelles informations

Le zero-padding peut rendre un spectre plus lisse parce qu’il échantillonne plus finement la transformée sous-jacente, mais il n’ajoute pas de nouvelles données mesurées.

Négliger la préparation du signal

La suppression de la moyenne, le fenêtrage et des choix d’échantillonnage soignés peuvent beaucoup compter. Si ces conditions sont ignorées, la sortie de la FFT peut rester mathématiquement correcte pour les échantillons donnés, tout en étant trompeuse pour l’interprétation.

Où la FFT est utilisée

La FFT apparaît partout où l’on a besoin d’informations fréquentielles rapides à partir de données échantillonnées. Parmi les exemples courants, on trouve l’analyse spectrale, le filtrage, le traitement d’image, l’analyse vibratoire, la résolution numérique d’équations différentielles, ainsi que les calculs rapides de polynômes ou de convolution.

La raison est pratique : de nombreuses opérations deviennent plus simples ou plus rapides après être passées du domaine des échantillons au domaine fréquentiel.

Essayez un cas similaire

Prenez $8$ échantillons régulièrement espacés d’une onde sinusoïdale sur une période complète et calculez la DFT avec une calculatrice ou un script. Ajoutez ensuite un décalage constant et comparez la nouvelle sortie. La valeur plus forte en $X_0$ est une manière simple de voir ce que la FFT sépare.