Transformée de Fourier rapide

La transformée de Fourier rapide est un algorithme de calcul de la transformée de Fourier discrète.



Catégories :

Transformée - Théorie de Fourier - Algorithme numérique - Transformée du signal

Page(s) en rapport avec ce sujet :

  • Transformée de Fourier rapide. Quelques références : http ://www. fftw. org/links. html. Définition. Algorithme de Cooley-Tukey; Transformée de Fourier inverse.... (source : brassens.upmf-grenoble)
  • La transformée de Fourier discrète d'un signal de durée infinie et non pé- riodique ne peut être calculée qu'approximativement, en limitant la durée du ... (source : tele.ucl.ac)
  • La transformation rapide de Fourier (FFT) est un procédé mathématique simplifié qui permet dans certaines conditions de faire cette transformation... (source : physique-appliquee)

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é fluctue en \mathcal{O}(n\ln n) avec le nombre de points n, tandis que la complexité du calcul de base s'exprime en \mathcal{O}(nˆ2). Ainsi, pour n=1024, le temps de calcul de l'algorithme rapide peut être 100 fois plus petit que le calcul utilisant la formule de définition de la TFD.

Cet algorithme est fréquemment utilisé en traitement numérique du signal pour transformer des données discrètes du domaine temporel dans le domaine fréquentiel, surtout dans les analyseurs de spectre. Son efficacité sert à réaliser des filtrages en passant dans le domaine transformé.

Formulation mathématique

Soient x0, ...., xn-1 des nombres complexes. La transformée de Fourier discrète est définie par la formule suivante :

 f_j =  \sum_{k=0}ˆ{n-1} x_k eˆ{-{2\pi i \over n} jk }
\qquad
j = 0,\dots,n-1.

ou en notation matricielle :


\begin{array}{l}
\begin{pmatrix}
f_0 \\
f_1 \\
f_2 \\
\vdots \\
f_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 & \cdots & 1\\
1 & w & wˆ2 & \cdots & wˆ{n-1}\\
1 & wˆ2 & wˆ4 & \cdots & wˆ{2(n-1)}\\
\vdots & \vdots & \vdots & \ddots & \vdots &\\
1 & wˆ{n-1} & wˆ{2(n-1)} & \cdots & wˆ{(n-1)ˆ2}
\end{pmatrix}
\end{array}
\begin{pmatrix}
x_0 \\
x_1 \\
x_2 \\
\vdots \\
x_{n-1}
\end{pmatrix}
,
w = eˆ{-\frac{2 \pi i}{n}}

Évaluer ces sommes directement coûte (n − 1) 2 produits complexes et n (n − 1) sommes complexes tandis que seuls (n / 2) (log2 (n) − 2) produits et nlog2 (n) sommes sont nécessaires avec la version rapide. Généralement, de tels algorithmes dépendent de la factorisation de n mais au contraire de une idée répandue, il y a des transformées de Fourier rapides de complexité \mathcal{O}(n\log_2(n)) pour l'ensemble des n, même les n qui sont des nombres premiers.

Comme la transformée de Fourier inverse discrète est équivalente à la transformée de Fourier discrète, à un signe et facteur 1/n près, il est envisageable de générer la transformation inverse de la même manière pour la version rapide.
Remarque : on peut reconnaître ici une matrice de Vandermonde en la matrice n*n.

L'algorithme de Cooley-Tukey

Il s'agit d'un algorithme souvent utilisé pour calculer la transformation de Fourier rapide. Il se base sur une approche de type «diviser pour régner» par le biais d'une récursion. Celle-ci subdivise une transformation de Fourier discrète d'une taille composite n = n1n2 en plusieurs transformées de Fourier discrètes de tailles inférieures n1 et n2. Cet algorithme nécessite \mathcal{O}(n) multiplications par des racines d'unité, plus couramment nommés facteurs de rotation.

C'est en 1965 que James Cooley et John Tukey publient cette méthode mais il a été découvert ensuite que l'algorithme avait déjà été découvert par Carl Friedrich Gauss en 1805 et adapté à plusieurs reprises sous des formes différentes.

L'utilisation la plus classique de l'algorithme de Cooley-Tukey est une division de la transformation en deux parties de taille semblable n / 2 et ceci à chaque étape. Cette contrainte limite les tailles envisageables, puisque celles-ci doivent être des puissances de deux. Cependant, une factorisation reste envisageable (principe déjà connu de Gauss). Généralement, les implémentations essaient d'éviter une récursion pour des questions de performance. Il est aussi envisageable de mélanger plusieurs types d'algorithme lors des subdivisions.

Autres algorithmes

Il existe d'autres algorithmes qui permettent de calculer la transformée de Fourier rapide. Pour une taille n = n1n2, avec des nombres premiers entre eux n1 et n2, il est envisageable d'utiliser l'algorithme PFA (Good-Thomas) basé sur le théorème des restes chinois. Le PFA est comparable à celui de Cooley-Tukey.

L'algorithme de Rader-Brenner est aussi une variante de Cooley-Tukey avec des facteurs de rotation purement imaginaires qui perfectionnent les performances en réduisant le nombre de multiplications mais au détriment de la stabilité numérique et une augmentation du nombre d'additions. Les algorithmes qui procèdent aussi par des factorisations successives sont ceux de Bruun et l'algorithme QFT. Les versions originales travaillent sur des fenêtres dont la taille est une puissance de deux mais il est envisageable de les adapter pour une taille quelconque. L'algorithme de Bruun considère la transformée de Fourier rapide comme une factorisation récursive du polynôme zn − 1 en des polynômes avec des cœfficients réels de la forme zm − 1 et z2m + azm + 1.

