La transformée de Fourier est très courante en physique et en mathématiques, ce qui signifie qu'elle a aussi de nombreux usages dans la vie quotidienne.
En bref, la transformée de Fourier prend un signal d'entrée, souvent exprimé dans le domaine temporel ou spatial, et le transforme vers le domaine fréquentiel.
Plus concrètement, si un signal d'entrée est un mélange (c'est-à-dire une superposition) de différentes fréquences, la transformée sépare les fréquences individuelles et montre leurs intensités relatives.
Cela fait de la transformée un outil de premier plan en traitement du signal (par exemple le filtrage, la compression, etc.) et dans de nombreuses applications de science des données.
Elle est donc peut-être plus répandue qu'on ne l'imagine au premier abord, ce qui en fait aussi un excellent exemple de domaine où les nombres imaginaires s'avèrent indispensables, étant donné que la sortie de la transformée de Fourier est en général un nombre complexe.
Bien que la transformée de Fourier ait une formulation intégrale, nous sommes dans le numérique, et c'est donc la version discrète qui nous intéresse.
La dérivation de la transformée dépasse le cadre de cet exercice, mais la transformée discrète directe (vers le domaine fréquentiel) prend la forme suivante :
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Ici, la somme porte sur n, N est le nombre d'échantillons, k la fréquence, i l'unité imaginaire et xₙ un échantillon individuel.
Bien qu'extrêmement utile, la transformée de Fourier, implémentée naïvement, est un peu lente (O(n²)).
La transformée de Fourier rapide (FFT) est un algorithme qui accélère considérablement ce calcul.
On y parvient généralement grâce à une stratégie « diviser pour régner » qui exploite certaines symétries de la formulation et aboutit à une complexité asymptotique en O(Nlog(N)).
Cette accélération améliore grandement le caractère pratique de la transformée ainsi que l'éventail des applications qui lui conviennent.
