Brevet FR2484672A1 — publié le 19811218

La présente invention concerne un module de calcul pour la détermination de la transformee de Fourier discrète d'une suite temporelle d'échantillons sous forme complexe et un dispositif de calcul de transformée de Fourier utilisant de tels modules. Dans un certain nombre de domaines ou on doit procéder a l'analyse spectrale d'un signal échantillonné, par exemple dans le domaine du radar, on utilise des dispositifs de calcul db la trànsformee de Fourier discrete d'une suite d'echantillons. De tels dispositifs utilisent des algorithmes de calcul dont certains sont maintenant bien connus. Ainsi, divers algorithmes dits "de racine 2k" ont été développes depuis la mise au point par J.W. Cooley et J.W.Tukey de l'algorithme de racine 2 ou algorithme de transformee de Fourier rapide (cf. "An algorithm for the machine calculation of complex Fourier seriez", Matheaa- tics of Computation, vol. 19, 1965, pages 297 a 301). Les algorithmes de racine 2k sont basés sur L'ides de decow- poser une transformee de Fourier discrete de N = 2P termes en 2k transformées de Fourier de 2P k termes chacune. Pour cela, on regroupe les differents termes en 2k paquets correspondant respectivement aux termes d'indices 0, 1, ... 2k-1 modulo 2k Si l'algorithme de racine 2 est encore frequemment utilise pour le calcul de transformee de Fourier discrete, les algorithmes de racine de valeur plus elevee sont de plus en plus utilises car plus efficaces et d'une plus grande simplicita au moins jusqu a une certaine dimension des transformees de Fourier. C'est le cas en particulier de l'algorithme de racine 4. L'invention a pour objet un dispositif de calcul de transformee de Fourier discrete qui, grâce à une mise en oeuvre particuliere de l'algorithme de racine 4, presente une structure particulièrement simple et repetitive, donc économique. Selon l'invention, il est prevu un module de calcul effectuant des additions et soustractions des échantillons reçus en série dans l'ordre normal et fonctionnant en partage dans le temps, ainsi qu'un dispositif de calcul de transformée de Fourier discrete utilisant de maniere repetitive de tels modules. L'invention sera mieux comprise et d'autres caractéristiques apparaîtront a l'aide de la description ci-apres et des dessins joints où - la figure I représente un diagramme de calcul de transformée de Fourier discrète a l'aide de modules de calcul semblables - la figure 2 représente le diagramme de base d'un tel module ; - la figure 3 est un graphe de circulation correspondant au calcul d'une transforméa de Fourier discrète a seize points - la figure 4 est le schéma d'un module de calcul selon l'invention - la figure 5 est un diagramme de signaux d'horloge utilisés dans le module de la figure 4 ; 5 et - la figure 6 représente un dispositif de calcul de transformée de Fourier discrète selon l'invention. Ainsi qu'il est connu, les différents points (ou raies) Ak de la transformée de Fourier discrète d'une suite d'échantillons a comr plates sont donnés par avec : k = O, 1, ..., N-1 et : Wnk = e-2#jnk/N N étant le nombre de points de la transformée de Fourier ainsi que le nombre d'échantillons dans la suite. La technique pour l'algorithme de racine 4 consiste a regrouper les termes d'indices respectivement de la forme 4n, 4n+l, 4n+2 et 4n+3. Ainsi, on décompose la somme Ak comme suit avec :k = 0, 1, ...,N-1. Par un regroupement avantageux de ces termes, en tenant compte que : Wm(k+t.N/4) = [(-1)t]m Wmk pour m = 1, 2, 3 et t = 1, 2, 3 et en posant on obtient On a ainsi a calculer quatre transformées de Fourier a N/4 points. On peut évidemment réitérer l'opération jusqu a se ramener. a une décomposition en transformées de Fourier a quatre points Si N est une puissance de quatre. Gracie a cette décomposition, on peut constater- que l'#lgo- rithme peut se synthétiser a l'aide de modules simples réalisant l'algorithme de transformée de Fourier discrète à quatre points. La figure 1 représente le diagramme obtenu pour N = 16. Les modules 10 a 13 et 20 a 23 sont tous identiques et le graphe de-circu- lation correspondant est représenté sur la figure 2 pour une transformée de Fourier a quatre points. Les symboles 100 représentent des multiplications -par des coefficients complexes. Le graphe de la figure 2 stinterprete ainsi : chaque point où une ligne horizontale et une ligne oblique se rejoignent, en allant vers la droite du dessin, représenta une addition, par exemple en 14 et 16. Ainsi, au point 14, on a aO + a2. Sil'on rencontre un signe moins sur la ligne qui achemine une donnée, celle-ci est affectée du signe moins, ce qui correspond a une soustraction, par exemple au point 15 où on obtient aO - a2. Une multiplication par -j est intercalée sur la dernière ligne horizontale. Le point A0 de la transformée de Fourier a quatre points est donc donné par A0 = as +a2 +a3. Cela étant, la figure 3 donne le graphe de circulation pour une transformée de Fourier a seize points en utilisant cet algorithme de racine 4. Ce graphe se déduit des relations #(I) apres remise en ordre des échantillons. On voit que le calcul de la transformée de Fourier s'effectue à l'aide de deux étapes, la première et la troisième, comportant seulement des transformées de Fourier a quatre points, et d'une. étape, la deuxième, de multiplication par les coefficients complexes indiqués sur la figure. Ainsi, on a par exemple B0 = a0+ a8 B'0 = B0 B15 = a7 -a15 B'15 = -jB15 C15 = B'11 - B'15 etc. La figure 4 représente le schéma d'un module de calcul permettant par utilisation en partage dans le temps, de réaliser entièrement une étape de calcul telle que la première ou la troisième étape de la figure 3. Ce module comporte une voie imaginaire et une voie réelle recevant respectivement les parties imaginaire zi et réelle zr des échantillons anreçus en série dans l'ordre normal de leur apparition a = zrn + jzin. n Les voies imaginaire et réelle comprennent chacune deux blocs de calcul, BC1, BC3 et BC2, 3C4 respectivement, qui sont séparés par un bloc d'aiguillage BA commun aux deux voies. Les quatre blocs de calcul 3C1 à BC4 comportent des éléments similaires connectés de manière identique - deux registres a décalage en série (M1, M'l ; M2, M'2 ; ...) - un multiplexeur (Mux1 a Mux4) a deux entrées reliées respectivement à l'entrée du premier registre et du bloc, et à la sortie du deuxième registre - une unité logique arithmétique (ALU1 è ALU4) effectuant, sur les données appliquées sur ses deux entrées A et B,une opération arithmé tique qui dépend du niveau de signal de commande appliqué sur ses entrées de commande SO et S1. Lorsque l'entrée S1 n'est pas représen tée, elle est maintenue constamment au niveau haut. Les opérations effectuées sont les suivantes S1 = haut SO = haut -- > A plus B Si = haut SO = bas -- > A moins B S1 = bas SO = haut B moins A. Une telle unité peut par exemple etre constituée par un circuit TTL SN74S381 de la société Texas Instruments ; - un registre de mémoire (R1 a R4) connecté entre la sortie de l'unité logique arithmétique et la sortie du bloc de calcul. Ces quatre blocs diffèrent, d'une part,par les signaux de commande appliqués à leur unité logique arithmétique et, d'autre par; par le nombre de cellules des registres a décalage, ainsi qu'on va le voir. Le bloc d'aiguillage comprend deux multiplexeurs Huai, Mux6 à deux entrées dont les premières entrées sont respectivement reliées aux sorties des blocs BC1 et BC2 des voies imaginaire et réelle, dont les secondes entrées sont reliées respectivement aux sorties des blocs BC2 et BC1 et dont les sorties fournissent les parties imaginaire Cim et réelle Crm respectivement aux entrées des blocs de calcul BC3 et BC4. Le fonctionnement de l'ensemble va etre expliqué en liaison avec la figure 5 qui représente les signaux d'horloge servant à la com- mande des unités logiques arithmétiques et du bloc d'aiguillage. On a supposé,è titre d'exemple,que# le module de calcul décrit est celui réalisant la première étape de calcul de la figure 3. La suite d'échantillons > présente à I'entrég, a22q échantillons avec q égal ici à deux, soit seize échantillons. Ces échantillons sont sous forme codée à x bits et bien entendu toutes les liaisons et opérations sur des données dans le module de la figure 4 s'effectuent sur x bits en parallèle. Les registres à décalage M1, M'1, M2, M'2 comprennent chacun 22q-1 cellules, ici huit cellules. Sur les deux premières lignes de la figure 5, sont indiquées les opérations successives réalisées respectivement par le bloc BCl et le bloc BC2. Dans le bloc de calcul BCI, le signal d'horloge H1 commande d'abord la liaison entre l'entrée du premier registre M1 et l'entrée A de l'unité logique ALUl et, par l'intermédiaire d'un inverseur, la réalisation de 22qu1 = 8 additions (zi0 + zi8 è zi7 + zip5) entre les huit premiers échantillons reçus qui apparaissent successi vement à la sortie du registre Ml et les huit derniers échantillons reçus qui apparaissent successivement en même temps sur l'entrée du registre Ml. Les mêmes additions s'effectuent simultanément dans le bloc BC2 sous la commande des signaux H1, H2 et R3.Après avoir effectué ces huit additions, le bloc de calcul BC1 est commandé par le signal H1 pour effectuer 2Zq 1 - 8 soustractions (ziO - zi8 à zi7 - zi15) entre les huit premiers échantillons qui se présentent successivement à la sortie du registre M' 1 et les huit derniers échantillons prélevés à la sortie du registre M1. Le bloc BC2 procède de même pour les 2q-2 premières soustractions sous la commande des signaux Hi à H3. Cependant, corne on le voit sur le graphe de la figure 3, les résultats des 22q 2 = 4 dernières soustractions de la première partie de la première étape doivent être multipliés par -j B'n = -j(Brn + jBin) jBrn. On constate que cette multiplication revient à intervertir partie réelle et partie imaginaire et à changer le signe de la partie réelle. Pour cela, lors des 22q-2 dernières soustractions, les signaux 112 et 113 prennent des valeurs commandant l'opération de soustraction B - A pour l'unité logique arithmétique ALU2, ce qui change le signe de la partie réelle, et le signal 112 commute les multiplexeurs Muxi et Mux6 pour intervertir les parties réelle et imaginaire. Les blocs de calcul BC3 et BC4 réalisent les additions et soustractions de la seconde partie de la première étape de la figure 3. Ces blocs sont identiques et fonctionnent de la même façon que le bloc BCI. Cependant, les registres a décalage M3, M'3 et M4, M-'4 ne comportent que 22q-2 n 4 cellules chacun. De plus, le signal d'horloge H'1,qui commande les multiplexeurs et unités logiques arithmétiques et qui est représenté sur la figure 5, change de valeur toutes les quatre opérations. On peut constater que l'ensemble de fonctionnement du module de la figure 4 s'effectue de manière synchrone. La figure 6 représente un dispositif de calcul de la transformée de Fourier discrète d'une suite de seize échantillons utilisant des modules de calcul du type représenté sur la figure 4. Un premier module Modal, qui est celui représenté sur la figure 4 et qu'on dira d'ordre 22q = 16, réalise la première étape du graphe de la figure 3 et fournit les valeurs des parties imaginaire Yp et réelle Xp d'une suite de 22q valeurs, qui sont envoyées un étage de multiplication complexe MC réalisant la deuxième étape de calcul du graphe de la figure 3. Cet étage MC comprend quatre multiplicateurs 31 à 34, deux mémoires mortes ROMI et ROM2 contenant respectivement les parties imaginaire Ip et réelle Rp des coefficients de multiplication, deux unités logiques arithmétiques ALUS et ALU6, fonctionnant respectivement en additionneur et en soustracteur, et deux registres de sortie R5, R6.Cet étage réalise l'opération de multiplication complexe: (p + jYp) (Rp + jlp) = (0pEp - YpIp) + j (XpIp + YpRp). Les valeurs complexes obtenues sont envoyées aux entrées d'un deuxième module de calcul Modl du même type, mais d'ordre 22qu4 = 4 (registres a décalage d'entrée è deux cellules). Ce module de calcul réalise la troi sième étape du graphe de la figure 3 et fournit les différents points de la transformée de Fourier. Il est clair que, pour des transformées de Fourier à un nombre de points N plus élevé (N étant une puissance de quatre), il suffirait d'ajouter des modules de calcul d'ordre plus élevé avant le module Mod1 de la figure 6, chaque module étant séparé du suivant par un étage de multiplication complexe du type de l'étage MC. On peut également utiliser le dispositif de calcul de la figure 6 à seize points comme module de base pour un arrangement selon la figure 1, pour soixante-quatre échantillons, et ainsi de suiteo Dans le cas où N, tout an étant une puissance de deux, n'est pas une puissance de quarre, on arriverait9 a l'avant- dernière étape, à une transformée à huit points pour laquelle on peut utiliser, par exemple, soit l'algorithme de racine 2 donnant une décompo- virion en deux transformées à quatre points, soit l'algorithme de Winograd à huit points. Un des avantages du dispositif selon l'invention est, outre sa simplicité et son volume réduit, sa grande facilité de test et de dépannage du fait de sa structure répétitive. Bien entendu, l'exemple de réalisation décrit n'est nullement limitatif de l'invention. REVENDICATIQNS 1. Module de calcul d'ordre 22q pour la détermination de la transformée de Fourier discrète d'une suite d'échantillons sous forme complexe par un algorithme dit "de racine 4", caractérisé en ce qu'il comprend en série pour chaque voie, imaginaire et réelle, deux blocs de calcul (3C1 à BC4) d'additions et de soustractions deux à deux des échantillons (zin, zrn, Cim, Crm) reçus en série sur leur entrée, lesdits blocs étant séparés par un bloc d'aiguillage (BA) commun aux deux voies, en ce que ledit bloc d'aiguillage aiguille les résultats fournis par les premiers blocs de chaque voie, respectivement de la voie imaginaire vers la voie réelle et réciproquement, lors du calcul des 22q-2 dernières soustractions par lesdits premiers blocs et en ce que le premier bloc de la voie réelle effectue une inversion des termes desdites 22q-2 dernières soustractions. 2. Module selon la revendication 1, caractérisé en ce que chaque bloc de calcul comprend deux registres à décalage identiques (M1, M'1 à M4, M'4) en série, une unité logique arithmétique (ALU1 à ALU4) dont la sortie est reliée à la sortie du bloc par un registre de mémoire (R1 à R4), dont une entrée est reliée à la jonction entre les deux registres et dont l'autre entrée est reliée à la sortie d'un multiplexeur (Muxi à Mux4) à deux entrées reliées respectivement à l'entrée du bloc et la sortie du deuxième registre à décalage, et en ce que les unités logiques arithmétiques (ALU1 à ALU4) comprennent des entrées de commande (SO, S1) pour commander l'exécution de l'addition ou de la sous traction, dans un ordre ou l'autre, des données appliquées à ses deux entrées. 3. Module selon la revendication 2, caractérisé en ce que l'unité logique arithmétique (ALU1) du premier bloc de calcul de la voie imaginaire est commandée pour effectuer successivement 22qu1 additions entre, respectivement, les 22qu1 premiers échantillons reçus par le bloc et les 22qu1 derniers échantillons reçus, puis 22q-1 soustractions entre, respectivement, lesdits premiers échantillons et lesdits derniers échantillons, en ce que l'unité logique arith métique (ALU2) du premier bloc de calcul de la voie réelle est commandée pour effectuer successivement 22qu1 additions entre, respectivement, les 22q-1 premiers échantillons reçus par le bloc et les 22qui derniers échantillons reçus, puis 22qu1 soustractions entre, respectivement, lesdits premiers échantillons et lesdits derniers échantillons, l'ordre des facteurs des soustractions etant inversé pour les 22q-2 dernières soustractions, en ce que les unités logiques arithmétiques (ALU3, ALU4) des deux deuxièmes blocs de calcul sont commandées pour effectuer successivement, sur chaque série de 22q-1 valeurs fournies par le bloc d'aiguillage, 22q-2 additions entre, respectivement, les 22q-2 premières valeurs reçues et les 22q-2 der nières valeurs reçues#, puis 22q-2 soustractions entre, respectivement, lesdites premières valeurs et lesdites dernières valeurs, et en ce que chaque registre à décalage (M1, M'1, M2, M'2) des premiers blocs de calcul (BCl, BC2) comprend 22q 1 cellules tandis que chaque registre à décalage (M3, M'3, M4, M'4) des deuxièmes blocs de calcul (BC3, BC4) comprend 22q-2 cellules. 4. Module selon l'une quelconque des revendications 1 à 3, caractérisé en ce que ledit bloc d'aiguillage (BA) comprend un multiplexeur (MuxS, Mux6) à deux entrées dans chacune des voies imaginaire et réelle, en ce que les premières entrées des deux multiplexeurs sont reliées, respectivement, aux sorties des premiers blocs de calcul (BCi, BC2) des voies imaginaire et réelle, et les secondes entrées des multiplexeurs sont reliées, respectivement, aux sorties des premiers blocs de calcul (BC2, BC1) des voies réelle et imaginaire, et en ce que la commutation des deux multiplexeurs est commandée en synchronisme avec le calcul des 22q-2 dernières soustractions effectuées par les deux premiers blocs de calcul. 5* Dispositif de calcul de la transformée de Fourier discrète d'une suite de 22t échantillons sous forme complexe, caractérisé en ce qu'il comporte en série q modules de calcul (mod1, Mod2), selon l'une quelconque des revendications 1 à 4, d'ordre respectivement 224 22t 1, 22, 22,chaque module étant séparé du suivant par un étage de multiplication complexe (MC) opérant en multiplex dans le temps, les parties réelles et imaginaires des coefficients multiplicateurs étant contenues dans des mémoires mortes (ROMi, ROM2) adressées en synchronisme avec l'apparïtlon des valeurs calculées aux sorties du module de calcul précédent.