Brevet FR2543325A1 — publié le 19840928

La présente invention concerne une structure de multiplieur rapide en circuit intégré MOS pour la multiplication de deux mots binaires N éléments binaires. Une structure connue de multiplieur utilisant la technique du "carry-save adder" est 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 a 29, en particulier page 21. Cette structure 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 demande de brevet français n0 82 05083 déposée le 25 mars 1982 par la demanderesse et intitulée "Structure de multiplieur rapide en circuit intégré MOS" décrit un perfectionnement a de tels multiplieurs permettant une utilisation optimisée de cellules d'additionneur binaire propagation rapide de la retenue. Ce perfectionnement consiste, pour rétablir l'équilibre entre la propagation des sommes et des retenues, a transférer les sommes intermédiaires a addi tonner dans des cellules ultérieures en effectuant des sauts de p en p cellules, p étant un nombre entier supérieur d un.En ce qui concerne les retenues se propageant de cellule en cellule adjacente, ce sont alternativement la valeur vraie et la valeur complémentée qui sont utilisées et les cellules sont donc alternativement d'un premier type (retenue à l'entrée complémentée, retenue de sortie vraie) et d'un second type (retenue l'entrée vraie, retenue de sortie complémentée). Cette structure qui permet d'améliorer la vitesse de la multiplication nécessite cependant %"remploi de quatre types de cellule différents comportant des cellules de calcul intermédiaire pour le décodage des variables A et B. Aussi, le dessin et la réalisation du circuit intégré présentent une certaine complexité et le nombre de transistors MOS utilisés est encore relativement important, avec des valeurs de surface de silicium et de consommation correspondantes. La présente invention a pour objet de remédier à ces inconvénients en prévoyant une structure de multiplieur utilisant des cellules d'additionneur binaire simplifiées connues qui diminuent le nombre de transistors total du multiplieur et donc la surface de silicium nécessaire et la consommation. La structure de multiplieur selon l'invention comprend de maniere connue N2 multiplieurs élémentaires disposés en matrice carrée, fournissant chacun le produit partiel d'un élément binaire d'un premier des mots binaires, affecté à la colonne correspondante de la matrice, et d'un élément binaire du second mot, affecté à la ligne correspondante de la matrice, et des cellules d'additionneur binaire élémentaires associées aux multiplieurs élémentaires pour effectuer les sommes successives nécessaires pour l'obtention des 2N éléments binaires du produit final, ces cellules étant également arrangées en une matrice associée dans laquelle la sortie somme de chaque cellule est raccordée à une entrée d'une cellule suivante dans la direction de la diagonale de la matrice passant par les multiplieurs élémentaires fournissant des produits partiels de même poids, les raccordements s'effectuant de p en p cellules (p nombre entier supérieur a un), et dans laquelle la sortie retenue de chaque cellule est raccordée a une entrée d'une cellule adjacente de poids immédiatement supérieur dans la direction d'une ligne ou d'une colonne de ladite matrice associée. Selon l'invention, la structure de multiplieur du type cidessus est caractérisée par le fait que, la direction diagonale de progression des sommes de p en p cellules définissant les deux côtés de la matrice associée par Qd sont fournis les éléments binaires du produit final, les transferts de retenue s'effectuent, le long des lignes ou colonnes, parallèlement au cété de fourniture des éléments binaires du produit final de plus faible poids dans la partie de ladite matrice associée, qui est délimitée par la diagonale de la matrice de multiplieurs, parallele à la direction de propagation des sommes, et qui contient les cellules de plus faible poids, et parallelement au c8té de fourniture des éléments binaires de plus fort poids dans l'autre partie de ladite matrice associée, par le fait que ladite matrice associée ne comporte pas de cellules associées correspondant aux multiplieurs élementaires des p premières lignes ou colonnes à partir du côté opposé au cote de fourniture des éléments binaires de plus fort poids et des p-l premières colonnes ou lignes à partir du côté opposé au côté de fourniture des éléments#binaires de plus faible poids et est complétée par p-l colonnes ou lignes de cellules supplémentaires sur le c8té de la matrice où sont fournis les éléments binaires de plus faible poids et par p-l lignes ou colonnes de cellules supplémentaires sur le côté de la matrice où sont fournis les éléments binaires de plus fort poids, lesdites cellules supplémentaires servant à rassembler les résultats intermédiaires fournis par les cellules des p lignes et des p colonnes adjacentes pour élaborer les éléments binaires du produit final, et par le fait que, dans la première colonne ou ligne de la matrice associée, du côté opposé au côté de fourniture des éléments binaires de plus faible poids, les retenues sont transférées d'une cellule à la suivante vers la cellule fournissant l'élément binaire de plus fort poids du produit final. Selon une autre caractéristique de l'invention, en suivant la propagation des retenues selon les directions définies pour les deux parties de la matrice associée, les cellules d'additionneur binaire sont alternativement des cellules d'un premier type fournissant des variables de sortie, somme et retenue, vraies a partir de variables d'entrée sous forme complémentée et des cellules d'un second type fournissant des variables de sortie complémentées à partir de variables d'entrée vraies et le motif de répartition des types de cellule est déterminé en disposant, le long de la diagonale de ladite matrice de N-I multiplieurs correspondant aux produits de poids 21 et a partir du point de fourniture de l'élément binaire de poids 2N-1 du produit final, une première cellule, de l'un des deux types, fournissant ledit élément binaire de poids 2N 1 puis p cellules changeant de type toutes les deux cellules, les deux cellules suivant ladite première cellule étant d'un type opposé à celle-ci, enfin en complétant la diagonale par N-p-2 cellules dont le type est choisi pour que les sauts de p en p cellules s'effectuent toujours entre cellules de type opposé, et en complétant la matrice associée par des cellules dont le type est déter-- miné en accord avec la loi d'alternance le long des deux directions principales de propagation des retenues. 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 le schéma d'un multiplieur 8 x 8 selon l'invention avec p = 2; la figure 2 est le schéma de répartition des cellules le long de la diagonale d'un multiplieur 16 x 16 selon l'invention avec p = 5; les figures 3 et 4 sont des schémas de portes NON-ET et ET servant de multiplieurs élémentaires; la figure 5 est le schéma d'une cellule d'additioneur binaire à trois entrées et deux sorties utilisée dans le multiplieur selon l'invention ; et - les figures 6 et 7 montrent des schémas de cellules d'additionneur binaire à deux entrées et deux sorties utilisées dans le multiplieur selon l'invention. La figure 1 représente le schéma d'un multiplieur 8 x 8 selon l'invention avec transfert des- sommes de deux en deux cellules, mettant à profit l'utilisation de cellules d'additionneur binaire sirplifiées et en particulier d'une cellule a trois entrées et deux sorties fournissant des variables de sortie (somme et retenue) vraies si elle reçoit des variables d'entrée complémentées et des variables de sortie complémentées si elle reçoit des variables d'entrée vraies. Le schéma d'une telle cellule est représenté sur la figure 5 et sera décrit ultérieurement. Sur la figure 1, on a symbolisé par des cercles les cellules d'additionneur binaire a deux entrées et deux sorties et par des carrés les cellules à trois entrées et deux sorties. Les cellules représentées en trait fort, telles que 103, 105, 108, 109, sont des cellules recevant des variables d'entrée sous forme complémen#tée et fournissant la somme et la retenue sous forme vraie. Les cellules représentées en trait fin, telles que 104, 106, 107, sont des cellules recevant des variables d'entrée vraies et fournissant la somme et la retenue sous forme complémentée.Les multiplieurs élémentaires, tels que 101, 102, sont symbolisés par des X en trait fin s'ils fournissent un produit partiel XY vrai (ce sont alors des portes ET) ou en trait fort s'ils fournissent un produit partiel XY complémenté (ce sont alors des portes NON-ET). Le multiplieur selon l'invention de la figure I comporte tout d'abord une matrice carrée de multiplieurs élémentaires fournissant chacun le produit partiel de l'élément binaire d'un premier mot huit éléments binaires X0 d X7, correspondant a la colonne où se trouve le multiplieur (par exemple X7 pour 101, X2 pour 102), les huit elle ments binaires X0 a X7 étant associés respectivement aux colonnes numé- rotées 0 a 7, par l'élément binaire du second mot a huit éléments binaires YO a Y7, correspondant a la ligne où se trouve le multiplieur (YO pour 101 et 102), les huit éléments binaires Y0 a Y7 étant associés respectivement aux lignes numérotées O a 7. Pour réaliser les différentes additions nécessaires pour effectuer la multiplication des deux mots binaires, il est prévu une matrice associée de cellules d'additionneur binaire. Dans l'exemple de réalisation choisi, les sommes partielles fournies par les cellules sont transférées de deux en deux cellules suivant la direction de la diagonale de la matrice de multiplieurs élémentaires passant par les multiplieurs de même poids, confor mément au principe décrit dans la demande de brevet français n0 82 05083 précitée.En conséquence, la matrice associée ne comporte pas de cellules associées correspondant aux multiplieurs des deux premières lignes 0 et 1 et de la première colonne 7. Chacune des cellules représente avec un symbole X d l'intérieur est une cellule associée à un multiplieur élémentaire local dont elle reçoit sur une entrée le produit partiel. La matrice associée est complétée par une colonne -1 et une ligne 8 de cellules supplémentaires non associées à des multiplieurs élémentaires locaux. Ces cellules supplémentaires servent à rassembler les sommes intermédiaires fournies par les cellules des deux lignes et colonnes adjacentes pour élaborer les éléments binaires PO PIS du produit final.Ces éléments binaires sont fournis par les sorties somme des cellules supplémentaires sauf pour l'élément binaire P15 qui est fourni pour la sortie retenue de la derniere cellule de la premier colonne, numérotée 6, de la matrice associée. Selon l'invention, dans la partie de la matrice associée qui est délimitée par la diagonale de la matricedemultiplieurs, parallèle à la direction de progression des sommes, et qui contient les cellules de plus faible poids, les retenues sont transférées de cellule an cellule dans la direction des colonnes. Dans l'autre partie de la matrice associée, les retenues sont transférées dans la direction des lignes. Selon ces deux directions principales de transfert de retenue, les cellules sont alternativement du premier et du second types (entrées complémentées - sorties vraies et entrées vraies - sorties complé- mentées).Enfin, dans la première colonne, numérotée 6 > de la matrice associée, les retenues sont transférées d'une cellule à la suivante vers la cellule fournissant les deux éléments binaires de plus fort poids P14 et P15. Comme, dans cette colonne, l'alternance des cellules n'est pas respectée, on prévoit des inverseurs tels que 110 ou 111 entre deux cellules de même type. Ceci n'a pas d'inconvénients quant a la durée globale de la multiplication puisqu'il n'y a pas d'inverseur ajoutant son temps de transfert sur le chemin de retenue le plus long. Pour bénéficier au maximum des avantages de cette structure et réduire le nombre d'inverseurs utilisés aux seuls inverseurs de la colonne 6, il faut adopter la répartition des cellules des deux types selon le motif représenté sur la figure 1 qui consiste a choisir d'abord les cellules de la diagonale en partant de la cellule 107 qui peut être de n'importe lequel des deux types mais qui est de préférence du second type (entrées vraies - sorties complémentées),si N est pair, pour que la cellule fournissant les éléments binaires de plus fort poids F14 et PIS soit du premier type (entrées complémentées - sorties vraies).Ceci économise un inverseur de sortie car, ainsi qu'on peut le remarquer, un élément binaire du produit final sur deux est sous forme complémentée et doit passer par un inverseur de sortie (non représenté) si on veut les valeurs vraies. Donc, le long de la diagonale, après cette premiere cellule 107, on dispose deux cellules de type opposé, 108 et 109. La diagonale est alors complétée par des cellules choisies de maniere telle que les sauts des sommes de deux en deux cellules s'effectuent toujours entre cellules de type opposé. On complete ensuite la matrice associée par des cellules alternativement de SVun et de l'autre type le long des deux directions principales de propagation des retenues. D'une maniera plus générale~ on va définir la structure de multiplieur selon l'invention an se reportant également a la figure 2 qui représente les multipliaurs élémentaires et les cellules d'additionneur binaire de la diagonale d'un multiplieur 16 x 16 avec sauts de cinq an cinq cellules pour les sommes. Si N est le nombre d'éléments binaires de chacun des deux mots a multiplier et si on choisit de transférer les sommes partielles de p en p cellules, la matrice associée de cellules d'additionneur binaire ne comportera pas de cellules correspondant aux p premieres lignes (cinq dans le cas de la figure 2) et aux p I premières colonnes de multiplieurs élémentaires. La -matrice associée est complétée par p-l colonnes et lignes supplémentaires (quatre dans le cas de la figure 2). Le motif de répartition des cellules est défini en choisissant la premiere cellule de la diagonale (120, figure 2) fournissant l'élément binaire de poids 2N 1 (F15, figure 25 puis p cellules changeant de type toutes les deux cellules, les deux cellules suivant la premiere cellule (120) étant d'un type opposé d celle-ci. On complete ensuite la diagonale par N-p-2 cellules dont le type est choisi pour que les transferts de p en p cellules s'effectuent toujours entre cellules de type opposé. On complete enfin la matrice associée par des cellules de type alterné le long des deux directions de propagation des retenues. Les multiplieurs élémentaires sont choisis du type adapté aux cellules auxquelles ils fournissent leur produit partiel. Ainsi, sur la figure 2, la première cellule 120 à l'extrémité de la diagonale, qui fournit l'élément binaire P15, est du second type puis suivent deux cellules du premier -type, deux cellules du second type et une cellule du premier type constituant le motif de base de cinq cellules. Ensuite, viennent les cellules choisies de telle sorte que les transferts de somme de cinq en cinq cellules s'effectuent toujours entre cellules de type opposé, les multiplieurs élémentaires étant ensuite choisis de manière appropriée. Ainsi, la porte ET formant le multiplieur 121 transmet un produit partiel vrai à la cellule à deux entrées du second type 123 dont la sortie somme est reliée à une entrée de la cellule à trois entrées du premier type 125 et ainsi de suite. De même, pour la porte NON-ET 122 et les cellules 124 du premier type et 126 du second type. Dans le cas d'un multiplieur 16 x 16, on peut constater que la solution la plus avantageuse du point de vue nombre d'inverseurs est le transfert de quatre en quatre cellules qui ne nécessite que quatre inverseurs de retenue dans la première colonne de la matrice associée. Cependant, le transfert de deux en deux cellules ne nécessite que sept inverseurs et, comme on l'a déjà mentionné, ces inverseurs n'augmentent nullement le temps global nécessaire pour une multiplication. Un des avantages de la structure de multiplieur ainsi décrite est qu'elle permet d'utiliser des cellules d'additionneur binaire connues, les plus simples, exigeant un nombre de transistors MOS minimum. Les figures 3 et 4 représentent respectivement-une porte NON ET et une porte ET réalisant la fonction de multiplieur élémentaire. La porte NON-ET de la figure 3 comprend en série, entre la masse et la borne positive de l'alimentation, deux transistors MOS T1 et T2 dont les grilles reçoivent respectivement les variables d'entrée X et Y et une résistance R. La sortie est prélevée au point commun entre la résistance R et le transistor T2 et fournit la variable complémentée A = Les transistors T1 et T2 peuvent être des transistors à enrichissement. De même, sur la figure 4, la porte ET comprend deux transistors MOS T'1 et T'2 et une résistance R'en série entre l'alimentation et la masse. La sortie fournit la variable vraie A = XY. Les transistors MOS T'1 et T'2 peuvent être des transistors dits "naturels", c'est-a-dire sans dopage additionnel du substrat. La figure 5 représente le schéma d'une cellule d'additionneur binaire connue à trois entrées et deux sorties qui peut être utilisée aussi bien comme cellule du premier type que comme cellule du second type selon qu'ellé reçoit des variables d'entrée sous forme complémentée ou sous forme vraie. Dans le cas de la figure 5, on a supposé qu'il s'agissait d'une cellule du premier type.La retenue de sortie vraie R est fournie au point commun entre une résistance R1, reliée à s la borne positive de l'alimentation, et un réseau comprenant une première branche, comportant un transistor MOS T11 commandé par une première variable A en série avec deux transistors en parallèle T12 et T13 respectivement commandés par une deuxième variable B et une troi sième variable Re qui est la retenue venant d'une cellule précédente, e et une seconde branche comportant deux transistors en série T14 et T15 commandés par les variables B et Re, de façon a former :: R R A s e De même, la somme S est fournie au point commun entre une résistance R2, reliée a la borne positive de l'alimentation, et un réseau comprenant une première branche, comportant un transistor T16 commandé par la retenue de sortie R en série avec trois transistors en parallele T17 s à T19 commandés par les variables A, B et Re, et une seconde branche comportant trois transistors en série T20, T21 et T22 commandés par les variables A, B et Re, de façon à former: S = (A+B+R )R + A B R e s e Il est facile de voir que la même cellule commandée par les variables A, B et R fournit en sortie la retenue R et la somme S complémentées. e s Cette cellule connue présente un nombre minimum de transistors. Comme elle sert pour toutes les cellules de la matrice associée sauf la première ligne, cela simplifie en outre la conception du circuit intégré. La figure 6 est le schéma d'une cellule à deux entrées du premier type (entrées complémentées - sorties vraies). La retenue de sortie R est fournie au point commun entre une résistance R3, reliée au s pôle positif, et deux transistors en parallèle T30 et T31 reliés à la masse et commandés par les variables A et B. La somme S est obtenue au point commun entre une résistance R4, reliée au pôle positif, et un transistor T32, commandé par la retenue Rs, en parallèle avec deux transistors en série T33 et T34, commandés par les variables A eut B. La figure 7 représente le schéma d'une cellule à deux entrées du second type (entrées vraies - sorties complémentées). La retenue de sortie R complémentée est fournie au point commun entre une résis s tance R'3, reliée au pôle positif, et deux transistors en série T41 et T42 commandés par les variables A et B. La somme S complémentée est obtenue au point commun entre une résistance R'4, reliée au ple positif, et un transistor T43, commandé par la retenue complémentée R, en série s avec deux transistors T44 et T45 en parallèle, commandés par les variables A et B. A titre d'exemple, avec ces diverses cellules, un multiplieur 16 x 16 selon l'invention utilise environ quatre mille transistors contre environ cinq mille transistors pour le multiplieur selon la demande de brevet français n0 82 05083, soit une réduction d'environ vingt-cinq pour cent de la surface de silicium utilisée et de la consomr mation. il faut noter que la valeur de p n'a pratiquement aucun effet sur ces chiffres. 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 à N éléments binaires, 2 ladite structure comprenant N multiplieurs élémentaires disposés en matrice carrée, fournissant chacun le produit partiel d'un élément binaire d'un premier desdits mots, affecté a la colonne correspondante de la matrice, et d'un élément binaire du second mot, affecté à la ligne correspondante de la matrice, et des cellules d'additionneur binaire élémentaires associées aux multiplieurs élémentaires pour effectuer les sommes successives nécessaires pour l'obtention des 2N éléments binaires du produit final, ces cellules étant également arrangées en une matrice associée dans laquelle la sortie somme de chaque cellule est raccordée une entrée d'une cellule suivante dans la direction de la diagonale de la matrice passant par les multiplieurs élémentaires fournissant des produits partiels de même poids, les raccordements s'effectuant de p an p cellules (p nombre entier supérieur a un), et dans laquelle la sortie retenue de chaque cellule est raccordée à une entrée d'une cellule adjacente de poids immédiatament supérieur dans#la direction d'une ligne ou d'une colonne de ladite matrice associée, ladite structure étant caractérisée an ce que, la direction diagonale de progression des sommes de p en p cellules définissant les deux cotés de la matrice associée par où sont fournis les éléments binaires du produit final, les transferts de retenue s'effectuent, le long des lignes ou colonnes, parallèlement au côté de fourniture des éléments binaires du produit final de plus faible poids (PO à P6) dans la partie de ladite matrice associée, qui est délimitée par la diagonale de la matrice de multiplieurs (101, 102 ; 121, 122), parallele d la direction de propagation des sommes, et qui contient les cellules de plus faible poids, et parai- le lament au cété de fourniture das éléments binaires de plus fort poids (P8 a P15) dans l'autre partie de ladite matrice associée, en ce que ladite matrice associée ne comporte pas de cellules associées correspondant aux multiplieurs élémentaires des p premières lignes (8, 1) ou colonnes partir du c8té opposé au coté de fourniture des éléments binaires de plus fort poids (P8 à F15) et des p-l premibres colonnes (7) ou lignes a partir du côté opposé au coté de fourniture des éléments binaires dè plus faible poids (PO à P6) et est complétée par p-l colonnes (-1) ou lignes de cellules supplémentaires sur le cote de la matrice où sont fournis les éléments binaires de plus faible poids et par p-1 lignes (8) ou colonnes de cellules supplémentaires sur le côté de la matrice où sont fournis les éléments binaires de plus fort poids, lesdites cellules supplémentaires (107, 120) servant à rassembler les résultats intermédiaires fournis par les cellules des p lignes et des p colonnes adjacentes pour élaborer les éléments- binaires du produit final, et en ce que, dans la première colonne (6) ou ligne de la matrice associée, du côté opposé au côté de fourniture des éléments binaires de plus faible poids, les retenues sont transférées d'une cellule à la suivante vers la cellule fournissant l'élément binaire de plus fort poids (P15) du produit final. 2. Structure de multiplieur selon la revendication 1, caractérisée en ce que, en suivant la propagation des retenues selon les directions définies pour les deux parties de la matrice associée, les cellules d'additionneur binaire sont alternativement des cellules (103, 105 ; 124, 125) d'un premier type fournissant des variables de sortie, somme et retenue, vraies à partir de variables d'entrée sous forme complémentée et des cellules (104, 106, 107 ; 120, 123, 126) d'un second type fournissant des variables de sortie complémentées a partir de variables d'entrée vraies et en ce que le motif de répartition des types de cellules est déterminé en disposant, le long de la diagonale de ladite matrice de multiplieurs correspondant aux produits de poids 2N 1 et a partir du point de fourniture de l'élément binaire (T7 ; P15) de poids 2N 1 du produit final, une première cellule (107 ; 120), de l'un des deux types, fournissant ledit élément binaire fiit ;P15) de poids 2N 1, puis p cellules (108, 109) changeant de type toutes les deux cellules, les deux cellules suivant ladite première cellule étant d'un type opposé a celle-ci, enfin en complétant la diagonale par N-p-2 cellules dont le type est choisi pour que les transferts de p en p cellules steffectuent toujours entre cellules de type opposé, et en complétant la matrice associée par des cellules dont le type est déterminé en accord avec la loi d'alternance le long des deux directions principales de propagation des retenues. 3. Structure de multiplieur selon la revendication 2, caractérisée en ce que la première ligne (2) ou colonne de la matrice, associée du côté opposé au côté de fourniture des éléments binaires de plus fort poids, ne comporte que des cellules d'additionneur binaire (103, 104 ; 123) a deux entrées et deux sorties et en ce que toutes les autres cellules sont des cellules d'additionneur binaire a trois entrées et deux sorties (105 a 109 ; 120, 124 a 126). 4. Structure de multiplieur selon la revendication 3, caractérisée en ce que toutes les cellules a trois entrées et deux sorties (105 a 109 ; 120, 124 a 126) sont identiques et d'une construction telle qu'elles peuvent fournir, soit des variables de sortie vraies si elles reçoivent des variables d'entrée complémentées, soit des variables de sortie complémentées si elles reçoivent des variables d'entrée vraies. 5. Structure de multiplieur selon l'une quelconque de#s revendications 2 a 4, caractérisée en ce que les multiplieurs élémen- taires sont constitués, soit de portes ET (102 ; 121), soit de portes NON-ET (101 ; 122) selon que le produit partiel qu'ils calculent doit être envoyé a une cellule du second ou du premier type respectivement. 6. Structure de multiplieur selon l'une quelconque des revendications 2 a 5, caractérisée an ce que ladite première cellule de la diagonale (107 ; 120) est une cellule du second type si N est pair.