Brevet FR2683340A1 — publié le 19930507

CIRCUIT ÉLÉVATEUR AU CARRÉ DE NOMBRES BINAIRES La présente invention conoemne un circuit élévateur au carré d'un nombre binaire de N bits et en particulier un tel circuit à table de carrés stockée dans une mémoire non volatile (ROM). Une façon classique de réaliser un élévateur d'un nombre binaire X au carré est de multiplier X par lui-même grâce à un circuit multiplieur binaire Un circuit multiplieur binaire de nombres de 8 bits comprend environ 1500 transistors dans des technologies et architectures courantes. Une autre façon de réaliser un élévateur au carré d'un nombre binaire X de N bits est de stocker dans une mémoire ROM tous les carrés possibles d'un nombre de N bits et de sélection- ner l'un de oes carrés en appliquant le nombre X sur les lignes d'adresses de la mémoire ROM Si le nombre X est de N bits, il faudra stocker dans la mémoire ROM 2 N nombres de 2 N bits (le carré d'un nombre de N bits est un nombre comprenant au maximum 2 N bits) En conséquenoe, il faut une mémoire ROM de 2 n 2 n bits Une mémoire ROM contenant tous les carrés des nombres de 8 bits comprendra environ 1900 transistors, mais ces transistors sont disposés de façon très régulière, ce qui permet de conce- voir facilement la mémoire ROM pour qu'elle occupe, pour n la même technologie), sinon moins. Un objet de la présente invention est de réaliser un élévateur au carré à mémoire ROM de taille au moins quatre fois inférieure à la taille de la méêmoire ROM d'un élévateur au carré classique équivalent. Cet objet est atteint grâce à un circuit élévateur au carré d'un nombre binaire X de N bits de poids croissant de O à n-1, comprenant une table des carrés de nombres binaires p. Chaque nombre p est constitué des seuls bits de poids 1 à n-2 du nombre X, et le circuit comprend en outre: un additionneur de nombres de 2 n-3 bits recevant sur une première entrée un nombre constitué par le bit de poids n-i du nombre X, juxtaposé à gauche du carré p 2 fourni par la table; un premier moyen d'aiguillage reoevant en entrée le nombre p et le délivrant aux n-2 lignes de poids faible d'une deuxième entrée de l'addition- neur si le bit de poids O du nombre X est à 1; un deuxième moyen d'aiguillage recevant en entrée le nombre p et le déli- vrant aux n-2 lignes de poids fort de la deuxième entrée si le bit de poids n-l du nombre X est à 1; et un troisième moyen d'aiguillage délivrant un 1 à la ligne restante de la deuxième entrée si les bits de poids O et n-l du nombre X sont tous les deux à 1 Le carré X 2 du nombre X est constitué par la sortie de l'additionneur, à laquelle sont juxtaposés à droite un bit à O et le bit de poids O du nombre X. Selon un mode de réalisation de la présente invention, la table est une mémoire ne stockant que les 2 (n-2)-2 bits de poids fort du nombre p 2, ce nombre p 2 étant constitué par la sortie de la mémoire, à laquelle sont juxtaposés à droite un bit à O et le bit de poids 1 du nombre X. Selon un mode de réalisation de la présente invention, les premiers moyens d'aiguillage comprennent n-2 portes ET dont des premières entrées reçoivent le bit de poids zéro du nombre X et dont des deuxièmes entrées reçoivent chacune l'un des bits du nombre p. Selon un mode de réalisation de la présente invention, les deuxièmes moyens d'aiguillage comprennent n-2 portes ET dont les premières entrées reçoivent le bit de poids n-1 du nombre X et dont les deuxièmes entrées reçoivent chacune l'un des bits du nombre p. Selon un mode de réalisation de la présente invention, les troisièmes moyens d'aiguillage comprennent une porte ET recevant en entrée les bits de poids 0 et n-i du nombre X. Ces objets, caractéristiques et avantages ainsi que d'autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite en relation avec les figures jointes parmi lesquelles: la figure 1 illustre symboliquement un procédé de calcul utilisé par un circuit élévateur au carré selon la présente invention; et la figure 2 illustre un mode de réalisation d'un circuit élévateur au carré selon la présente invention. Supposons que l'on veuille élever au carré un nombre X de N bits, X = Xn 1 2 n-1 + + x 1 21 + x O 20, o xo xn-l désignent respectivement les bits de poids O à n-i du nombre X. Pour élever ce nombre au carré, la présente invention se base sur le procédé décrit ci-dessous. Le nombre X peut être écrit sous la forme X = 2 n-1 xnl + 2 p + 20, ( 1) o p = 2 n-3 xn-2 + + 21 x 2 + 20 xi. Ainsi, en élevant l'équation ( 1) au carré et en développant, en tenant compte de ce que xi 2 =xi puisque xi= 1 ou 0, on obtient: x 2 = ( 2 n-1 Xn_ 1 + 2 p + xo)2 = 2 n+l xnl p + 4 xo O p + 2 N xo Xnl + 4 p 2 + 22 (n1) xn_ 1 + xo ( 2) = T 1 + T 2 + T 3 + T 4 + T 5 + T 6. La figure 1 illustre symboliquement cette équation ( 2) Divers nombres binaires y sont illustrés sous forme de rec- tangles divisés en cases correspondant à des bits Chacune des cases des rectangles est disposée dans une colonne qui corres- pond au poids du bit de la case Dans la figure, on a numéroté les colonnes O à 2 n-l, de droite à gauche, les bits de poids le plus faible correspondant à la colonne la plus à droite Un nombre binaire quelconque exprimé sous la forme 2 iz, o z est une valeur binaire de nz bits, est représenté par un rectangle de nz cases dont la case de poids le plus faible est dans la colonne i Les cases du rectangle sont occupées par les bits de la valeur z, ce qui est indiqué en écrivant cette valeur dans le rectangle Les colonnes non occupées par un rectangle correspon- dent à des bits nuls. Un rectangle X représente 1 ' expression ( 1) Les bits xo à xn_ 1 du nombre X sont ranges dans les colonnes O à n-1. Le nombre p est formé par les bits xl à xn_ 2 du nombre X. Les six rectangles suivants représentent chacun des termes T 1 à T 6 du membre de droite de l'équation ( 2) et le dernier rectangle représente le résultat X 2. Un rectangle T 1 représente le terme T 1 = 2 n+l xn_ 1 p de l'équation ( 2) Ce rectangle, comme cela est représenté, occupe les n-2 colonnes n+l à 2 n-2 La valeur xn_ 1 p comprend autant de bits que le nombre p car elle est obtenue par un simple ET logique entre chacun des bits du nombre p et le bit xn_ 1. Un rectangle T 2 représente le terme T 2 = 4 x O p = 22 xo p de l'équation ( 2) Comme cela est représenté, le rectangle T 2 occupe les n-2 colonnes 2 à n-1. Un rectangle T 3 représente le terme T 3 = 2 N xo Xn_ 1. Comme cela est représenté, le rectangle T 3 occupe la colonne n (xo xn_ 1 correspond à un bit). On constate en observant les rectangles T 1, T 2 et T 3 que la somme Tl+T 2 +T 3 est en fait égale à un nombre formé par la juxtaposition des valeurs Xn_ 1 p, xo Xn_ 1 et xo p suivie de deux O Par consequent, il n'est pas nécessaire de prévoir un additionneur binaire pour somnmer les termes T 1 à T 3, car, maté- riellement, une juxtaposition correspondante des lignes véhicu- lant les bits des valeurs ci-dessus suffit pour former la somme. Un rectangle T 4 représente le terme T 4 = 4 p 2 = 22 p 2 de l'équation ( 2) Comme cela est représenté, le rectangle T 4 occupe les 2 (n-2) colonnes 2 à 2 n-3. Un rectangle T 5 représente le terme T 5 = 22 (n-l) xn_ 1. Ce rectangle T 5 occupe la colonne 2 n-2. Enfin, un rectangle T 6 représente le terme T 6 = xo et occupe la colonne O On constate de nouveau que la somme des termes T 4, T 5 et T 6 correspond à une simple juxtaposition des valeurs Xnl, p 2, O et xo, ce qui évite l'emploi d'un addi- tionneur binaire. En outre, cette figure nous permet de constater que quel que soit le nombre X, le bit de poids 1 du nombre X 2 (représenté par le rectangle X 2) est toujours nul et que le bit de poids O est toujours égal au bit xo de poids O du nombre X. Ainsi, il n'est pas nécessaire de stocker les bits de poids O et 1 du nombre p 2 puisqu'ils sont respectivement égaux au bit xi du nombre p (qui est le bit de poids 1 du nombre X) et à O Le nombre p 2 peut donc être obtenu, conmme cela apparaît dans le rectangle T 4, par la juxtaposition de O et xl à droite de ses 2 (n-2)-2 bits de poids fort. Finalement, la somme des six termes T 1 à T 6 se réduit à une seule somme des nombres correspondant à la juxtaposition des rectangles T 1 à T 3 et du nombre correspondant à la juxtapo- sition des rectangles T 4 et T 5 A cette somme est ensuite juxta- posée à droite un bit nul et le bit x O (T 6) pour obtenir le nombre X 2. Il résulte de cette analyse qu'au lieu de stocker 2 n carrés de X, il suffit de stocker 2 n-2 carrés de p Ainsi, le nombre de valeurs à mémoriser est divisé par 4 De plus, on ne stocke que les 2 (n-2)-2 = 2 n-6 bits de poids fort des nombres p 2 au lieu des 2 N bits des nombres X 2 Le nombre total de bits de la mémoire nécessaire est donc de 2 n- 2 ( 2 n-6) = 2 n-1 (n-3), ce qui entraîne un gain de place de 4 n/(n-3) par rapport au circuit classique Ce gain tend vers 4 lorsque N tend vers l'infini Pour des nombres X de 8 bits, ce gain est de 6,4. Bien entendu, selon la présente invention, il faut prévoir en plus de la mémoire des circuits supplémentaires, à savoir, un additionneur 2 n-3 bits pour sommer les valeurs (Ti+T 2 +T 3) et (T 4 +T 5), et des portes logiques permettant de cal- culer les valeurs xn_ 1 p, xo p et xo xn_ 1 Mais ces circuits additionnels occupent peu de place par rapport à la place gagnée par la réduction de la mémoire. La figure 2 illustre un mode de réalisation de circuit élévateur au carré selon la présente invention Les bits xo à xnl d'un nombre X dont on veut calculer le carré sont intro- duits dans le circuit sur des lignes xo à xnl Les n-2 lignes xl à xn_ 2 qui véhiculent les bits du nombre p sont reliées aux lignes d'adresses d'une mémoire ROM 20 La mémoire ROM présente sur sa sortie les 2 n-6 bits de poids fort (p 2)2 à (p 2)2 n_ 5 du nombre p 2 Les lignes de poids faible restantes (p 2)1 et (p 2)o sont reliées respectivement à O et à la ligne xl. Le circuit comprend un additionneur ADD de nombres de 2 n-3 bits constitué de 2 n-3 additionneurs élémentaires ADD 2 à ADD 2 n_ 2 fournissant respectivement les bits de poids 2 à 2 n-2 du nombre X 2 Ces additionneurs élémentaires comprennent chacun deux entrées de bit a et b et une sortie de retenue c pour transmettre une retenue à un additionneur élémentaire de poids immédiatement supérieur La sortie de retenue de 1 'additionneur ADD 2 n_ 2 fournit le bit de poids 2 n-l du nombre X 2. Les bits (p 2)0 à (p 2)2 n_ 5 sont fournis aux entrées b des additionneurs ADD 2 à ADD 2 n_ 3 L'entrée b de l'additionneur ADD 2 n_ 2 est reliée à la ligne Xn_ 1 Les bits de poids O et 1 du nombre x 2 sont fournis respectivement par la ligne xo et une ligne reliée à 0. L'entrée a des additionneurs ADD 2 à ADD 2 n_ 2 est reliée à la sortie d'une porte ET & 2 a & 2 n-2 Une première entrée des portes & 2 à &n-1 est reliée à la ligne xo et les bits xl à xn_ 2 du nombre p sont respectivement fournis à une deuxième entrée des portes & 2 à &n-1 Ainsi, ces portes four- nissent la valeur xo p à l'additionneur ADD. Une première entrée des portes &n+l à & 2 n-2 est reliée à la ligne Xnl et les bits xl à xn_ 2 du nombre p sont respectivement fournis à une deuxième entrée de ces por- tes Ainsi, les portes &n+ 1 à & 2 n-2 fournissent la valeur xnl p à l'additionneur ADD. Les deux entrées de la porte &n sont reliées respec- tivement à la ligne xo et à la ligne Xn_ 1 Ainsi, cette porte fournit à l'additionneur ADD le nombre xo xn_ 1. En observant la figure 2, on constate que la disposi- tion des portes ET et des additionneurs élémentaires est tres régulière, ce qui permet de les réaliser facilement sur une surface réduite. La présente invention est susceptible de nombreuses variantes et modifications qui apparaîtront à l'homme de l'art, notamment, les portes & 2 à &n-l peuvent être remplacées par un multiplexeur piloté par la ligne xo et recevant sur une entrée un nombre binaire nul et sur l'autre entrée le nombre p De même, les portes &n+l à & 2 n-2 peuvent être remplacées par un multiplexeur identique piloté par la ligne xn_ 1 La mémoire ROM peut être remplacée par tout dispositif équivalent, tel qu'un circuit logique programmable (PLA) dont les bits de sortie correspondent à des équations préprogrammées sur les bits présents en entrée (sur les lignes d'adresses) L'additionneur ADD 2 peut être remplacé par une porte ET recevant le bit xl et le complémentaire du bit xo car (X 2)2 =xl xo. REVENDICATIONS 1 Circuit élévateur au carré d'un nombre binaire X de n bits de poids croissant de O à n-l, comprenant une table ( 20) des carrés de nombres binaires p; caractérisé en ce que chaque nombre p est constitué des seuls bits de poids 1 à n-2 du nombre X, et en ce que le circuit comprend: un additionneur de nombres de 2 n-3 bits (ADD) rece- vant sur une première entrée un nombre constitué par le bit de poids n-1 du nombre X, juxtaposé à gauche du carré p 2 fourni par la table; un premier moyen d'aiguillage (& 2 &n-l) rece- vant en entrée le nombre p et le délivrant aux n-2 lignes de poids faible d'une deuxième entrée de l'additionneur si le bit de poids O du nombre X est à 1; un deuxième moyen d'aiguillage (&n+l & 2 n-2) recevant en entrée le nombre p et le délivrant aux n-2 lignes de poids fort de la deuxième entrée si le bit de poids n-1 du nombre X est à 1; un troisième moyen d'aiguillage (&n) délivrant un 1 à la ligne restante de la deuxième entrée si les bits de poids O et n-1 du nombre X sont tousles deux à 1; le carré X 2 du nombre X étant constitué par la sortie de 1 'addi- tionneur, à laquelle sont juxtaposés à droite un bit à O et le bit de poids O du nombre X. 2 Circuit selon la revendication 1, caractérisé en ce que la table est une mémoire ( 20) ne stockant que les 2 (n-2)-2 bits de poids fort du nombre p 2, ce nombre p 2 étant constitué par la sortie de la mémoire, à laquelle sont juxtaposés à droite un bit à O et le bit de poids 1 du nombre X. 3 Circuit selon la revendication 1, caractérisé en ce que les premiers moyens d'aiguillage comprennent n-2 portes ET dont des premières entrées reçoivent le bit de poids zéro du nombre X et dont des deuxièmes entrées reçoivent chacune 1 'un des bits du nombre p. 4 Circuit selon la revendication 1, caractérisé en ce que les deuxièmes moyens d'aiguillage comprennent n-2 portes ET dont les premières entrées reçoivent le bit de poids n-l du nombre X et dont les deuxièmes entrées reçoivent chacune l'un5 des bits du nombre p. Circuit selon la revendication 1, caractérisé en ce que les troisièmes moyens d'aiguillage comprennent une porte ET recevant en entrée les bits de poids O et n-1 du nombre X.