Transformée de fourier discrète

Transformée de Fourier discrète

La transformée de Fourier discrète (TFD) est un outil mathématique de traitement du signal numérique, qui est l'équivalent discret de la transformée de Fourier continue qui est utilisée pour le traitement du signal analogique.

Sa définition mathématique pour un signal $s$ de $N$ échantillons est la suivante :

$S(k) = \sum_{n=0}^{N-1}s(n)\cdot e^{-2 i \pi k \frac{n}{N}} \qquad pour \qquad 0 \leq k < N$

La transformée inverse est donnée par :

$s(n) = \frac{1}{N} \sum_{k=0}^{N-1}S(k)\cdot e^{2 i \pi n \frac{k}{N}}$

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

Figure 1 : Transformée de Fourier discrète sur

N = 64

points d'un sinus de fréquence 10 kHz échantilloné à 100 000 échantillons par seconde ( 100 kéch/s).

Ces définitions ne sont pas uniques : on peut tout à fait normer la TFD par $1 / N$ , et ne pas normer la TFD inverse, ou encore normer 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.

La TFD est un cas particulier de la transformée en Z, lorsqu'on évalue cette dernière sur le cercle unité.

Sommaire

1 Fréquence d'échantillonnage et interpolation
2 Signaux réels
3 Applications
4 Quelques TFD de signaux classiques
5 Références
6 Voir aussi

Fréquence d'échantillonnage et interpolation

