Transformée de Fourier rapide (FFT) Vs. Transformée de Fourier discrète (DFT)
La technologie et la science vont de pair. Et il n’y a pas de meilleur exemple que le traitement des signaux numériques (DSP). Le traitement des signaux numériques est le processus qui permet d’optimiser la précision et l’efficacité des communications numériques. Tout est fait de données – qu’il s’agisse d’images provenant de sondes spatiales ou de vibrations sismiques, et de tout ce qui se trouve entre les deux. Convertir ces données en format lisible par l’homme à l’aide d’ordinateurs est le traitement numérique du signal. Il s’agit de l’une des technologies les plus puissantes qui combine à la fois la théorie mathématique et la mise en œuvre physique. L’étude du DSP a commencé par un cours de deuxième cycle en génie électrique, mais au fil du temps, elle est devenue un facteur de changement potentiel dans le domaine de la science et de l’ingénierie. Il suffit de dire que sans DSP, les ingénieurs et les scientifiques pourraient cesser d’exister.
La transformée de Fourier est un moyen de mettre en correspondance un signal, dans le domaine du temps ou de l’espace, avec son spectre dans le domaine des fréquences. Les domaines temporel et fréquentiel ne sont que des façons alternatives de représenter les signaux et la transformée de Fourier est la relation mathématique entre les deux représentations. Une modification du signal dans un domaine affecte également le signal dans l’autre domaine, mais pas nécessairement de la même manière. La transformée de Fourier discrète (TFD) est une transformée semblable à la transformée de Fourier utilisée avec des signaux numérisés. Comme son nom l’indique, il s’agit de la version discrète de la transformée de Fourier qui considère le domaine temporel et le domaine fréquentiel comme périodiques. La transformée de Fourier rapide (FFT) est un algorithme permettant un calcul rapide et efficace de la TFD.
Transformée de Fourier discrète (DFT)
La transformée de Fourier discrète (TFD) est l’un des outils les plus importants du traitement des signaux numériques. Elle permet de calculer le spectre d’un signal de durée finie. Il est très courant d’encoder l’information dans les sinusoïdes qui forment un signal. Cependant, dans certaines applications, la forme d’une onde dans le domaine temporel n’est pas une application pour les signaux, auquel cas le contenu en fréquence du signal devient très utile autrement que sous la forme de signaux numériques. La représentation d’un signal numérique en termes de sa composante de fréquence dans un domaine de fréquence est importante. L’algorithme qui transforme les signaux du domaine temporel en composantes du domaine fréquentiel est connu sous le nom de transformée de Fourier discrète, ou TFD.
Transformée de Fourier rapide (FFT)
La transformée de Fourier rapide (FFT) est une implémentation de la TFD qui produit presque les mêmes résultats que la TFD, mais elle est incroyablement plus efficace et beaucoup plus rapide, ce qui réduit souvent le temps de calcul de manière significative. Il s’agit simplement d’un algorithme de calcul utilisé pour un calcul rapide et efficace de la TFD. Diverses techniques de calcul rapide de la TFD sont connues collectivement sous le nom de transformée de Fourier rapide, ou FFT. Gauss a été le premier à proposer cette technique pour calculer les coefficients d’une trigonométrie de l’orbite d’un astéroïde en 1805. Toutefois, ce n’est qu’en 1965 qu’un article fondamental de Cooley et Tukey a attiré l’attention de la communauté scientifique et technique, jetant ainsi les bases de la discipline du traitement des signaux numériques.
Différence entre FFT et DFT
Signification de FFT et DFT
La transformée de Fourier discrète, ou plus simplement appelée DFT, est l’algorithme qui transforme les signaux du domaine temporel en composantes du domaine fréquentiel. La TFD, comme son nom l’indique, est véritablement discrète ; les ensembles de données du domaine temporel discret sont transformés en représentation fréquentielle discrète. En termes simples, elle établit une relation entre la représentation du domaine temporel et la représentation du domaine fréquentiel. La transformée de Fourier rapide, ou FFT, est un algorithme de calcul qui réduit le temps de calcul et la complexité des grandes transformations. La FFT n’est qu’un algorithme utilisé pour le calcul rapide de la TFD.
Algorithme de la FFT et de la DFT
L’algorithme FFT le plus couramment utilisé est l’algorithme de Cooley-Tukey, nommé d’après J. W. Cooley et John Tukey. Il s’agit d’un algorithme de division et de conquête pour le calcul automatique des séries complexes de Fourier. Il divise la TFD en plus petites TFD. Parmi les autres algorithmes FFT figurent l’algorithme de Rader, l’algorithme de transformée de Fourier de Winograd, l’algorithme de transformée en Z de Chirp, etc. Les algorithmes DFT peuvent être programmés sur des ordinateurs numériques à usage général ou mis en œuvre directement par du matériel spécial. L’algorithme FFT est utilisé pour calculer la TFD d’une séquence ou son inverse. Une TFD peut être réalisée en O(N2) en termes de complexité temporelle, tandis que la FFT réduit la complexité temporelle à l’ordre de O (NlogN).
Applications de la FFT et de la DFT
La TFD peut être utilisée dans de nombreux systèmes de traitement numérique pour une variété d’applications telles que le calcul du spectre de fréquence d’un signal, la résolution d’applications différentielles partielles, la détection de cibles à partir d’échos radar, l’analyse de corrélation, le calcul de la multiplication polynomiale, l’analyse spectrale, et bien plus encore. La FFT a été largement utilisée pour les mesures acoustiques dans les églises et les salles de concert. Parmi les autres applications de la FFT figurent l’analyse spectrale dans les mesures vidéo analogiques, la multiplication de grands entiers et de polynômes, les algorithmes de filtrage, le calcul des distributions isotopiques, le calcul des coefficients de la série de Fourier, le calcul des convolutions, la génération de bruit à basse fréquence, la conception de kinoformes, l’exécution de matrices structurées denses, le traitement d’images, et bien d’autres encore.
Résumé de FFT Vs. DFT
En résumé, la transformée de Fourier discrète joue un rôle clé en physique car elle peut être utilisée comme outil mathématique pour décrire la relation entre la représentation des signaux discrets dans le domaine temporel et dans le domaine fréquentiel. Il s’agit d’un algorithme simple mais qui prend beaucoup de temps. Toutefois, pour réduire le temps de calcul et la complexité des grandes transformées, il est possible d’utiliser un algorithme plus complexe mais moins long, tel que la transformée de Fourier rapide. La FFT est une implémentation de la TFD utilisée pour le calcul rapide de la TFD. En bref, la FFT peut faire tout ce que fait la TFD, mais de manière plus efficace et beaucoup plus rapide que la TFD. C’est un moyen efficace de calculer la TFD.