La transformation de Fourier rapide (sigle anglais : FFT ou fast Fourier transform) est un algorithme de calcul de la transformation de Fourier discrète (TFD). Sa complexité varie en O(n log n) avec le nombre n de points, alors que la complexité de l’algorithme « naïf » s'exprime en O(n). Ainsi, pour n = , le temps de calcul de l'algorithme rapide peut être 100 fois plus court que le calcul utilisant la formule de définition de la TFD. C'est en 1965 que James Cooley et John Tukey publient l’article qui « lance » définitivement l'adoption massive de cette méthode en traitement du signal et dans les télécommunications. On a découvert par la suite que l'algorithme avait déjà été imaginé par Carl Friedrich Gauss en 1805, et adapté à plusieurs reprises (notamment par Lanczos en 1942) sous des formes différentes. L'algorithme a aussi été découvert indépendamment par le chanoine Lemaître. Cet algorithme est couramment utilisé en traitement numérique du signal pour transformer des données discrètes du domaine temporel dans le domaine fréquentiel, en particulier dans les oscilloscopes numériques (les analyseurs de spectre utilisant plutôt des filtres analogiques, plus précis). Son efficacité permet de réaliser des filtrages en modifiant le spectre et en utilisant la transformation inverse (filtre à réponse impulsionnelle finie). Il est également à la base des algorithmes de multiplication rapide (Schönhage et Strassen, 1971), et des techniques de ayant mené au format d'image JPEG (1991). Le développement d'algorithmes rapides pour la FFT remonte au travail non publié de Carl Friedrich Gauss en 1805, alors qu'il en avait besoin pour interpoler l'orbite des astéroïdes Pallas et Junon à partir d'observations d'échantillons. Sa méthode était très similaire à celle publiée en 1965 par James Cooley et John Tukey, à qui l'on attribue généralement l'invention de l'algorithme générique moderne de la FFT. Bien que les travaux de Gauss soient antérieurs aux résultats de Joseph Fourier en 1822, il n'a pas analysé le temps de calcul et a finalement utilisé d'autres méthodes pour atteindre son objectif.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (31)
COM-303: Signal processing for communications
Students learn digital signal processing theory, including discrete time, Fourier analysis, filter design, adaptive filtering, sampling, interpolation and quantization; they are introduced to image pr
PHYS-332: Computational physics III
This course teaches the students practical skills needed for solving modern physics problems by means of computation. A number of examples illustrate the utility of numerical computations in various d
EE-205: Signals and systems (for EL)
Ce cours pose les bases d'un concept essentiel en ingénierie : la notion de système. Plus spécifiquement, le cours présente la théorie des systèmes linéaires invariants dans le temps (SLIT), qui sont
Afficher plus
Concepts associés (46)
Transformation de Fourier
thumb|Portrait de Joseph Fourier. En mathématiques, plus précisément en analyse, la transformation de Fourier est une extension, pour les fonctions non périodiques, du développement en série de Fourier des fonctions périodiques. La transformation de Fourier associe à toute fonction intégrable définie sur R et à valeurs réelles ou complexes, une autre fonction sur R appelée transformée de Fourier dont la variable indépendante peut s'interpréter en physique comme la fréquence ou la pulsation.
Transformation de Fourier discrète
En mathématiques, la transformation de Fourier discrète (TFD) sert à traiter un signal numérique. Elle constitue un équivalent discret (c'est-à-dire pour un signal défini à partir d'un nombre fini d'échantillons) de la transformation de Fourier (continue) utilisée pour traiter un signal analogique. Plus précisément, la TFD est la représentation spectrale discrète dans le domaine des fréquences d'un signal échantillonné. La transformation de Fourier rapide est un algorithme particulier de calcul de la transformation de Fourier discrète.
Série de Fourier
vignette|250px|Les quatre premières sommes partielles de la série de Fourier pour un signal carré. vignette|250px|Le premier graphe donne l'allure du graphe d'une fonction périodique ; l'histogramme donne les valeurs des modules des coefficients de Fourier correspondant aux différentes fréquences. En analyse mathématique, les séries de Fourier sont un outil fondamental dans l'étude des fonctions périodiques. C'est à partir de ce concept que s'est développée la branche des mathématiques connue sous le nom d'analyse harmonique.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.