Transformée de Fourier Discrète

La Transformée de Fourier Discrète (TFD), (DFT : Discrete Fourier Transform) est un élément essentiel dans l’ analyse, la conception et la mise en oeuvre des algorithmes et systèmes du traitement du signal à temps discret. En physique numérique, on dispose presque toujours de signaux issus d’ une acquisition électronique ou de résultats de mesures discrètes. Ces signaux et résultats ne sont pas infinis, et généralement sont non périodiques. La TFD a été conçue pour traiter ce genre de données. Elle réalise une décomposition d ‘un signal tronqué (fini, de durée T) et échantillonné (discret) en une série de Fourier, en le « périodisant », avec une période égale à T. La TFD nous permet donc de calculer de façon approchée les coefficients de Fourier des différentes harmoniques d’un signal quelconque et ainsi d’ obtenir son spectre en fréquence. Son application est donc utilisée dans plusieurs domaines technologiques tels que les télécommunications, le biomédic »al, le traitement séismique, etc. [YW07], [MJ08] La DFT d’ un signal discret x(n) peut-être directement calculée par l’ équation (2.1), (2.1) Avec x(n) etX(n), respectivement, représentent la séquence d’ entrée et la séquence de sortie en nombre complexe et N est la longueur de la transformée.

À partir de l’équation (2.1), on constate que la complexité de calcul de la TFD s’exprime en O(N2 ) , il augmente avec le carré de la longueur de la transformée et donc devient cher pour des N larges. Plusieurs additions et soustractions, en plus de quelques autres opérations, sont nécessaires donc pour réaliser une seule multiplication complexe. C’est pour ces raisons que la TFD n’ est pas utilisée pour le traitement du signal temps réel. Puisque le processeur numérique est généralement limité par la taille de sa mémoire. La taille de la TFD N limite les calculs exécutés le processeur [WY07]. L’ équation de définition de la DFT fournit une relation entre deux ensembles de N nombres complexes, en posant: W:k = e-j (2rr/N)nk avec l =-1 (2.2) W: est appelé Facteur de Fourier (TWF – Twiddle Factors), plusieurs propriétés caractéristiques de la représentation de ce coefficient sont utilisées [A V03], par exemple : W kn _ w.k(n+N) _ w. (k+N)n N – N – N W2kn – W kn N – N/2 Où x* représente le complexe conjugué de la donnée complexe x. (2.3) Une forme matricielle montrée par l’ équation (2.4) de la DFT peut être donc déduite. [ WJ WJ x(k) = : W°w.(N-l) N N Elle peut être représentée sous la forme matricielle suivante: (2.4) (2.5) Avec [BN] la matrice des coefficients et [Xn] la matrice d’ entrée de la TFD. Donc la TFD est une décomposition d’ un signal échantillonné, composé de sinusoïdes. En exploitant les propriétés de symétrie et de périodicité de la TFD, plusieurs méthodes efficaces ont été développées pour calculer la TFD et ainsi diminuer significativement la charge de calcul.

La Transformée de Fourier Rapide

En introduisant le premier algorithme de la FFT en 1965, Cooley&Tukey ont été capable de réduire d’une façon remarquable le temps de calcul de la TFD d’une suite de nombre d’ échantillons N qui est une puissance de 2, connu sous le nom de radix-2 [JC65]. Depuis, et encore dans les dernières années, les algorithmes de FFT ont été dans le centre d’ intérêt pour de nombreuses recherches qui ont révolutionné le traitement numérique de signal (DSP : Digital Signal Processing). La réduction du nombre d’opérations nécessaires, en particulier le nombre des multiplications constituent leurs avantages essentiels et est devenu l’approche de base dans toutes les nouvelles applications. La grande majorité des algorithmes sont basés sur un même principe qUi consiste à décomposer le calcul de la TFD en plusieurs sous-ensembles de TFD de longueur plus petite. En profitant des propriétés de symétrie et de périodicité suivant les équations (2.6) et (2.7) des facteurs de phases: 2.4 Architectures pipelines pour le calcul de la FFT L’ architecture en pipeline radix-r FFT (figure 9) est caractérisée par un traitement continu des entrées séquentielles de la FFT. Une telle architecture est composée de logr(N) modules de calcul (MC), un par étage, qui correspond aux opérateurs papillon.

La valeur de r correspond au radix de l’ algorithme utilisé. Chaque BPE traite N/r opérations successives. Par conséquent, la taille maximale réalisable pour ce type d’architecture est dictée par le nombre de MC. En effet, ce type d’ architecture offre un bon compromis complexité matérielle/taux de traitement de données pour les systèmes de communication à haut débit [YJ03]. Comme le montre la figure 9, l’architecture comporte un nombre de modules ‘Commutator’ . Ces derniers réorganisent les données entre les BPE et contiennent les modules de délais. À chaque étage du pipeline, un BPE, calcule r donnés de valeurs complexes, puis génère r donnés intermédiaires à la sortie. On a donc un débit de données r fois la fréquence d’ horloge. Pour un BPE de radix-2 qui fonctionne à R MHz, les données sont traitées à une fréquence de 2R MHz, puisque deux données sont traitées au cours de chaque période d’ horloge. [YJ03]. Il existe plusieurs architectures en pipeline basé principalement selon deux points :

1. Le premier point de différence est le nombre de chemins de données utilisés pour traiter les échantillons. Il y a deux types d’ architectures: i) à chemin unique (Singlepath; S) et ii) à chemin multiple (Multi-path; M).

