Brevet FR2908905A1 — publié le 20080523

PROCEDE ET CIRCUIT MULTIPLIEUR DE NOMBRES BINAIRES La présente invention concerne un procédé et un circuit multiplieur de nombres binaires utilisant un 5 réseau d'additionneurs. Elle trouve une application particulièrement importante bien que non exclusive dans le domaine des systèmes informatiques mettant en oeuvre des algorithmes nécessitant de réaliser rapidement de 10 nombreuses multiplications comme par exemple dans le domaine du traitement numérique de signal. Elle peut donc être employée à la place de multiplieurs connus réalisés par recodage ou avec des compteurs, et ce de façon plus simple et plus 15 efficace. On connaît déjà des multiplieurs du type basé sur un schéma à points matriciels ( dot matrix en langue anglosaxonne). Le multiplicande y est décalé, multiplié par un 20 bit de multiplieur et additionné avec la somme intermédiaire du calcul précédent. L'opération est ensuite répétée jusqu'au dernier bit, l'addition des valeurs de multiplicandes décalés étant soit effectuée par recodage en utilisant des 25 algorithmes simplificateurs reconsidérant les éléments successifs comme des multiples, (recodage du type connu en terminologie anglosaxonne sous le nom de recodage Booth ), ce qui permet de diminuer le nombre de multiplicandes à additionner, soit en 30 mettant en oeuvre un réseau de demi-additionneurs organisés en compteurs. De tels multiplieurs peuvent cependant être encore améliorés ; en effet, ils se révèlent coûteux en 2908905 2 énergie et sont de plus difficiles à tester préalablement de façon parfaitement fiable. La présente invention vise à fournir un procédé et un circuit multiplieur répondant mieux que ceux antérieurement connus aux exigences de la pratique, notamment en ce qu'elle autorise une propriété particulière non présente dans l'art antérieur, du fait de l'expression intermédiaire du nombre calculé sous une forme d'approximations avec affinements successifs. Une telle forme favorise les tests de fonctionnement du circuit proposé, et ce pour un coût en général plus faible et une rapidité à tout le moins équivalente. Pour ce faire, l'invention part d'une nouvelle implantation avec approximations successives organisées en trois étages, qui n'utilise pas la matrice générée par les ET logiques des multiplieurs et multiplicandes connus, mais le OU exclusif, beaucoup plus facile à tester. Avec l'invention, on réexprime la matrice de calcul sous une forme différente, en le transformant de sorte qu'elle exprime la structure même du nombre recherché. Dans ce but, l'invention propose essentiellement un Procédé multiplieur par un réseau d'additionneurs de deux nombres binaires X et Y respectivement de N et de M bits, à savoir : X =xN.2N +xv, + +x". 2" + + x .2i +x02" y = yni.2" +y•2" + + y .2" + + y .2' +y0 ,o définissant une matrice [E7= x .y ], caractérisé en ce que 2908905 3 on transforme la matrice initiale [E,=xä-Y en une matrice [E , = (xä Y,) _ (Xn_i Y;)-Y, avec y. =Y;-~ O+Y; on constitue une première approximation U" et R" 5 de la somme et de la retenue des deux premières lignes yo et yl de cette matrice ainsi transformée sur toute la longueur desdits nombres, on reprend cette première approximation qu'on utilise comme entrée pour l'étape d'estimation suivante qui 10 est réitérée pour toutes les lignes suivantes, et ce en réalisant successivement l'addition des lignes yl+l suivantes jusqu'à la dernière non nulle, en fonction d'une première série d'équations de propagation déterminée, 15 puis on réalise la propagation des retenues R" a sur les lignes Y1_+1 nulles en fonction d'une deuxième série d'équations de propagation déterminée, pour obtenir le résultat final du produit : P = n +N+,211,+,ti+I +pn,+N.24,+,v + + pN.2N + + p~.2' + p~2o 20 Dans des modes de réalisation avantageux, on a de plus recours à l'une et/ou à l'autre des dispositions suivantes . - la première approximation des bits de la somme U est déterminée en effectuant un calcul à partir 25 du signal correspondant à la valeur E0 de la matrice corrigé par le signal correspondant à la valeur Y~ =Yo Y,' 2908905 4 et en ce que la première approximation des bits de la retenue Rä+I est déterminée en effectuant un calcul à partir des signaux correspondant aux valeurs 0 E, et En de la matrice corrigées par le signal 5 correspondant à la valeur Y I= yoO+ yI. la première approximation est donnée par la {UHyjyoxn formule nommée EI1 0 R= 10 - en la réexprimant en fonction de YI,Yo,E E _I la première approximation est alors donnée par les nommée E'11 avec les hypothèses d'anticipation de retenue suivantes : Si la deuxième ligne n'est pas nulle 15 (YI=1), une retenue est anticipée quelque soit la valeur de la première ligne (y0=oouy0=1). - la première approximation est donnée par la avec . y0 =OOyo=yo et Yl=yooy 20 - En la réexprimant en fonction de Y ,Y E",E, il vient . formules . o RäùYIEn~En-) iU= ycy ci y p.xn formule : nommée EI2 0+1 2908905 nommée E'I2 U=Y1•Y1,C, E R ( O =Y1~ E E+O YtY o Rä 5 avec les hypothèses d'anticipation de retenue suivantes : Si les deux lignes ne sont pas nulles (y0=lety1 =i), une retenue est anticipée. la première approximation est donnée par la formule : nommée EI3 R0ù 1~ Yt-J' oO+.l' l'xäùI - En la réexprimant en fonction de Y ,Y ,E,,E " t o äùt 10 la première approximation est donnée par les U1t=10 E o = (EEII) t hypothèses d'anticipation de retenue suivantes : Quelques soient les valeurs de YoetY1, une retenue est anticipée. - la première approximation est donnée par la formule : o Un_ - y1.yoO yo X` nommée EI4 R o _ l) , } IX,,-1 20 -la première approximation est donnée par la formule . 5 Uä=Yo+O Yo-xn formules . nommée E'I3 avec les 15 2908905 6 nommée E15 Un = Y1 Y,.Y0 Yoxä R =YI.Y,1 Y1.Y .xn - la première approximation est donnée par la formule Un = YI.Yo0Yo.xn o _ O R n Y o Y .x nùI nommée EI6 5 - la première approximation est formuledonnée par la {u ,,= Y ,.xä lRn=Y1.Y Yl xn-I nommée EI7 10 - la première approximation est donnée par la formule {u:=y1c'Yoc).Yo.xn R o e n= / o / I/ px n I nommée EI8 15 - la première série d'équations s'écrit U n= U R n Y;+1 I i+l O (i'-' nùI O t/ nù2 R nù1 iR'n+l U;ù1 Ro E +1 11ù1 nù1 n 20 nommée EEP1 1+1 avec ~+ n = (Xn o Y ;+1 'Y ;+I Y ;+I = Y ; e Y ;+I et 2908905 7 - la première série d'équations s'écrit {u, = Un R Y;+t R ,.,+1 = Y;+t R .(E t c) U ) ~ Y nommée EEP2 5 -la deuxième série d'équations s'écrit : ä (u:' U nù1 ) la deuxième sérienommée EP1 d'équations s'effectue avec .1 ;--t Un=U @R = (u:'u:')R:1 des additionneurs de type Carry-Look-Ahead. L'invention propose également un système 10 multiplieur comprenant des moyens de calculs mettant en oeuvre le procédé ci-dessus mentionné. Elle propose aussi et plus précisément un multiplieur permettant de multiplier des signaux d'entrée comportant un premier nombre binaire (X) de 15 N bit et un second nombre binaire (Y), de M bits, à savoir : X = xN•2N +x~ + +xn.2n + +xt.21 +x0.2' Y =y Af.2 +y + +y n.2n+ +y 1.2'+y.2 1/-1 0 [En =xn-;-~J J , caractérisé en ce que il comporte 20 des moyens de calcul pour transformer la matrice initiale [E = x y ] en une matrice . n n-; [En= (x . y;). (y;-t y;) = (x n-, y;).Y; ] une matrice définissant avec y ; y ;-t e y 2908905 8 des moyens d'estimation initiale (MEOi) agencés pour fournir une première approximation U, et p de la somme et de la retenue des deux premières lignes yo et yl sur toute la longueur N desdits nombres, 5 comprenant N blocs d'estimation (MIi) montés en parallèle, chaque bloc d'estimation étant apte à effectuer lesdites sommes et lesdites retenues , des moyens d'estimation /propagation (MEEPi; agencés pour réaliser successivement l'addition des lignes 10 y1+i suivantes jusqu'à la dernière non nulle, en fonction d'une première série d'équations de propagation déterminée, comprenant des blocs d'estimation/propagation (MEPi) montés en cascade, chaque bloc d'estimation/propagation étant apte à 15 effectuer lesdites sommes et les dites retenues, et des moyens de propagation (MPi) des retenues ä sur les lignes yl+i nulles en fonction d'une deuxième série d'équations de propagation déterminée. Avantageusement les moyens de propagation (MPi) Ri-1 20 des retenues n comprennent des blocs d'estimation en cascade inverse, chaque bloc d'estimation étant apte à effectuer lesdites retenues. Egalement avantageusement et pour accélérer le fonctionnement des moyens de propagation (Mpi) des 25 retenues ,: , on utilise une forme d'additionneur de type Carry-Look-Ahead. L'invention sera mieux comprise à la lecture de la description qui suit de modes de réalisation donnés ci-après à titre indicatif et de façon non 30 limitative. 2908905 9 Celle-ci fait référence aux figures qui l'accompagnent, dans lesquelles : - La figure 1 représente la matrice initiale de calcul d'un multiplieur 5 x 5 bits. 5 - La figure 2 illustre la transformation d'une expression d'une matrice connue du type de la figure 1, en une nouvelle matrice pour l'utilisation avec l'invention. -Les figures 3A et 3B montrent un exemple de 10 matrice de type dot-matrix de l'art antérieur permettant la multiplication de deux nombres déterminés, et la matrice obtenue selon l'invention après transformation. - Les figures 4 à 7 illustrent graphiquement à 15 titre d'exemple, l'élaboration et le fonctionnement de la première série d'équations. - Les figures 8 à 10 sont des exemples de représentation des circuits logiques correspondant respectivement à des modes de réalisation de la 20 première approximation (EI1), de la première série d'équations (EEP2) et de la deuxième série d'équations (EP1). - La figure 11 est un schéma général d'un multiplieur selon le mode de réalisation de 25 l'invention plus particulièrement décrit ici. - La figure 12 montre une variante de multiplieur dont le dernier étage est remplacée par un étage du type Carry-Look-Ahead . - La figure 13 donne un schéma fonctionnel du 30 multiplieur de l'invention plus particulièrement décrit ici. Les figures 14 et 15 sont des représentations schématiques et fonctionnelles des étapes ou modules 2908905 10 d'estimation initiale et d'estimation propagation en vertu de la première série et/ou de la deuxième série d'équations, selon un mode de réalisation de l'invention. 5 La figure 1 représente la matrice initiale de calcul de la multiplication de deux nombres binaires de cinq bits chacun, à savoir : _ x4.2a + x3.2' + x2.2z + x1.2i+ x0.20 X y = / 4.24 + v 3.23 + v 2.22 + v ~.2' + v 0.2 Le produit va donc être exprimé sur 10 bits: 10 p =p9.29+pX.2X+ +p.2'+p.2 (voir ligne - de la figure 1) Pour la forme connue les valeurs sont par ailleurs telles que • Eä = x n-;• y i et les valeurs Eä en dehors de la zone hachurée 2 de la figure 1 sont 15 nulles. Selon l'invention, une nouvelle expression de cette matrice initiale est utilisée avec des valeurs , telles que : Enù (xnùi Y;).(Y; Y;) 20 avec y, +O y i-1 . L'équivalence entre les deux formes de matrice [la forme connue (référencée 3 sur la figure 2) et celle utilisée avec l'invention référencée 4 sur la figure 2)] est montrée ci-après en référence à ladite figure 25 2. 11 On remarque d'ores et déjà que la nouvelle matrice 4 comporte une ligne 5 de plus que la matrice standard 3 (avec En = car la dernière ligne 6 de cette matrice 4 contient les valeurs : 5 En = (xä-5 c) Y5).Y5 = xn-5Y5 et Y5=Y4 Y5=Y4 qui peuvent donc être non nulles. Plus précisément la matrice connue exprimée en fonction de En= x y1 est transformée en une n-i nouvelle matrice exprimée en fonction de 10 E,,= (x! O Y,). (Y;_l Y i) par la re-expression des ensembles de bit à 1 de la matrice connue. Cette transformation se fait sur la base des considérations suivantes. Soit un ensemble de bit ayant la valeur 1. Cet S = 2k+1 [(2"+m -2m)+(2" -2" -2+` )+ (2 -2" + 2908905 15 ensemble est généré par les bits x k a x k--n-1 ayant pour valeur 1 multiplié par les bits y à y ayant / /+m-1 pour valeur 1. Le résultat S est exprimé ainsi : S (xk+n-1.2k+n-I + + xk+I.2k+1 + 2k) ( y 2'+m I + + y 1+I2'+1 x k' l+m-1 En affectant les valeurs x;=1,y =1 et en factorisant 20 2k et 2' , il vient : S 21+' (2"-' + +2' +20) (2m 1 + +21 +2 ) S û 2k.+/ (2ä û 20) (2m û 20) û 2k+1 (2" ~'" û 2"' û 2" -1- 20) +y,.2) 2908905 12 S, = 2k+ (2ä+n, -2n')+(2" -2k+I+ä -2+~)+ (2k+' -2 +2- avec 2k+/.(2"+"' - 2"') . Partie référencée 7 en trait mixte sur la figure 2. (2" - 2k+r+ä - 2+"~ Partie référencée 8 et 8' sur la 5 figure 2 en trait mixte. (2k+i -2" +21 : Partie référencée 9 et 9' sur la figure 2 en trait mixte. Ainsi et dans un exemple numérique avec un multiplieur y=63669 = 1111100010110101 et un 10 multiplicande x=40119 = 1001110010110111 la matrice initiale s'exprime selon le Tableau I ci-après. Tableau I 1001 1 0000 1 O00O0O00 101 Q 1 01 1(3001 1 15 Et après transformation selon l'invention, on obtient la matrice 10 de la figure 3A. 1:10111 }00000 100 1 1 10010 10011100101 00000000000(3( 310010110.11 i3000000000 0000-o_ - 0000 10o-11 i 10011 1001.11 100111110 110111 1 9~;ia 2908905 13 Les bits 11, 12, 13, 14 et 15 doublement encadrés figurent les valeurs en 2-0 et les bits 16, 17, 18, 19 et 20 les valeurs en 2+a, On constate donc qu'une ligne supplémentaire 21 5 est nécessaire pour la matrice transformée en2'+'. On voit également que dans la multiplication décrite, il n'est pas nécessaire d'additionner les valeurs en 2ù car elle est réalisée avec des additionneurs qui supposent toujours une retenue. 10 Il n'est pas non plus nécessaire de propager les retenues au delà du parallélogramme pour la même raison. On va maintenant décrire plus avant le principe de la multiplication (appliqué à l'exemple numérique 15 ci-dessus) mis en oeuvre dans le mode de réalisation de l'invention plus particulièrement décrit ici, en référence à la figure 3B, à la formule E'I1 pour la première approximation, à la formule EEP2 pour la première série d'équations et à la formule EP1 pour 20 la deuxième série d'équations. On calcule tout d'abord la première approximation U" et R de la somme des 2 premières lignes de la matrice. Soient les lignes Eô à E, et Eo à à 25 additionner : si la ligne Eo a E =Y,O+Y.x RùY•(xäYoc)Yoex,,Y,Y,•Y,(DI) Y,•(x •YI> xä Yo Y, 1) Avec : Y I =y0 y1 et Y0=yo Un=Y,(DY0.xä (xä.Yä0 Yä0 Y, 0 1) = Y,-xä.Y0 Y,.(Yo <> Y,) Rn+, = Y I~ suivantes : ,, 20 On obtient . o Uä=xäcYI,c)Y, 0 Rä+I=x,,.Y } 2908905 18 Ces relations sont implantées dans le schéma 40 de la figure 8. On a par ailleurs représenté sur la figure 9 un 5 exemple de réalisation du module d'estimation/propagation (MEP) 41 mettant en œuvre l'équation EEP2. L'addition des lignes suivantes de la matrice est en effet calculée avec les modules dits d'estimation 10 propagation réalisant les équations suivantes U = Uä R n Y;+1 Rn=Y;+, E;+t (U o n nù1 nù] Comme précédemment, on regroupe les signaux pour minimiser les entrées et donc les équations implantées par module calculent plutôt un système 15 fonction de U et R Exprimable aussi ainsi R,0,+, x ä-Y o. y t Un=xn'YpOy, R J ,,-] (U n ; ùt1 Un RnùI iù1 O lù1 n) (Un ;ùI nù1 Rn {U1 =U; R;,1 ~Y1+, R /+I O , O n+1 = Y;+I L 11+1 (u: EEP1 décomposée en fonction des termes Y;+1 et -1 de la ùt +I I l Y+t R; n ~ E1(u;:' eRä)J n-I) .R ä 'Y ;+I manière 20 suivante . i i+1 ;-t Rn+1=Y;+I R~En+1 (u:' Rn L' expression de peut quant à elle être R n+] 2908905 19 Puis, avec regroupement des deux termes en et simplifications il vient : R =Y Rit E;+I UoR;1 rJ:' TT n+I i+1 n n+l n n) n n-1 J ; I Y;+,•R i-1 R n 'Y ;+] ;+I O i-1 O ;1 R n+1 ù Y;+1 R n • En+l R,, U n-1 i-I i+l 1•Rn En+I $ U ;-1 n c) Rni1)e Uä Un i-1 ) -, R n Y;+1 oy 1 ( ;+1 O ) R n+1 = Y;+1 R n E n+l n-1 -i ;+1 i-1) -1 Y;+l Rn EUR•Y;+l' (u:' Ci U-I) Une relation de récurrence découverte par l'inventeur -1 i-1 montre par ailleurs que Y;+l Rn E';+1 ' Un-l) = 0 On obtient ainsi le système d'équations suivant : ] ;-1 ;1 1 ;-1 Rn+1=Y;+1.Rn En+1 U )eY;+1.Rnù•(U +I ~U ) n n-1 10 qui est celui plus particulièrement mis en oeuvre dans un mode de réalisation de l'invention. Comme indiqué ci-dessus, une implantation possible de ce système 41 est représentée figure 9. L'implantation précédente est en fait obtenue en 15 i substituant E +l = (xn-i O+ Y )•ydans R n+l : +l ( 1ù11 O 1ù1 ( iù1 Q r _ ) R n+l ù Y 1+1R n x n-; ,i i+1 U n J Y n U n n -1 Les deux termes de Rn+l étant ici disjoints, on note ici que le OU-exclusif peut être remplacé par un OU 20 normal. 5 1 O ;] O Un = Un Rn Yi+l EEP2 2908905 20 Plusieurs autres implantations en portes sont possibles. Soit à partir de l'expression : i+I iùI) I 1 I R n+I = Y i+l R n E n+l U n Y;+IR n. ~U n U nù1 5 Soit à partir de l'expression : R n+I = l i+l E( iùI) (u:' Rn(u' ' O T T i ùI R I Il nù1fl n Enfin, selon le mode de réalisation de l'invention plus particulièrement décrit ici, il est mis en oeuvre 10 une deuxième série d'équations EP1 qui réalisent donc les équations . U;, = U;,' R ùI iùI R (Un Un .Rnù1 Pour ce faire un module de propagation finale (dit 15 MP) (cf. figure 10) est par exemple réalisé. On a maintenant représenté en référence à la figure 11 le schéma général d'un multiplieur 5 bits x 5 bits 43 mettant en oeuvre les implantations décrites ci- 20 dessus selon le mode de réalisation de l'invention plus particulièrement décrit. Ce dispositif 43 est constitué de trois étages : le premier étage 44 comprend une ligne de modules d'estimation initiale (MI0 à MI4), 25 le deuxième étage 45 comprend quatre lignes de modules d'estimation/propagation (MEP10 à MEP15, MEP20 à MEP26, MEP30 à MEP37, MEP40 à MEP48), le troisième étage 46 comprend un réseau de modules de propagation (MPxx). 2908905 21 Le bit de poids fort est quant à lui généré par une cascade de Ou exclusif 47. On a enfin fait figurer en 48 les schémas logiques d'obtention des valeurs Yi, Yi à partir des valeurs 5 yi utilisant les portes OU Exclusif selon le mode de réalisation avantageux de l'invention. On a également décrit en référence à la figure 12 un autre mode de réalisation de l'invention utilisant comme troisième étage une propagation finale type 10 Carry-Look-Ahead. Pour diminuer le temps de propagation le dernier étage de modules de propagation peut en effet être remplacé par un étage 49 de type Carry-Look--Ahead prenant en entrée la forme d'expression en U et 15 R Ici encore, et comme pour la figure 11A, on a représenté les schémas logiques 48 utilisant les portes OU exclusif selon l'invention. La figure 13 donne quant à elle une description 20 fonctionnelle du multiplieur 50 selon le mode de réalisation de l'invention plus particulièrement décrit ici, montrant la modularité de la structure. Un premier étage 51 comprenant les modules 52 d'estimation initiales MEC), est prévu, qui vient 25 attaquer le deuxième étage 53 de module d'estimation et propagation MEPll 54, qui lui-même attaque le troisième étage 55 de module de propagation MEPmi 56 pour donner le produit P. Une interprétation fonctionnelle des modules 30 d'estimation initiale 52 et d'estimation/propagation 54 est décrite figure 14 et 15. 2908905 22 Ces interprétations sont fonction d'une manière d'exprimer les équations réalisées. Dautres interprétations sont bien entendu possibles pour d'autres expressions des équations. 5 Plus précisément la figure 14 montre le module 52 d'estimation initiale. A partir d'une entrée d'estimation E0 qui attaque d'une part directement (liaison 58) et d'autre part via un calculateur d'estimation 59, un multiplexeur 10 60, on mixe avec l'entrée y , pour obtenir 0 l'estimation initiale tin. La retenue I?, est quant à elle obtenue à partir des entrées E et Ë qui attaquent une unité de calcul d'affinement 61 comme décrit ci-dessus avant 15 de faire jouer un multiplexeur 62 dans lequel est également introduite l'entrée y , et ce pour obtenir 0 in fine la retenue . La figure 15 illustre quant à elle le module 54 d'estimation/propagation permettant d'altérer les 20 valeurs Ur, et les retenues R selon l'invention en mettant en oeuvre les algorithmes ci-dessus mentionnés. Ri-' A partir des entrées ä et T2 on effectue (bloc 63) la correction en n des valeurs par application de 25 l'affinement. La sortie 64 attaque alors, d'une part un calculateur d'estimation 65, lui même connecté au multiplexeur 66, d'autre part (ligne 67) le même multiplexeur (bit 2908905 23 0) dans lequel on introduit également la valeur v;+, et enfin un calculateur d'affinement 67. Le multiplexeur 66 donne la valeur tin. Quant à la retenue Rä+1 elle s'obtient par i.e biais 5 d'un multiplexeur 69 attaqué par les valeurs Y i+1 et Rn et par la sortie du calculateur 68, et du circuit de calcul de propagation/Affinement 70, circuit ayant lui même comme entrées Un u'-' et Io Comme il va de soi et comme il résulte de ce qui précède, la présente invention n'est pas limitée aux modes de réalisation plus particulièrement décrits. Elle en embrasse au contraire toutes les variantes et notamment celles où les circuits logiques sont 15 constitués différemment pour obtention d'un même résultat. REVENDICATIONS 1. Procédé multiplieur par un réseau d'additionneurs de deux nombres binaires X et Y 5 respectivement de N et de M bits, à savoir : X =xN.2"+x i•2"'+ +x .2"+ ++x02 2Â1 + + + .2" + + .2' + .20 = yA1 YY y yo définissant une matrice [ E = x .y ], caractérisé en ce que on transforme la matrice initiale [ E = x y ] en Io une matrice [En= (x ci y;).(y,-, y,)= (D' y,)Y ] avec y +O on constitue une première approximation U0 et R`1 de la somme et de la retenue des deux premières lignes yo et y1 de cette matrice ainsi transformée 15 sur toute la longueur desdits nombres, on reprend cette première approximation qu'on utilise comme entrée pour l'étape d'estimation suivante qui est réitéré pour toutes les lignes suivantes, et ce en réalisant successivement l'addition des lignes yl+l 20 suivantes jusqu'à la dernière non nulle, en fonction d'une première série d'équations de propagation déterminée, puis on réalise la propagation des retenues R1-1 17 sur les lignes yl+l. nulles en fonction d'une deuxième 25 série d'équations de propagation déterminée, pour obtenir le résultat final du produit P P = p >+,~+~.2A,+;, +1 + p ä1+,N 2~1+ + + p N.2" + + p 2' + n .20 2908905 25 2. Procédé multiplieur selon la revendication 1, caractérisé en ce que la première approximation des bits de la somme U" est déterminée en effectuant un calcul à partir du signal correspondant à la valeur En de la matrice corrigé par le signal correspondant En à la valeur y1 = y O+ y l, et en ce que la première approximation des bits de la retenue R~+I est déterminée en effectuant un calcul à partir des signaux correspondant aux valeurs E0 et de la matrice corrigées par le signal correspondant à la valeur y, =yoO yI. 3. Procédé selon la revendication 2, caractérisé en ce que la première approximation est donnée par o U_ y les formules : ä '_ O y oxn nommé EI1 o Y y0XnùI 4. Procédé selon la revendication 3, caractérisé en ce que en réexprimant la première approximation en fonction de Yi,Yo,Eo,L 0_1 la première approximation est alors donnée par les formules : 1 O ) /I Un'=Y1c) E o o Rn Y1' (En EnùI nommée E'11 avec les hypothèses d'anticipation de retenue suivantes : Si la deuxième ligne n'est pas nulle (Y1=1), une retenue est anticipée quelque soit la valeur de la première ligne (y0=oouy0=1). 2908905 26 5. Procédé selon la revendication 1, caractérisé en ce que la première approximation est donnée par U n = / 0 / 0.x n les formules : nommé EI2 R,,= / I / 0 xnû1O+ 1 5 avec . Y =OO+ y =y et Y1=y0oy 6. Procédé selon la revendication 5, caractérisé en ce que en réexprimant en fonction de En_I il vient : U~=Y1•Y(D E Rn= Y 1-(E,, E 10 avec les hypothèses d'anticipation de retenue suivantes : Si les deux lignes ne sont pas nulles (y0=lety1 = 1) , une retenue est anticipée 7. Procédé selon la revendication 1, caractérisé en ce que la première approximation est donnée par nommée E' 12 15 les formules : U,,_Y0 Y xn Rn = Y ,..y y 1•x wû1 nommé EI3 8. Procédé selon la revendication 3, caractérisé en ce que en réexprimant la première approximation en fonction de Y I ,Y 0,En ,E n û1 la première approximation est donnée par les formules : U =1oE o _ (E1nO+E 0n- I) Rn nommée 20 E'I3 avec les hypothèses d'anticipation de retenue suivantes : Quelques soient les valeurs de Y0etY1' une retenue est anticipée. 2908905 27 9. Procédé selon la revendication 1, caractérisé en ce que la première approximation est donnée par la formule . U = Y,Y O+ Yä x 5 10. Procédé selon la revendication 1, caractérisé en ce que la première approximation est donnée par la formule . nommée EI4 o _ Rn Y, -xn nommée EI5 Un = Y, Y(Y Y •xä O+ Rn Y,-Y YYOxnù1 11. Procédé selon la revendication 1, caractérisé 10 en ce que la première approximation est donnée par la formule : 12. Procédé selon la revendication 1, caractérisé en ce que la première approximation est donnée par la 15 formule . 13. Procédé selon la revendication 1, caractérisé en ce que la première approximation est donnée par la formule . 14. Procédé multiplieur selon l'une quelconque des revendications précédentes, caractérisé en ce que la première série d'équations s'écrit Un = Y,•Y@O+ Yo•xn Rn = Y Q+Y,•xn nommée EI6 1U0,, = Yo.xn Rn=.l ,•Y1,~/,xn nommée EI7 20 U = Y O+ +O Yä Yo.x nommée EI8 Ri', YoOYlYoxn 2908905 U,=U,1oR;,l Y1+I n-I n nommé EEP1 =(xneY;+I .Y;+I et Y,+1=Y;eY;+I 15. Procédé multiplieur selon l'une quelconque 5 des revendications 1 à 13, caractérisé en ce que la première série d'équations s'écrit {U',, =U',, ~Rn ~Y1+I nommé EEP2 16. Procédé multiplieur selon l'une quelconque des 10 revendications précédentes, caractérisé en ce que la deuxième série d'équations s'écrit . [Un= nommée EP1 Rn+I (u:'u:,)R;:' n 17. Procédé multiplieur selon l'une quelconque des revendications précédentes, caractérisé en ce que 15 la deuxième série d'équations s'effectue avec des additionneurs de type Carry-Look-Ahead. 18. Multiplieur permettant de multiplier des signaux d'entrée comportant un premier (X) et un second nombres (Y) binaires respectivement de N et de 20 M bits, à savoir : X xN.2N +x + +x".2" + +x1.21 +x02c y .2" + .2"~-I + + .2" + + .2' + .20 =Y Yy y Yo définissant une matrice caractérisé en ce que il comporte 28 Rn+I = (u:I R;-1 E ;+] (;+I Y o U /7_1 `-II U; n-2 ~ R n-I I avec +I O 1~0 I (u:' 0 1 1 Rn+, =Y,+I R ' En+i u Y;+,~Rn ' Uä_1 2908905 29 des moyens de calcul pour transformer la matrice initiale [E,=xä-,•y,I en une matrice . [En= ( Y,)-(Y; Y;) _ (x e Y;).Y; avec Y c 5 des moyens d'estimation initiale (MEOi) agencés pour fournir une première approximation U et R +I de la somme et de la retenue des deux premières lignes yo et yl sur toute la longueur N desdits nombres, comprenant N blocs d'estimation (MIi) montés en 10 parallèle, chaque bloc d'estimation étant apte à effectuer lesdites sommes et lesdites retenues , des moyens d'estimation /propagation (MEEPi) agencés pour réaliser successivement l'addition des lignes suivantes jusqu'à la dernière non nulle, en 15 fonction d'une première série d'équations de propagation déterminée, comprenant des blocs d'estimation/propagation (MEPi) monté en cascade, chaque bloc d'estimation/propagation étant apte à effectuer lesdites sommes et les dites retenues, R1-1 20 et des moyens de propagation (MPi) des retenues n sur les lignes y1+i. nulles en fonction d'une deuxième série d'équations de propagation déterminée. 19. Multiplieur selon la revendication 10, caractérisé en ce que les moyens de propagation (MPi) R i-1 des retenues ä comprennent des blocs d'estimation en cascade inverse, chaque bloc d'estimation étant apte à effectuer lesdites retenues. 20. Multiplieur selon la revendication caractérisé en ce que les moyens de propagation 18, (MPi) 2908905 R`ù1 des retenues ä comprennent des additionneurs de type Carry-Look-Ahead. 21. Multiplieur selon la revendication 18, caractérisé en ce que en ce que les moyens agencés 5 pour effectuer la première approximation comportent des moyens pour calculer U comprenant une porte n logique de type OU EXCLUSIF > apte à recevoir en entrée d'une part le bit correspondant à yl et d'autre part un bit issu d'une première porte logique 10 ET > réalisant le produit des bits X,, et 170, et des moyens pour calculer la retenue R comprenant une deuxième porte logique de type ET > apte à recevoir en entrée les bits correspondant à yl , YO et X, 15 22. Multiplieur selon l'une quelconque des revendications 18 à 20, caractérisé en ce que les moyens agencés pour effectuer la première approximation mettent en oeuvre les formules : nommées EI1 20 avec y l = y f y, 23. Multiplieur selon l'une quelconque des revendications 18 à 20, caractérisé en ce que les moyens agencés pour effectuer la première approximation mettent en oeuvre les formules : U:=Y, Yo•xä Rä = Y, Y0•xn o _ Un=Y,yosy0'xä nommées EI2 25 R ä = Y I.Y o. x äù1O+1 v O U" _ / 0 ypxn R,,= y I formules : nommées EI3 xn 1 2908905 31 avec . yo=0O+y=yo et Y=y11O y 24. Multiplieur selon l'une quelconque des revendications 18 à 20, caractérisé en ce que les moyens agencés pour effectuer la première 5 approximation mettent en oeuvre les 25. Multiplieur selon l'une quelconque des revendications 18 à 24, caractérisé en ce que les moyens d'estimation /propagation (MEEPi) agencés 10 pour réaliser successivement l'addition des lignes yin suivantes jusqu'à la dernière non nulle, mettent en oeuvre la première série d'équations suivantes : û ;-I O ;+I) O /-I O -I ;-I ;-~ (DEI Y;+l (U n-1 U n-2) R nù1 nommées EEP1 15 avec E n = (r,, y;+1).Y;+1 et Y+1 = y O y1+1 26. Multiplieur selon l'une quelconque des revendications 18 à 25, caractérisé en ce que les moyens d'estimation /propagation (MEEPi) agencés pour réaliser successivement l'addition des lignes 20 y suivantes jusqu'à la dernière non nulle, mettent i+1 en oeuvre la première série d'équations suivantes : = 1 O R Uä Un ä O Y;+. R n+1 = Y;+. R Eä+1 Uä Y+1.R (u nommées EEP2 27. Multiplieur selon la revendication 26, 25 caractérisé en ce que les moyens d'estimation {u, =U;,1 R;,'eY+1 n-1 R n+1 U R n n U 2908905 32 /propagation (MEEPi) agencés pour réaliser successivement l'addition des lignes y suivantes jusqu'à la dernière non nulle comportent des moyens pour calculer Un comprenant une 5 première porte logique de type OU EXCLUSIF apte à recevoir en entrée d'une part le bit correspondant à R iù1 n etd'autre part le bit correspondant à Y+1 , la dite porte délivrant un signal à l'entrée d'une deuxième porte du type OU EXCLUSIF pour, en 10 combinaison avec une deuxième entrée correspondant au i bit calculé précédemment U'ù' n donner le signal U Ri et des moyens pour calculer Rn+l comprenant une troisième porte de type OU EXCLUSIF INVERSE apte à recevoir en entrée d'une part le bit correspondant à 15 X l et d'autre part le bit correspondant à y ladite porte délivrant un signal à l'entrée d'une quatrième porte du type OU EXCLUSIF recevant par ailleurs en deuxième entrée le bit correspondant à i1 Un , bit alimentant simultanément en parallèle une 20 cinquième porte logique du type OU EXCLUSIF recevant par ailleurs en deuxième entrée le bit u i-1 correspondant à , les signaux de sortie desdites quatrième et cinquième portes logiques du type OU EXCLUSIF attaquant 25 chacun respectivement une première et une seconde porte logique ET , la seconde porte ET réalisant le produit logique avec les bits issus de 2908905 33 la première porte du type OU EXCLUSIF et Y+1 et la première porte logique ET réalisant le produit logique avec les bits issus de ladite première porte du type OU EXCLUSIF et li+l , 5 les bits issus des deux portes ET consti-:uant les entrées d'une sixième porte du type OU EXCLUSIF propre à délivrer le bit correspondant à la valeur de i Rn+1 28. Multiplieur selon l'une quelconque des 10 revendications 18 à 26, caractérisé en ce que les moyens de propagation (MPi) des retenues n sur les lignes yl+?. nulles en fonction d'une deuxième série d'équations de propagation mettent en oeuvre Un Rn Rn+,=(u:'u1)R: 15 29. Multiplieur selon la revendication 28, caractérisé en ce que les moyens de propagation (MPi) les formules : nommées EP1 des retenues R1-1 nsur les lignes yl+i. nulles en 20 fonction d'une deuxième série d'équations de propagation nulle comportent des moyens pour calculer Un comprenant une première porte logique de type OU EXCLUSIF apte à recevoir en entrée d'une part le bit correspondant à Ri-1 n et d'autre part le bit correspondant à LTi ,, et des moyens pour calculer R,1+1 comprenant une 2908905 34 deuxième porte logique du type OU EXCLUSIF recevant en première entrée la valeur de bit i 1 Uä et en deuxième entrée le bit correspondant à correspondant U'-' n-1pour générer un signal qui 5 attaque en combinaison avec le bit correspondant R-1 n une porte logique ET propre à donner la i valeur de Rn+l