Jouons à implémenter une transformée de Fourier rapide !
La transformée de Fourier est un outil essentiel dans de nombreux domaines, que ce soit en Physique, en traitement du signal, ou en Mathématiques. La méthode qui est probablement la plus connue pour la calculer numériquement s’appelle la FFT pour Fast Fourier Transform, ou Transformée de Fourier Rapide. Dans ce petit tutoriel, je vous propose d’essayer de comprendre et d’implémenter cet algorithme de manière efficace. J’utiliserais pour cela le langage Julia, mais il devrait vous être possible de suivre en utilisant d’autres langages tels que Python ou C. Nous comparerons les résultats obtenus avec ceux donnés par le portage en Julia de la bibliothèque FFTW.
Ce tutoriel S’adresse plutôt à des personnes ayant déjà eu l’occasion de rencontrer la transformée de Fourier, mais sans l’avoir pour autant déjà implémentée. Il se base en grande partie sur la troisième édition de Numerical Recipes1, que je ne saurais que vous encourager à consulter: c’est une mine d’or.
- William H. Press, Saul A. Teukolsky, William T. Vetterling, & Brian P. Flannery. (2007). Numerical Recipes 3rd Edition : The Art of Scientific Computing (3e éd.). Cambridge University Press.↩
Quelques rappels sur la transformée de Fourier discrète
- La transformée de Fourier
- De la transformée de Fourier à la transformée de Fourier discrète
- Calculer la transformée de Fourier discrète
- Pourquoi un algorithme de transformée de Fourier rapide ?
Implémentons la FFT
- Ma première FFT
- Analyse de la première implémentation
- Calculer la permutation inverse des bits
- Ma seconde FFT
- Le cas particulier d'un signal réel
- Une FFT pour les réels
- Optimisation des fonctions trigonométriques
Au terme ce tutoriel j’espère vous avoir aidé à comprendre les mécanismes qui font fonctionner le calcul de la FFT, et montré comment l’implémenter efficacement, modulo quelques simplifications. Personnellement, écrire ce tutoriel m’a permis de me rendre compte des grandes qualités de FFTW, l’implémentation de référence, que j’utilise au quotidien dans mon travail !
Cela devrait vous permettre de comprendre que pour certains cas d’utilisation, il peut être intéressant d’implémenter et d’optimiser sa propre FFT. Une application qui a peu été discutée dans ce tutoriel est le calcul de produits de convolution. Une méthode efficace dans le cas où on convolue des signaux de longueur comparable est de le faire un multipliant les deux transformées de Fourier puis en prenant la transformée de Fourier inverse. Dans ce cas, puisque la multiplication se fait terme à terme, il n’est pas nécessaire que la transformée de Fourier soit ordonnée. On pourrait donc imaginer une implémentation spéciale qui sauterait la partie permutation de bits inverse.
Une autre amélioration que l’on pourrait apporter concerne le calcul de la transformée de Fourier inverse. Il s’agit d’un calcul très similaire (seuls les coefficients multiplicatifs changent), et peut constituer un bon exercice pour expérimenter avec les codes donnés dans ce tutoriel.
Je tiens enfin à remercier @Gawaboumga, @Næ, @zeqL et @luxera pour leurs retours sur la bêta de ce tutoriel, et @Gabbro pour la validation !