2. Le deuxième point de différence consiste en la stratégie de mémorisation pour créer les différents délais nécessaires à l’ ordonnancement des échantillons.

Multi-path Delay Commutator MDC

L’architecture radix-r MDC (Multi-path Delay Commutator) est considérée comme l’une des conceptions les plus utilisées dans la mise en oeuvre des systèmes de communication à haut débit. Un des éléments qui fait partie de cette architecture est le commutateur qui a pour rôle de permuter les données entre les étages de l’architecture, on trouve aussi des délais pour synchroniser ces mêmes données. Dépendamment de l’algorithme radix-r utilisé, nous aurons r-l délais avant et après chaque module BPE. De plus, cette architecture nécessite r-l multiplieurs par module BPE. On peut trouver plusieurs variétés de cette architecture, nous trouvons par exemple le R2MDC et le R4MDC qui sont les architectures les plus populaires, on trouve aussi les radix supérieures comme le radix-22 et radix-23. De plus, l’approche MDC est l’architecture la plus adaptée dans les nouvelles applications puisqu’ elle possède un multiple chemin d’ entrées et de sorties [FB09]. Cette propriété permet aux modules FFI utilisant cette architecture d’ opérer à haute vitesse avec un haut débit. D’une autre part, cette architecture utilise plus de ressources matérielles. Une des méthodes utilisées pour réduire la consommation est d’ aller plus haut dans le degré de la FFI implémentée. La figure 13 représente l’ architecture pipeline R4MDC à 4 canaux pour N=64 points.

Cette architecture utilise quatre chemins d’ entrées en parallèle, et la même chose est trouvée en sortie. Le flux de données d’ entrée et les données inter-étage sont contrôlés avec des commutateurs. Ces derniers sont implémentés par de simples éléments de délais et un multiplexeur, ce qui réduit leurs complexités matérielles au cours de leurs implémentations. Le rôle de ces commutateurs est de réorganiser les quatre flux d’entrées/sortie de données avant de les injecter dans l’ étage suivant [YJ03]. La complexité matérielle du coprocesseur FFI de radix-r MDC, avec r la valeur du radix, peut être réduite en utilisant d’ autres algorithmes comme le Mixed-radix plus et le Splitradix [ES84] [SL07]. La figure 14 représente l’ architecture MC-MRMDC (Mufti Channel – Mixed Radix Multipath Delay Commutator) présentée dans [SL07] pour N = 64 points et k = 4, où k est le nombre de canaux.

Cette architecture, utilise l’ algorithme Mixed radix est permet de diminuer le nombre des ressources utilisées en diminuant le nombre de multiplications nontriviales. En comparant les deux coprocesseurs radix-4 MDC et MC-MRMDC, on peut remarquer que le premier illustré dans la figure 13 utilise 6 multiplications non-triviales tandis que le deuxième illustré dans la figure 14 n’ utilise que 4 multiplications non-triviales, [SL07]. Le tableau 3 contient une comparaison des exigences matérielles de plusieurs architectures FFT pipelines y compris le radix-2 2SDF, le radix-23 SDF et le MRMDC. La constante T désigne le nombre des additionneurs requis pour implémenter une multiplication triviale. D’ après le tableau 3, pour k = 4 et N = 64, l’architecture MC-MRMDC sauve 2 multiplications non-triviales comparant à l’architecture radix-4 MDC et 76 additionneurs complexes comparant à l’architecture radix-23 SDF. On constate donc, qu’en utilisant l’architecture pipeline MDC, on utilise moins de processeurs. À titre d’exemple ; pour implémenter un système à 4 canaux; on aura besoin de 4 processeurs utilisant l’ architecture pipeline SDF au lieu d’un seul processeur utilisant l’ architecture MDC. On réalise ainsi un grand gain en termes de ressources matérielles. Ce qui constitue la raison que la plupart des implémentations VLSI des coprocesseurs FFT tendent à utiliser l’ architecture pipeline MDC. [SL07].