On peut remarquer que ce signal est périodique de période $N$ , et renseigne sur les fréquences comprises entre $- F e / 2$ et $F e / 2$ , $F e$ étant la fréquence d'échantillonnage souvent noté $f s$ dans la littérature anglosaxonne. On n'a donc que $N$ points pour analyser le spectre, et il peut être intéressant d'augmenter ce nombre de points afin d'augmenter sa résolution spectrale ( $δ F = F e / N)$ et donc de mieux localiser les maxima de son spectre (un signal de fréquence non multiple de $F e / N$ ne sera pas vue après TFD. Il y a alors perte d'information).

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 du bourrage de zéros (en anglais zero-padding), qui consiste à compléter le signal $s (n)$ par $P$ zéros. La nouvelle définition devient :

$S(k) = \sum_{n=0}^{N+P-1}s(n)\cdot e^{-2 i \pi k \frac{n}{N+P}} = \sum_{n=0}^{N-1}s(n)\cdot e^{-2 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 résolution. Cette technique est notamment utilisée pour avoir un nombre de points total $N + P$ en puissance de deux, et pouvoir utiliser un algorithme de transformée de Fourier rapide.

On peut, de la même manière, faire du bourrage de zéros sur le spectre afin d'obtenir, par transformée 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$ ).

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 d'un signal, on élève le module de sa TFD au carré : le spectre est donc pair.

Or, on a vu que la TFD est périodique, de période $N + P$ : les fréquences $\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$ .

Applications

La TFD est utilisée dans un large spectre d'applications, seuls les plus communs sont listés 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 transformée 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 harmonique apportée 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 transformée de Fourier rapide) est ici utilisé 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 de points $N$ 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), ils 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 transformées 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 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, qui sont 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 n'en 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

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 leur 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 évenements 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_n=\frac{1}{N}\sum_{k=0}^{N-1}X_k \cdot e^{i 2 \pi kn/N}$	$X_k=\sum_{n=0}^{N-1}x_n \cdot e^{-i 2 \pi kn/N}$	Note
$x_n \cdot e^{i 2 \pi kn/N} \,$	$X_{n-k}\,$	Propriété de translation
$x_{n-k}\,$	$X_k \cdot e^{-i 2 \pi kn/N}$	Propriété de translation
$x_n \in \mathbb{R}$	$X_k=X_{N-k}^*\,$	TFD d'un signal réel
$a^n\,$	$\frac{1-a^N}{1-a \cdot e^{-i 2 \pi k/N} }$
${N-1 \choose n}\,$	$\left(1+e^{-i 2 \pi k/N} \right)^{N-1}\,$

Références

Analyse de Fourier et applications, Claude Gasquet, Patrick Witomski: Université de Grenoble I, Dunod (1996)
Efficient Similarity Search In Sequence Databases, Rakesh Agrawal, Christos Faloutsos, Arun Swami, Proceedings of the 4th International Conference of Foundations of Data Organization and Algorithms (1993)

Voir aussi

Matrice circulante qui donne une interprétation géométrique de la transformée de Fourier discrète
Transformée de Fourier
Transformée de Fourier rapide
Transformée en Z
Fenêtrage
Transformée de Fourier à court terme
Transformée en cosinus discrète

Portail des mathématiques

Ce document provient de « Transform%C3%A9e de Fourier discr%C3%A8te ».

Catégories : Transformée | Transformée du signal | Analyse harmonique discrète

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Transformée de fourier discrète de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

Transformee de Fourier discrete — Transformée de Fourier discrète La transformée de Fourier discrète (TFD) est un outil mathématique de traitement du signal numérique, qui est l équivalent discret de la transformée de Fourier continue qui est utilisée pour le traitement du signal … Wikipédia en Français
Transformée de Fourier discrète — La transformée de Fourier discrète (TFD) est un outil mathématique de traitement du signal numérique, qui est l équivalent discret de la transformée de Fourier continue qui est utilisée pour le traitement du signal analogique. En anglais on parle … Wikipédia en Français
Transformee en cosinus discrete — Transformée en cosinus discrète La transformée en cosinus discrète ou TCD (de l anglais : DCT ou Discrete Cosine Transform) est une transformation proche de la transformée de Fourier discrète (DFT). Le noyau de projection est un cosinus et… … Wikipédia en Français
Transformée en cosinus discrète — La transformée en cosinus discrète ou TCD (de l anglais : DCT ou Discrete Cosine Transform) est une transformation proche de la transformée de Fourier discrète (DFT). Le noyau de projection est un cosinus et crée donc des coefficients réels … Wikipédia en Français
Transformee de Fourier rapide — Transformée de Fourier rapide La transformée de Fourier rapide (sigle anglais : FFT ou Fast Fourier Transform) est un algorithme de calcul de la transformée de Fourier discrète (TFD). Sa complexité varie en avec le nombre de points n, alors… … Wikipédia en Français
Transformée de fourier rapide — La transformée de Fourier rapide (sigle anglais : FFT ou Fast Fourier Transform) est un algorithme de calcul de la transformée de Fourier discrète (TFD). Sa complexité varie en avec le nombre de points n, alors que la complexité du calcul de … Wikipédia en Français
Transformee de Fourier — Transformée de Fourier Joseph Fourier En analyse, la transformation de Fourier est un analogue de la théorie des séries de Fourier pour les fonctions non périodiques, et permet de leur associer un spectre en fréquences. On cherche ensuite à… … Wikipédia en Français
Transformée de fourier — Joseph Fourier En analyse, la transformation de Fourier est un analogue de la théorie des séries de Fourier pour les fonctions non périodiques, et permet de leur associer un spectre en fréquences. On cherche ensuite à obtenir l expression de la… … Wikipédia en Français
Transformée de Fourier rapide — La transformée de Fourier rapide (sigle anglais : FFT ou Fast Fourier Transform) est un algorithme de calcul de la transformée de Fourier discrète (TFD). Sa complexité varie en avec le nombre de points n, alors que la complexité du calcul de … Wikipédia en Français
Transformée de Fourier — Joseph Fourier En analyse, la transformation de Fourier est un analogue de la théorie des séries de Fourier pour les fonctions non périodiques, et permet de leur associer un spectre en fréquences. On cherche ensuite à obtenir l expression de la… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Transformée de fourier discrète