Transformation de Fourier discrète

En mathématiques, la transformation de Fourier discrète (TFD) sert à traiter un signal numérique. Elle constitue un équivalent discret (c'est-à-dire pour un signal défini à partir d'un nombre fini d'échantillons) de la transformation de Fourier (continue) utilisée pour traiter un signal analogique. Plus précisément, la TFD est la représentation spectrale discrète dans le domaine des fréquences d'un signal échantillonné.

La transformation de Fourier rapide est un algorithme particulier de calcul de la transformation de Fourier discrète.

Définitions

Transformation de Fourier discrète

La transformation de Fourier discrète d'un signal $s$ de $N$ échantillons $(s(0),s(1),\dots ,s(N-1))$ est le vecteur $(S(0),S(1),\dots ,S(N-1))$ défini par :

$S(k)=\sum _{n=0}^{N-1}s(n)\mathrm {e} ^{-2\mathrm {i} \pi k{\frac {n}{N}}}\qquad {\text{pour}}\qquad 0\leqslant k<N$.

On obtient ainsi une représentation spectrale discrète du signal échantillonné $s(n)$.

La TFD ne calcule pas le spectre continu d'un signal continu. Elle permet seulement d'évaluer une représentation spectrale discrète (spectre échantillonné) d'un signal discret (signal échantillonné) sur une fenêtre de temps finie (échantillonnage borné dans le temps).

L'exemple ci-dessous peut laisser croire que la TFD permet de calculer le spectre d'un signal continu, mais cela n'arrive que lorsque la fenêtre d'échantillonnage correspond à un multiple strictement supérieur à deux fois la période du signal échantillonné (dans ce cas on a forcément évité le repliement de spectre, c'est le théorème d'échantillonnage de Nyquist-Shannon) :

Figure 1 : Transformée de Fourier discrète sur N = 64 points d'un sinus de fréquence 7 812,5 Hz échantillonné à 100 000 échantillons par seconde (100 kéch/s).

Transformation de Fourier discrète inverse

La transformation de Fourier discrète inverse est donnée par :

$s(n)={\frac {1}{N}}\sum _{k=0}^{N-1}S(k)\mathrm {e} ^{2\mathrm {i} \pi n{\frac {k}{N}}}$.

En fait, il existe plusieurs définitions de la transformation de Fourier discrète et son inverse, qui différent par le facteur multiplicatif. On peut tout à fait normaliser la TFD par $1/N$, et ne pas normaliser la TFD inverse, ou encore normaliser les deux par ${\tfrac {1}{\sqrt {N}}}$, le but étant dans tous les cas de retrouver le signal originel par la TFD inverse de sa TFD.

Fréquence d'échantillonnage et interpolation

On peut remarquer que ce signal est périodique de période $f$, et renseigne sur les fréquences comprises entre $-\mathrm {F_{e}} /2$ et $\mathrm {F_{e}} /2$ (où $\mathrm {F_{e}}$ est la fréquence d'échantillonnage, souvent notée $f_{\mathrm {s} }$ dans la littérature anglo-saxonne). On n'a donc que $N$ points pour analyser le spectre, et il peut être intéressant d'augmenter ce nombre de points d'analyse afin d'augmenter la précision spectrale ($\delta \mathrm {F} =\mathrm {F_{e}} /N$ ; sans zero-padding, la résolution se confond avec la précision) et donc de mieux localiser les maxima de son spectre (un signal de fréquence non multiple de $\mathrm {F_{e}} /N$ ne sera pas vu après TFD. Il y a alors perte d'information). Il faut distinguer la précision de la résolution qui est la capacité de distinguer deux sinusoïdes à des fréquences proches ($\mathrm {F_{e}} /N$).

Pour augmenter le nombre de points, on peut :

• augmenter la fréquence d'échantillonnage. Mais cela a un coût en termes de ressources matérielles ;
• faire une interpolation.

Cela se fait par la technique de complétion de zéros (en anglais zero-padding), qui consiste à compléter le signal $s(n)$ par $P$ zéros. Le nombre de points d'analyse est donc augmenté, mais le nombre de points de signal utile reste le même (ce qui ne change donc pas la résolution). La nouvelle définition devient :

$S(k)=\sum _{n=0}^{N+P-1}s(n)\mathrm {e} ^{-2\mathrm {i} \pi k{\frac {n}{N+P}}}=\sum _{n=0}^{N-1}s(n)\mathrm {e} ^{-2\mathrm {i} \pi k{\frac {n}{N+P}}}$.

On somme toujours les mêmes valeurs de $s(n)$ (les $P$ autres étant nulles), mais on obtient une TFD de période $N+P$ au lieu de simplement $N$ : on a $P$ points supplémentaires pour décrire la même TFD, on a donc augmenté sa précision. Cette technique est notamment utilisée pour avoir un nombre de points total $N+P$ en puissance de 2, et pouvoir utiliser un algorithme de transformation de Fourier rapide.

On peut, de la même manière, faire du bourrage de zéros sur le spectre afin d'obtenir, par transformation inverse, une interpolation sur le signal initial.

On considère ici toujours une fréquence d'échantillonnage de 1. En parlant en fréquences réduites (normalisées par rapport à la fréquence d'échantillonnage), la TFD est décrite pour des valeurs de la fréquence réduite variant entre 0 (pour $k=0$) et 1 (pour $k=N+P$).

