Dept GEII IUT Bordeaux TRANSFORMEES de FOURIER NUMERIQUE DISCRETE (FAST FOURIER TRANSFORM) APPLICATIONS (Vol. 4) G. couturier Tel : 05 56 84 57 58 email : [email protected] iuta. u-bordeaux. fr Sommaire l- Transformée de Fo ll- Transformée de F 11-1- les fenêtres dian Snipe to View er Transformées de Fourier numérique et discrète : FFT (Fast Fourier Transform) Applications Nous avons montré précédemment l’intérêt de la transformée de Fourier pour obtenir par exemple la réponse en fréquence H(f) d’un système.
Le calcul de la transformée de Fourier pose cependant un certain nombre de problèmes, en effet un rdinateur ne peut traiter que des signaux numériques, ceux-ci sont obtenus après un échantillonnage et une quantification. Par ailleurs la memoire d’un ordinateur est forcément limitée, il s’ensuit que le calcul porte sur un nombre de points limités. récédemment que le spectre du signal échantillonné était périodique, de période égale à Fe – 1/Te, et que son module était pair. D’un point de vue mathématique la transformée de Fourier Xl(f) des échantillons x(nTe), appelée transformée de Fourier numérique, s’écrit • xl(f)- Ex(k) e- lu. ‘kTe NB : pour simplifier l’écriture on écrit x(k) à la place de x(kTe), ce qui sous entend un échantillonnage à
On vérifie bien que XI (f) est une fonction périodique de période Fe, en effet si on remplace f par (f+MFe) on obtient toujours le même résultat • e -j 21Mf• ee-j21WFeae=e-j2 TtfkTe e — j 2nMk = e — j 2 TtfkTe Par ailleurs, on remarque que les parties réelle et imaginaire de Xl(f) sont respectivement des fonctions paire et impaire de la variable fr il s’ensuit que le module de Xl(f) est également une fonction paire de la variable f. La périodicité de Xl(f) résulte de l’échantillonnage, c’est un résultat que nous avions déjà obtenu en étudiant la théorie de l’échantillonnage.
Avec un ordinateur il est impossible de calculer XI (f) pour k allant de – effet il faudrait une mémoi pratique, le nombre PAG » – jwkTe signal échantillonné Te échantillonneur théorique de la fréquence f. Comme Z(f) est périodique, de période Fe dans l’espace des fréquences, on découpe l’intervalle Fe en N parties égales et on ne calcule Z(f) que pour les multiples de Fe/N comme le montre la Fig. 3, on vient ainsi d’introduire la transformée de Fourier discrète. On note Z(n) les composantes de la transformée de Fourier discrète; Z(n) Z(f) calculé pour f = nFe/N avec n = O, 1, (N-l). L’indice n est référencé comme le canal. =N-1 – j2 e kTe k)e z( k) e— j2 rtnk / N pour n- x(t) PAGF multiplications et 2(N-1)N additions. Le temps de calcul est d’autant plus long que le nombre de points d’acquisition est élevé, et on arrive très vite à des temps de calcul très longs de l’ordre de quelques millisecondes pour 1000 points (cas d’un processeur ? 300 MHz avec 5 cycles machine pour une multiplication). Dans le cas où le nombre de points ‘acquisition N est une puissance de deux (N=2n), on dispose d’algorithme de calcul très rapide ramenant le nombre de multiplications à : Nn. Ces algorithmes portent le nom de FFT (Fast Fourier Transform).
L’algorithme le plus connu est celui de Cooley-Tuckey. Le nombre de multiplications est donc divisé par 2N/n (exemple : si N = 1024 210, le nombre de multiplications est divisé grosso modo par 200 ramenant le temps de calcul à quelques microsecondes). Sans l’introduction d’algorithmes de calcul rapide, la transformée de Fourier discrète serait probablement restée un objet mathématique sans rand intérêt. Remarque: Dans un algorithme de FFT, les composantes Z(n) sont obtenues simultanément en fin de calcul, il faut donc réaliser les Nn multiplications même si seulement P composantes sont intéressantes.
Dans le cas d’un algorithme de calcul n’utilisant pas la FFT (an parle alors de DFT pour Direct Fourier Transform), le calcul des Z(n) est indépendant, c’est ? dire que l’on peut décider de calculer par exemple Z(2) et Z(5) sans calculer 43), 44), . pour obtenir p com calculer par exemple Z(2) et Z(5) sans calculer Z(l ), Z(3), Z(4), Pour obtenir P composantes de Z(n), il faut donc réaliser 2NP ultiplications. Pour savoir SI un algorithme de FFT s’impose, il faut donc comparer Nn et 2NP, (exemple : si N = 1024 un algorithme de FFT s’impose à partir de p = 5).
Remarque: Si le nombre de points d’acquisition n’est pas une puissance de deux, on a intérêt à compléter la longueur de l’enregistrement par des zéros afin de pouvoir utiliser un algorithme de FFT, cette technique porte le nom de technique de remplissage (zero padding en anglais), (exemple : N = 1000, on fait z(k) = O pour 1000, 1001, 1002, 1023). ce remplissage par des zéros ne modifie pas Z(f), par contre le pas de calcul dans l’espace des réquences devient Fe/ 1024 et non plus Fe/1000.
Dans le cas précédent, on pourrait être tenté de tronquer la suite des échantillons pour ramener leur nombre ? 512 et gagner ainsi en temps de calcul. Cette dernière opération conduit à modifier les Z(n) si les échantillons z(k) sont différents de zéros pour k allant de 512 à 999. En supposant régler le problème du calcul des Z(n), on peut se demander si les composantes Z(n) sont bien égales aux valeurs de Xl(f) calculées pourf nFe/N. Analysons les cas les plus fréquemment rencontrés. 1er cas : les échantillons x(k) sont nuls pour (N-l)< k
