Leçon 4 sur 5
La transformée de Fourier rapide (FFT)
Je sais expliquer pourquoi la FFT est rapide, dérouler l'algorithme radix-2 à décimation temporelle sur 4 ou 8 points et comparer son coût à celui du calcul direct de la TFD.
- 1 h 10
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Évaluer le coût du calcul direct de la TFD
- Établir la décomposition radix-2 à décimation temporelle et l'équation du papillon
- Dérouler une FFT de 4 ou 8 points avec l'ordre à bits inversés
- Citer les principales applications de la FFT (analyse spectrale, convolution rapide, OFDM)
Avant de commencer : Leçon 3 (TFD, racines de l'unité, convolution circulaire) ; notion de complexité d'un algorithme.
1Je découvre
Le téléphone d'un étudiant de Labé affiche en temps réel le spectre du son capté par son micro grâce à une petite application d'accordeur de guitare. À chaque fraction de seconde, il calcule la TFD de plusieurs milliers d'échantillons. Avec la formule directe de la leçon précédente, une TFD de 4 096 points demande environ 16,8 millions de multiplications complexes : beaucoup trop pour un calcul répété des dizaines de fois par seconde sur un téléphone.
L'application utilise en réalité la transformée de Fourier rapide (FFT, Fast Fourier Transform), popularisée par Cooley et Tukey en 1965. Elle donne exactement le même résultat, mais avec environ 25 000 multiplications.
Comment la FFT parvient-elle à calculer la TFD aussi vite, et comment dérouler l'algorithme ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.
Voir toutes les leçons de Traitement numérique des signaux 1