Interprétation matricielle

Matrice de Vandermonde-Fourier

Soit s un signal de périodicité N, et ${\hat {s}}$ sa transformée de Fourier. On peut relier s à sa transformée de Fourier par la multiplication avec une matrice qui dépend uniquement de N. Il s'agit de la matrice de Vandermonde-Fourier

$W_{N}={\begin{pmatrix}\omega _{N}^{0\times 0}&\cdots &\omega _{N}^{0(N-1)}\\\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)0}&\cdots &\omega _{N}^{(N-1)(N-1)}\end{pmatrix}}$

avec $\omega _{N}=\mathrm {e} ^{-2\pi \mathrm {i} /N}$. Plus précisément, ${\hat {s}}=W_{N}s$.

Remarquons que l'on retrouve bien la définition de la transformée de Fourier, car pour chaque élément ${\hat {s}}(m),m\in [\![0,N-1]\!]$, on a bien, par multiplication de chaque élément de la m-ième ligne de $W_{N}$ par le vecteur s :

${\hat {s}}(m)=\sum _{n=0}^{N-1}s(n)\omega _{N}^{nm}=\sum _{n=0}^{N-1}s(n)\mathrm {e} ^{-2\pi \mathrm {i} {\frac {nm}{N}}}$.

Matrices de Vandermonde-Fourier pour les dimensions 2 et 4

On peut appliquer la formule générale pour N = 2 :

$W_{2}={\begin{pmatrix}\omega _{2}^{0\times 0}&\omega _{2}^{0\times 1}\\\omega _{2}^{1\times 0}&\omega _{2}^{1\times 1}\end{pmatrix}}={\begin{pmatrix}\omega _{2}^{0}&\omega _{2}^{0}\\\omega _{2}^{0}&\mathrm {e} ^{-2\pi \mathrm {i} /2}\end{pmatrix}}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}$.

De même, pour N = 4 :

$W_{4}={\begin{pmatrix}1&1&1&1\\1&-\mathrm {i} &-1&\mathrm {i} \\1&-1&1&-1\\1&\mathrm {i} &-1&-\mathrm {i} \end{pmatrix}}$.

Exemple d'application à un signal

Soit s un signal de période 4.

s(0) = 2, s(1) = 4, s(2) = –1, s(3) = 3, s(4) = 2 = s(0), s(5) = 4 = s(1)…

Ce signal peut se résumer au vecteur $s={\begin{pmatrix}2\\4\\-1\\3\end{pmatrix}}$.

La transformée de Fourier de ce signal est donc :

${\hat {s}}=W_{4}s={\hat {s}}={\begin{pmatrix}1&1&1&1\\1&-\mathrm {i} &-1&\mathrm {i} \\1&-1&1&-1\\1&\mathrm {i} &-1&-\mathrm {i} \end{pmatrix}}{\begin{pmatrix}2\\4\\-1\\3\end{pmatrix}}={\begin{pmatrix}8\\3-\mathrm {i} \\-6\\3+\mathrm {i} \end{pmatrix}}$.

Signaux réels

Pour un signal réel, on a la relation

