Transformée de Fourier rapide généralisée

 

par Charles Hubert

 

Introduction

 

Pour le calcul de la transformée de Fourier, je présente ici une fonction dont j'avais écrit la première version en APLSV ; je l'ai réadaptée et améliorée pour APL*PLUS/PC puis étendue pour APL+DOS. Elle fonctionne aussi en APL+WIN. Elle devrait fonctionner en APL2, mais elle n'utilise pas les complexes de cet interprète, car ils n'existent pas dans les APL*PLUS.

Elle est généralisée dans trois sens :

1) Elle accepte des données complexes représentées par deux réels ;

2) Le nombre de valeurs (la période) peut être autre chose qu'une puissance de 2, ce qui implique de lui associer une fonction décomposant ce nombre en facteurs premiers ;

3) Elle traite plusieurs ensembles de données à la fois et accepte les tableaux gigognes.

4) Les fonctions: On peut les trouver dans le fichier APL*PLUS " trsf.sf" ; la composante 1 contient une table des matieres, les composantes suivantes contiennent les VR de ces fonctions.

 

Description des deux fonctions

 

 

 

 

Fourier calcule la transformée de Fourier ; elle utilise FacPre pour décomposer la dimension n de la période en facteurs premiers. FacPre peut être utilisée pour autre chose bien sûr. Pour la rapidité de Fourier mieux vaut que ces facteurs premiers soient petits ; les valeurs 2, 3, 5 permettent toutes les puissances de 2 mais aussi 24, 360, 1000, 1440...

Fourier calcule la somme

 

 

La constante s est le signe moins pour la transformée directe et le signe plus pour la transformée inverse ; la constante k prend une valeur pour la transformée directe suivant la convention adoptée et l'autre valeur pour la transformée inverse. On utilise Fourier de la façon suivante

 

 

opt est une option qui est prise modulo 4 et

 

 

x est un tableau de dimension (nbCas,n,nbCol). Fourier ramène la dernière dimension à 2 par

 

 

La première colonne contient les parties réelles, la deuxième les parties imaginaires. Si on ne donne qu'une colonne, elle est alors complétée par des parties imaginaires nulles : les données sont réelles. n est le nombre de valeurs complexes dans la période. Quant à nbCas il structure les      ensembles de données de même période qu'on traite à la fois.

De plus chaque case du tableau x peut être un tableau de profondeur quelconque, Fourier traite les cas correspondants simultanément. Il faut que les dimensions d'une même matrice (n,2) soient compatibles c'est-à-dire que l'opération +/+/x soit permise.

Le résultat y a la même structure que

 

 

Par exemple si x est une matrice de dimension (n,2), chaque case contenant soit un scalaire soit un vecteur de dimension V, le calcul est fait comme si chaque scalaire était étendu V fois dans un vecteur ; chaque case du résultat y contient un vecteur de dimension V dont les composantes d'une même place résultent des composantes de la même place du x étendu. Ainsi

 

 

donne le même résultat que

 

 

Commentaires sur la fonction Fourier

 

Si T est la période d'un phénomène continu échantillonné, on peut expliquer Fourier[2] en posant

 

 

ainsi les commentaires Fourier[1] et [2] rappellent ce que la fonction calcule.

Fourier[4] ramène les (×/nbCas) ensembles au cas d'une matrice dont chaque case est un tableau. Fourier[5] force x à une matrice à 2 colonnes. Fourier[6] étend les cases de x qu'il faut, mémorise dans y la structure obtenue et en fait un tableau simple de rang 3 de dimension (NbCas,n,2) car la suite de la fonction est plus rapide sur un tableau simple que sur un tableau gigogne.

Fourier[10] calcule ce que Fourier[9] explique en commentaire, mais avec une précision améliorée, car la réduction à des sinus d'angles dans l'intervalle [-π/2, +π/2] est réalisée sur des entiers. Elle construit la table e des exp(s iωt) utiles pour la suite du calcul.

La boucle Fourier[12] à [15] est exécutée pour chaque facteur premier de n.

Pour analyser Fourier[14] il faut noter que si A+iB et C+iD sont deux vecteurs complexes rangés dans des matrices AB et CD à 2 colonnes, on peut développer leur produit scalaire ainsi :

 

 

et on calcule ses parties réelle et imaginaire respectivement par

 

 

Fourier[12] et [13] préparent les tableaux x et c nécessaires à l'exécution de Fourier[14].

Fourier[16] reconstitue la structure attendue pour le résultat.

 

La fonction Fourier présentée ci-dessus fut construite directement à partir de la théorie ; elle n'est inspirée par aucun programme antérieur en Fortran, C ou autre.