Transformée de Fourier Discrète

La transformée de Fourier discrète (TFD) est un outil fondamental en traitement du signal et en analyse numérique. Elle permet de représenter une suite finie de données dans le domaine fréquentiel, facilitant ainsi l’étude des composantes fréquentielles d’un signal. Cet article s’adresse aux étudiants en sciences, ingénierie ou mathématiques qui souhaitent comprendre les bases, les méthodes de calcul et les propriétés essentielles de la TFD ainsi que son algorithme rapide, la transformée de Fourier rapide (FFT).

La question

Le travail aborde le problème de la transformation d’un signal continu en une représentation fréquentielle discrète, adaptée au calcul informatique. La difficulté principale réside dans le fait que les ordinateurs ne peuvent manipuler qu’un nombre fini d’échantillons et de valeurs, ce qui impose de discrétiser et tronquer le signal temporel, puis de discrétiser également le domaine fréquentiel. La question est donc de définir précisément la transformée de Fourier discrète, d’étudier ses propriétés, ses liens avec la transformée de Fourier continue, et d’optimiser son calcul via des algorithmes efficaces. Cette étude est essentielle pour toute personne souhaitant analyser numériquement des signaux ou des suites numériques.

Concepts de base

La transformée de Fourier discrète (TFD) s’applique à une suite finie de N échantillons x(0), x(1), ..., x(N−1). Elle produit une autre suite de N termes X(0), X(1), ..., X(N−1) définie par la formule :

X(k) = ∑(n=0 à N−1) x(n) e^(−j 2π n k / N)

Cette suite X(k) représente une approximation discrète du spectre fréquentiel du signal. La TFD est souvent utilisée pour analyser des signaux numériques ou des suites sans lien direct avec un signal physique.

Pour un signal analogique x(t), la transformée de Fourier continue est donnée par :

X(f) = ∫(−∞ à +∞) x(t) e^(−j 2π f t) dt

Mais en pratique, on échantillonne x(t) à une fréquence d’échantillonnage fe = 1/Te, on tronque la durée d’observation à N échantillons, puis on calcule la TFD sur cette suite finie. Ce processus entraîne plusieurs phénomènes :

• Échantillonnage temporel : rend le spectre périodique et peut provoquer un recouvrement spectral (aliasing) si la fréquence d’échantillonnage n’est pas suffisante.
• Troncature temporelle : correspond à une multiplication du signal par une fenêtre temporelle, ce qui revient à convoluer son spectre avec la transformée de la fenêtre, introduisant des ondulations appelées « ripples ».
• Échantillonnage fréquentiel : on obtient alors N points de fréquence espacés de 1/T0, avec T0 = NTe, ce qui correspond à la TFD.

La TFD est donc une approximation discrète et périodique de la transformée de Fourier continue, avec des erreurs liées à l’échantillonnage et à la troncature.

Approche

La méthode consiste à définir la TFD comme une somme finie d’exponentielles complexes pondérées par les échantillons du signal. Pour calculer cette somme, un algorithme direct nécessite un nombre d’opérations proportionnel à N², ce qui est coûteux pour de grandes valeurs de N.

Pour améliorer l’efficacité, on utilise l’algorithme de la transformée de Fourier rapide (FFT), notamment celui de Cooley-Tukey. Cet algorithme repose sur la décomposition récursive de la TFD d’ordre N (où N est une puissance de 2) en deux TFD d’ordre N/2, l’une sur les échantillons d’indices pairs, l’autre sur les indices impairs. Ces résultats sont ensuite combinés par une étape appelée « papillon ».

Cette décomposition permet de réduire le nombre de multiplications complexes de N² à (N/2) log2(N), ce qui accélère considérablement le calcul. Deux variantes principales existent :

• FFT avec entrelacement temporel : les données d’entrée sont désordonnées, les résultats sont dans l’ordre naturel.
• FFT avec entrelacement fréquentiel : les données d’entrée sont dans l’ordre naturel, les résultats sont désordonnés.

Le choix de la fenêtre temporelle utilisée pour tronquer le signal est également crucial. Différentes fenêtres (rectangulaire, triangulaire, cosinusoïdale, Hanning, Hamming, Blackman, Gauss, Kaiser, Dolph-Chebychev) offrent un compromis entre la largeur du lobe principal (résolution fréquentielle) et la hauteur des lobes secondaires (dynamique et atténuation des ondulations).

Résultats

Le travail montre que :

• La TFD est une approximation discrète de la transformée de Fourier continue, exacte uniquement dans des cas particuliers (signal périodique, bande limitée, fenêtre de troncature adaptée).
• Les erreurs dues à l’échantillonnage et à la troncature peuvent être atténuées par le choix judicieux de la fréquence d’échantillonnage et de la fenêtre temporelle.
• Les fenêtres non rectangulaires (Hanning, Hamming, Blackman, etc.) réduisent significativement les lobes secondaires, améliorant la qualité de l’analyse spectrale.
• L’algorithme FFT réduit drastiquement la complexité du calcul, rendant la TFD applicable en temps réel ou sur de grandes données.
• Les propriétés fondamentales de la TFD, telles que le théorème de Parseval, la convolution circulaire, et le théorème du retard circulaire, sont démontrées et permettent d’utiliser la TFD dans diverses applications (filtrage, analyse spectrale, etc.).

Limites et questions ouvertes

Le travail souligne que :

• La TFD n’est pas une approximation parfaite de la transformée de Fourier continue, sauf dans des conditions idéales (signal périodique, bande limitée, fenêtre adaptée).
• Le choix de la fenêtre temporelle implique un compromis entre résolution fréquentielle et atténuation des lobes secondaires, sans solution parfaite.
• Le phénomène d’aliasing peut toujours apparaître si la fréquence d’échantillonnage est insuffisante.
• La FFT nécessite que la taille N soit une puissance de 2, ce qui peut imposer des contraintes sur la taille des données ou nécessiter un zero-padding.
• Les algorithmes FFT sont dépendants de l’architecture matérielle pour leur efficacité réelle, ce qui n’est pas traité ici.

Glossaire

• Transformée de Fourier discrète (TFD) : représentation fréquentielle discrète d’une suite finie de données.
• Transformée de Fourier rapide (FFT) : algorithme efficace pour calculer la TFD en réduisant la complexité de calcul.
• Fenêtre temporelle : fonction utilisée pour tronquer un signal dans le temps avant calcul de la TFD.
• Lobe principal : partie centrale de la transformée de Fourier d’une fenêtre, liée à la résolution fréquentielle.
• Lobes secondaires : oscillations autour du lobe principal dans la transformée de Fourier d’une fenêtre, influençant la dynamique.
• Convolution circulaire : opération entre deux suites périodiques, liée à la multiplication de leurs TFD.
• Théorème de Parseval : égalité entre l’énergie totale dans le domaine temporel et dans le domaine fréquentiel.
• Aliasing : recouvrement spectral dû à un échantillonnage insuffisant.
• Zero-padding : ajout de zéros à une suite pour augmenter la résolution fréquentielle de la TFD.
• Papillon : étape élémentaire de calcul dans l’algorithme FFT combinant deux TFD d’ordre réduit.