$S(k)^{*}=S(-k)$

(propriété de symétrie hermitienne). Lorsque l'on s'intéresse au spectre des amplitudes d'un signal (ou à sa densité spectrale de puissance), on calcule le module de $S(k)$, qui est équivalent au module de $S(k)^{*}$ : ce spectre est donc pair.

Or, on a vu que la TFD est périodique, de période $N+P$ : les fréquences comprises entre ${\tfrac {N+P}{2}}$ et $N+P$ sont les mêmes que celles comprises entre $-{\tfrac {N+P}{2}}$ et 0. Les fréquences négatives étant identiques aux positives, toute l'information spectrale est contenue entre les fréquences ${\tfrac {N+P}{2}}$ et $N+P$.

Transformation à deux dimensions

En traitement d'images, on utilise la transformation de Fourier à deux dimensions. Sa définition discrète est :

$S(u,v)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}s(m,n)\mathrm {e} ^{-2\mathrm {i} \pi \left({\frac {um}{M}}+{\frac {vn}{N}}\right)}$.

TFD et convolution

En théorie du signal notamment, on utilise le produit de convolution de deux séquences :

$p(x)=\{s*t\}(x)=\sum _{n=0}^{N-1}s(n)t(x-n_{\mod N}).$

La TFD transforme ce produit de convolution en produit terme à terme des coefficients de Fourier : $P(n)=S(n)\times T(n)$

Cette propriété peut être vue comme un corollaire de l'interprétation matricielle ci-dessus, puisque les coefficients de Fourier sont les valeurs propres des matrices associées aux séquences périodiques, associées aux mêmes vecteurs propres.

Elle admet une réciproque: toute automorphisme linéaire de l'espace des séquences N-périodiques qui transforme le produit de convolution en produit terme à terme est, à une éventuelle permutation près des coefficients, la TFD.

Cette propriété permet, par exemple, de réduire la complexité du produit de convolution qui est en $O(N^{2})$ à celle de la transformation de Fourier rapide en $O(N\log(N))$.

Applications

La TFD est utilisée dans un large spectre d'applications, seules les plus communes sont listées ici. Toutes ces applications nécessitent l'existence d'un algorithme rapide de calcul de la TFD et de son inverse, voir à ce sujet les méthodes de transformation de Fourier rapide.

Analyse spectrale

L'analyse spectrale des signaux est un élément essentiel en électronique pour de nombreuses raisons parmi lesquelles on peut citer :

• déterminer la largeur de bande de fréquence occupée par une transmission ;
• évaluer les distorsions harmoniques apportées par le traitement des signaux ;
• mesurer les filtres.

L'électronicien qui a toujours besoin de vérifier expérimentalement, a besoin d'un outil de mesure, l'analyseur de spectre. Il existe trois grandes familles d'analyseur de spectre, chacun ayant des caractéristiques intrinsèques :

L'analyseur de spectre à balayage (analogique)

Comme son nom l'indique, cet analyseur balaye une plage de fréquence en utilisant un filtre de largeur réglable. Il est capable de mesurer des plages de fréquence allant de l'audio à l'optique et ce pour des signaux d'amplitude très faible.

L'analyseur de spectre à FFT (numérique)

La FFT (Fast Fourier Transform ou transformation de Fourier rapide) est ici utilisée après échantillonnage du signal d'entrée basses fréquences (audio). Avantage : il est capable de capturer les signaux en temps réel avec une résolution spectrale très fine qui dépend du nombre $N$ de points et de la fenêtre de pondération utilisée.

L'augmentation de la rapidité et de la résolution des convertisseurs analogique numérique permettra d'analyser des signaux à des fréquences de plus en plus élevées.

L'analyseur de signaux vectoriel (analogique/numérique)

Comme il combine les technologies des deux premiers (balayage et FFT), il permet d'analyser des signaux dont les fréquences ne sont séparées que de quelques MHz sur toute la gamme de fréquences radio. Très utilisé dans le domaine des transmissions numériques pour analyser des signaux complexes (QAM, QPSK)

Compression de données

