La transformation rapide de Fourier (FFT) est un algorithme efficace pour calculer la transformation discret de Fourier (DFT). L'algorithme Cooley-Tukey est la méthode la plus courante pour mettre en œuvre la FFT, en s'appuyant sur la décomposition récursive de la DFT.

Base mathématique de la FFT

La DFT transforme une séquence de nombres complexes en composants de fréquence. Elle est définie comme suit:

X(k) = -n=0N-1 x(n) e-2πi kn/N

où x(n) est la séquence d'entrée, X(k) est la composante de fréquence, et N[ est la longueur de la séquence.

Dérivation de l'algorithme Cooley-Tukey

L'algorithme Cooley-Tukey décompose le DFT en petits DFT en divisant la séquence en parties paires et impaires :

N-1 x(n) e-2πi kn/N

qui peut être réécrit comme suit:

n=0N/2-1 x(2n) e-2πi 2n k/N + e-2πi k/N -n=0N/2-1] x(2n+1) e-2πi 2n k/N

Cette séparation permet de calculer récursifs des DFT plus petits, réduisant ainsi la complexité du calcul de O(N2) à O(N log N).

Appliquer l'algorithme

L'algorithme FFT applique la décomposition récursive à plusieurs reprises jusqu'à ce que le cas de base de la taille 1 soit atteint. Les résultats sont ensuite combinés en utilisant des facteurs de oscillation, qui sont des termes exponentiels complexes:

WNk) = e-2πi k/N

Ces facteurs ajustent la phase des petits DFT pendant la recombinaison, permettant un calcul efficace de la transformation complète.