FR 2681453 A1 19930319 FR 9210886 A 19920911 Structure de circuit pour l'exécution de la transformation de Fourier rapide L'invention concerne une structure de circuit pour l'exécution de la transformation de Fourier rapide par un fonctionnement commandé d'opérateurs papillon en réseau, auxquels sont associés des multiplicateurs et auxquels sont appliquées les données d'entrée. La transformation de Fourier rapide, encore appelée "Fast Fourier Transformation" (FFT) est utilisée entre autres pour l'évaluation des signaux radar en liaison avec le traitement des données Il convient que la FFT soit exécutée avec un débit élevé des données, notamment pour l'algorithme d'augmentation de netteté de faisceau Doppler (Doppler Beam Sharpening Algorithm) En général, on utilise pour l'exécution de la FFT des processeurs rapides tels que des transputers. Un agencement de circuit du type indiqué est décrit par exemple dans l'article de P Eckelmann "Transputer richtig eingesetzt; Beispiele fur die Fourier-Transformation in OCCAM" (ELEKTRONIK brochure 4 du 22 02 85, pages 57 à 62) Un autre agencement de circuit est connu sous la forme du processeur de signaux FFT TMS 320 (ELEKTRONIK brochure 21 du 17.10 86, pages 101 à 110). Quand on exécute la FFT sur une calculatrice numérique, l'algorithme approprié est utilisé de façon répétée sur des cellules à mémoire De ce fait, la FFT n'est pas exécutée avec des circuits universels optimaux qui doivent être programmés pour leur utilisation en fonction de l'algorithme de transformation à traiter Il est vrai qu'une FFT destinée à l'analyse de fréquence de valeurs dépendant du temps est possible en optimisant le logiciel pour des circuits universels de ce type Mais des limites sont imposées à la vitesse de calcul du mode de travail de ces calculatrices du fait de la structure du programme de calcul Ces limites sont particulièrement gênantes quand il s'agit de transformer en temps réel un nombre élevé de données d'entrée (appelées 'mots") discrètes et complexes (c'est-à-dire constituées par une partie réelle et une partie imaginaire), ainsi que cela est nécessaire par exemple pour le traitement des signaux d'installations radar haute fréquence en vue de tâches de classification. Comme le traitement demande relativement beaucoup de temps en raison du nombre élevé des données et du type déterminé de traitement, la possibilité a été fournie au cours des dernières années du fait des vitesses d'intégration qui sont toujours plus élevées, de développer un processeur à puce fortement intégré qui résout au moyen du matériel l'algorithme nécessaire à la FFT. Il en résulte que certaines étapes du programme qui étaient jusqu'alors nécessaires deviennent inutile. La transformation de Fourier rapide (FFT) est traitée en général avec un réseau d'opérateurs papillon ou opérateurs butterfly individuels et accouplés les uns aux autres Les paires de valeurs d'entrée de la plage de temps sont combinés dans les opérateurs papillon et un résultat complexe transformé dans la plage de fréquences est obtenu sur l'énergie et la position de phase des lignes spectrales. Les opérateurs papillon sont montés sur une puce, une mémoire et un multiplexeur leur étant associés Deux valeurs d'entrée complexes sont traités simultanément de façon précise dans chaque opérateur papillon au cours de chaque impulsion d'horloge Mais les données arrivent en série Il faut donc mettre en mémoire intermédiaire un cycle d'attente jusqu'à ce que des données soient à nouveau demandées à l'entrée Dans le même temps, on a choisi la solution consistant à rétrocoupler les valeurs de sortie aux entrées De ce fait, cette structure comprend de larges bus de données qui ne sont utilisés que pendant 50 % du temps Comme il est peu important pour l'utilisation du silicium sur la puce qu'il y soit placé des transistors, des éléments de commutation ou des lignes, un besoin de place important n'est pas totalement satisfait dans ce cas. L'invention a donc pour but de constituer les opérateurs papillon de manière qu'ils puissent exercer leur fonction sans rétrocouplage de phases de données et de pouvoir intégrer les opérateurs papillon sur une surface limitée de la puce. Selon l'invention, ce but est atteint en prévoyant deux multiplicateurs dans chaque demi- opérateur papillon, dans lesquels sont traités respectivement deux valeurs d'entrée au cours de deux cycles pour obtenir deux valeurs de sortie, ces valeurs d'entrée étant traitées à l'intérieur de deux cycles de manière que les données puissent être continuellement transmises dans les demi-opérateurs papillon sans avoir à combler des lacunes de temps. Selon cette solution, la transformation de Fourier rapide s'effectue dans une structure permettant un travail sans périodes vides et fournissant les résultats désirés sans rétrocouplage de phases de données Bien que les opérations de calcul soient les mêmes et que le besoin en éléments individuels soit important, le besoin en surface de puce est réduit considérablement par rapport aux structures connues, car des bus pour le retour de données ne sont plus nécessaires On dispose donc de la même capacité qu'avec un processeur FFT à papillons complets tout en réduisant nettement le matériel et avec un retardement du passage légèrement plus élevé (pipeline delay). Les demi-opérateurs papillon traitent deux valeurs d'entrée au cours de deux cycles de manière que les données puissent être continuellement avancées dans les demi-opérateurs papillon sans avoir à combler des lacunes de temps. Selon l'invention, une série de demi-opérateurs papillon sont montés les uns à la suite des autres, et à la suite de chaque demi-opérateur papillon est monté un multiplexeur 32 bits qui peut être commandé de manière à court-circuiter le demi-opérateur papillon associé. L'invention prévoit de monter en amont du premier demi-opérateur papillon un étage d'entrée et une mémoire d'entrée, ces deux éléments comprenant chacun un multiplexeur 16 bits. Au dernier demi-opérateur papillon et à son multiplexeur 16 bits sont associés un étage de sortie et un autre multiplexeur 32 bits duquel sont prélevés les valeurs de sortie. Selon l'invention, chaque demi-opérateur papillon peut être adressé individuellement. Chaque demi-opérateur papillon calcule les valeurs A' et B' selon les formules: A'= A+WB = lAi+(Wi Bi-Wq Bq)l + j lAq+(Wq Bi+Wi Bq)l B'= A- WB = lAi-(Wi Bi-Wq Bq)l + j lAq-(Wq Bi+Wi Bq)l i représentant la partie imaginaire et q la partie réelle, et W le facteur de rotation. Avantageusement, la partie réelle A est appliquée par l'intermédiaire de deux organes de temporisation à un additionneur et à un soustracteur. La partie imaginaire Bi avec la partie imaginaire du facteur de rotation Wi sont appliquées en commun au premier multiplicateur, et la partie imaginaire Si avec la partie réelle du facteur de rotation Wq au second multiplicateur. Avantageusement, des deux organes de temporisation sont montés en aval du premier multiplicateur et deux organes de temporisation en aval du second multiplicateur. Le résultat du premier multiplicateur peut être appliqué par 1 'intermédiaire des deux organes de temporisation à un étage additionneur et soustracteur. Le résultat du second multiplicateur peut être appliqué par l'intermédiaire de ses trois organes de temporisation et d'un multiplexeur à l'étage additionneur et soustracteur. Le résultat du second multiplicateur peut être appliqué par l'intermédiaire d'un premier organe de temporisation au multiplexeur. Selon l'invention, la sortie de 1 'étage additionneur et soustracteur est appliquée à l'additionneur et au soustracteur. Les sorties de l'additionneur et du soustracteur sont alors appliquées au multiplexeur associé. Finalement, l'invention prévoit que les valeurs d'entrée qui sont fournies simultanément par les organes de temporisation sont retardées de manière qu'elles soient disponibles au moment approprié. L'invention va maintenant être décrite plus en détail dans ce qui suit et de façon non limitative au moyen d'un mode de réalisation. Sur les dessins annexes: la figure 1 est un schéma par blocs d'un circuit FFT, la figure 2 représente un demi-papillon dont la précision est de 16 bits. A la figure 1 est montré un schéma par blocs d'un circuit FFT o toutes les commandes additionnelles qui ne sont pas l'objet de l'invention, telles que les mémoires de données situées avant, entre et après les opérateurs papillon et par lesquelles s'effectue le triage des données pour la décimation dans l'Algorithme de Temps ne sont pas montrées Le circuit représenté est constitué pour le calcul d'une transformation à 16, 32, 64 ou 128 points Le circuit est constitué essentiellement par 7 demi-papillons 1 à 7 Les données provenant d'un circuit de commande habituel 8 sont fournies à un étage d'entrée 9 Partant de cet étage d'entrée 9, les données sont appliquées par l'intermédiaire d'un multiplexeur 10 à une mémoire d'entrée 20 En aval de cette mémoire d'entrée 20 est monté un second multiplexeur 11 par lequel les données sont appliquées au premier demi-papillon 1 Ce premier demi-papillon i est relié au demi-papillon suivant 2 par un multiplexeur 11 1 monté en aval Les premiers six demi-papillons 1 à 6 sont ainsi reliés de la même manière par des multiplexeurs 11 1 à 11 6 aux demi- papillons suivants 2 à 7 Le septième demi-papillon 7 est également raccordé par un multiplexeur 11 7 à un étage de sortie 21, et en aval duquel est également monté un multiplexeur 12. Tous les multiplexeurs 10, 11, 11 1 à 11 7, 12 sont reliés entre eux par un bus de test et de sortie 22 de manière à pouvoir court-circuiter la mémoire de signaux d'entrée, les demi-papillons 1 à 7 et l'étage de sortie 21. Le circuit FFT selon la figure 1 comprend en outre des étages 13, 14, 15 La commande 13 est prévue pour effectuer la discrimination entre les signaux START, STROBE et MODE, sa sortie MODE étant raccordée à une commande de test 14 Cette commande de test est excitée par le signal SCAN interne ou par les signaux TEST, d'ou résulte également la fréquence d'horloge de la commande 13 et du circuit de contrôle 15 Ce dernier reçoit ses données de l'étage de sortie 21. A la figure 2 est représenté le circuit détaillé d'un demi-papillon utilisé à la figure 1. Grâce à cet agencement, les valeurs A' et B' peuvent être calculées au moyen des formules suivantes: A'= A+WB = lAi+(Wi Bi-Wq Bq)l + j lAq+(Wq Bi+Wi Bq)l B'= A-WB = lAi-(Wi Bi-Wq Bq)l + j lAq-(Wq Bi+Wi Bq)l La caractéristique de ce circuit est constituée par deux multiplicateurs 23, 24 Les données Wi sont appliquées au premier multiplicateur 23 et en alternance les données Bi et Bq; et les données Wq sont appliquées au second multiplicateur 24 et en alternance les données Bi et Bq Les sorties du premier multiplicateur 23 sont envoyées à un premier organe de temporisation 25 et les sorties du second multiplicateur 24 à un second organe de temporisation 26 Un troisième organe de temporisation 27 reçoit alternativement les données Ai et Aq, et après chacun des organes de temporisation 25, 26, 27 est respectivement monté un autre organe de temporisation 25.1, 26 1 et 27 1. Une sortie de balayage du premier organe de temporisation 25 1 qui est monté à la suite de l'organe de temporisation 25 est appliquée à l'organe de temporisation 27 o les données Ai et Aq sont retardées L'organe de temporisation 26 1 qui est monté à la suite du second organe de temporisation 26 est relié à un autre organe de temporisation 26 2 dont la sortie de balayage est également renvoyée au premier organe de temporisation 25 La sortie de balayage 28 de l'organe de temporisation 27 1 qui est monté à la suite du troisième organe de temporisation 27 sert à effectuer des tests La ligne de balayage 28 est reliée au demi-papillon monté à la suite et utilisée pour alimenter l'organe de temporisation 26 associé à ce dernier. Les données Ai et Aq sont alors appliquées par l'intermédiaire de deux organes de temporisation 27, 27.1 à un additionneur 29 1 et à un soustracteur 29 2, alors que les données provenant du premier multiplicateur 23 sont retardées et appliquées à un étage additionneur et soustracteur 30 Le résultat du second multiplicateur 24 qui est fourni par trois organes de temporisation 26, 26 1, 26 2 est également appliqué par l'intermédiaire d'un multiplexeur 31 à l'étage additionneur et soustracteur 30 Par ailleurs, les données du second organe de temporisation 26 sont également appliquées 3 ce multiplexeur 31 Le résultat de l'étage additionneur et soustracteur 30 est traité dans l'additionneur 29 1 et le soustracteur 29 2 dont les sorties sont appliquées au multiplexeur 11 i (i = 2 à 7) monté à la suite. Le bus de test et de sortie 22 est appliqué directement au multiplexeur associé 11 i de chaque demi-papillon La sortie de balayage 28 du demi- papillon monté en amont et constituant l'autre ligne de test est raccordée au second étage de temporisation 26. Les organes de temporisation 25 à 27 1 sont soit activés soit mis hors circuit par les signaux SEL, PMX et PMY qui parviennent par les lignes de commande 32, 33 et 34 Une autre ligne de commande 35 sert à l'activation du multiplexeur 31 et de l'étage additionneur et soustracteur 30 On prévoit pour réaliser des tests un bus de test 36 qui conduit aux multiplexeurs 11 i montés en aval, ce bus de test 36 étant activé par une ligne de test 37. On peut réaliser une transformation de 128 points par le circuit FFT représenté Pour pouvoir calculer cette transformation de 128 points, on a besoin de sept passages, une opération de papillon étant respectivement calculée pour chaque passage, pour toutes les valeurs Ce circuit est constitué essentiellement par les sept demi-papillons i à 7, leur étage d'entrée 9 et leur étage de sortie 21, une commande non représentée ayant pour fonction d'ordonner les données d'une manière déterminée. La succession du traitement ne correspond pas à la successions selon laquelle les données sont fournies, et les données qui apparaissent à la sortie du circuit doivent donc être également à nouveau triées Les trois blocs 13, 14, 15 servent, comme déjà décrit, à des fins de commande et de test Ils sont intégrés à la puce car ceci est avantageux pour les fonctions de test Ils sont cependant sans importance pour le fonctionnement proprement dit du circuit FFT. Comme les grandeurs d'entrée de 16 bits sont dirigées respectivement vers les demi-papillons 1 à 7 et en dérivation de ceux-ci aux multiplexeurs 11 1 à 11.7, on dispose de la possibilité de calculer avec ce circuit non seulement une FFT de 126 points, cas pour lequel on utilise sept opérateurs, mais aussi de 64 points, 32 points ou 16 points On a besoin dans chacun de ces cas d'un opérateur de moins On peut donc par une commande appropriée passer en dérivation de chaque demi-papillon 1 à 7 C'est ainsi qu'il est possible après le sixième opérateur d'envoyer les données en sortie vers l'étage de sortie 21, c'est-à-dire de passer en dérivation du septième opérateur Grâce à cette structure, on est en position d'adresser individuellement chaque demi-papillon 1 à 7, notamment à des fins de test. Le résultat des demi-papillons 1 à 7 peut ainsi être directement envoyé à la sortie On peut donc tester chaque opérateur individuel indépendamment de son environnement La commande qui est nécessaire dans ce cas s'effectue de l'extérieur Chaque demi-papillon est également associé à un mécanisme de commande qui n'est pas représenté et dont la fonction, pour chaque fréquence d'horloge, est de toujours actionner le "commutateur" correct, c'est-à-dire de prendre les facteurs dits "twiddle" corrects Les facteurs twiddle fonctionnent alors comme des multiplicateurs au moyen desquels on obtient une rotation de phase Pour faire savoir au mécanisme de commande s'il s'agit d'une addition ou d'une soustraction et pour lui indiquer à partir de quelles entrées parviennent les opérandes, on utilise habituellement une ROM, qui contient le programme de commande correspondant. Dans chaque étage s'effectuent alors des multiplications avec un mot complexe sur le circuit unitaire, de manière à modifier la phase de ce mot complexe, mais non son amplitude. Grâce aux formules indiquées plus haut, on peut essentiellement réaliser le produit W B complexe et ensuite effectuer une addition ou une soustraction, W représentant le facteur de rotation complexe Ceci s'effectue au cours de deux fréquences d'horloge successives Les valeurs Wi (pour l'en phase) et Wq (pour la quadrature), c'est-à-dire la partie réelle et la partie imaginaire, sont mises en mémoire dans la ROM Ce qui est décisif est alors l'utilisation des organes de temporisation 25 à 27 1 qui mettent en mémoire les valeurs pour chaque fréquence d'horloge et fonctionnent en tant qu'organes de temporisation pour chaque cycle Les organes de temporisation individuels à 27 1 peuvent être activés par leurs lignes de commande 32, 33, 34 par les instructions de calcul de manière que les données à traiter soient envoyées à l'étage additionneur et soustracteur 30 monté à la suite au moment correct et simultanément. On constate ceci en particulier quand on envoie les données au multiplexeur 31 On peut faire l'échange entre le produit Bq Wq retardé seulement une fois et le produit Bi Wq retardé trois fois de manière que dans l'étage additionneur et soustracteur 30 monté à la suite on puisse former la différence Bi Wi Bq Wq ou la somme Bq Wi + Bi Wq avec les produits Bi Wi et Bq Wi calculés précédemment dans le multiplicateur 23 Dans cet étage additionneur et soustracteur 30 et dans l'additionneur 29 1 et le soustracteur 29 2 montés à la suite, o les valeurs de A sont appliquées, sont effectuées l'addition et la soustraction complexes correspondant à la formule indiquée plus haut, et les deux résultats A' et B' sont calculés. Les valeurs arrivantes Bi, Wi et Wq sont transférées en paralèlle dans les multiplicateurs 23, 24 au cours de deux cycles, c'est-à-dire les données Bi, Wi et Wq au cours du premier cycle et les données Bq, Wi et Wq au cours du second cycle Pour satisfaire les exigences de précision du calcul, on utilise des dispositifs d'arrondi Les 32 bits des multiplicateurs 23 et 24 provenant de la multiplication de 16 bits sont arrondis à 16 bits plus 2 bits de précision Ces 2 bits de précision sont ensuite éliminés dans le dernier étage de calcul de l'additionneur 29 1 et du soustracteur 29 2, de manière à obtenir un résultat de 16 bits Ce mode de fonctionnement empêche les mots de croître de façon arbitraire. il REVENDICATIONS 1 Structure de circuit pour l'exécution de la transformation de Fourier rapide par un fonctionnement commandé d'opérateurs papillon en réseau, auxquels sont associés des multiplicateurs et auxquels sont appliquées les données d'entrée, caractérisée en ce que sont prévus deux multiplicateurs ( 23, 24) pour chaque demi-opérateur papillon ( 1 à 7), dans lesquels sont traités respectivement deux valeurs d'entrée au cours de deux cycles pour obtenir deux valeurs de sortie. 2 Structure de circuit selon la revendication 1, caractérisée en ce que les demi- opérateurs papillon ( 1 à 7) traitent deux valeurs d'entrée au cours de deux cycles de manière que les données puissent être continuellement avancées dans les demi-opérateurs papillon sans avoir à combler des lacunes de temps. 3 Structure de circuit selon les revendications 1 et 2, caractérisée en ce qu'une série de demi-opérateurs papillon ( 1 à 7) sont montés les uns à la suite des autres et en ce qu'à la suite de chaque demi-opérateur papillon ( 1 à 7) est monté un multiplexeur 32 bits ( 11 1 à 11 7) qui peut être commandé de manière à court-circuiter le demi-opérateur papillon associé ( 1 à 7). 4 Structure de circuit selon 1 'une quelconque des revendications 1 à 3, caractérisee en ce qu'un étage d'entrée ( 9) et une mémoire d'entrée ( 20) sont montés en amont du premier demi-opérateur papillon ( 1), ces deux éléments comprenant chacun un multiplexeur 16 bits ( 10, 11). 5 Structure de circuit selon 1 'une quelconque des revendications 1 à 3, caractérisée en ce qu'au dernier demi-opérateur papillon ( 7) et à son multiplexeur 16 bits ( 11 7) sont associés un étage de sortie ( 21) et un autre multiplexeur 32 bits ( 12) duquel sont prélevés les valeurs de sortie. 6 Structure de circuit selon l'une quelconque des revendications 1 à 5, caractérisée en ce que chaque demi-opérateur papillon ( 1 à 7) peut être adressé individuellement. 7 Structure de circuit selon les revendications 1 et 2, caractérisée en ce que chaque demi-opérateur papillon ( 1 à 7) calcule les valeurs A' et B' selon les formules: A'= A+WB = lAi+(Wi Bi-Wq Bq)l + j lAq+(Wq Bi+Wi Bq)l B'= A-WB = lAi-(Wi Bi-Wq Bq)l + j lAq-(Wq Bi+Wi Bq)l i représentant la partie imaginaire et q la partie réelle, et W le facteur de rotation. 8 Structure de circuit selon la revendication 7, caractérisée en ce que la partie réelle A est appliquée par l'intermédiaire de deux organes de temporisation ( 27, 27 1) à un additionneur ( 29 1) et à un soustracteur ( 29 2). 9, Structure de circuit selon la revendication 7, caractérisée en ce que la partie imaginaire Bi avec la partie imaginaire du facteur de rotation Wi sont appliquées en commun au premier multiplicateur ( 29), et la partie imaginaire Bi avec la partie réelle du facteur de rotation Wq au second multiplicateur ( 24) Structure de circuit selon la revendication 9, caractérisée en ce que deux organes de temporisation ( 25, 25 1) sont montés en aval du premier multiplicateur ( 23) et trois organes de temporisation ( 26, 26 1, 26 2) en aval du second multiplicateur ( 24). 11 Structure de circuit selon les revendications 9 et 10, caractérisée en ce que le résultat du premier multiplicateur ( 23) peut être appliqué par l'intermédiaire des deux organes de temporisation ( 25, 25 1) a un étage additionneur et soustracteur ( 30). 12 Structure de circuit selon l'une quelconque des revendications 9 à 11, caractérisée en ce que le résultat du second multiplicateur ( 24) peut être appliqué par l'intermédiaire de ses trois organes de temporisation ( 26, 26 1, 26 2) et d'un multiplexeur ( 31) à l'étage additionneur et soustracteur ( 30). 13 Structure de circuit selon la revendication 12, caractérisée en ce que le résultat du second multiplicateur ( 24) peut être appliqué par l'intermédiaire du premier organe de temporisation ( 26) au multiplexeur ( 31). 14 Structure de circuit selon 1 'une quelconque des revendications 8 et 11 à 13, caractérisée en ce que la sortie de l'étage additionneur et soustracteur ( 30) est appliquée à l'additionneur ( 29 1) et au soustracteur ( 29 2). Structure de circuit selon la revendication 14, caractérisée en ce que les sorties de l'additionneur ( 29 1) et du soustracteur ( 29 2) sont appliquées au multiplexeur associé ( 11 i). 16 Structure de circuit selon l'une quelconque des revendications 8 et 10 à 13, caractérisée en ce que les valeurs d'entrée qui sont fournies simultanément par les organes de temporisation ( 25 à 27 1) sont retardées de manière qu'elles soient disponibles au moment approprié.