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.