Brevet FR2553539A1 — publié le 19850419

La présente invention se rapporte à une structure de multiplieur rapide en circuit intégré MOS pour la multiplication de deux-mots binaires ayant respectivement Ni et N2 éléments binaires, ladite structure comprenant Ni x N2 multiplieurs élémentaires disposés en matrice, fournissant chacun le produit partiel d'un élément binaire d'un premier desdits mots, affecté à la colonne correspondante de la matrice, et d'un élément binaire du second mot, affecté à la ligne correspondante de la matrice. Pour la réâlisation de multiplieurs asynchrones rapides, il est connu d'utiliser la technique du "carry-save adder" décrite par exemple dans l'article de Shlomo Waser "High-speed monolithic multipliers for real-time digital signal processing" paru dans la revue "COMPUTER", octobre 1978, pages 19 à 29, en particulier page 21. Une telle structure de multiplieur est représentée sur la figure 1 de la présente demande de brevet et se caractérise essentiellement par l'ajournement de l'addition des retenues à un étage ultérieur, ce qui évite d'attendre le report de la retenue pour faire l'addition suivante. La vitesse de la multiplication est conditionnée par le délai de propagation des retenues. Par ailleurs, on connaît des additionneurs complets effectuant l'addition de deux nombres à plusieurs éléments binaires dont la rapidité est améliorée, par réduction du temps de propagation de la retenue. Une première méthode est la méthode à prévision de retenue ("carry lookahead") décrite par exemple dans un article de O.L. MacSorley "Highspeed arithmetic in binary computers" paru dans la revue "Proceedings of the IRE", volume 49, janvier 1961, pages 67 à 91.Une autre possibilité connue est d'utiliser, pour constituer un tel additionneur rapide, des cellules à propagation rapide de la retenue telles que celles décrites dans la demande de brevet français n0 81 08531 (2 505 065) déposée le 29 avril 1981 par la demanderesse et intitulée "Cellule d'additionneur binaire à propagation rapide de la retenue et additionneur utilisant de telles cellules" et dans la demande de brevet français n0 81 21656 (2 516 675) déposée le 19 novembre 1981 par la demanderesse et intitulée "Cellule d'addition binaire à trois entrées à propagation rapide de la retenue". Un objet de la présente invention est de mettre à profit la rapidité d'addition ainsi obtenue pour réaliser un multiplieur rapide. Selon l'invention, il est prévu une structure de multiplieur rapide du type mentionné au début, caractérisée en ce que les sommes successives, à effectuer à partir des produits partiels pour obtenir les éléments binaires du produit final, sont réalisées par N1 [ ou N21 additionneurs du type à prévision de retenue ou à propagation rapide de la retenue, les N1-1 [ ou N2-1 ] premiers additionneurs ayant N2-1 a [ ou N1-ll étages et le dernier additionneur, qui sert à rassembler les retenues finales des premiers additionneurs et les résultats intermédiaires de poids correspondants, ayant N1-1 tou N2-1 ] étages. L'invention sera mieux comprise et d'autres caractéristiques apparaîtront à l'aide de la description ci-après et des dessins joints où - la figure 1 représente schématiquement une structure de multi plieur 8x8 connue; - la figure 2 est le schéma d'une cellule connue à propagation rapide de la retenue; - la figure 3 montre le schéma d'une première variante de structure de multiplieur selon l'invention ; et - la figure 4 représente schématiquement une seconde variante selon l'invention. La figure 1 représente un schéma connu de structure de multiplieur 8x8 découlant de la structure "carry-save" décrite dans l'article précité de Shlomo Waser. Ce multiplieur permet d'effectuer la multiplication de deux mots binaires à huit éléments binaires XO à X7 et YO à Y7. Chacun des symboles X disposés en matrice carrée représente un multiplieur élémentaire, tel MOO ou M20, par exemple une porte ET, fournissant le produit partiel de l'élément binaire du premier mot correspondant à la colonne où se trouve le multiplieur (X2 pour le multiplieur M20) par l'élément binaire du second mot correspondant à la ligne où se trouve le multiplieur (PO pour le multiplieur M20).La structure de multiplieur 8x 8 comprend en outre des cellules d'additionneur binaire, telle C01 ou C03, disposées en une matrice associée et effectuant les sommes partielles nécessaires pour l'obtention des éléments binaires PO à P15 du produit final. Les cellules symbolisées par un octogone, telle C01, sont des cellules à deux entrées et deux sorties, à savoir retenue f vers le bas et somme s obliquement sur le coté. Les cellules symbolisées par un carré, telle C03, sont des cellules à trois entrées dont une reçoit la retenue de la cellule précédente et à deux sorties somme et retenue disposées comme pour les cellules précédentes. Les cellules entourant un symbole X sont celles dont une entrée reçoit le produit partiel fourni par le multiplieur élémentaire local.Sur la figure 1, toutes les cellules sont dans ce cas. Ainsi qu'on peut le constater, toutes les sommes fournies par les cellules sont envoyées à une entrée de la cellule adjacente de même poids, dans la direction de la diagonale de la matrice passant par les multiplieurs élémentaires fournissant des produits partiels de même poids. Les retenues se propagent verticalement vers le côté de la matrice d'où sortent les éléments binaires de plus fort poids du produit final (P8 à P15). En sortie vers le bas de la matrice, on a deux opérandes constitués l'un des retenues du dernier étage de cellules, l'autre des sommes de ce même étage. Les dernières additions sont effectuées, comme cela est connu, à l'aide d'un additionneur à prévision de retenue ALA (additionneur du type "carry look-ahead"). Comme on peut le voir, la vitesse de la multiplication est gouvernée principalement dans une telle structure par le temps de propagation de la retenue. On sait qu'un additionneur à prévision de retenue permet d'obtenir une plus grande rapidité de calcul. Cependant, lorsque le nombre d'étages d'un tel additionneur devient trop important, sa structure devient très complexe. On peut donc préférer un additionneur à propagation rapide de la retenue dont chaque étage successif est constitué par une cellule d'additionneur binaire à trois entrées et deux sorties du type de celle représentée sur la figure 2 et décrite dans les demandes de brevet précitées. La cellule de la figure 2 comprend un module de calcul intermédiaire MCI fournissant à partir des deux variables d'entrée A et B une variable intermédiaire M = A 23 B et son complément M. Elle comprend en outre une cellule de découplage formée des transistors MOS T1 et T2, un transistor de transfert T4 commandé par la variable M, dont l'entrée reçoit la retenue Re venant de l'étage précédent et dont la sortie forme la sortie de la retenue Rs, et un transistor T3 commandé par la variable M, dont l'entrée reçoit la variable d'entrée A découplée et dont la sortie est reliée à la sortie de la retenue Rs. Enfin, la cellule comporte une partie d'élaboration de la somme S qui comprend deux transistors T5 et T6 commandés respectivement par les variables M et M, dont les sorties, reliées, fournissent la somme S et dont les entrées reçoivent respectivement le complément Re de la retenue d'entrée, par l'intermédiaire d'un inverseur Il, et la retenue d'entrée Re. Cela étant, l'idée de base de l'invention consiste à n'utiliser que des additionneurs à prévision de retenue ou à propagation rapide de la retenue du type décrit ci-dessus pour effectuer toutes les additions nécessaires dans un multiplieur asynchrone tel que celui de la figure 1. La figure 3 représente le schéma d'une première variante de multiplieur selon l'invention. Celui-ci ne comprend que des additionneurs 1 à 8 à propagation rapide de la retenue à sept étages et des multiplieurs élémentaires 170, 161, etc. symbolisés par des X et disposés en matrice comme dans le cas de la figure 1. Les sept premiers additionneurs 1 à 7 servent à effectuer les différentes sommes de produits partiels nécessaires et le huitième additionneur 8 sert à rassembler les résultats intermédiaires et les retenues fournies par les sept premiers. Pour désigner les différents multiplieurs élémen- taires, on utilise comme premier chiffre la référence de l'additionneur auquel ils sont rattaches, les deux chiffres suivants représentant respectivement l'exposant du poids de la colonne et de la ligne auxquelles ils appartiennent.Ainsi, par exemple, le multiplieur élémen- taire 416 est rattaché à l'additionneur 4 et se trouve à l'intersection de la colonne recevant ltelement-binaire Xi de poids 21 et de la ligne recevant l'élément binaire Y6 de poids 26. Dans l'exemple décrit, les produits partiels sont additionnés par des additionneurs dits de premier niveau 1 à 4 qui additionnent chacun les produits partiels de deux colonnes adjacentes de la matrice. Ainsi, l'additionneur 1 reçoit sur ses paires d'entrées les produits partiels venant des multiplieurs élémentaires des colonnes X7 et X6. Les entrées d'une paire d'entrées reçoivent des produits de même poids. Ainsi, le premier étage reçoit les produits des multiplieurs 170 et 161 de poids 27. Le multiplieur élémentaire 177 étant le seul à fournir un produit de poids 214, celui-ci est envoyé directement à une entrée du dernier additionneur 8. Le produit partiel fourni par le multiplieur 160 n'ayant pas de correspondant de même poids dans la colonne X7 n'est pas envoyé à l'additionneur 1 mais à l'additionneur 5, ce qui est symbolisé par un point référencé 506-1. De même, l'additionneur 2 reçoit les produits partiels des colonnes X5 et X4. Les produits partiels de poids 7 fournis par les multiplieurs élémentaires 252 et 243 sont reçus sur la paire d'entrées du troisième étage de l'additionneur 2. Les additionneurs 3 et 4 sont affectés respectivement aux colonnes X3, X2 et X1, XO et ont une paire d'entrées recevant les produits partiels de poids 2 venant respectivement des multiplieurs élémentaires 334, 325, 416 et 407. Les sommes fournies par les additionneurs de premier niveau sont symbolisées par des cercles placés dans les additionneurs dont les entrées reçoivent ces sommes. Les sommes de premier niveau, telle la somme 507-1, sont reçues sur les entrées d'additionneurs dits de second niveau 5, 6 additionnant les sommes venant de deux additionneurs de premier niveau successifs. Dans la référence des sommes, le premier chiffre indique le numéro de l'additionneur auquel elles sont associées (par exemple 5 pour les sommes 507-1 ou 513-1), les deux suivants correspondent à l'exposant du poids de la somme (par exemple 7 pour la somme 507-1) et le chiffre après le trait d'union est la référence de l'additionneur ayant fourni cette somme.Ainsi, les sommes de premier niveau de poids 27 507-1, 507-2, 607-3, 607-4 sont envoyées respectivement aux paires d'entrées du deuxième étage de l'additionneur 5 et du sixième étage de l'additionneur 6. La somme de premier niveau 601-4 constitue l'élément binaire P1 du produit final cependant que l'élément binaire PO de ce produit final est constitué par le produit partiel fourni par le multiplieur élémentaire 400. Les sommes de deuxième niveau fournies par les additionneurs 5 et 6 sont symbolisées par un carré. Elles sont envoyées essentiellement sur les entrées de l'additionneur de troisième niveau 7. Ainsi, les sommes de poids 27 707-5 et 707-6 sont envoyées sur la paire d'entrées du quatrième étage de l'additionneur 7. Les sommes 702-6 et 703-6 constituent les éléments binaires P2 et P3 du produit final cependant que les sommes 712-5 et 711-5 sont envoyées à l'additionneur 8. Les sommes de troisième niveau fournies par l'additionneur 7 sont symbolisées par des triangles. Les sommes des premiers étages, 904 à 907, constituent les éléments binaires P4 à P7 du produit final. Les sommes 908 à 910 sont envoyées au dernier additionneur 8. Celui-ci reçoit sur ses entrées, d'une part, les retenues finales venant des premiers additionneurs 1 à 7 et, d'autre part, les sommes finales de mêmes poids venant des premiers additionneurs 1, 2, 5, 7 plus le produit partiel du multiplieur élémentaire 177. Ainsi, par exemple, l'additionneur 8 reçoit sur sa première paire d'entrées la retenue finale de l'additionneur 4 et la somme de troisième niveau 908, toutes deux de poids 28. L'additionneur 8 fournit sur ses sorties somme les éléments binaires P8 à F14 du produit final et sur sa sortie retenue finale l'élément binaire P15. Bien entendu, bien qu'on ait décrit la structure de multiplieur selon l'invention dans le cas de deux mots binaires ayant le même nombre N = 8 d'éléments binaires, l'invention peut aussi s'appliquer dans le cas de deux mots ayant respectivement des nombres Ni et N2 d'éléments binaires quelconques. En outre, on peut très bien disposer les premiers additionneurs à propagation rapide de la retenue de manière qu'ils additionnent des produits partiels de lignes adjacentes au lieu de colonnes. Dans ce cas, le dernier additionneur sera disposé à coté de la colonne XN1. Dans le cas général, on aura donc N1-1 premiers additionneurs (dans le cas où on associe des colonnes adjacentes de la matrice) à N2-1 paires d'entrées ou N2-1 premiers additionneurs à N1-1 paires d'entrées (dans le cas où on associe des lignes adjacentes de la matrice) et un dernier additionneur à N1-1 ou N2-1 paires d'entrées respectivement. La figure 4 représente le schéma d'une deuxième variante de multiplieur selon l'invention n'utilisant que des multiplieurs élémen- taires tels 170, 171 et des additionneurs 10 à 70 et 8 à propagation rapide de la retenue. Les multiplieurs élémentaires sont également disposés en matrice mais celle-ci est modifiée par rapport à la figure 3. Sur la figure 3, les multiplieurs élémentaires étaient disposés en lignes et colonnes de manière telle que les multiplieurs fournissant des produits partiels de même poids étaient alignés parallèlement à une première diagonale de la matrice passant par les multiplieurs 170 et 407. Dans le cas de la figure 4, la matrice est ensuite repliée autour d'une droite D parallèle à la seconde diagonale de la matrice passant par les multiplieurs 900 et 977, cette droite D étant immédiatement adjacente à cette diagonale. La partie de la matrice ne contenant pas les multiplieurs 977 et 900 est repliée autour de la droite D et les multiplieurs correspondants sont symbolisés par une étoile *. Ainsi, par exemple, la ligne Y7 est repliée après le multiplieur 977, ce qui est indiqué par une flèche coudée contre la droite D. Le multiplieur élémentaire 117' est celui qui effectue le produit partiel de Y7 (partie repliée de la ligne) par X1 (partie repliée de la colonne). Les produits partiels de chaque partie de colonne non repliée et ceux de la partie de ligne repliée adjacente sont envoyés aux paires d'entrées d'un additionneur à propagation rapide de la retenue. L'indice de l'élément binaire correspondant à la colonne non repliée et l'indice de l'élément binaire correspondant à la ligne repliée associées à un même additionneur sont les mêmes. Ainsi, pour l'additionneur 40, il s'agit de la partie de colonne non repliée X4 et de la partie de ligne repliée Y4. Si N est le nombre d'éléments binaires de chacun des mots, on utilise donc N-1 premiers additionneurs, 10 à 70 dans le cas de la figure 4, à N-l étages. Les deux entrées d'une paire d'entrées des additionneurs reçoivent des produits partiels de mêmes poids. Comme on le-voit, en se déplaçant vers la droite, les additionneurs ont de plus en plus d'étages ne recevant pas de produits partiels. Les entrées de ces étages reçoivent les sommes intermédiaires fournies par les additionneurs précédents, ces sommes étant transférées toujours parallèlement à la première diagonale de la matrice. Les mêmes symboles que sur la figure 3 sont utilisés pour représenter les sommes dites de premier-niveau (cercle), de deuxième niveau (carré) et de troisième niveau (triangle). 8 Ainsi, Si l'on considère tous les résultats de poids 2 , on voit que le second étage du premier additionneur 10 fait la somme des produits partiels des multiplieurs élémentaires 171 (X7x Y1) et 117' (X1x Y7), que le troisième étage de l'additionneur 20 fait la somme des produits partiels des multiplieurs 262 (X6xY2) et 226' (X2xY6), que le quatrième étage de l'additionneur 30 fait la somme des produits partiels des multiplieurs 353 (X5xY3) et 335' (X3xY5). Le cinquième étage de l'additionneur 40 fait la somme du produit partiel du multiplieur 444 (X4xY4) et de la somme de premier niveau 408-10 venant du second étage de l'additionneur 10.De même, le sixième étage de l'additionneur 50 fait la somme des sommes de premier niveau 508-20 venant du troisième étage de l'additionneur 20 et 508-30 venant du quatrième étage de l'additionneur 30. Enfin, le septième étage de l'additionneur 60 fait la somme des sommes de second niveau 608-40 venant du cinquième étage de l'additionneur 40 et 608-50 venant du sixième étage de l'additionneur 50 et fournit une somme finale de troisième niveau 908' qui est envoyée au premier étage du dernier additionneur 8, en même temps que la retenue finale de l'additionneur 70 qui a le même poids.Comme on le voit, l'élément binaire P0 du produit final est fourni par le multiplieur élémentaire 900, l'élément P1 est la somme de premier niveau 901' fournie par l'additionneur 70, les éléments P2 et P3 sont les sommes de deuxième niveau 902' et 903' et les éléments P4 à P7 les sommes de troisième niveau 904' à 907' fournies par l'additionneur 70. Les éléments binaires P8 à P15 sont fournis par le dernier additionneur 8. Il est clair que cette variante s'applique quel que soit le nombre N d'éléments binaires des mots à multiplier pourvu que les deux mots aient le même nombre d'éléments. De plus, on peut disposer les additionneurs selon les lignes au lieu de les disposer selon les colonnes, le dernier additionneur étant alors parallèle à la colonne XN. Enfin, la droite D de repliement peut être placée d'un côté ou de l'autre de la seconde diagonale. Bien entendu, les exemples de réalisation décrits ne sont nullement limitatifs de l'invention. REVENDICATIONS 1. Structure de multiplieur rapide en circuit intégré MOS pour la multiplication de deux mots binaires ayant respectivement Ni et N2 éléments binaires, ladite structure comprenant N1x N2 multiplieurs élémentaires disposés en matrice, fournissant chacun le produit partiel d'un élément binaire d'un premier desdits mots, affecté à la colonne correspondante de la matrice, et d'un élément binaire du second mot, affecté à la ligne correspondante de la matrice, caractérisée en ce que les sommes successives à effectuer à partir des produits partiels pour obtenir les éléments binaires (P0 à P15) du produit final sont réalisées par Ni [ ou N2 ] additionneurs (1 à 8 ; 10 à 70, 8) du type à prévision de retenue ou à propagation rapide de la retenue, les N1-1 [ou N2-1 ] premiers additionneurs (1 à 7 ; 10 à 70) ayant N2-1 [ou N1-1 ] étages et ie dernier additionneur (8), qui sert à rassembler les retenues finales des premiers additionneurs et les résultats intermédiaires de poids correspondants, ayant N1-1 [ou N2-1l étages. 2. Structure de multiplieur selon la revendication 1, dans lequel on a Ni = N2 = N, caractérisée en ce que tous les additionneurs sont du même type à N-l étages. 3. Structure de multiplieur selon l'une des revendications 1 ou 2, caractérisée en ce que les paires d'entrées des étages successifs des additionneurs reçoivent des produits partiels ou des résultats intermédiaires de même poids, le poids augmentant d'une unité d'un étage au suivant. 4. Structure de multiplieur selon la revendication 3, où on N choisit N = 2N caractérisée en ce qu'elle comprend 2 additionneurs (i à 4) de premier niveau, additionnant uniquement des produits partiels venant des multiplieurs élémentaires (170, 161, 243, 252, 325, 334, 407, 416), N4 additionneurs (5, 6) de second niveau additionnant essentiellement les sommes intermédiaires venant des additionneurs de premier ième niveau, et ainsi de suite et enfin un additionneur (7) de n niveau additionnant essentiellement les sommes intermédiaires venant des deux iême additionneurs de (n-1)ième niveau, chacun des additionneurs de premier niveau additionnant les produits partiels venant de deux colonnes [ ou deux lignes ] adjacentes de la matrice de multiplieurs élémentaires, chacun des additionneurs de second niveau additionnant les sommes intermédiaires venant de deux additionneurs de premier niveau successifs et ainsi de suite. 5. Structure de multiplieur selon la revendication 2, caractérisée en ce que, la matrice de multiplieurs élémentaires comportant les multiplieurs qui fournissent des produits partiels de même poids disposés parallèlement à une première diagonale, cette matrice est repliée autour d'une droite (D) perpendiculaire à ladite première diagonale, cette droite (D) étant située immédiatement adjacente à la seconde diagonale de la matrice passant par les multiplieurs (900, 977) fournissant respectivement les produits partiels de plus faible poids et de plus fort poids et la partie de matrice ne contenant pas ces multiplieurs (900, 977) étant repliée sur la partie les contenant, en ce que chacun des premiers additionneurs (10 à 70) additionne les produits partiels d'une partie de colonne [ ou de lignez et de la partie de ligne repliée [ ou de colonne repliée correspondant à des éléments binaires (Xj, Yj) de même poids et en ce que les entrées de poids le plus élevé desdits additionneurs ne recevant pas de produits partiels reçoivent les sommes intermédiaires fournies par les additionneurs précédents et transférées parallèlement à ladite première diagonale. 6. Structure de multiplieur selon la revendication 5, caractérisée en ce que la somme de plus fort poids (913' à 908') des premiers additionneurs (10 à 60) est envoyée avec la sortie retenue de l'additionneur suivant à une paire d'entrées correspondante du dernier additionneur (8).