Le traitement du signal en général utilise énormément les opérations dans le domaine fréquentiel et en particulier la TFD ou une de ses variantes. En compression du son ou de l'image, des transformations proches de la TFD (par exemple la transformée en cosinus discrète) sont appliquées en général sur des portions de signal, pour en réduire la complexité. Les coefficients $S(k)$ sont ensuite quantifiés avec des pas de quantification plus élevés pour les hautes fréquences, considérées comme négligeables pour la perception humaine. Le gain en compression vient de la réduction de précision de ces coefficients (voire leur suppression totale) qui nécessitent alors moins de bits pour être codés. Il s'ensuit généralement une étape de codage entropique. La reconstruction du signal s'effectue alors à partir de cet ensemble réduit de coefficients quantifiés.

Exemple : Sur la figure 1, il est facile d'observer que le traitement temporel du signal sans perte d'information, nécessite de mémoriser 64 échantillons alors que le traitement fréquentiel ne nécessite qu'un seul point (en rappelant que les deux raies portent la même information). Et il n'y a pas de perte.

Équations aux dérivées partielles

La transformée de Fourier discrète est utilisée pour résoudre des équations aux dérivées partielles numériquement. Sans être exhaustif, on peut citer les utilisations suivantes :

• Utilisation de méthodes pseudo-spectrales : les dérivées spatiales sont calculées grâce à la transformée de Fourier discrète,
• Utilisation de la transformée de Fourier rapide pour calculer efficacement des opérateurs aux différences finies.

Multiplication de grands nombres entiers

Certains des algorithmes les plus rapides pour la multiplication de grands nombres entiers sont basés sur la TFD. Les séquences de chiffres sont interprétées comme les éléments d'un vecteur, dont on calcule la convolution. On calcule pour cela leurs TFD, qui sont multipliées entre elles (une convolution en temps est un produit en fréquence) puis on effectue la TFD inverse.

Analyse de séries temporelles

La TFD est utilisée pour l'étude des séries temporelles (ou chronologiques) où le but est de trouver des corrélations entre deux séquences de données. Un exemple classique est l'analyse des cours de la bourse, afin de repérer des événements particuliers. La problématique est en général celle de la fouille de données, ou de la recherche par similarité. La TFD est utilisée ici comme un moyen de réduire la dimensionnalité du problème. La TFD permet en effet de décorréler les données de départ et de ne travailler que sur un petit nombre de coefficients significatifs.

Quelques TFD de signaux classiques

Quelques signaux et leur TFD

$x_{k}={\frac {1}{N}}\sum _{n=-N/2}^{(N/2)-1}X_{n}\mathrm {e} ^{\mathrm {i} 2\pi kn/N}$	$X_{n}=\sum _{k=0}^{N-1}x_{k}\mathrm {e} ^{-\mathrm {i} 2\pi kn/N}$	Note
$y_{k}=x_{k}\mathrm {e} ^{\mathrm {i} 2\pi kl/N}$	$Y_{n}=X_{n-l}$	Propriété de translation
$y_{k}=x_{k-n}$	$Y_{n}=X_{n}\mathrm {e} ^{-\mathrm {i} 2\pi kn/N}$
$x_{n}\in \mathbb {R}$	$X_{n}=X_{N-n}^{*}$	TFD d'un signal réel
$a^{k}$	${\frac {1-a^{N}}{1-a\mathrm {e} ^{-\mathrm {i} 2\pi n/N}}}$
${N-1 \choose k}$	$\left(1+\mathrm {e} ^{-\mathrm {i} 2\pi n/N}\right)^{N-1}$

Voir aussi

Articles connexes

• Matrice circulante qui donne une interprétation géométrique de la transformation de Fourier discrète
• Transformée de Fourier à court terme
• La TFD correspond à l'évaluation sur le cercle unité de la transformée en Z pour des valeurs discrètes de la fréquence^{[réf. nécessaire][Information douteuse]}.

Bibliographie

• Claude Gasquet et Patrick Witomski, Analyse de Fourier et applications, Dunod, 1996
• (en) Rakesh Agrawal, Christos Faloutsos et Arun Swami, « Efficient Similarity Search In Sequence Databases », in Proceedings of the 4th International Conference of Foundations of Data Organization and Algorithms, 1993, p. 69-84
• Maïtine Bergounioux, Mathématiques pour le traitement du signal 2e éd.: Cours et exercices corrigés, Dunod, 2014