Brevet FR2013795A1 — publié le 19700410

La présente invention concerne des perfectionnements aux équipements de calcul numérique et, plus particulièrement, un multiplicateur de nombres exprimés en système binaire. Selon le cadre le plus large de cette invention, un multiplicateur de nombres binaires comporte deux registres à décalage (A, B) pour les deux nombres qui doivent être multipliés, une mémoire de produit (P) dans laquelle le produit des deux nombres est formé, et une mémoire de retenue (Q) pour la mise en mémoire temporaire des éléments binaires de retenue, les deux registres et les deux mémoires étant associés de telle façon que les cases d'une mémoire peuvent être considérées chacune comme occupant une colonne contenant aussi une case de l'autre mémoire et de chacun des deux registres, et des moyens d'introduire les deux nombres d'entrée dans les deux registres avec les éléments binaires de chaque nombre espacés dans leurs registres respectifs de façon que chaque élément soit séparé du suivant par une seule case vide du registre, les deux nombres se lisant dans le même sens et 1' élément le moins significatif d'un nombre se trouvant dans la même colonne que l'élément le plus significatif de l'autre nombre. La multiplication des deux nombres est effectuée en une série de phases successives après chacune desquelles les deux nombres sont décalés chacun d'une case et en sens opposé dans leurs registres respectifs. Chaque phase comprend la réalisation d'une opération logique sur toutes les colonnes du multiplicateur prises par paires constituées d'une colonne (m) dans laquelle les registres À et 3 contiennent des éléments binaires (a., b.) des nombres d'entrée et la colonne d'ordre immédiatement supérieur (m + i), les phases successives se continuant jusqu'à ce que tous les éléments binaires des deux nombres aient été multipliés et que la mémoire de retenue Q soit vide. Les registres et mémoires du multiplicateur, en association avec les circuits de logique et de commande nécessaires à leur fonctionnement d'une manière définie, peuvent être associés en permanence si bien que le multiplicateur a une existence réelle comme entité physique. L'invention concerne également des équipements, par exemple un calculateur arithmétique, dans lesquels les registres requis, les mémoires et les autres éléments sont mis en relation fonctionnelle par un programme central, ou tout autre système de commande, de manière à former un multiplicateur tel que celui décrit dans le paragraphe précédent, mais peuvent remplir d'autres fonctions dans l'équipement. Les processus courants de multiplication de nombres à plusieurs chiffres impliquent des opérations d'addition répétées avec un décalage ou un produit partiel après chaque opération. Ce procédé demande beaucoup de temps puisque chaque opera- tion d'addition comporte un temps de propagation d'une retenue qui, dans les plus mauvaises conditions, correspond pratiquement à toute la longueur du registre de produit. Un multiplicateur conforme à la présente invention fonctionne en une série de phases répétées avec un décalage relatif du multiplicateur et du multiplicande après chaque phases Une phase consiste en plusieurs opérations logiques identiques effectuées simultanément sur des paires de colonnes du multiplicateur, et tout élément binaire de retenue produit par ces opérations n'est reporté que sur la prochaine colonne, c'est-à-dire que le processus de report n'est pas cumulatif. L'augmentation de la vitesse d'opération globale qui en résulte est obtenue par des circuits logiques simples. Les registres, mémoires et autres éléments du multiplicateur peuvent etre réalisés dans tout système logique à deux niveaux. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée à titre dgexemple non limitatif, en se reportant aux figures annexées qui représentent : la figure 1(a)2 un schéma de la disposition des registres et mémoires formant le multiplicateur ; - la figure 1(b), un tableau des étapes successives d'une opération de multiplication ; - la figure 2, US circuit logique simplifié dune partie du multiplicateur - la figure 3, un tableau indiquant l'opération logique de base qui doit être effectuée par le circuit de la figure 2 à chaque étape de la multiplication. la disposition générale du multiplicateur est apparente sur les figures i (a) et 2o Les parties essentielles sont deux registres à décalage À et B servant à inscrire les deux nombres d entrée qui doivent être multipliés, et deux mémoires P et Q pour contenir le produit cherché et tout chiffre de report temporaire apparaissant en cours d'opération. Chaque case de mémoire des registres Â et B et des mémoires P et Q est un élément bistable de tout type adéquat. Les registres et les mémoires sont associés de manière que chaque case de la mémoire P ou Q puisse être considéree comme occupant une colonne qui contient également une case de l'autre mémoire et de chacun des registres À et 3. Ces colonnes du multiplicateur sont numérotées de droite à gauche, ctest-a-dire de l'élément le moins significatif en numération binaire normale vers l'élément le plus significatif. Sur la figure 2, les cases individuelles des memoires et des registres sont identifiées par une lettre représentant la mémoire ou le registre et le numéro de la colonne à laquelle elles appartiennent. Pour siaplifieri on suppose que le multiplicateur traite des nombres d'entrée de longueur fire de quatre éléments binaires chacun Ces nombres sont introduits dans les registres d'entrée À et B de façon que leurs éléments individuels à à e et dq à b4 occupent les cases du registre représentées dans la figure i(a). On peut voir que : 1) les deux nombres se lisent dans le même sens dans leurs registres respectifs ; 2) l'élément le moins significatif b1 d'un nombre occupe la même colonne que 1 élément le plus significatif a de l'autre nombre 3) les éléments de chaque nombre sont séparés les uns des autres par une case inutilisée. Ces dernières, qui se trouvent dans les colonnes de numéro pair sur la figure 1(a), sont amenées dans l'état binaire 0 pendant l'opération d'écriture, mais, de manière à faire la distinc tion entre ces cases et celles qui mémorisent un élément du nombre d'entrée pouvant prendre la valeur binaire 0, ces cases intermédiaires sont marquées "X" dans la figure l(a) et dans l'exemple de fonction nement de la figure l(b). Les circuits d'inscription des nombres dans les registres A et B sont représentés schématiquement pour des parties de ces registres sur la figure 2. On suppose que les chiffres des nombres d'entrée sont représentés par la présence ou l'absence (1 ou 0) d'un potentiel sur une série de lignes d'entrée 10 et 11, une pour chaque chiffre de chaque nombre. La figure 2 englobe les colonnes 6, 7 et 8 du multiplicateur ; on peut constater sur la figure 1(a) que la colonne 7 contient les chiffres a et a des nombres d'entrée, ces chiffres étant inscrits dans les mémoires B7 et A7 par les portes 12 commandées par un signal sur la ligne d'entrée 13. L'impulsion d'entrée est également appliquée directement aux éléments de mémoire des colonnes de numéro pair, de sorte que ces mémoires sont toutes dans l'état 0, L'opération de multiplication est effectuée par une série d'étapes successives après chacune desquelles un signal appliqué sur le fil 14 provoque le décalage du contenu des registres A et B, ce décalage étant dlune case pour les deux registres mais en sens opposé. Dans l'état initial des registres (figure la), seule la paire d'éléments binaires b et a se trouve dans une mQme colonne du multiplicateur. A la fin de la première phase de multiplication, le contenu du registre A est décalé d'une case vers la gauche tandis que le contenu du registre B est décalé d'une case vers la droite. Les éléments m et b sont maintenant sur la colonne 8 et les éléments > et 4 sur la colonne 6o La colonne 7 précédemment occupée ne contient plus d'entrées "actives". Ce processus est répété jusqu'à ce que l'opération de multiplication soit terminée. Chaque phase comprend plusieurs fois l'opération logique représentée par la figure 3. Cette opération est effectuée sur deux colonnes adjacentes du multi- plicateur, ctest-à-dire toute colonne pour laquelle les registres A et B contiennent des éléments binaires des nombres d'entrée et, à chaque fois, la colonne d'ordre immédiatement supérieur. Ainsi, dans l'état initial des registres correspondant à la figure l(a) toutes les colonnes de numéro impair contiennent des éléments des nombres d'entrée et toute colonne impaire correspond à la colonne rn de la figure 3, La colonne paire d'ordre immédiatement supérieur correspond à la colonne m + 1 Toutes les colonnes des registres prises par paires de cette façon sontconsîde,re,cs à chaque phase de la multiplication, l'opération logique de la figure 3 étant réalisée pour toutes les paires de colonnes. Il est à noter que le décalage des nombres contenus dans les registres A et B après chaque phase conduit au fait que la colonne m de la figure 3 est alternativement de numéro impair et de numéro pair. L'opération consiste à modifier les éléments binaires 4 4 + 1, ~ et 4 + 1 en fonction de la valeur des éléments d'entrée a. et b dans la colonne m. Cette opération logique elle-m & me est divisée en deux parties La première partie est une opération sur la colonne m qui conduit à un changement de l'élément Pm quand le résultat de l'opération a., b est ltélenent binaire 1. L'élément q de la mémoire Q n'est pas modifié par cette première partie. Une retenue peut être produite comme l'indique la colonne de droite du tableau correspondant à cette partie de l'opération sur la figure 3, et doit être transmise à la colonne suivante m + 1. La seconde partie est à nouveau une opération sur la valeur des éléments Pm + 1 et a + 1 mais, cette fois, étant donné qu'il n'y a pas de chiffres d'entrée dans les cases appropriées des registres A et 3, elle s'effectue en fonction de l'exis- tence ou de l'absence d'une retenue sur la colonne mo Les différentes possibilités de ces opérations sont indiquées par la figure 3 et ne seront donc pas détaillées dans cette description. En se reportant à la figure 2, on va maintenant décrire le circuit logique nécessaire pour réaliser la fonction précédemment décrite. Chaque colonne des mémoires est munie d'une porte ET 15 dont les entrées sont les sorties "1" des bistables individuels des registres A et B. La sortie de la porte 15 est ainsi le produit des chiffres binaires mémorisés par ces bistables. Cette sortie est appliquée, par une porte OU 16, comme entrée de complémentation du bistable formant l'étage de mémorisation correspondant de la mémoire de produit Po L'étage correspondant de la mémoire de retenue Q reçoit une entrée "1" à chaque fois que l'étage de la mémoire P situé sur la même colonne revient dans son état "0". Deux fils de remise au repos 17 et 18 appliquent des impulsions relativement retardées aux colonnes alternantes des mémoires de manière à replacer le bistable de la mémoire Q dans l'état "0" et, ce faisant, à produire une impulsion de retenue sur le fil de report 19 vers la colonne de mémoire d'ordre supérieur. Par l'examen du circuit logique de la figure 2, on peut constater qu'il réalise l'opération logique de la figure 30 La figure 1(b) représente les états successifs du multiplicateur pendant qu'il effectue l'opération 7 x 15 = 105, si on l'exprime en notation décimale. Le produit cherché est le nombre contenu dans la mémoire de produit P lorsqu'un nombre suffisant de phases a été effectué pour que chaque chiffre d'un nombre d'entrée ait partagé une colonne avec chaque chiffre de l'autre nombre et que la mémoire de retenue Q soit vide. La fin du processus peut ëtre détectée par des circuits répondant à ces deux critères, lorsqu'on désire éviter des phases inutiles de l'opération. En pratique, il est plus simple de faire en sorte que le processus se déroule selon un nombre de phases fixe correspondant aux exigences de la plus longue opération envisagée. Le nombre maximum de phases nécessaires pour multiplier deux nombres binaires de chacun n chiffres est 3n-2. Bien que le déroulement d'une opération de multiplication correspondant à l'exemple de la figure 1(b) implique 1 1exsmen consécutif des différentes paires de colonnes du multiplicateur à chaque phase du processus, il est à noter que ces opérations ne sont pas obligatoirement consécutives et peuvent en fait 8tre conduites simultanément. Cette possibilité est due au fait que les impulsions de retenue sont uniquement transmises d'une colonne de chaque paire à la colonne suivante et ne se propagent pas de paire en paire. La vitesse de fonctionnement du multiplicateur est ainsi beaucoup plus élevée que celle qui pourrait être envisagée par la seule considération de l'exemple donné. Il est bien évident que la description qui précède n'a été donnée qu'à titre d'exemple non limitatif et que de nombreuses variantes peuvent être envisagées sans sortir pour autant du cadre de l'invention. Rl :VENTDICÌO1NS 1. Multiplicateur de nombres. binaires comportant deux registres à décalage pour les deux nombres qui doivent entre multipliée, une mémoire de produit dans laquelle le produit des deux nombres est formé, et une mémoire de retenue pour la mise en mémoire temporaire des éléments binaires de retenue, les deux registres et les deux mémoires étant associés de telle façon que les cases d'une mémoire peuvent être considérées chacune comme occupant une colonne contenant aussi une case de l'autre mémoire et de chacun des deux registres, et des moyens d'introduire les deux nombres d'entrée dans les deux registres avec les éléments binaires de chaque nombre espacés dans leurs registres respectifs de façon que chaque élément soit séparé du suivant par une seule case vide du registre, les deux nombres se lisant dans le mme sens et l'élément le moins significatif d'un nombre se trouvant dans la neume colonne que l'élément le plus significatif de l'autre nombre ; et dans lequel la multiplication des deux nombres est effectuée en une série de phases successives après chacune desquelles les deux nombres sont décalés chacun d'une case et en sens opposé dans leurs registres respectifs. 2. Multiplicateur conforme à la revendication 1, dans lequel chacune desdites phases comprend la réalisation dune opération logique sur toutes les colonnes du rultiplicateur prises par paires constituées d'uns colonne dans laquelle les registres contiennent des éléments binaires des nombres d'entrée et la colonne d 'ordre immédiatement supérieur. 30 Multiplicateur conforme à la revendication 2, dans lequel lesdites phases successives se continuent jusqu'à ce que tous les éléments binaires des deux nombres aient étS multipliés et que la mémoire de retenue soit vide.