Pour un signal f à N échantillons, la transformée de Fourier discrète s'écrit
Le calcul de la transformée de Fourier par cette formule demande N2 additions et multiplications complexes.
Or, un calcul simple montre que les coefficients de fréquence paire sont ceux de la transformée de Fourier du signal N/2 périodique
et que les coefficients de fréquence impaire sont ceux de la transformée de Fourier du signal
En poussant le raisonnement par récurrence, on voit que le nombre d'opérations nécessaires au calcul de la transformée de Fourier par cette méthode est de l'ordre de KN log2(N), où K est une constante indépendante de N.
C'est le principe de base de la transformée de Fourier rapide. Plusieurs variantes en existent, qui cherchent à minimiser K.
La convolution circulaire de deux signaux de période N est définie par
La transformée de Fourier discrète de la convolution circulaire est le produit des transformées de Fourier discrètes.
Pour deux signaux f et h de longueur M>=32, il est plus rapide de calculer leur convolution en utilisant une FFT. Pour cela, on définit les deux signaux 2M-périodiques suivants:
et on vérifie que leur convolution circulaire coïncide avec la convolution classique
pour 0<=n<2M. La convolution circulaire est elle-même calculée en faisant la FFT des deux signaux, le produit des FFT, puis une FFT inverse.