Scribd
Importer
24 vues7 pages

Introduction à la Transformée de Fourier

La Transformée de Fourier Rapide (FFT) est un algorithme qui optimise le calcul de la Transformée de Fourier Discrète (DFT) en réduisant sa complexité de O(N²) à O(N log N). Elle utilise une méthode de diviser pour régner et exploite les symétries de la DFT pour effectuer des calculs plus efficaces. La FFT a de nombreuses applications dans le traitement du signal, la compression d'image, l'analyse vibratoire, et bien d'autres domaines.

Transféré par

syusahou
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
24 vues7 pages

Introduction à la Transformée de Fourier

La Transformée de Fourier Rapide (FFT) est un algorithme qui optimise le calcul de la Transformée de Fourier Discrète (DFT) en réduisant sa complexité de O(N²) à O(N log N). Elle utilise une méthode de diviser pour régner et exploite les symétries de la DFT pour effectuer des calculs plus efficaces. La FFT a de nombreuses applications dans le traitement du signal, la compression d'image, l'analyse vibratoire, et bien d'autres domaines.

Transféré par

syusahou
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Transformée de Fourier Rapide (FFT)

FOKOU NZOKOU FRANCK ADAM 19M2451


TAPAH NGASSA CLAUDIA 20V2342
YUSAHOU SALIFUH 22Y1033
NGAH ABANDA STEVE JORDAN 19M2348
SAKTA NZIA PIERRICK MIGUEL 22Y1042

November 30, 2024


Introduction à la FFT

La Transformée de Fourier Rapide (FFT) est un algorithme


optimisé pour calculer la Transformée de Fourier Discrète (DFT)
d’un signal. Elle réduit la complexité de O(N 2 ) à O(N log N).
Principes de la FFT
▶ La FFT utilise une méthode de diviser pour régner.
▶ Elle exploite les symétries et les redondances de la DFT.
▶ Les calculs sont divisés en sous-séquences pair et impair.
Transformée de Fourier Discrète (DFT)

La DFT transforme un signal discret x[n] en un spectre fréquentiel


X [k]. Elle est définie par :
N−1
X
X [k] = x[n]e −2πikn/N , k = 0, 1, . . . , N − 1.
n=0

Complexité de la DFT brute


Le calcul direct nécessite N 2 multiplications complexes. La FFT
réduit cette complexité grâce à des optimisations basées sur les
propriétés des exponentielles complexes.
Pseudocode détaillé de la FFT (ligne par ligne)
Voici le pseudocode de la FFT basé sur l’approche récursive,
affiché ligne par ligne pour une meilleure compréhension :
Étape 1 : Initialisation et cas de base
1. Entrée : Signal x[n] de longueur N.
2. Si N = 1, retourner x[0].
Étape 2 : Diviser le signal
3. Séparer x[n] en deux sous-séquences : - xeven pour les indices
pairs. - xodd pour les indices impairs.
Étape 3 : Calcul récursif
4. Calculer récursivement : - Xeven = FFT(xeven ). -
Xodd = FFT(xodd ).
Étape 4 : Combinaison des résultats
5. Pour k = 0 à N/2 − 1 : - Calculer les facteurs de rotation
Wk = e −2πik/N .
- Combiner :
Code MATLAB de la FFT (ligne par ligne)

Voici une implémentation propre et détaillée de la FFT en


MATLAB, ligne par ligne :

Listing 1: Code MATLAB de la FFT récursive


1 xe ven = x(1 : 2 : end); xo dd = x(2 : 2 : end);
2 Xe ven = fftr ecur (xe ven); Xo dd = fftr ecur (xo dd);
3 W = exp(-2j * pi * (0:(N/2-1)) / N); X =
[Xe ven + W . ∗ Xo dd, ...Xe ven − W . ∗ Xo dd]; end
Applications de la FFT

La FFT est utilisée dans de nombreux domaines, tels que :


▶ Traitement du signal : Analyse spectrale et filtrage.
▶ Compression d’image : Algorithmes JPEG et traitement
fréquentiel.
▶ Analyse vibratoire : Détection des fréquences de résonance.
▶ Audio et musique : Compression et égalisation sonore.
▶ Simulation numérique : Résolution d’équations
différentielles.
Conclusion

La Transformée de Fourier Rapide (FFT) est un algorithme


essentiel en ingénierie et sciences :
▶ Elle permet de calculer efficacement la DFT avec une
complexité O(N log N).
▶ Elle est utilisée dans presque tous les domaines impliquant des
signaux ou des données numériques.
▶ Son efficacité repose sur l’exploitation des symétries et
redondances dans les données.

Résumé des avantages


▶ Réduction drastique du temps de calcul.
▶ Large éventail d’applications pratiques.
▶ Fondamentale pour les technologies modernes.

Vous aimerez peut-être aussi