FR2811168A1 - Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee - Google Patents
Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee Download PDFInfo
- Publication number
- FR2811168A1 FR2811168A1 FR0008547A FR0008547A FR2811168A1 FR 2811168 A1 FR2811168 A1 FR 2811168A1 FR 0008547 A FR0008547 A FR 0008547A FR 0008547 A FR0008547 A FR 0008547A FR 2811168 A1 FR2811168 A1 FR 2811168A1
- Authority
- FR
- France
- Prior art keywords
- bit
- rank
- binary representation
- calculation
- bits
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/02—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word
- H03M7/12—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word having two radices, e.g. binary-coded-decimal code
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
- G06F7/523—Multiplying only
- G06F7/533—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even
- G06F7/5332—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by skipping over strings of zeroes or ones, e.g. using the Booth Algorithm
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Complex Calculations (AREA)
- Executing Machine-Instructions (AREA)
Abstract
Un procédé de conversion dans une représentation binaire signée (r'm ,..., r'0 ) d'un nombre r est basé sur un traitement gauche vers droite des bits de la représentation binaire (rm-1 ,..., r0 ) et permet d'obtenir une représentation équivalente de la représentation dite de Reitwiesner. L'utilisation d'un tel procédé de conversion avec des traitements arithmétiques de type gauche droite permettent d'améliorer les performances de calcul et facilite leur réalisation matérielle.
Description
PROCEDE DE CONVERSION DE LA REPRESENTATION BINAIRE D'UN
NOMBRE DANS UNE REPRESENTATION BINAIRE SIGNEE
La présente invention concerne un procédé d'obtention d'une représentation binaire signée d'un nombre à
partir de sa représentation binaire.
Les techniques de calcul arithmétique rapide utilisent depuis longtemps la représentation binaire signée, parce qu'elle permet de calculer de manière très
efficace des additions, multiplications ou divisions.
De nombreux circuits intégrés comprennent un dispositif de conversion d'un nombre en code binaire signé à partir de sa représentation binaire et des dispositifs de calcul arithmétique pour effectuer des opérations avec cet opérande en représentation binaire signée. En général, un dispositif de conversion inverse est prévu,
pour fournir le résultat sous la forme binaire.
On rappelle que dans la représentation binaire signée, un nombre est exprimé sur m chiffres de valeurs "0", "1" ou "-1". Plusieurs représentations binaires signées d'un même nombre existent. Par exemple, le nombre 5
peut s'écrire comme (1 1 -1), soit lx22 + lx21 -lx2 .
Mais il peut aussi s'écrire (1 0 1).
Parmi les représentations binaires signées possibles, il en existe une de remarquable, appelée représentation de Reitwiesner. Cette représentation a comme caractéristiques particulièrement intéressantes, d'être unique, creuse, et de présenter le plus petit poids de Hamming. Si on note r= (rm1,.., ro) la représentation binaire du nombre r, la représentation binaire signée de
2 2811168
Reitwiesner, que l'on note r=(r'm, r'm,..., r'2, r'1, r'0), comprend 1 chiffre supplémentaire Dire que cette représentation est creuse signifie qu'elle vérifie que la multiplication de deux chiffres adjacents est nulle, ce qui s'écrit:
r'i.r'i_,=0, Vis{O,..., m}.
Le poids de Hamming exprime quant à lui le nombre de
chiffres non nuls dans la représentation considérée.
Avoir un poids de Hamming minimum signifie donc un nombre optimum, maximum, de chiffres à "0". Or, moins il y a de chiffres "1" ou -1" dans la représentation, moins il y a de calculs à réellement effectuer, d'o
une amélioration en termes de rapidité de calculs.
C'est donc une propriété particulièrement intéressante de la représentation de Reitwiesner en matière de
calcul arithmétique rapide.
L'algorithme qui permet d'obtenir cette représentation binaire signée remarquable à partir de la représentation binaire (r-1,..., ro) d'un nombre r, peut être décrit comme suit:
-On utilise une variable de calcul c, en binaire.
-On initialise à "0" le bit co de rang 0 de cette
variable c.
-On ajoute à la représentation binaire (rm_,..., ro) du nombre r, un bit de rang m+1 et un bit de rang m, tous deux initialisés à "0": rm+1=0; rm=0 -puis pour i égal 0 jusqu'à i égal m, on calcule: cj+1= L (ci+ri+ri+) /2J r'i= ci+ri-2ci+l o LtJ signifie la valeur par défaut, c'est à dire, la valeur entière immédiatement inférieure au nombre t. En pratique, comme la somme arithmétique des bits ci+ri+ri>+ se code sur deux bits au maximum en binaire, le bit ci+,
3 2811168
est obtenu en décalant d'une position vers la droite de
cette somme.
On peut voir que dans cet algorithme de Reitwiesner, les bits ri de la représentation binaire du nombre r sont traités de droite à gauche, pour obtenir chacun des chiffres r'i de la représentation binaire signée,
depuis i égal 0 jusqu'à i égal m.
Différents travaux ont pu montrer qu'il n'existait pas d'algorithme dans lequel les bits seraient traités de gauche à droite et par lequel on obtiendrait la
représentation binaire signée de Reitwiesner.
Or, dans nombre d'applications, les algorithmes de calcul arithmétique rapide appliqués à un opérande r, traitent les chiffres r'i de la représentation binaire signée de cet opérande de gauche à droite. Ces algorithmes se révèlent en effet, dans certains cas, plus efficaces tant sur le plan du temps de calcul que
sur le plan matériel (moins de registres nécessaires).
Si on prend l'exemple du calcul de l'exponentiation, un algorithme d'exponentiation modulaire d'un nombre a par un exposant r basé sur le traitement droite vers gauche (ARL) peut être comme suit: -On applique en entrées de l'algorithme un nombre
a, et la représentation binaire signée (r'm, r'm-1,...
r'2, r'l, r'o).
-On initialise à 1 l'accumulateur qui contient le
résultat M, soit M=1.
-On initialise un registre temporaire qui contient une variable de calcul S avec le nombre c auquel est
appliqué l'exponentiation.
-On réalise pour i égal 0 jusqu'à i égal m-1 la boucle suivante: -si r'i=l, on multiplie le contenu M de l'accumulateur par la variable S, et on charge le
4 2811168
résultat dans l'accumulateur, ce qui s'écrit: M=M.S -si r'i=-l, on multiplie le contenu M de l'accumulateur par l'inverse de la variable S, et on charge le résultat dans l'accumulateur, ce qui
s'écrit M=M.S-'.
Un algorithme d'exponentiation modulaire du nombre a par l'exposant r basé sur un traitement gauche vers droite (ALR) de l'exposant est le suivant: -On applique en entrées le nombre a, et la représentation binaire signée (r'm, r'm-1,..., r'2, r',
r'0)de l'exposant r.
-On initialise à 1 le contenu M de
l'accumulateur: M=l.
-Pour i égal m à i égal 0: -On effectue la multiplication du contenu de l'accumulateur par lui-même et on charge l'accumulateur avec le résultat, ce qui s'écrit: M=M2 puis, -si r'i=l, on multiplie le contenu de l'accumulateur par a et on charge le résultat dans l'accumulateur: M=M.a ou -si r'i=-l, on multiplie le contenu de l'accumulateur par l'inverse de a et on charge
le résultat dans l'accumulateur: M=M.-C'.
L'algorithme droite vers gauche ARL nécessite donc au moins un registre supplémentaire, pour la variable S, que l'algorithme gauche vers droite ALR. En outre, S étant variable, il faut calculer S-1 à chaque fois que la condition associée est réalisée dans l'algorithme droite vers gauche. Dans l'algorithme gauche vers droite, a étant déterminé (fixe), son inverse a-' peut
n'être calculée qu'une seule fois et mémorisé.
2811168
Dans l'invention, on a cherché à cumuler les avantages du traitement gauche vers droite à la fois dans le procédé de conversion d'un opérande et dans le
traitement arithmétique utilisant cet opérande.
Ainsi, dans l'invention, on a recherché une représentation binaire signée équivalente de la représentation de Reitwiesner, c'est à dire une représentation qui présente le même poids de Hamming pour une même longueur m (nombre de chiffres dans la
représentation).
L'invention a donc pour objet un procédé de conversion d'une représentation binaire d'un nombre dans une représentation binaire signée comprenant un nombre optimum, c'est à dire maximum, de zéro (poids de Hamming minimal), et dans lequel les bits sont traités
de la gauche vers la droite.
L'invention a aussi pour objet un dispositif de conversion permettant l'obtention d'une représentation
binaire signée correspondante.
Telle que caractérisée, l'invention concerne donc un procédé d'obtention d'une représentation binaire signée sur m+l chiffres (r'm,..., r'0) d'un nombre à partir
de sa représentation binaire sur m bits (rm-:,..., r0).
Selon l'invention, ce procédé consiste: -A ajouter dans la représentation binaire du
nombre r à convertir un bit de rang m, un bit de rang -
1 et un bit de rang -2 et à initialiser lesdits bits à la valeur 0, -A prendre au moins une variable de calcul et à initialiser à 0 un bit de rang m de cette variable, et -A effectuer m+1 itérations d'une boucle de conversion, pour i égal m jusqu'à i égal 0, la boucle de conversion comprenant les opérations suivantes:
6 2811168
-Appliquer en entrées de premiers moyens de calcul le bit de rang i de la variable de calcul b, et les bits de rangs i-1 et i-2 de la représentation binaire du nombre r à convertir, lesdits premiers moyens fournissant en sortie le bit de rang i-1 de la variable de calcul, en effectuant une opération arithmétique équivalente à la valeur par défaut de la somme arithmétique divisée par deux des bits appliqués en entrées, - Appliquer en entrées de deuxièmes moyens de calcul, les bits de rang i et i-1 de la variable de calcul b, et le bit de rang i de la représentation binaire du nombre à convertir r, lesdits moyens de calcul effectuant une opération arithmétique équivalente à la multiplication par moins deux du bit de rang i de la variable de calcul b, et la somme arithmétique du résultat précédent avec les deux autres bits appliqués en entrée, pour fournir en sortie le chiffre de rang
i de la représentation binaire signée.
D'autres caractéristiques et avantages de l'invention
sont détaillés dans la description suivante, faite à
titre indicatif et non limitatif de l'invention et en référence aux dessins annexés dans lesquels: -la figure 1 représente un circuit intégré comprenant un tel dispositif de conversion et un dispositif de
calcul arithmétique d'une exponentiation modulaire.
-la figure 2 représente un schéma-bloc d'un dispositif de conversion selon l'invention, -la figure 3 représente une table de correspondance utilisable pour effectuer une conversion selon le procédé de l'invention; -la figure 4 représente un exemple de réalisation d'un dispositif de conversion utilisant une telle table; et
7 2811168
-la figure 5 représente un autre exemple de réalisation d'un dispositif de conversion selon l'invention,
utilisant des opérateurs booléens.
Sur la figure 1, on a représenté un circuit intégré du type à microprocesseur gP et comprenant une mémoire MEM
et un générateur de nombre aléatoire GEN.
Ce circuit intégré comprend en outre un dispositif 1 de calcul d'exponentiation d'un nombre a par un exposant r. Dans l'exemple, le nombre a est un nombre fixe contenu en mémoire MEM et l'exposant r est un nombre fourni en binaire (rm-1,...,ro) par le générateur de
nombre aléatoire.
Un dispositif de conversion 2 en binaire signé est prévu dans le circuit intégré, pour convertir le nombre r appliqué comme exposant dans le dispositif 1 de calcul. On obtient en sortie de ce dispositif de conversion, la représentation binaire signée (r'm,...,r'o) selon l'invention, appliquée en entrée du dispositif 1 de calcul. Cette représentation binaire signée est telle qu'elle présente un poids de Hamming optimum, à
l'instar de la représentation dite de Reitwiesner.
Le dispositif 1 de calcul représenté sur la figure 1 permet d'appliquer l'algorithme d'exponentiation
modulaire gauche vers droite ALR précédemment décrit.
Dans cet exemple, le dispositif de calcul comprend un accumulateur 10 pour les résultats intermédiaires et le résultat final de l'exponentiation et trois registres: un registre 11 pour l'exposant, un registre 12 pour le nombre a, et un registre 13 pour son inverse a-l. En réalité, le registre 11 pour l'exposant est un double registre: car chaque chiffre "0", "1" "-1" en binaire
signé est habituellement codée sur au moins deux bits.
8 2811168
Dans un exemple, ce code comprend deux bits: un bit pour le signe et un bit pour la valeur absolue du chiffre. Dans cet exemple, on a alors: "0" = (X,0); "1"=(0,1); "-1"=(1,1) o X signifie que le bit peut valoir indifféremment 0 ou 1. Dans l'exemple de la
figure 1, X vaut 0.
Le dispositif de calcul 1 comprend encore deux multiplexeurs 20 et 21, un multiplieur 22. Un circuit de commande 23 et un commutateur 24 fournissent les
signaux de commande des multiplexeurs.
Le circuit de commande 23 reçoit le bit de valeur absolue r'1L du chiffre r'i de rang i de l'exposant r (et un signal de séquencement Ck). Si ce bit vaut "l",il active (coml) le commutateur 24, pour appliquer le bit r'iH de signe du chiffre r'i de l'exposant en entrée de commande du multiplexeur 20. Selon que le bit r'iH vaut "0" ou "1", le multiplexeur 20 transmet
alors a ou x-' en entrée du deuxième multiplexeur 21.
Ce deuxième multiplexeur 21 reçoit sur une autre entrée, le contenu M de l'accumulateur 10. Il est commandé par une sortie Com2 du circuit de commande 23, pour appliquer sur une entrée du multiplieur 22, soit la sortie du premier multiplexeur 20, c'est à dire a ou
c-f, soit le contenu M de l'accumulateur.
Le résultat en sortie du multiplieur est chargé dans l'accumulateur. Le circuit de commande 23 est tel que dans chaque itération de la boucle de calcul d'un bit de résultat de l'exponentiation modulaire, il commande d'abord la commutation de l'entrée M en sortie du multiplexeur 21, pour calculer M.M dans le multiplieur, puis, si la valeur absolue r'iL du chiffre r'i de l'exposant vaut 1, pour commander la commutation de la sortie du premier multiplexeur 20 (a ou a-l) en sortie du multiplexeur 21 Le dispositif de calcul permet ainsi le calcul de l'exponentiation de a par r, par un traitement gauche
vers droite.
L'association d'un dispositif de conversion gauche droite et d'un dispositif de traitement arithmétique traitant de gauche à droite le résultat de la conversion, permet d'effectuer tous ces traitements en temps réel. En effet, dès que le chiffre r'i est calculé et disponible en sortie du dispositif 2 de conversion, il est immédiatement utilisé dans le
dispositif 1 de traitement arithmétique.
Avec un dispositif de conversion traitant les bits de droite à gauche (Reitwiesner), on ne peut utiliser la représentation binaire signée qu'une fois qu'elle est entièrement calculée, puisque le dernier chiffre converti r'm est le premier utilisé dans le dispositif de traitement arithmétique traitant les chiffres de
gauche à droite.
L'homogénéité des traitements de gauche à droite des bits dans le dispositif de conversion selon l'invention et des chiffres dans le dispositif de calcul, permet donc de simplifier la réalisation matérielle de ces dispositifs, en économisant notamment des registres et d'améliorer les performances en termes de vitesse de
calcul.
Le dispositif de conversion ne s'applique pas qu'à un dispositif de calcul d'une exponentiation. Il s'applique aussi bien au calcul de la multiplication d'un nombre a par un nombre r en représentation binaire signée, ou à la multiplication scalaire d'un point par le nombre r en représentation binaire signée. Dans ce dernier cas, une application particulièrement intéressante de l'invention concerne le cas o le point
est pris sur une courbe elliptique.
2811168
La figure 2 représente un schéma bloc d'un dispositif de conversion 2 illustrant un procédé de conversion
selon l'invention.
Le procédé d'obtention d'une représentation binaire signée selon l'invention, utilisant un traitement gauche vers droite est le suivant: On ajoute dans un registre R1 contenant la représentation binaire du nombre r, un bit rm de rang m, un bit r-1 de rang -1 et un bit r2 de rang -2 et on
initialise ces trois bits à la valeur 0.
-On prend une variable de calcul b dans un registre R2, et on initialise à 0 le bit bm de rang m de
cette variable.
-On effectue m+1 itérations d'une boucle de conversion, depuis i égal m jusqu'à i égal 0, la boucle de conversion comprenant les opérations suivantes: -Application en entrées el, e2, e3 de premiers moyens de calcul 30 du bit bi et des bits ri-1, ri-2, pour calculer la somme arithmétique divisée par deux de ces bits et fournir comme bit de sortie bi-, le bit correspondant à la valeur par défaut du résultat, ce qui s'écrit:
bi-,= L (bi+ri-, +ri-2)/2J.
-Application en entrées el', e2', e3' de deuxièmes moyens de calcul 31, des bits bi, bi-, de la variable de calcul b, et du bit ri de rang i de la représentation binaire du nombre r, pour calculer la somme arithmétique de moins deux fois le bit bi avec les deux autres bits appliqués en entrées, et fournir en sortie le chiffre r'i de la représentation binaire signée, ce qui s'écrit:
r'i=-2.bi + bi-, + ri.
il 2811168 Les premiers et deuxièmes moyens de calcul peuvent effectuer l'opération arithmétique indiquée, ou une
opération arithmétique équivalente.
Ces calculs sont effectués au moyen d'une variable b.
Mais il est possible de mettre en oeuvre l'invention en
utilisant plusieurs variables.
Comme représenté sur la figure 2, un dispositif de conversion permettant de mettre en ouvre ce procédé comprend le registre Ri pour contenir la représentation binaire signée du nombre r, y compris les bits rm, r-, r-2 ajoutés à cette représentation. Ce registre est du type à décalage vers la gauche, correspondant au sens
de traitement des bits de gauche (i=m), à droite (i=0).
Les sorties de rang m, m-1 et m-2 du registre Rl sont ainsi respectivement appliquées sur l'entrée e'3 des deuxièmes moyens de calcul 31, et sur les entrées e2 et e3 des premiers moyens de calcul 30. A la fin de chaque itération, le registre Rl est décalé d'une position à gauche, en sorte que les sorties de rang m, m-1 et m-2 fournissent à chaque itération les bits de rang i, i-1
et i-2 correspondants.
Le dispositif de conversion comprend un autre registre R2 pour la variable de calcul b, également du type à décalage vers la gauche. Dans l'exemple, ce registre
comprend pour chaque itération, le bit bi et le bit bi-1.
Comme le bit bi_ est établi à partir du bit bi, les premiers moyens de calcul sont activés en premier, pour charger dans le registre R2 la nouvelle valeur bi-, à utiliser dans l'itération en cours, dans les deuxièmes
moyens de calcul.
A la fin de l'itération, le registre R2 est décalé d'une position vers la gauche, pour l'itération suivante.
12 2811168
Dans l'invention, on a pu établir une table de correspondance correspondant au procédé de conversion qui vient d'être exposé. Cette table de correspondance représentée sur la figure 3 permet de simplifier la conversion selon l'invention. En effet, elle donne directement le résultat en sortie, en fonction des entrées. En outre le registre R2 de la figure 2 peut alors être réalisé sous forme d'un simple latch, pour
contenir, pour l'itération i en cours, le bit bi.
Pour obtenir cette table, on a déterminé la valeur du bit bi-1 pour chaque triplet possible (el, e2, e3)=(bi, ri-1, ri-2), et la valeur du chiffre r'i pour chaque
triplet possible en entrées (el', e2', e3')=(bi, ri, bi-
i), à partir de l'algorithme de conversion selon l'invention exposé précédemment en relation avec la
figure 2.
On a ainsi pu montrer que l'on pouvait déterminer la valeur du bit bi-1 et du chiffre r'i, à partir du quadruplet (bi., r ri-1 et ri-2), pour chacune des
valeurs possibles de ce dernier.
Avec cette table de conversion, seul le bit bi de la variable b est utilisé comme entrée pour l'itération en cours. Le bit bi- fourni en sortie sert pour l'itération suivante. Ainsi, avec une telle table de correspondance le registre R2 peut se réduire à un simple latch, dont la nouvelle valeur est chargée à la fin de chaque
itération, par le bit bi-1 fourni en sortie par la table.
Cette nouvelle valeur devient celle du bit bi dans
l'itération suivante.
Un exemple de réalisation pratique d'un dispositif de conversion selon l'invention utilisant une telle table de conversion est représenté sur la figure 4. Il comprend une mémoire adressable par son contenu, notée CAM. La table de correspondance de la figure 3 est
13 2811168
programmée dans cette mémoire en sorte qu'en appliquant sur les bits d'adresse A0, Al, A2, A3 de cette mémoire, les bits bi., ri, ri-1 et ri-2, elle fournit en sortie le
bit bi-1 et le chiffre r'i correspondants.
A la fin de chaque itération, le bit bi-1 est chargé dans le registre R2. Ce bit devient le bit bi pour
l'itération suivante de la boucle.
Le chiffre r'i est chargé dans un registre R3, qui comprend en pratique un premier registre R3H, pour contenir le bit de signe r'i, de chaque chiffre de la représentation binaire signée et un deuxième registre
R3L, pour contenir sa valeur absolue r'iL-
Un autre exemple de réalisation d'un dispositif de conversion selon l'invention est représenté sur la figure 5. Dans cet exemple, le dispositif de conversion est basé sur des opérateurs booléens. Là encore, le registre R2 peut être un simple latch rechargé par le
bit bi-1 déterminé dans l'itération courante.
La définition des opérateurs booléens est issue d'un travail de manipulation logique et de minimalisation de l'algorithme correspondant au procédé de conversion et
à la table de correspondance selon l'invention.
Dans l'invention, on a pu définir ces opérateurs à partir des bits bi, ri, ri-1 et ri-2, pour obtenir
directement en sortie le bit bi- et le chiffre r'i.
En utilisant le codage sur deux bits représentant le signe et la valeur absolue, les opérations booléennes suivantes ont pu être définies: bil=/bi.ri-.ri-2 + bi.ri -1 + bi.ri-2 r' iH=bi;
r'iL=/bi.ri-l.ri-2 + /bi.ri +.bi./ri+ bi./ri-./ri-2.
On notera que lorsque le chiffre r'i est nul, soit si r'iL=0, le bit de signe r'ipeut être pris indifféremment égal à 0 ou 1. Faire r'lH=bi, couvre ainsi tous les cas,
14 2811168
si on accepte une valeur quelconque 0 ou 1 pour le bit de signe dans le cas o le chiffre vaut 0. Mais on peut prévoir que ce bit de signe soit fixé, par exemple fixé à 0, lorsque le chiffre vaut 0, comme dans l'exemple donné à la figure 1. Un exemple de réalisation d'un dispositif de conversion comprenant des opérateurs booléens correspondante est représenté sur la figure 5. Dans cet exemple, le dispositif de conversion comprend, en plus des registres Rl et R2: -Une première porte Pi de type ET, comprenant une entrée inverseuse pour recevoir le bit ri, et une entrée non inverseuse pour recevoir le bit bi; -Une deuxième porte P2 de type ET avec les entrées inverses de la première; -Une troisième porte P3 de type ET, comprenant une entrée inverseuse pour recevoir le bit ri-1, une autre entrée inverseuse pour recevoir le bit ri-2 et une entrée non inverseuse pour recevoir le bit bî; -Une quatrième porte P4 de type ET, recevant les entrées inverses de la troisième porte; -Une cinquième porte P5 de type ET comprenant une entrée non inverseuse pour recevoir le bit ri-, et une autre entrée non inverseuse pour recevoir le bit bi; -Une sixième porte P6 de type ET, comprenant une entrée non inverseuse pour recevoir le bit ri-2, et une autre entrée non inverseuse pour recevoir le bit bi; -Une septième porte P7 de type OU, recevant en entrées, les sorties des première, deuxième, troisième et quatrième portes, et fournissant en sortie la valeur absolue r'iL (0 ou 1) du chiffre r'i de rang i de la représentation binaire signée, le bit de signe r'liH étant fourni par le bit bi; et
2811168
-Une huitième porte P8 de type OU, recevant en entrées, la sortie des quatrième, cinquième et sixième portes,
pour fournir en sortie le bit bi-1.
Les registres Ri, R2 et R3 qui contiennent respectivement la représentation binaire de r, la variable de calcul et le résultat de la conversion en
binaire signé sont commandés comme dans la figure 4.
L'invention qui vient d'être décrite est utilisable dans beaucoup d'applications, et notamment celles utilisant des procédés cryptographiques. Elle est applicable pour fournir la représentation binaire signée d'un opérande utilisé dans un traitement arithmétique quelconque, traitant de préférence les bits de gauche à droite pour en retirer le plus grand bénéfice en terme de simplicité de réalisation et de vitesse de traitement. On notera que l'on a donné un exemple d'application de l'invention à l'exponentiation d'un nombre fixe par un nombre r variable (aléatoire) qui utilise les techniques de calcul par carrés et multiplications (square and multiply). L'invention s'applique aussi bien à l'exponentiation d'un nombre aléatoire par un nombre r fixe, qui utilise les techniques des chaînes additives. Plus généralement, l'invention s'applique à des dispositifs de calcul arithmétique pour la multiplication d'un nombre a par le nombre r en représentation binaire signée, ou à la
multiplication scalaire d'un point par le nombre r.
Dans ce dernier cas, une application particulièrement intéressante de l'invention concerne le cas o le point est pris sur une courbe elliptique. La liste des
applications possibles n'est pas exhaustive.
Dans toutes ces applications le nombre d'opérations est réduit, comme avec la représentation de Reitwiesner, du fait du poids de Hamming minimum, avec les avantages
16 2811168
supplémentaires lié au traitement gauche vers droite
(simplicité matérielle, réduction du nombre de registre, traitement en temps réel).
Claims (17)
1. Procédé de conversion dans une représentation binaire signée sur m+l chiffres (r'm,..., r'0) d'un nombre (r) à partir de sa représentation binaire sur m bits (rm-,..., ro), caractérisé en ce qu'il consiste: a) à ajouter dans la représentation binaire du nombre à convertir (r) un bit (rm) de rang m, un bit (r-.) de rang -1 et un bit (r2) de rang -2 et à initialiser lesdits bits à la valeur 0, b) à utiliser au moins une variable de calcul (b), et c) à initialiser à la valeur 0 un bit de rang m (bm) de ladite variable, d) à effectuer pour i égal m jusqu'à i égal 0 une boucle de conversion, comprenant les opérations suivantes: (1) appliquer en entrées (el, e2, e3) de premiers moyens de calcul (30) le bit de rang i (bi) de la variable de calcul (b), et les bits de rangs i-1 et i-2 (ri-1, ri-2) de la représentation binaire du nombre à convertir, lesdits premiers moyens fournissant en sortie le bit de rang i-1 (bi-1) de la variable de calcul (b), en effectuant une opération arithmétique équivalente à la valeur par défaut de la somme arithmétique divisée par deux desdits bits appliqués en entrées (el, e2, e3), (2) appliquer en entrées (el', e2', e3') de deuxièmes moyens de calcul (31), les bits (bi, bi-1) de rang i et i-1 de la variable de calcul (b), et le bit (ri) de rang i de la représentation binaire du nombre à convertir (r), lesdits moyens de calcul effectuant une opération arithmétique équivalente à la multiplication par moins deux du bit de rang i de la variable de calcul (b), et la somme arithmétique du résultat précédent avec les deux autres bits appliqués en entrée, pour fournir en sortie le chiffre de rang i (r'i)
de la représentation binaire signée.
2. Procédé selon la revendication 1, caractérisé en ce qu'il consiste à appliquer la représentation binaire signée en entrées d'un dispositif (1) de calcul arithmétique dont ledit nombre (r) est un opérande, ledit dispositif de calcul traitant les chiffres dudit opérande du rang le plus élevé au rang le moins élevé.
3. Procédé de conversion selon l'une quelconque des revendication précédentes, caractérisé en ce qu'il comprend l'utilisation d'une table de conversion à quatre entrées comme premiers et deuxièmes moyens de calcul, lesdites entrées correspondant au bit (bi) de rang i de la variable de calcul (b), et aux bits (ri, ri-1, ri-2) de rang i, i-1 et i-2 de la représentation binaire du nombre à convertir (r), pour fournir directement en sortie la valeur du bit (bi-1) de rang i-1 de la variable de calcul (b) et la valeur du chiffre (r'i) de rang i de la représentation binaire signée.
4. Procédé de conversion selon l'une des revendications
1 à 3, caractérisé en ce que chaque chiffre (r'i) de la représentation binaire signée est fourni en sortie
sous la forme d'un code à au moins deux bits.
5. Procédé de conversion selon la revendication 4, caractérisé en ce que chaque chiffre est codé sur deux bits, un premier bit correspondant à la valeur absolue (r'iL) et un deuxième bit correspondant au bit de signe (r'iH), les premiers bits des chiffres de la représentation binaire signée étant mémorisés dans un premier registre de sortie (R3L) et les deuxièmes bits de ces chiffres étant mémorisés dans un deuxième registre de sortie (R3H), lesdits registres de sortie
étant du type à décalage vers la gauche.
6. Dispositif de conversion en binaire signé pour la mise en ouvre d'un procédé selon l'une des
revendications 3 à 5, caractérisé en ce qu'il
comprend une mémoire adressable par son contenu (CAM), le bit (bi) de rang i de la variable de calcul (b), et les bits (ri, ri-1, ri2) de rang i, i-1 et i-2 de la représentation binaire du nombre à convertir (r) étant appliqués à la dite mémoire comme bits
d'adresse (A0, Ai, A2, A3).
7. Dispositif de conversion mettant en oeuvre le procédé de conversion selon l'une quelconque des
revendications 1, 2, 4 ou 5, caractérisé en ce que
les premiers et deuxièmes moyens de calcul
comprennent des opérateurs booléens.
8. Dispositif de conversion selon la revendication 7, caractérisé en ce que lesdits opérateurs booléens reçoivent en entrées le bit (de rang i de la variable de calcul (b), noté bi, et les bits de rang i, i-1 et i-2 de la représentation binaire du nombre à convertir (r), respectivement notés ri, ri-, et ri-2, pour fournir en sortie le bit de rang i-1 de la variable de calcul (b), noté bi-1 et le chiffre de
rang i, noté r'i de la représentation binaire signée.
9. Dispositif de conversion selon la revendication 8 dans lequel chaque chiffre de la représentation binaire signée est fourni sous forme d'un code à deux bits selon la revendication 5, caractérisé en ce que lesdits opérateurs booléens comprennent un ensemble de portes logiques aptes à appliquer sur les bits d'entrées bi, ri, ri-1 et ri-2 une première opération booléenne équivalente à /bi.ri-l.ri-2 + bi.ri-, + bi.ri-2, pour fournir en sortie le bit bi-, et une deuxième opération booléenne équivalente à /bi.ri-.ri-2, /bi.r +.bi./ri + bi./ri-l./ri-2, pour fournir en sortie le bit représentant la valeur absolue (riL) du chiffre de rang i (r'i) de la représentation binaire signée, le bit (riH) représentant le signe dudit chiffre étant égal au bit de rang i (bi) de la variable de calcul
ou égal à 0 ou 1 si ledit chiffre est nul.
10. Dispositif de conversion selon la revendication précédente, caractérisé en ce que lesdits opérateurs booléens comprennent: a) Une première porte (Pi) de type ET, comprenant une entrée inverseuse pour recevoir le bit (r1) de rang i de la représentation binaire du nombre à convertir (r), et une entrée non inverseuse pour recevoir le bit (bi) de rang i de la variable de calcul; b) Une deuxième porte (P2) de type ET avec les entrées inverses de la première; c) Une troisième porte (P3) de type ET, comprenant une entrée inverseuse pour recevoir le bit (ri-) de rang i-1 de la représentation binaire du nombre à convertir (r), une autre entrée inverseuse pour recevoir le bit (ri-2) de rang i-2 de la représentation binaire du nombre à convertir (r), et une entrée non inverseuse pour recevoir le bit (bi) de la variable de calcul (b); d) Une quatrième porte (P4) de type ET, recevant les entrées inverses de la troisième porte; e) Une cinquième porte (P5) de type ET comprenant une entrée non inverseuse pour recevoir le bit(ri1) de rang i-1 de la représentation binaire du nombre à convertir (r), et une autre entrée non inverseuse pour recevoir le bit (bi) de rang i de la variable de calcul (b); f) Une sixième porte de type ET, comprenant une entrée non inverseuse pour recevoir le bit (ri-2) de rang i-2 de la représentation binaire du nombre à convertir (r), et une autre entrée non inverseuse pour recevoir le bit (bi) de rang i de la variable de calcul (b); g) Une septième porte (P7) de type OU, recevant en entrées, les sorties des première, deuxième, troisième et quatrième portes, et fournissant en sortie le bit (r'iL) représentant la valeur absolue (0 ou 1) du chiffre (r'i) de rang i de la représentation binaire signée, le bit (r'iH) représentant le signe étant fourni par le bit (bi) de rang i de la variable de calcul (b); et h) Une huitième porte (P8) de type OU, recevant en entrées, la sortie des quatrième, cinquième et sixième portes, pour fournir en sortie le bit (bi-1)
de rang i-1 de la variable de calcul (b).
11. Dispositif de conversion selon l'une quelconque
des revendications 6 à 10, caractérisé en ce qu'il
comprend un premier registre d'entrée (R1) à décalage vers la gauche pour contenir la représentation binaire du nombre à convertir (r) et un deuxième registre (R2) à décalage vers la gauche, pour
contenir la variable de calcul (b).
12. Dispositif selon la revendication 11, caractérisé en ce que ledit deuxième registre (R2) est un latch, qui contient le bit de rang i correspondant à l'itération courante, et en ce que le bit de rang i-1 délivré en sortie dans cette itération est chargée dans le latch pour fournir le bit de rang i dans
l'itération suivante.
13. Circuit intégré comprenant un dispositif de
conversion selon l'une quelconque des revendications
6 à 12, caractérisé en ce qu'il comprend en outre un dispositif (1) de calcul arithmétique selon un traitement du chiffre de rang le plus élevé au chiffre de rang le plus faible de la représentation
binaire signée.
14. Circuit intégré selon la revendication 13, caractérisé en ce que ledit dispositif (1) de calcul arithmétique est un dispositif d'exponentiation d'un nombre (a) par la représentation binaire signée du
nombre (r) appliqué au dispositif de conversion.
15. Circuit intégré selon la revendication 13, caractérisé en ce que ledit dispositif (1) de calcul arithmétique est un dispositif de multiplication d'un nombre (a) par la représentation binaire signée du
nombre (r) appliqué au dispositif de conversion.
16. Circuit intégré selon la revendication 13, caractérisé en ce que ledit dispositif (1) de calcul arithmétique est un dispositif de multiplication scalaire d'un point (a) par la représentation binaire signée du nombre (r) appliqué au dispositif de conversion.
17. Circuit intégré selon la revendication 16, caractérisé en ce que ledit point est pris sur une
courbe elliptique.
Priority Applications (6)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0008547A FR2811168B1 (fr) | 2000-06-30 | 2000-06-30 | Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee |
| AU2001269217A AU2001269217A1 (en) | 2000-06-30 | 2001-06-20 | Method for converting the binary representation of a number in a signed binary representation |
| US10/312,530 US6903663B2 (en) | 2000-06-30 | 2001-06-20 | Method for converting the binary representation of a number in a signed binary representation |
| CN01812126.8A CN1258883C (zh) | 2000-06-30 | 2001-06-20 | 将一个数的二进制表示变换成一个带符号的二进制表示的方法 |
| EP01947558A EP1299953A1 (fr) | 2000-06-30 | 2001-06-20 | Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee |
| PCT/FR2001/001944 WO2002001727A1 (fr) | 2000-06-30 | 2001-06-20 | Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0008547A FR2811168B1 (fr) | 2000-06-30 | 2000-06-30 | Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| FR2811168A1 true FR2811168A1 (fr) | 2002-01-04 |
| FR2811168B1 FR2811168B1 (fr) | 2002-11-15 |
Family
ID=8851988
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| FR0008547A Expired - Fee Related FR2811168B1 (fr) | 2000-06-30 | 2000-06-30 | Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US6903663B2 (fr) |
| EP (1) | EP1299953A1 (fr) |
| CN (1) | CN1258883C (fr) |
| AU (1) | AU2001269217A1 (fr) |
| FR (1) | FR2811168B1 (fr) |
| WO (1) | WO2002001727A1 (fr) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4682852B2 (ja) * | 2006-01-16 | 2011-05-11 | ソニー株式会社 | 暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラム |
| US7996798B2 (en) * | 2007-05-24 | 2011-08-09 | Microsoft Corporation | Representing binary code as a circuit |
| EP2169535A1 (fr) * | 2008-09-22 | 2010-03-31 | Thomson Licensing | Procédé, appareil et support de programme informatique pour le recodage régulier d'un entier positif |
| US8812570B2 (en) * | 2009-05-28 | 2014-08-19 | Red Hat, Inc. | String hashing using a number generator |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4215417A (en) * | 1978-01-27 | 1980-07-29 | Nippon Electric Company, Ltd. | Two-term vector multiplier |
| DE4308112A1 (de) * | 1993-03-15 | 1994-10-13 | Andreas Herrfeld | Schaltung zur CSD-Codierung einer binären Zweierkomplement- oder Dualzahl |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0892520A3 (fr) | 1997-07-17 | 2001-10-17 | Matsushita Electric Industrial Co., Ltd. | Dispositif de calcul de courbe elliptique pouvant calculer des multiples a une vitesse élevée |
-
2000
- 2000-06-30 FR FR0008547A patent/FR2811168B1/fr not_active Expired - Fee Related
-
2001
- 2001-06-20 WO PCT/FR2001/001944 patent/WO2002001727A1/fr not_active Ceased
- 2001-06-20 US US10/312,530 patent/US6903663B2/en not_active Expired - Fee Related
- 2001-06-20 AU AU2001269217A patent/AU2001269217A1/en not_active Abandoned
- 2001-06-20 EP EP01947558A patent/EP1299953A1/fr not_active Withdrawn
- 2001-06-20 CN CN01812126.8A patent/CN1258883C/zh not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4215417A (en) * | 1978-01-27 | 1980-07-29 | Nippon Electric Company, Ltd. | Two-term vector multiplier |
| DE4308112A1 (de) * | 1993-03-15 | 1994-10-13 | Andreas Herrfeld | Schaltung zur CSD-Codierung einer binären Zweierkomplement- oder Dualzahl |
Non-Patent Citations (3)
| Title |
|---|
| CHAO-LIANG CHEN ET AL: "A simplified signed powers-of-two conversion for multiplierless adaptive filters", 1996 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS. CIRCUITS AND SYSTEMS CONNECTING THE WORLD, ISCAS 96 (CAT. NO.96CH35876), 1996 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS. CIRCUITS AND SYSTEMS CONNECTING THE WORLD. ISCAS 96, ATLANT, 1996, New York, NY, USA, IEEE, USA, pages 364 - 367 vol.2, XP002165296, ISBN: 0-7803-3073-0 * |
| CHIANG A C L ET AL: "ARITHMETIC NORMS AND BOUNDS OF THE ARITHMETIC AN CODES", IEEE TRANSACTIONS ON INFORMATION THEORY,US,IEEE INC. NEW YORK, vol. IT-16, no. 4, July 1970 (1970-07-01), pages 470 - 476, XP000760887, ISSN: 0018-9448 * |
| GOTO MUNEHIRO: "NONBINARY CYCLIC AN CODES", ELECTRON COMMUN JAP MAY 1973, vol. 56, no. 5, May 1973 (1973-05-01), pages 31 - 37, XP000990544 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN1258883C (zh) | 2006-06-07 |
| WO2002001727A1 (fr) | 2002-01-03 |
| AU2001269217A1 (en) | 2002-01-08 |
| EP1299953A1 (fr) | 2003-04-09 |
| FR2811168B1 (fr) | 2002-11-15 |
| US20040215684A1 (en) | 2004-10-28 |
| CN1440591A (zh) | 2003-09-03 |
| US6903663B2 (en) | 2005-06-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP3394797A1 (fr) | Circuit neuronal optimise, architecture et procede pour l'execution des reseaux de neurones | |
| FR2726667A1 (fr) | Procede de mise en oeuvre de multiplication modulaire selon la methode montgomery | |
| EP0692762B1 (fr) | Circuit logique de multiplication parallèle | |
| JP2004519017A (ja) | 係数乗算するための方法および装置 | |
| EP0110767B1 (fr) | Multiplieur binaire rapide | |
| FR2604270A1 (fr) | Additionneur binaire comportant un operande fixe, et multiplieur binaire parallele-serie comprenant un tel additionneur | |
| FR2811168A1 (fr) | Procede de conversion de la representation binaire d'un nombre dans une representation binaire signee | |
| FR2568036A1 (fr) | Circuit de calcul | |
| EP0259231A1 (fr) | Dispositif de détermination de la transformée numérique d'un signal | |
| CN114579079A (zh) | 用于常数乘法的集成电路、操作其的方法和包括其的装置 | |
| FR3101980A1 (fr) | Processeur | |
| EP0476592A2 (fr) | Générateur d'adresses pour la mémoire de données d'un processeur | |
| FR2687004A1 (fr) | Architecture de memoire associative. | |
| EP2315388B1 (fr) | Procédé sécurisé de calcul cryptographique et composant électronique correspondant. | |
| US5777918A (en) | Fast multiple operands adder/subtracter based on shifting | |
| US20090077151A1 (en) | Multi-Input, Multi-State Switching Functions and Multiplications | |
| EP0254628B1 (fr) | Circuit de traitement numérique de signal réalisant une transformation cosinus | |
| WO2005006557A1 (fr) | Dispositif de comparaison de deux mots de n bits chacun | |
| EP0329572B1 (fr) | Multiplieur de nombres binaires à très grand nombre de bits | |
| FR2772160A1 (fr) | Circuit de calcul de la transformee de fourier rapide et de la transformee de fourier rapide inverse | |
| FR2558612A1 (fr) | Appareil de multiplication binaire | |
| CA2359198C (fr) | Unite de calcul pour l'execution d'un protocole cryptographique | |
| EP1335277A1 (fr) | Opérateur saturant à haute efficacité | |
| EP0145533B1 (fr) | Procédé et réseau multiplicateur pour la multiplication, modulo un nombre binaire N, de deux nombres binaires X et Y | |
| FR2655444A1 (fr) | Reseau neuronal a circuits neuronaux electroniques a apprentissage de coefficients, et procede d'apprentissage. |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| ST | Notification of lapse |
Effective date: 20100226 |