L'algorithme de Winograd factorise zn − 1 en un polynôme cyclotomique, dont les cœfficients sont fréquemment -1, 0 ou 1 ce qui diminué le nombre de multiplications. On peut voir cet algorithme comme la version optimale en termes de multiplications. Winograd a montré que la transformée de Fourier discrète peut être calculée avec uniquement \mathcal{O}(n) multiplications, ce qui représente une limite inférieure atteignable pour les tailles qui sont des puissances de deux. Cependant, des additions supplémentaires sont nécessaires ce qui peut être pénalisant sur les processeurs modernes comportant des unités arithmétiques performantes.

L'algorithme de Rader est quant à lui destiné aux fenêtres dont la taille est un nombre premier. Il profite de l'existence d'une génératrice pour le groupe multiplicatif modulo n. La transformation discrète dont la taille est un nombre premier s'exprime ainsi comme une convolution cyclique d'une taille n − 1. On peut ensuite la calculer par une paire de transformation de Fourier rapide.

Finalement, un autre algorithme destiné aux transformations avec des tailles qui sont des nombres premiers est due à Bluestein. On l'appelle plus fréquemment l'algorithme chirp-z. Ici encore, la transformation est vue comme une convolution dont la taille est semblable à la fenêtre originale. On utilise à cet effet l'identité jk = − (jk) 2 / 2 + j2 / 2 + k2 / 2.

Algorithmes spécialisés dans le traitement de données réelles ou/et symétriques

Dans énormément d'applications, les données en entrée de la transformation discrète de Fourier sont seulement des nombres réels. Dans ce cas, les sorties satisfont la symétrie suivante : f_{n-j} = f_jˆ*,

Des algorithmes efficaces ont été conçus pour cette situation, par exemple celui de Sorensen en 1987. Une approche envisageable consiste à prendre un algorithme classique comme celui de Cooley-Tukey ainsi qu'à enlever les parties inutiles dans le calcul. Cela se traduit par un gain de 50% en mémoire et en vitesse de calcul. Alternativement, il est envisageable d'exprimer une transformation discrète sur des nombres réels (avec une taille paire) en une transformation avec des nombres complexes mais dont la taille a été divisée par deux (les parties imaginaires sont les éléments impairs et les parties réelles sont les éléments pairs) suivie d'un décodage dont la complexité est de l'ordre de \mathcal{O}(n) opérations.

On pensait que les transformations avec des nombres réels pouvaient être plus efficacement calculées via une transformation discrète de Hartley mais il a été prouvé ensuite qu'une transformation de Fourier discrète modifiée pouvait être plus efficace que la même transformation de Hartley. L'algorithme de Bruun était un candidat pour ces transformations mais il n'a pas eu la popularité escomptée.

Il existe toujours d'autres variantes pour les cas où les données sont symétriques (c'est-à-dire des fonctions paires ou impaires) avec un gain supplémentaire de 50%. Dans ce cas, on utilise une transformée en cosinus discret.

Problèmes numériques et approximations

Tous les algorithmes proposés ci-dessus calculent la transformée sans aucune erreur, de par leur nature analytique. Cependant, il existe des algorithmes qui peuvent s'accommoder d'une marge d'erreur pour accélérer les calculs. En 1999, Edelman et al. proposent une approximation à la transformée de Fourier rapide. Cette version est conçue pour une implémentation en parallèle. Une approximation basée sur les ondelettes est proposée en 1996 par H. Guo et Burrus et tient compte de la répartition dans les entrées/sorties. Un autre algorithme a toujours été proposé par Shentov et al. en 1995. Seul l'algorithme de Edelman fonctionne bien avec n'importe quel type de données, il profite de la redondance dans la matrice de Fourier plutôt que de la redondance dans les données initiales.

Cependant, même les algorithmes décrits de manière analytique présentent des erreurs quand ils sont implémentés avec des virgules flottantes dont la précision est limitée. L'erreur est cependant limitée. Une limite supérieure d'erreur relative pour Cooley-Tukey est donnée par O (εlog (n) ) tandis qu'elle est de On3 / 2) pour la formulation triviale de la transformée de Fourier discrète (Gentleman et Sande, 1966). Le terme ε représente ici la précision relative en virgule flottante. En réalité, l'erreur quadratique moyenne est toujours plus limitée avec uniquement O(\epsilon \sqrt{\log(n)}) pour Cooley-Tukey et O(\epsilon \sqrt{n}) pour la version triviale. Il ne faut malgré tout pas oublier que la stabilité peut être perturbée par les différents facteurs de rotation qui interviennent dans les calculs. Un manque de précision sur les fonctions trigonométriques peut fortement augmenter l'erreur. L'algorithme de Rader est par exemple nettement moins stable que celui de Cooley-Tukey en cas d'erreurs prononcées.

Avec une arithmétique en virgule fixe, les erreurs s'accumulent toujours plus vite. Avec Cooley-Tukey, l'augmentation de l'erreur quadratique moyenne est de l'ordre de O(\epsilon \sqrt{n}). Qui plus est , il faut tenir compte de la magnitude des variables lors des différentes étapes de l'algorithme.

Il est envisageable de vérifier la validité de l'algorithme grâce à une procédure qui vise à déterminer la linéarité et d'autres caractéristiques de la transformation sur des entrées aléatoires (Ergün, 1995).

Références

Voir aussi

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Transform%C3%A9e_de_Fourier_rapide.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu