Brevet FR2741448A1 — publié le 19970523

PROCEDE ET DISPOSITIF D'ANALYSE SPECTRALE RAPIDE ET RECONFIGURABLE La présente invention se rapporte à un procédé et un dispositif d'analyse spectrale rapide et reconfigurable de signaux sous forme numérique pour le calcul de la transformée de Fourier de dimension N de ces signaux, dans lequel on décompose le calcul en des calculs de transformées de Fourier de dimensions plus faibles. Dans un certain nombre de domaines où on doit procéder à l'analyse spectrale d'un signal échantillonné, par exemple dans le domaine du radar, on utilise des dispositifs de calcul de la transformée de Fourier discrète d'une suite d'échantillons. De tels dispositfs utilisent des algorithmes de calcul dont certains sont maintenant bien connus. Ainsi pour permettre le calcul plus rapide, avec une charge de calcul plus faible, de transformées de Fourier de dimension importante, il est connu de décomposer le calcul en des calculs de transformées de Fourier de dimensions plus faibles notamment à l'aide d'algorithmes dits de base 2 . On décompose alors une transformée de Fourier discrète de N = 2q termes en 2k transformées de Fourier de 2q termes chacune.Ces algorithmes ont l'avantage d'une charge de calcul intéressante et une structure modulaire et très répétitive. Cependant, ils ne permettent pas une reconfiguration en temps réel aisée de la dimension des blocs d'échantillons complexes ni la très grande vitesse de traitement souhaitable dans certaines applications. C'est notamment le cas pour les radars modernes de surveillance du sol où on peut souhaiter changer de dimension de transformée de Fourier d'une rafale d'impulsions à l'autre et où on doit traiter un grand nombre de portes en distance, ce qui conduit à des durées minimum de calcul d'une transformée de Fourier très faible, par exemple de l'ordre de quelques dizaines de microsecondes. L'invention a pour objet un procédé et un dispositif bien adaptés à ces exigences grâce à une architecture très modulaire et une très grande capacité de traitement. Un autre objet de l'invention est un procédé et un dispositif exempts des inconvénients ci-dessus grâce à l'utilisation d'algorithmes courts. Selon l'invention, il est donc prévu un procédé d'analyse spectrale rapide et reconfigurable de signaux sous forme numérique pour le calcul de la transformée de Fourier de dimension N de ces signaux, dans lequel on décompose ledit calcul en des calculs de transformées de Fourier de dimensions plus faibles, ledit procédé étant caractérisé en ce que, si Ni et N2 sont deux nombres entiers tels que Ni x N2 = N, ledit procédé comprend au moins : - une première étape consistant à calculer N2 transformées de Fourier de dimension Ni selon un algorithme court de dimension Ni sur les N échantillons traités ; et - une deuxième étape consistant à calculer Ni transformées de Fourier de dimension N2 sur les N résultats de l'étape précédente. Selon un autre aspect de l'invention, il est également prévu un dispositif d'analyse spectrale rapide et reconfigurable de signaux sous forme numérique pour le calcul de la transformée de Fourier de dimension N de ces signaux, mettant en oeuvre un procédé tel que mentionné ci-dessus, ledit dispositif étant caractérisé en ce qu'il comprend - g processeurs élémentaires identiques en parallèle pour effectuer les additions et multiplications élémentaires nécessaires au calcul desdites N2 et Ni transformées de Fourier respectivement - des moyens d'interface d'entrée/sortie pour transmettre auxdits processeurs élémentaires lesdits échantillons du signal à analyser - une mémoire de sortie pour stocker les modules des raies spectrales calculés par lesdits processeurs élémentaires et transmis par l'intermédiaire desdits moyens d'interface - un séquenceur d'entrée/sortie pour fournir auxdits moyens d'interface les adresses d'écriture des échantillons qui leur sont fournis et à la mémoire de sortie les adresses d'écriture des modules des raies spectrales reçues desdits processeurs ; et - un séquenceur de calcul pour fournir, sous la commande de synchronisation dudit séquenceur d'entrée/sortie, les coefficients des transformées de Fourier et des adresses de mémoire de microcodes d'instruction auxdits processeurs élémentaires ainsi que les adresses de mémoires internes desdits processeurs. L'invention sera mieux comprise et d'autres caractéristiques et avantages apparaîtront à l'aide de la description ci-après et des dessins joints où - la figure l représente le graphe de circulation des données d'un algorithme diagonal de Winograd de dimension 8 - la figure 2 est le graphe de circulation des données de l'algorithme de base 4 - la figure 3 est le graphe de circulation de données pour le calcul d'une transformée de Fourier de N = 32 points d'après le procédé selon l'invention ; - la figure 4 est le graphe de circulation de données pour le calcul d'une transformée de Fourier de N = 64 points d'après le procédé selon l'invention ; - la figure 5 est le schéma fonctionnel d'un dispositif d'analyse spectrale selon l'invention ; et - la figure 6 représente le schéma d'un processeur élémentaire du dispositif de la figure 5. A titre d'exemple pour fixer les idées et rendre plus claire la description, on va décrire l'invention dans le cadre du calcul de transformée de Fourier de dimension reconfigurable N = 32 ou 64 points, sans que cela soit en rien limitatif de l'invention. On va d'abord rapidement passer en revue deux types d'algorithmes rapides connus de transformation de Fourier discrète qui sont d'une grande utilité pour le dispositif selon l'invention. Sur la figure 1 est représenté le graphe de circulation Wi d'un algorithme court ou diagonal dit de Winograd de dimension 8. De tels algorithmes sont décrits plus en détail par exemple dans l'article de S. Winograd "On computing the Discrete Fourier Transform" paru dans Proc. Nat. Acad. Sc USA (avril 1976), 73, n' 4 pages 1005-1006. Ils permettent le calcul de transformées de Fourier discrètes (TFD) de petites dimensions d'une manière très performante grâce à une très faible charge de calcul. Ils ne comportent que des multiplications par des réels ou des imaginaires purs. Sur la figure 1, aO à a7 représentent les échantillons d'entrée, Ag à A7 les différentes points de la TFD. Sur le graphe, chaque point où une ligne horizontale et une ligne oblique se rejoignent, en allant vers la droite du dessin, représente une addition. Si l'on rencontre un signe moins sur la ligne qui achemine une donnée, celle-ci est affectée du signe moins, ce qui correspond à une soustraction au point suivant. La colonne centrale correspond à des multiplications par des réels 1 ou On effectue ensuite des multiplications par j sur les quatrième, sixième et septième lignes. La charge de calcul en opérations élémentaires est de quatre multiplications et cinquante-deux additions. L'ordre des points en sortie présente des permutations. La figure 2 qui s'interprète de la même façon représente le graphe de base de circulation B des données pour a l'algorithme de base 4. Ce "papillon" de base très simple ne fait intervenir aucune multiplication. Le principe de base du procédé selon l'invention est le suivant. Si l'on note a = (a0, a1, ... aN 1) un vecteur complexe de dimension N, aO . . aN-1 étant par exemple des échantillons complexes d'un signal à analyser, le calcul direct de la TFD de a s'écrit avec k = 0, 1, ... , N-1 et la notation m entier Si l'on suppose que N est le produit de deux entiers N1 et N2, l'idée de base consiste - Si N1 et N2 sont premiers entre eux, à effectuer un changement sur les indices temporels i = nlN2 + n2Nl modulo N k = k1N2 + k2N1 modulo N avec : nl, kl = O, 1, . . , N1-1 n2, k2 = 0, 1, .. , N2-1 La transformée de Fourier devient alors après permutation sur les variables kl et k2 telle que ki - > k*j ki # avec Nj k*j = 1 [mod.Ni] i # j i, ; = 1, 2 On voit que cette transformée de Fourier discrète peut donc se calculer en calculant N2 transformées de Fourier de dimension N1 suivi du calcul de N1 transformées de Fourier de dimension N2. - Si N1 et N2 ne sont pas premiers entre eux, à effectuer un changement sur les indices temporels i = nlN2 + n2 modulo N k = kl + k2N1 modulo N avec n1, k1 = 0, 1 ... , N1-1 n2, k2 = 0, 1, ... , N2-1 On obtient alors l'expression d'une transformée de Fourier bidimensionnelle On voit que cette transformée de Fourier discrète peut donc se calculer en trois phases - calcul de N2 transformées de Fourier de dimension N1 - calcul de N multiplications complexes respectivement par les coefficients - calcul de Ni transformées de Fourier de dimension N2. On peut démontrer que la charge de calcul est alors proportionnelle à la somme N1+N2. On doit donc choisir N1 et N2 de manière à minimiser cette somme. Dans les deux cas ci-dessus, le procédé selon l'invention prévoit de calculer les transformées de Fourier de dimension N1 et N2 grâce à l'emploi d'algorithmes courts très performants, ceci étant possible grâce à la réduction des dimensions des TUF'). L'algorithme le plus intéressant est l'algorithme diagonal de Winograd dont le graphe de circulation des données pour la dimension 8 est donné sur la figure 1. La figure 3 représente le graphe de circulation des données pour le calcul d'une transformée de Fourier discrète de dimension N=32. On choisit les valeurs N1=8 et N2=4 et on utilise donc l'expression (2). Les échantillons d'entrée sont répartis selon quatre graphes WiO à Wi3, correspondant aux valeurs de n2 = 0, 1, 2, 3 respectivement, qui sont suivis de N2=4 ensembles de multiplications complexes WO à W3 correspondant aux multiplications par les coefficients respectivement. Les résultats sont répartis selon huit graphes BaO à Ba7 correspondant à des transformées de Fourier de base 4. Les indices concernés sont indiqués à chaque niveau de progression du calcul.Ainsi, par exemple, les valeurs de l'indice 4nl+n2 pour la répartition des échantillons d'entrée et les valeurs de l'indice kl+8k2 pour la répartition des points de transformée de Fourier en sortie. La figure 4 représente le graphe de circulation des données pour le calcul d'une transformée de Fourier discrète de dimension N=64. On choisit alors les valeurs N1=8 et N2=8 et on utilise donc l'expression (2). Les échantillons d'entrée sont répartis selon huit graphes WiO à Wi7 correspondant à des transformées de Fourier selon l'algorithme de Winograd de dimension 8. On trouve ensuite huit ensembles de multiplications complexes W'O à W'7 correspondant aux multiplications par les coefficients p2kl 64 respectivement. Les résultats sont répartis selon huit graphes Wi'O à Wi'7 correspondant à des transformées de Fourier selon l'algorithme de Winograd de dimension 8. On voit ainsi qu'il suffit de mémoriser quelques algorithmes courts tels que Winograd de dimension 8 ou base 4 pour pouvoir reconfigurer très facilement les calculs pour l'obtention de nombreuses TFD de grandes dimensions. La figure 5 représente le schéma fonctionnel d'un dispositif d'analyse spectrale mettant en oeuvre le procédé selon l'invention. Ce dispositif comporte essentiellement des processeurs élémentaires PE1 à PE4 identiques fonctionnant en parallèle. Le nombre de processeurs peut être choisi en fonction de la charge de calcul à assurer, par exemple en fonction du nombre de portes en distance d'un radar, c'est-à-dire du nombre maximum de spectres à calculer. Les échantillons d'entrée complexes (composantes x et y) provenant d'une mémoire amont (non représentée) sont envoyés aux processeurs élémentaires par l'intermédiaire d'une interface d'entrée/sortie 2. Une mémoire de sortie 4 stocke les modules des raies spectrales calculées par les processeurs élémentaires. L'écriture s'effectue avec des adresses fournies par l'interface 2 à partir des adresses d'écriture des échantillons d'entrée qui sont générées par un séquenceur d'entrée/sortie 1. Ce séquenceur 1 fournit également les adresses de lecture et l'horloge pour la mémoire amont non représentée et les adresses de lecture de la mémoire de sortie 4. Il reçoit des informations d'initialisation et contrôle un séquenceur de calcul 3. Celui-ci fonctionne à l'aide de microcodes d'instruction à champs multiples stockés en mémoire assurant le séquencement du programme et des calculs des processeurs élémentaires. Pour cela, le séquenceur 3 fournit les adresses nécessaires aux processeurs élémentaires pour les différentes phases du calcul, les coefficients W du calcul et des adresses de microcodes dans les processeurs, ces microcodes déterminant les diverses opérations successives d'addition et de multiplication à effectuer selon les algorithmes choisis. L'ensemble de ces circuits peut être par exemple réalisé à l'aide de circuits de traitement du signal de la famille WORD SLICE commercialisée par la société ANALOG DEVICES. Ainsi on a représenté sur la figure 6 le schéma d'un processeur élémentaire basé sur l'emploi d'une mémoire à registres multiaccès 102, type ADSP-3128A, et d'une unité arithmétique et logique 103, type ADSP-1101. Les échantillons venant de l'interface 2 sont appliqués à des mémoires d'entrée 100, 101 de type FIFO puis envoyés sur un accès ,B, de la mémoire 102. L'unité arithmétique et logique 103 a ses entrées x et y reliées aux sorties C et D de la mémoire 102 et reçoit également les coefficients W venant du séquenceur de calcul 3. La sortie de l'unité 103 est reliée à des mémoires de sortie 104, 105 du type FIFO ainsi qu'à un autre accès d'entrée A de la mémoire 102. L'écriture des mémoires d'entrée 100, 101 et la lecture des mémoires de sortie 104, 105 sont synchronisées et vice-versa. L'ensemble des instructions pour le fonctionnement du processeur élémentaire, notamment pour le contrôle de l'unité 103, est fourni par des microcodes issus d'une mémoire de microcodes 106 qui est adressée par le séquenceur de calcul 3 en fonction des opérations successives à effectuer et des paramètres déterminant le mode de fonctionnement (dimension N, nombre de portes du radar, ...). Il est clair qu'un tel processeur peut effectuer toutes les opérations successives d'une analyse spectrale, à savoir - pondération des échantillons - calcul de la TFD ; - calcul du module des raies spectrales. Les circuits utilisés étant bien connus, leur fonctionnement ne sera pas détaillé. Après initialisation du dispositif la mémoire d'instruction du séquenceur 3 fournit les adresses de microcode, les commandes d'adresses de mémoire et les coefficients nécessaires aux processeurs élémentaires. Ceux-ci effectuent séquenciellement les opérations élémentaires telles qu'elles sont représentées par exemple sur les graphes des figures 1 et 3. Ainsi les échantillons aO et a16 (Figure 3) sont additionnés et soustraits puis les échantillons a4 et a20, etc ... Ainsi tous les points de la mémoire 102 (Figure 6) où se trouvaient les échantillons aO à sont SO"t progressivement chargés à la place par les résultats correspondants des opérations en cours. Grâce au procédé de calcul utilisé, on obtient une réduction très importante de la charge de calcul et une grande modularité du logiciel. On peut reconfigurer en temps réel de nombreuses TFD, tant à cause de la modularité du système que de l'architecture adoptée qui permet en outre de s'adapter très facilement à la rapidité et au volume de calcul nécessaire (nombre de spectres à calculer), simplement en adaptant le nombre de processeurs élémentaires. Bien entendu, les exemples de réalisation décrits ne sont nullement limitatifs de l'invention. REVENDICATIONS 1. Procédé d'analyse spectrale rapide et reconfigurable de signaux sous forme numérique pour le calcul de la transformée de Fourier de dimension N de ces signaux, dans lequel on décompose ledit calcul en des calculs de transformées de Fourier de dimensions plus faibles, ledit procédé étant caractérisé en ce que, si N1 et N2 sont deux nombres entiers tels que N1 x N2 = N, ledit procédé comprend au moins - une première étape consistant à calculer N2 transformées de Fourier de dimension N1 selon un algorithme court de dimension N1 sur les N échantillons traités ; et - une deuxième étape consistant à calculer N1 transformées de Fourier de dimension N2 sur les N résultats de l'étape précédente. 2. Procédé selon la revendication 1, caractérisé en ce que, N1 et N2 étant premiers entre eux, ladite première étape de calcul de N2 transformées de Fourier utilise un algorithme diagonal de Winograd, en ce que lesdites étapes sont effectuées selon l'expression de la transformée de Fourier bidimensionnelle suivante où nl et kl sont des entiers variables compris entre O et N1-l, où n2 et k2 sont des entiers variables compris entre O et N2-1, a représente les échantillons complexes du signal à analyser et A les différents points de la transformée de Fourier dudit signal, et où est un coefficient complexe tel que 3.Procédé selon la revendication 1, caractérisé en ce que, N1 et N2 n'étant pas premiers entre eux, le calcul de la transformée de Fourier de dimension N s'effectue selon l'expression de la transformée de Fourier bidimensionnelle suivante où nl et kl sont des entiers variables compris entre O et N1-l. où n2 et k2 sont des entiers variables compris entre O et N2-1, a représente les échantillons complexes du signal à analyser et A les différents points de la transformée de Fourier dudit signal, et où est un coefficient complexe tel que en ce que, entre la première et la deuxième étapes, est insérée une étape intermédiaire consistant à effectuer N multiplications complexes par les coefficients respectivement sur les N valeurs obtenues dans la première étape et en ce que les nombres N1 et N2 sont choisis de manière à minimiser la somme N1+N2. 4. Procédé selon la revendication 3, caractérisé en ce que ladite première étape s'effectue selon un algorithme diagonal de Winograd de dimension N1 et ladite deuxième étape s'effectue selon un algorithme diagonal de Winograd de dimension N2. 5. Procédé selon la revendication 3, caractérisé en ce que ladite première étape s'effectue selon un algorithme diagonal de Winograd de dimension Nt et ladite deuxième étape s'effectue selon un algorithme de base 2P = N2, lorsque N2 est une puissance de 2. 6. Dispositif d'analyse spectrale rapide et reconfigurable de signaux sous forme numérique pour le calcul de la transformée de Fourier de dimension N de ces signaux, mettant en oeuvre le procédé selon l'une quelconque des revendications 1 à 5, ledit dispositif étant caractérisé en ce qu'il comprend - g processeurs élémentaires (PE1 à PE4) identiques en parallèle pour effectuer les additions et multiplications élémentaires nécessaires au calcul desdites N2 et N1 transformées de Fourier respectivement - des moyens d'interface d'entrée/sortie (2) pour transmettre auxdits processeurs élémentaires lesdits échantillons du signal à analyser - une mémoire de sortie (4) pour stocker les modules des raies spectrales calculés par lesdits processeurs élémentaires et transmis par l'intermédiaire desdits moyens d'interface (2) - un séquenceur d'entrée/sortie (1) pour fournir auxdits moyens d'interface (2) les adresses d'écriture des échantillons qui leur sont fournis et à la mémoire de sortie (4) les adresses d'écriture des modules des raies spectrales reçus desdits processeurs (PE1 à PE4) ; et - un séquenceur de calcul (3) pour fournir, sous la commande de synchronisation dudit séquenceur d'entrée/sortie (1), les coefficients (31) des transformées de Fourier et des adresses de mémoire de microcodes d'instruction (30) auxdits processeurs élémentaires ainsi que les adresses de mémoires internes desdits processeurs. 7. Dispositif selon la revendication 6, caractérisé en ce que chacun desdits processeurs élémentaires (PE1 à PE4) comprend - des moyens de mémoire à registres multiaccès (102) ayant des accès d'entrée (A, B) et des accès de sortie (C, D) - des moyens de mémoire d'entrée (100, 101) du type FIFO recevant sur leurs entrées lesdits échantillons fournis par les moyens d'interface (2) et dont les sorties sont connectées à un des accès d'entrée (B) desdits moyens de mémoire multiaccès (102) - une unité arithmétique et logique (103) susceptibles d'effectuer des multiplications, des additions ou des soustractions avec accumulation sous la commande de microcodes d'instruction, ladite unité ayant des entrées reliées auxdits moyens de mémoire multiaccès (102) et pouvant également recevoir lesdits coefficients des transformées de Fourier fournies par ledit séquenceur de calcul (3) et une sortie reliée à un autre accès (A) desdits moyens de mémoire multiaccès (102) - des moyens de mémoire de sortie (104, 105) du type FIFO dont les entrées sont connectées à la sortie de ladite unité arithmétique et logique (103), lesdits moyens de mémoire d'entrée et de sortie étant commandés simultanément les uns en écriture, les autres en lecture et vice-versa ; et - une mémoire de microcodes (106) adressée par ledit séquenceur de calcul (3) et fournissant lesdits microcodes d'instruction à l'unité arithmétique et logique.