Brevet FR2617300A1 — publié le 19881230

MULTIPLIKUR- A C CÙMULATEuR L'invention concerne les cfrcuits-intégrés numériques, et plus précisément un circuit apte å exécuter des multiplicatlons, additions et soustractions sur des données numériques. La fonction qu Ion cherche à réaliser est une fonction de multipllcation-acuumulation du genre A(n) = x(n) . y(n) + A où x(n) et y(n) représentent deux données numériques codées chacune sur p bits par exemple, introduites régulièrement dans le multiplieur, A(n) représente le résultat de l'opération effectuée ; n représente le numéro de l'opération dans une séquence d'opérations successives et A représente un nombre qui peut être le résultat d'une multiplication précédente x(n-1) . y(n-1). Un tel multiplleur-accumulateur est particulièrement utile pour effectuer des multiplications de nombres complexes la partie réelle du produit est la différence de deux produits et la partie imaginaire est la somme de deux produits. On doit donc successivement effectuer un premier produit, un deuxième produit, la différence de ces deux produits, un troisième produit, un quatrième produit, la somme de ces deux derniers produits. Les données sont introduites sous forme de signaux électriques numériques et les résultats sont obtenus sous la même forme. Une structure classique d'un muitiplieur-accumulateur est représentée à la figure 1. Cette structure comporte des registres d'entrée REGX et REGY pour recevoir les données x(n) et y(n) respectivement elle comporte aussi un ensemble en cascade d'étages additionneurs alternés avec des étages d'aiguillage, chaque étage d'aiguillage fournissant un produit partiel de la multiplication x(n) . y(n), c'est-à-dire en principe le produit de x(n) par un bit de y(n) en pratique le produit partiel n'est pas directement le produit de x(n) par un bit de y(n), mais c'est plutôt le produit de x(n) par un bit résultant d'un codage particulier des bits de y(n) ; ce codage est classique, l'algorithme utilisé est par exemple l'algorithme de Booth et son #but est de réduire le nombre d'étages additionneurs. Les étages additionneurs servent à fournir la somme cumulée des produits partiels établis aux étages précédents. On trouvera des explications plus détaillées dans des ouvrages spécialisés tels que le Journal IEEE Solid State Circuits, Vol SC-20 N02, Avril 1975. Sur la figure 1, les aiguillages sont désignés par les références AIG1 à AIG9 et ils sont commandés soit directement par les sorties du registre REGY soit par les sorties (moins nombreuses que celles du registre) d'un décodeur DEC. utilisé par exemple lorsque l'on utilise l'algorithme de Booth ou d'autres algorithmes de réduction du nombre des produits partiels. Les additionneurs sont désignés par ADD1 à ADD7 et ils additionnent aux sorties de l'additionneur de rang précédent les signaux issus de. l'aiguillage qui les précède. Les signaux issus de 1'aiguillage sont les bits du registre REGX modifiés (par multiplication par 1 ou O et éventuellement par décalage d'une ou plusieurs positions à gauche) en fonction du produit partiel à réaliser, donc en fonction des sorties du décodeur DEC. Les additionneurs sont des additionneurs à sauvegarde de retenue qui se différencient des additionneurs classiques en ce que: - ils sont constitués de cellules d'addition juxtaposés horizontalement et correspondant aux différents poids binaires des chiffres des nombres à additionner, mais la retenue ne se propage pas horizontale, ment d'une cellule à la cellule voisine - ils fournissent vers l'additionneur de rang suivant, pour chaque bit, deux sorties qui sont une sortie "somme" et une sortie "retenue". - on les utilise parcequ'ils sont plus rapides que les additionneurs classiques étant donné qu'ils ne sont pas affectés par le temps de propagation horizontale de la retenue le long de toute la rangée de cellules. Pour un multiplleur 16 bits, capable de multiplier un nombre x(n) de 16 bits par un nombre y(n) de 16 bits, le dernier étage d'addition est un étage de 32 bits (composé par conséquent de 32 cellules élémentaires, et il fournit 32 sorties "somme" et 32 sorties "retenue", comme cela est visible sur la figure 1. Pour obtenir un résultat final de la multiplication sur 32 bits, il est maintenant nécessaire de terminer l'addition dans un additionneur normal (à propagation de retenue des étages de poids faible vers les étages de poids fort); cet additionneur normal est l'additionneur ADDN de la figure 1; il reçoit les 32 sorties "somme" de l'additionneur ADD? et les additionne aux 32 sorties "retenue" du même additionneur ADD7; il fournit 32 sorties qui représentent les 32 bits du résultat P de la multiplication du nombre x par le nombre y. Pour réaliser un multiplieur-accumulateur exécutant la fonction A(n) = x(n).y(n) j A on prévoit en outre les éléments suivants: - un deuxième additionneur ou un additionneur-soustracteur ADDNS pour ajouter le résultat x(n) . y(n) de la multiplication au nombre A. - un registre tampon de sortie REGS pour stocker le nombre A, notamment lorsque ce nombre est lui-même le résultat d'une opération précédente effectuée par le multiplieur- accumulateur. En pratique le registre tampon est suivi d'un étage de complémentation COMPL qui fournit soit le contenu inchangé du registre soit le complément à deux, selon qu'une addition ou une soustraction doit être effectuée dans la fonction A(n). L'additionneur ADDNS reçoit alors la sortie de l'étage de complémentation et la sortie du tnultiplieur proprement dit, c'est-à-dire la sortie de l'additionneur ADDN. Comme on veut que le multiplieur ait un débit aussi rapide que possible, les étages additionneurs ADDN et ADDNS doivent être conçus spécialement en vue de la rapidité. Le plus souvent, on utilisera des additionneurs dits "à retenue antlcipée" ou "carry-look-ahead". Ces additionneurs sont très encombrants en surface de silicium dans un circuit-intégré. Selon l'invention on propose de ne pas établir physiquement le produit x(n).y(n) sous forme d'un nombre de 32 bits avant de faire l'addition ou la soustraction entre ce produit et le nombre A, et de se contenter d'un résultat sous forme analogue à celle des produits partiels cumulés obtenus en sortie des additionneurs ADD1 à ADD7, c'est-à-dire un résultat sous forme de 32~sorties "somme" et 32 sorties "retenue". On prévoit alors que les sorties du dernier étage (ADD7) de calcul des produits partiels cumulés sont appliquées à deux groupes d'entrées d'un additionneur supplémentaire à sauvegarde de retenue, lequel possède aussi un troisième groupe d'entrées recevant les sorties d'un registre tampon ou d'un étage de complémentation suivant ce registre ; l'additionneur supplémentaire fournit 32 sortie n somme et 32 sorties "retenue" ; ces sorties "somme" et "retenue" sont additionnées dans un additionneur classique à propagation horizontale de retenue dont la sortie alimente le registre tampon. Par conséquent, l'invention propose ' un multiplieur-accumulateur recevant des signaux représentant des données numériques x(n) et y(n) et fournissant comme résultat des signaux représentant des données numériques A (n) avec: A(n) = x(n) . y(n) + A n étant l'indice représentant le numéro de l'opération en cours dans une suite d'opérations et A représente un nombre qui peut être le résultat de l'opération précédente, le multiplieur comprenant classiquement une cascade d'étages d'addition de produits partiels de la multiplication x(n) . y(n), le dernier étage de cette cascade générant 2p sorties-somme et 2p sorties-retenue ;; selon l'invention, ces sorties sont appliquées à un étage additionneur à sauvegarde de retenue recevant par ailleurs - 2p sorties d'un registre tampon et qui fournit 2p sorties-somme et 2p sorties-retenue elles-même appliquées à un étage additionneur à propagation horizontale de retenue dont les sorties sont les sorties du multiplieur-accumuiateur et sont appliquées au registre tampon pour stocker le résultat de l'opération. Un étage de complémentation est interposé entre le registre tampon et l'additionneur à sauvegarde de retenue#, cet étage recevant un signal de commande indiquant si une addition ou une soustraction doit être effectuée et fournissant soit le contenu inchangé du registre soit son complément à deux. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description détaillée qui suit et qui est faite en référence aux dessins annexés dans lesquels: - la figure 1, déjà décrite représente une structure classique de multlplleur-accumulateur; - la figure 2 représente la structure selon l'invention; - la figure 3 représente un détail de structure du multlplieur-accumulateur selon l'invention. La figure 2 représente la structure selon l'invention, avec les mêmes références qu'à la figure 1 pour les éléments qui se correspondent. La structure de base du multiplieur est la même que celle de la figure 1 pour ce qui concerne l'établissement des produits partiels et leur addition avec les produits partiels précédemment accumulés; on retrouve donc sur la figure 2 les registres d'entrée REGX pour le nombre x(n) et REGY pour le nombre y(n), le décodeur éventuel DEC en sortie du registre REGY, les aiguillages AIG1 à AIG9 commandés par le décodeur DEC, et les additionneurs à sauvegarde de retenue ADD1 à ADD7 qui additionnent chacun un produit partiel à la somme des produits partiels précédents; mais on ne complète pas cette structure avec l'additionneur ADDN à propagation de retenue de la figure 1. La sortie de l'additionneur -ADD7 associé au dernier produit partiel est constituée par 32 sorties "somme" et 32 sorties "retenue" qui sont toutes amenées à un nouvel additionneur à sauvegarde de retenue ADD8 qui reçoit par ailleurs les 32 sorties d'un registre tampon REGS à travers un étage de complémentation COMPL nécessaire lorsque l'on veut effectuer une soustraction entre le produit de la multiplication et le résultat du calcul précédent; le résultat final de la multiplication x(n).y(n) est donc à nouveau traité comme un produit partiel au lieu d'être établi sous forme binaire directe (32 bits qui seraient les chiffres binaires par poids décroissants du résultat de la multiplication). Le contenu du registre tampon 1REGS est soit égal à zéro si une commande RAZ est appliquée à ce registre, soit égal à la sortie S précédemment obtenue si on a chargé (sous la commande d'un signal de chargement LOADA) l'état de cette sortie précédente dans le registre; on voit sur la figure 2 que l'entrée du registre tampon REGS est reliée à la sortie S du multiplieur accumulateur, et on voit les entrées de commande LOADA et RAZ du registre. L'étage de complémentation COMPL en sortie du registre est commandé par un signal A/S qui indique si une addition ou une soustraction doit être effectuée. L'additionneur ADD8 possède donc trois groupes de 32 entrées, et il fournit deux groupes de sorties qui sont respectivement un groupe de 32 sorties "somme" et un groupe de 32 sorties "retenues". Dans un premier temps de l'opération, le registre tampon est remis à zéro par la commande RAZ, de sorte que l'additionneur ADD8 est parfaitement transparent: il fournit sur ses 32 sorties "somme" et ses 32 sorties "retenue" exactement les mêmes signaux qu'il reçoit sur ses entrées "somme" et "retenue". Dans un deuxième temps, le registre contient une information (le résultat de la multiplication précédente) et l'additionneur ADD8 se comporte comme un additionneur classique à sauvegarde de retenue: il fournit 32 sorties "somme" et 32 sorties "retenues".Ces sorties sont appliquées aux entrées d'un additionneur ADDN à propagation horizontale de retenue (de préférence un additionneur rapide, par exemple un additionneur à anticipation de retenue). Cet additionneur ADDN additionne les 32 bits "somme" et les 32 bits "retenue" qu'il reçoit de l'additionneur ADD8, et il fournit 32 bits (ou plus dans le cas de multiplications de nombres signés) sur une sortie S qui est la sortie du multiplleur-accumulateur. La figure 3 représente de manier un peu plus détaillée une structure possible pour les derniers blocs du multiplieuraccumulateur selon l'invention. On a représenté partiellement les éléments suivants: cellules de l'additionneur à sauvegarde de retenue ADD7, cellules du registre tampon, cellules de complémentation, cellules de l'additionneur à sauvegarde de retenue ADDB, et cellules de l'additionneur final à propagation horizontale de retenue ADDN. Pour simplifier la représentation, on n'a représenté que quelques cellules et non les 32 cellules de chaque additionneur ou registre. Pour chaque poids binaire des chiffres des nombres à additionner, les additionneurs comportent une cellule élémentaire d'addition; les cellules correspondant aux poids croissants sont juxtaposées de la droite vers la gauche sur la figure 3. Les cellules d'addition des additionneurs comportent chacune trois entrées et deux sorties, ceci aussi bien pour les additionneurs à sauvegarde de retenue que pour les additionneurs à propagation de retenue; si U, V, W représentent les bits appliqués aux trois entrées et X, Y les bits obtenus sur les deux sorties, les fonctions logiques suivantes sont réalisées par la cellule: X = U*V*W (sortie somme) Y = (U.V) + W. (U*V) (sortie retenue) le point représente le "ET" loglque, le + le "OU" logique, et l'astérisque le "OU EXCLUSIF". Pour l'additionneur ADD7, chaque cellule D(i), de rang i, comporte une première entrée a pour recevoir une sortie "somme" de l'additionneur précédent ADD6, une deuxième entrée b pour recevoir une sortie "retenue" de l'additionneur précédent, et une troisième entrée c pour recevoir une sortie de l'aiguillage AIG9 qui établit le dernier produit partiel de la multiplication. La cellule élémentaire de l'additionneur ADD7 possède deux sorties qui sont une sortie "somme" s et une sortie "retenue" r. La sortie "somme" s est reliée à l'entrée a d'une cellule F(i) de l'étage d'addition ADD8 à propagation horizontale de retenue. Cette cellule F(i) correspond au même rang binaire i que la cellule D(i) de l'additionneur ADD7- à laquelle elle est connectée. La cellule F(i) reçoit par ailleurs sur une deuxième entrée b la sortie s d'une cellule E(t) de même rang binaire l de l'étage de complémentation COMPL. Enfin, la cellule F(l) reçoit sur une troisième entrée c la sortie "retenue" r de l'étage D(i-1) de rang i-1 de l'additionneur ADD?. La cellule F (i) a une sortie "somme" s et une sortie "retenue" r. La sortie "somme" est reliée à une première entrée a d'une cellule G(i) de même rang binaire i de l'étage d'addition final ADDN ; la cellule G (i) a une deuxième entrée b reliée à la sortie "retenue" r de la cellule F(i-1) de rang i-I de l'additonneur ADDB. L'étage d'addition final ADDN est un étage à propagation horizontale de retenue, ce qui veut dire que chaque cellule G(i) possède, outre ses deux entrées a et b, une entrée de retenue qui reçoit une sortie de retenue de la cellule g(i-1) de rang précédent. La sortie s de la cellule G(i) de rang -i de l'additionneur final ADDN est reliée d une part à l'entrée e d'une cellule H (l) de rang i du registre tampon REGS et d'autre par à la sortie S (i) de rang i du multiplieur-accumulateur (qui comporte 32 sorties de poids binaires croissants) ; la sortie ~ S(i) fournit le bit de rang i du résultat de la multiplication. x(n).y(n) + A. A est le contenu du registre tampon. La cellule H(l) de rang i de- ce registre possède une sortie s qui est reliée à l'entrée e de la cellule de même rang i de l'étage de complémentation (cellule E(i)). Le registre tampon REGS possède . une entrée de commande de chargement LOADA, sous le contrôle de laquelle les bits présents sur les entrées e des cellules H(i) du registre sont chargés dans le registre. Il possède aussi une entrée de commande de validation de la sortie (entrée SDT), sous le contrôle de laquelle le contenu du registre est placé sur les sorties s des cellules H(l). L'étage de complémentation COMPL possède une entrée de commande d'addition/soustraction (entrée A/S), sous le contrôle de laquelle la sortie de étage de # complémentation fournit soit le nombre binaire placé sur les entrées de cet étage, soit le complément à 2 de ce nombre; de cette manière, le contenu du registre. tampon est soit additionné soit soustrait dans l'additlonneur qui reçoit la sortie de l'étage de complémentation. L'étage de complémentation possède par ailleurs une entrée de remise à zéro par laquelle la sortie de l'étage de complémentation peut fournir le nombre zéro au lieu du contenu du registre tampon; cette commande permet de masquer le contenu du registre, c'est-à-dire de rendre virtuellement ce contenu égal à zéro pour obtenir en sortie du multiplieur-accumulateur la valeur d'un produit x(n).y(n) au lieu de la valeur x(n).y(n) + A ou la valeur x(n).y(n) - A Dans le cas fréquent où l'on désire effectuer une miltiplication de deux nombres complexes (a+jb). (c+jd), on effectue la suite des opérations suivantes: - multiplication des parties imaginaires b et d; maintien à zéro des sorties de l'étage de complémentation par la commande RAZ, chargement du résultat b.d + 0 dans le registre tampon REGS. - multiplication des parties réelles a et c. relâchement de la commande RAZ, commande A/S en position "soustraction", c'est-à-dire compléméntation à 2 des sorties du registre REGS; chargement du résultat de l'opération a.c - b.d dans le registre tampon et obtention de ce résultat en sortie du multiplieur-accumulateur; ce résultat constitue la partie réelle du résultat de la multiplication. - multiplication des nombres a et d; maintien à zéro des sorties de l'étage de complémentation par la commande RAZ, chargement du résultat a. d + 0 dans le registre tampon REGS. - multiplication des nombres b et c. relâchement de la commande RAZ, commande A/S en position "addition", c'est-à-dire transfert sans altération des sorties du registre REGS; chargement du résultat de l'opération b; c + a.d dans le registre tampon et obtention de ce résultat en sortie du multiplleur-accumulateur; ce résultat constitue la partie imaginaire du résultat de la multiplication. JzvE & ICAtIoNS 1. Multiplleur-accumulateur recevant des signaux représent des données numériques x(n) et y(n) et fournissant comme résultat des signaux représentant des données numériques A(n) = x(n).y(n) + A(n-1) n étant un indice représentant le numéro de l'opération dans une séquenced'opération et A représentant un nombre qui peut être le résultat de l'opération précédente, le multiplieur comprenant classiquement une cascade d'étages d'addition de produits partiels de la multiplication x(n).y(n), le dernier étage (ADD7) de cette cascade générant 2p sorties "somme" et 2p sorties "retenue" (p =. 16 pour 16 bits), caractérisé en ce que ces 2p sorties "somme" et 2p sorties "retenue" sont appliquées à un étage additionneur à sauvegarde de retenue (ADD8) qui reçoit par ailleurs 2p sorties d'un registre tampon (REGS) et qui fournit 2p sorties nsommen et 2p sorties "retenue" appliquées à un additionneur à propagation horizontale de retenue (ADDN) fournissant 2p sorties représentant A(n), le registre tampon (REGS) recevant ces 2p sorties pour stocker le résultat A(n). 2. Multiplieur-accum.ulateur selon la revendication 1, caractérisé en ce qu'il comporte un étage de complémentation COMPL interposé entre le registre tampon (REGS) et l'additionneur à propagation horizontale de retenue (ADDN), cet étage étant commandé par un signal (A/S) déterminant si les sorties de l'étage de complémentation doivent représenter le nombre appliqué à l'entrée de cet étage ou le complément à 2 de ce nombre. 3. Multiplleur-accumulateur selon la revendication 2, caractérisé en ce que l'étage de complémentation comporte une entrée (RAZ) de forçage à zéro de ses sorties, pour masquer le contenu du registre lors du calcul d'un produit x(n).y(n).