Brevet FR2628232A1 — publié le 19890908

(J RÉPUBLIQUE FRAN AISE Q N de -publication: 2 628 232 (à n'utiliser que pour les INSTITUT NATIONAL commandes de reproduction) DE LA PROPRIÉTÉ INDUSTRIELLE D N d'enregistrement national 88 02867 PARIS () Int CI': G06 F 7/42. Qô DEMANDE DE BREVET D'INVENTION 'A1 Date de dépôt: 7 mars 1988. () Demandeur(s): ETAT FRANCAIS, représenté par le Mi- nistre Délégué aux Postes et Télécommunications Centre ) Priorité National d'Etudes des Télécommunications et MATRA- HARRIS-SEMICONDUCTEURS. - FR. @ Inventeur(s): Francis Jutand Luc Montperrus. N Date de la mise à disposition du public de la demande: BOPI " Brevets " n 36 du 8 septembre 1989. y Références à d'autres documents nationaux appa- rentés: rné Titulaire(s): ÀG Mandataire(s): Brevatome. Additionneur de type recursif pour calculer la somme de deux opérandes. @ L'invention concerne un additionneur de type récursif, pour calculer la somme de deux opérandes A et B formés respectivement de données binaires ai, a2,...a0 et b1, b2,..., b. Un additionneur ayant un niveau NH de récursivité et un ordre K, est noté ADKNN, et comporte selon l'invention: AL 5L AH BH - un premier additionneur ADKINH' d'ordre K-1 et de SE niveau NH-1 construit de façon récursive, recevant des opé- r'- randes AL et BL de poids faibles, et fournissant un bit COUT I \ mde retenue sortante et un opérande de sommation SH: I G de -- un deuxième additionneur ADPK_ H' d'ordre K-1 et de niveau NH-1 construit de manière récursive, recevant des H I I' opérandes AH et BH de poids forts, le bit COUT de retenue ADP I. sortante, et fournissant un opérande de sommation SH, un bit I COUP P de propagation de retenue, et un bit G de génération de L retenue; N N " - un sélecteur global de retenue SE recevant les bits G, P SL et COUT et fournissant un bit de retenue globale: w C ---NH = G + P.COUT Application à la fabrication intégrée des additionneurs de type récursif. NVente des fascicules à 'IMPRIMERIE NATIONALE, 27, rue de la Convention75732 PARIS CEDEX 15 IUL O Vente des fascicules à l'IMPRIMERIE NATIONALE, 27, rue de la Convention -- 75732 PARIS CEDEX 15 ADDITIONNEUR DE TYPE RECURSIF POUR CALCULER LA SOMMNE DE DEUX OPERANDES DESCRIPTION La présente invention concerne un additionneur de type récursif pour calculer la somme de deux opérandes. Cette invention s'applique au calcul de La somme de deux nombres de données binaires grace à des additionneurs constitués sous forme de circuits intégrés, notamment pour les systèmes de traitement de l'information dans lesquels ces additionneurs constituent l'un des opérateurs fondamentaux de traitement du signal. L'invention se classe dans la catégorie des additionneurs de type parallèle-parallèle. Ils permettent d'additionner deux opérandes A et B constituées respectivement de données binaires a1, a2,..., a et b, b,..., b. Le résuLtat n i 2n est fourni sous forme binaire parallèle. Généralement, un additionneur paraLLèle-paralLèle est constitué par une association complexe de séries d'additionneurs élémentaires connectés entre eux. Chaque additionneur élémentaire reçoit deux bits à additionner qui appartiennent à chacun des opérandes ou à des résultats intermédiaires effectués par d'autres additionneurs élémentaires du circuit complexe. Chaque additionneur fournit sur une sortie le résultat binaire d'une addition mais peut également fournir, sur deux autres sorties, deux bits dits respectivement de propagation et de génération. Le bit de propagation P fourni par un additionneur k ADk, de rang k (fulI adder), dans une rangée comportant K additionneurs reliés en série (1 l'opérateur OU exclusif. a et b désignent respectivement les bits d'entrée de k k rang k, à additionner. Si l'on désigne par addition locale, La sommation effectuée par chaque additionneur élémentaire AD d'une rangée, k il s'agit d'additionner deux bits a et b appartenant aux deux k k opérandes A et B. Trois cas peuvent se présenter: 1) si a =b =0 aucune retenue n'est générée par k k l'additionneur élémentaire et si une retenue vient des additionneurs de rang inférieur à k.qui effectuent des additions de bits de poids plus faible, cette retenue est aLors "piégée" k par l'additionneur AD. Alors, le bit sk de poids 2 de la somme k est un 1 logique; 2) si a =0 et b =1 ou a =1 et b.=0, alors aucune retenue n'est générée localement, mais une retenue venant des poids faibles est propagée vers l'additionneur de rang k+1, et S =0. Sinon s reste égal à 1; k k 3) si a =b =1, une retenue est générée localement par k k l'additionneur AD et cette retenue est transmise vers k l'additionneur de rang k+1 supérieur. De la mime manière, la fonction logique de génération 9, pour l'additionneur AD de rang k obéit à la relation: k k g. = a.b k k k Cette relation de multiplication logique correspond à la fonction logique ET. La fonction génération G d'un additionneur AD k k correspond à un bit de sortie de cet additionneur, égal à 1, à chaque fois qu'une retenue apparait lors de l'addition. La fonction de propagation P correspond à un bit de sortie de cet k additionneur, égal à 1, quand une retenue provenant d'un additionneur du rang précédent (k-1), doit être propagée à l'additionneur de rang suivant (k+1). Dans ces conditions, la relation de base relative à la retenue rk calcuLée par un additionneur parallèle rapide de rang k, s'écrit: r gk + (P.r) k 9 k kk k-I Dans cette relation le signe + désigne l'opération Logique OU INCLUSIF. r est la retenue produite par l'addition des k premiers bits des k deux opérandes. Cette relation est valable quel que soit k. Le calcul finaC de la somme S est effectué par un k simple opérateur OU EXCLUSIF: k k k-1 Dans une série de k additionneurs, on désignera par rlIN la retenue entrante appliquée au premier additionneur de la série, et par rKOUT la retenue sortante du dernier additionneur de la série. Des additionneurs parallèles, fonctionnant sur ce principe et qui utilisent des séries d'additionneurs élémentaires de type 'additionneur complet" ("fuLl adder") sont décrits par exemple dans les revues suivantes: - la revue IEEE TRANSACTIONS ON COMPUTERS - volume C31 - nO3 Mars 1982 - pages 260 à 264 - dans un article intitulé "Regular lay out for paralLel adders"; - la revue IEEE - 1983 - pages 10 à 16-- dans un article intitulé "Comparison of ALU structures for VLSI technology"; - le livre intitulé "Circuits Logiques de traitement numérique de l'information" - édition CEPADUES - ECOLE NATIONALE SUPERIEURE DE L'AERONAUTIQUE ET DE L'ESPACE - 1979 - pages 185 à 289. Dans ces revues sont décrits des circuits complexes d'additionneurs élémentaires permettant d'effectuer une somme de deux opérandes binaires. Le problème essentiel posé par les additionneurs complexes constitués de "ful adders" provient essentiellement du fait que des retenues sont générées par certains des additionneurs et que certaines retenues doivent Stre propagées. En effet, toute génération ou La propagation d'une retenue nécessite des connexions complexes -et des circuits supplémentaires; dans La réalisation d'un additionneur sous forme de circuit intégré, ces connexions et ces circuits supplémentaires affectent non seulement La surface du circuit intégré mais aussi ses performances. Parmi les additionneurs rapides de type parallèle, l'un des plus utilisés est l'additionneur à "sélection de retenue" ("carry select adder" en anglais). Dans ce type d'additionneur qui est constitué par au moins une série d'additionneurs élémentaires complets (full adders) on effectue deux calculs de retenue en parallèle. Le premier calcul est effectué aven l'hypothèse d'une retenue entrante égale à 1, tandis que le second calcul est effectué avec l'hypothèse d'une retenue entrante égale à zéro. On évite ainsi, lors d'une addition, l'obligation de connaître préalablement la retenue provenant des bits précédents pour pouvoir effectuer l'addition des bits suivants. Lorsque la retenue est effectivement connue, dans le temps nécessaire aux calculs d'addition effectués.dans chacune des hypothèses, on sélectionne le résultat correspondant à la bonne hypothèse. Ce type d'additionneur, s'il a pour inconvénient de doubler une partie du matériel, puisqu'on en effectue deux calculs en parallèle avec des hypothèses différentes, a pour avantage d'augmenter la vitesse de calcul. En effet, lorsque la retenue entrante dans le premier additionneur de la série n'est pas connue, il est possibLe de gagner du temps grâce aux deux hypothèses mentionnées plus haut, en effectuant les calculs d'addition pendant le temps nécessaire à l'arrivée de la retenue entrante à l'entrée de la série d'additionneurs. D'une façon générale, les additionneurs parallèles peuvent être de deux types: les additionneurs de type "itératif" et ceux de type "récursif". Dans ces deux types d'additionneurs, la propagation de la retenue est le problème essentiel. Dans un additionneur de type itératif, on construit un additionneur pour n bits, en ajoutant une cellule élémentaire (additionneur complet ou fuil adder), à un additionneur comprenant déjà n-1 cellules élémentaires reliées en série. Cette structure traduit la relation de récurrence de l'addition. Pour augmenter la vitesse de propagation d'un additionneur de ce type, il est nécessaire d'optimiser un chemin unique de propagation de la retenue. L'exemple classique d'un tel type d'additionneur est l'additionneur de type Manchester à chaîne de propagation de retenue (Manchester carry chain). Dans un additionneur de type récursif, on subdivise un additionneur à n bits en deux additionneurs à n/2 bits. Dans ce type d'additionneur, le temps de propagation de la retenue est théoriquement Log(n)T, si T désigne Le temps de propagation pour une cellule élémentaire. Cette structure récursive est essentiellement utilisée dans des additionneurs utilisant des structures en arbre qui permettent de distribuer les informations nécessaires aux différentes cellules en un temps optimisé. Ce type d'additionneur est souvent qualifié d'additionneur à retenue anticipée (carry look ahead adder). D'une manière générale, les additionneurs de type itératif nécessitent moins de silicium pour leur fabrication, mais ils sont moins rapides que les additionneurs de type récursif qui eux, consomment beaucoup de silicium. Entre les solutions itératives et les solutions récursives, il existe des solutions intermédiaires connues qui sont en fait des solutions de compromis. Ces solutions de compromis utilisent à la fois l'aspect itératif de l'additionneur pour son faible encombrement et l'aspect récursif pour ses performances en vitesse. L'une de ces solutions connues de compromis est un additionneur de type à "sélection de retenue" (carry select. adder), optimisé. Cette solution consiste à découper l'addition en plusieurs tranches. Pour chacune de ces tranches on fait des hypothèses, comme indiqué plus haut, sur la retenue entrante dans chaque tranche. La retenue entrante dans chaque tranche est déterminée de proche en proche à t'aide d'une série de cellules qui effectuent l'opération logique g.r+p; dans cette relation, g est un bit qui indique s'itl y a ou non génération de retenue, r désigne un bit de retenue, et p est un bit qui indique s'il y a ou non propagation de la retenue. Ce type d'additionneur peut être qualifié d'additionneur de type g.r+p. L'additionneur dont la retenue entrante est égale à zéro a pour retenue sortante la retenue générée par la tranche, que l'on désigne par G. t L'additionneur dont la retenue entrante est égale à'1 a pour retenue sortante sa propre retenue calculée. Le bit de propagation est égal à 1 et est désigné par P quand il y a t propagation de la tranche. Si rIN désigne la retenue réelle qui entre dans une tranche, la retenue sortante rOUT est obtenue par l'opération logique rOUT=G +P.rIN. t t Les calculs sont effectués en parallèle dans les différentes tranches et l'optimisation d'un additionneur de ce type porte sur le nombre de bits que chaque tranche doit calculer pour rendre tous les chemins de propagation critiques, dans une structure d'additionneurs en arbre, de niveau hiérarchique prédéterminé. Les définitions concernant les chemins critiques, les structures en arbre et les niveaux hiérarchiques, sont données dans les revues précitées. Dans un additionneur à sélection de retenue optimisé, on peut augmenter progressivement le nombre de cellules élémentaires d'addition dans chaque. nouvelLe tranche, de sorte que le temps de calcul nécessaire à une tranche, soit égal à celui de la tranche précédente, augmenté du temps de sélection de la retenue. On obtient dans ce cas un additionneur à sélection de retenue optimisé. Une autre solution connue de compromis est l'utilisation d'un additionneur à saut de retenue (Carry Skip Adder). Ce type d'additionneur ressemble au précédent pour la propagation de la retenue. La différence avec l'additionneur précédent est que pour chaque tranche, on utilise un seul additionneur de type itératif (comportant plusieurs cellules élémentaires d'addition reliées en série) dont la retenue entrante est la retenue provenant de la cellule de sélection de retenue précédente. Il faut cependant, pour chaque tranche, calculer la fonction de propagation pour commander la cellule de sélection correspondante. Le nom de cet additionneur vient du fait que la retenue peut être propagée plus vite, par une ligne parallèle aux additionneurs en série et qui est un chemin beaucoup plus rapide que celui qui traverse la série d'additionneurs. Cet additionneur présente un inconvénient par rapport au précédent: pour rendre tous les chemins critiques, aussi bien pour la somme à calculer que pour la retenue, il est nécessaire en allant des poids faibles aux poids forts de bits à additionner, d'augmenter La taille des tranches (c'est-à-dire le nombre d'additionneurs élémentaires en série dans chaque tranche), puis de diminuer cette taille à partir du milieu de l'additionneur. La diminution de la taille des tranches est en effet indispensable afin d'éviter que la retenue ne soit obtenue trop rapidement par rapport à la somme S. Pour l'additionneur à sélection de retenue (carry select adder) optimisé, la taille des tranches augmente en progression linéaire. Le temps de sélection de la somme varie dans l'hypothèse d'un temps de sélection égal à un temps de propagation à travers un Full-Adder. On dit de manière connue, que l'on calcule approximativement n(n+1)/2 bits en un temps nT, Z n /2 bits sont calculés en nT et n bits sont calculés en InT (T désignant le temps nécessaire au calcul de l'addition de deux bits de données). Pour l'additionneur à saut de retenue, optimisé (carry skip adder), la taille des tranches augmente en progression linéaire pour la première moitié des bits à additionner et décroît ensuite de la -mime manière. On dit, pour ce type d'additionneur, que l'on calcule approximativement n bits en un temps égal à 2'4-t. D'une façon générale ces deux solutions ont un comportement asymptotique en racine carrée de N, et si l'additionneur à saut de retenue optimisé est plus lent que l'additionneur à sélection de retenue optimisé, il est par contre moins coûteux en substrat servant à sa fabrication. Les additionneurs utilisant des solutions arborescentes (Carry Look Akead Adder par exemple), totalement itératives, occupent une surface importante qui croÂt en N logarithme de N (N étant le nombre de bits respectifs des données à additionner), tandis que les solutions totalement itératives sont très lentes. Les solutions optimisées, telles que L'additionneur à saut de retenue ou l'additionneur à sélection de retenue, sont-un compromis intéressant mais ne sont pas totalement satisfaisantes: elles ne permettent pas, tout en conservant une surface occupée proche de celle d'un additionneur à saut de retenue, d'atteindre la performance de vitesse d'un additionneur à sélection de retenue. L'invention a pour but de remédier à ces inconvénients et notamment de réaliser un additionneur occupant une surface voisine de celle d'un additionneur à saut de retenue, tout en présentant une performance en vitesse voisine de celle d'un additionneur à sélection de retenue. L'additionneur de l'invention présente, comme on le verra plus loin en détail, une nouvelle structure dite récursive, qui permet d'obtenir un facteur de mérite vitesse/surface particulièrement élevé. L'invention a pour objet un additionneur de type récursif, pour calculer la somme de deux opérandes A et B formés respectivement de données binaires a1, a2,...a et b, b2,... n 12 b de différepts poids, les opérandes A et B comprenant un n premier et un deuxième opérandes AL et BL formés respectivement par des données de poids faibles et un troisième et un quatrième opérandes AH et BH formés respectivement par des données de poids forts, caractérisé par le fait que pour un niveau NH de récursivité de l'additionneur (NH étant un nombre entier supérieur ou égal à 1) et pour un ordre K de cet additionneur (K étant un entier définissant un nombre de cellules élémentaires d'additions dans un additionneur de niveau 1), cet additionneur NH étant noté AD, étant construit de façon récursive et K comportant NH - un premier additionneur ADK1 d'ordre K-1 et de K-i niveau NH construit de faon récursive et comportant des entrées recevant respectivement les premier et deuxième opérandes AL et BL de poids faibles, et une première et une deuxième sorties fournissant respectivement un opérande de sommation SL des premier et deuxième opérandes AL et BL de poids faibles, et un bit de retenue sortante COUT, pour la sommation effectuée; - un deuxième additionneur ADPK_1 d'ordre K- 1 et de niveau NH-1 construit de manière récursive et comportant des entrées recevant respectivement Les troisième et quatrième opérandes AH et BH de poids forts, une entrée (CIN) reliée à la deuxième sortie (COUT) du premier additionneur, et une première, une deuxième et une troisième sorties fournissant respectivement un opérande de sommation SH des troisième et quatrième opérandes - AH et BH de poids forts, un bit P de propagation de retenue correspondant à cette sommation et un bit G de génération de cette retenue; - un sélecteur global de retenue (SE) comportant trois entrées (C, G, P) respectivement reliées à la deuxième sortie du premier additionneur et aux deuxième et troisième sorties du NH deuxième additionneur, et une sortie fournissant un bit C de - OUT retenue globale sortante résultant de la sommation logique: NH C = 6 + P.COUT OUT SeLon une autre caractéristique de L'invention, le NH-1 deuxième additionneur ADP est construit de manière K-1 récursive et comporte: NH-1 - un troisième additionneur ADP d'ordre K-2 et K-2 de niveau NH-2 comportant des entrées recevant respectivement des opérandes AHL et BHL constitués respectivement de données de poids faibles des troisième et quatrième opérandes AH et BH, et une entrée (CIN) de retenue entrante reliée à la deuxième sortie du premier additionneur pour recevoir le bit (COUT) de retenue sortante de ce premier additionneur, et des première, deuxième et troisième sorties pour fournir respectivement un opérande (SHL) de sommation des opérandes AHL et BHL reçus en entrée, un bit (G1) de génération de retenue et un bit (P1) de propagation de retenue de la sommation effectuée; - un premier sélecteur intermédiaire de retenue (SES) comportant trois entrées respectivement reliées à la deuxième sortie (COUT) du premier additionneur, à la deuxième sortie (G1) du troisième additionneur et à la troisième sortie (P1) du troisième additionneur, ce premier sélecteur de retenue fournissant sur une sortie un bit C OUT de retenue sortante obéissant à la sommation logique: C OUT = G1 + P1.COUT I NH-2 - un quatrième additionneur ADP d'ordre K-2 et K-2 de niveau NH-2 comportant des entrées recevant respectivement des opérandes AHH et BHH constitués respectivement de données de poids forts des troisième et quatrième opérandes, une entrée (C2IN) de retenue entrante reliée à la sortie du premier sélecteur (SES) pour recevoir le bit de retenue sortante (CLOUT) de ce sélecteur et des première, deuxième et troisième sorties fournissant respectivement un opérande (SHH) de sommation des opérandes (AHH et BHH) reçus en entrée, un bit (G2) de génération de retenue, et un opérande (P2) de propagation de retenue de la sommation effectuée; - un deuxième sélecteur intermédiaire (SEC) de génération de retenue, comprenant trois entrées respectivement reliées à la deuxième sortie (G1) de génération de retenue du troisième additionneur à la deuxième sortie (G2) de génération de retenue du quatrième additionneur et à la troisième sortie (P2) de propagation de retenue du quatrième additionneur, ce deuxième sélecteur fournissant sur une sortie correspondant à la troisième sortie du deuxième additionneur, le bit (G) de génération de retenue de ce deuxièmee additionneur, résultant de la sommation logique: G = 62 + P2.G1 - une porte logique de type "ET" à deux entrées respectivement reliées à la troisième sortie (P2) de propagation du quatrième additionneur et à la troisième sortie (P1) de propagation du troisième additionneur, cette porte logique fournissant sur une sortie correspondant à la deuxième sortie du deuxième additionneur, le bit de propagation P de sortie de ce deuxième additionneur, résultant de La multiplication logique p=P1.P2. SeLon une autre caractéristique, l'additionneur ADP. K d'ordre K et de niveauN 1, obtenu de manière récursive, à partir NH-1 de l'additionneur ADP d'ordre K-1 et de niveau NH-1, K-1 capable d'additionner deux à deux des bits d'une tranche de données a1, a,1,,..., a i+j, a i+K, et bi, bi+i,..., bi+j, bi+K des deux opérandes A et B (i étant compris entre I et n), comporte: - une succession d'au moins K cellutes éLémentaires d'addition, de type "additionneurs complets", chaque cellule (FA) de rang i+J comportant deux entrées pour recevoir i + J respectivement une paire de bits tels que (a i+j, bi+j), une entrée de retenue entrante pour recevoir un bit de retenue sortante (r) fourni par une première sortie de retenue i+J-1 sortante d'une ceLlule éLémentaire précédente FA+ _ de Ladite succession, l'entrée de retenue entrante. de La première celLuLe élémentaire de ladite succession recevant un bit de valeur 0 et la sortie de retenue sortante de La dernière cellule élémentaire de ladite succession fournissant un bit (G) de génération de retenue pour Ladite succession, chaque ceLttule élémentaire (FA) comportant en outre une deuxième et une troisième sorties i+J fournissant respectivement un bit de sommation LocaLe s et un t+J bit de propagation pi+, les bits r+j, si+ et pi+ résultant des opérations logiques: r = (r.p )+(a.b) l+J i+J-l i+J i+J M+J p a b i+J i+J i+J s =a 0b (Dr i+J +J + i+J1 dans lesquelles. est l'opérateur "ET", et + est L'opérateur "OU INCLUSIF" et O est l'opérateur "OU EXCLUSIF"; - un ensemble Logique (CP) de calcul de la propagation P de la retenue pour cet additionneur comportant des entrées -2- 2628232 respectivement reliées aux troisièmes sorties (pi+) de *1+J propagation des cellules élémentaires pour fournir sur une sortie un bit pi+K de propagation pour cet additionneur ADP résultant K de l'opération logique: r i+k i+k 'Pi+k-1 i+l'Pi ou P = P i+k i+k-'1 i+k - un ensemble Logique (CS) de calcul de sommation comportant des entrées respectivement reliées aux deuxièmes sorties de sommation des cellules élémentaires, à des sorties p de propagation de l'ensemble de propagation (CP) fournissant i+ J des bits p =p i l.p i+j, et une entrée de retenue entrante CIN reliées à la sortie de retenue sortante d'un additionneur précédent, cet ensemble de calcul de sommation (CS) fournissant respectivement sur des sorties des opérandes de sommation S., 1 1 15..., S,..., Si+K calculés par l'additionneur ADP et i+K K résultant de l'opération logique: Si+J = si+j (Pi+ l.CIN) avec P =1 i-1 1 Selon une autre caractéristique, l'additionneur AD K d'ordre K et de niveau 1 est constitué comme un additionneur ADP d'ordre K et de niveau 1 dont l'entrée de retenue entrante K (CIN) reçoit un bit (CIN) égal à O. Les caractéristiques et avantages de l'invention ressortiront mieux de la description qui va suivre, donnée en référence aux dessins annexes dans lesquels: - la figure 1 représente schématiquement, un additionneur NH AD de niveau NH et d'ordre K, à structure récursive, conforme K à l'invention, - la figure 2 représente schématiquement l'un des NH-1 additionneurs ADP d'ordre K-1 et de niveau NH-1 à K-1 structure récursive, appartenant à l'additionneur à structure récursive de la figure 1, - la figure 3 représente schématiquement un additionneur ADP d'ordre K et de rang 1, appartenant à l'additionneur à structure récursive de lKa figure 1, structure récursive de la figure 1, la figure 4 représente schématiquement un additionneur 1. 1 AD d'ordre K et de rang 1 déduit de L'additionneur ADP de la K K figure 3. NH L'additionneur AD à structure récursive représenté K schématiquement sur ta figure I présente un niveau NH de récursivité et un ordre K. L'ordre K correspond au nombre de cellules élémentaires d'addition ou additionneurs complets (en anglais "FULL ADDERS") que comprend un additionneur de niveau NH=1. Le niveau NH (NH étant un entier) est en fait le nombre de récursivités qu'il est nécessaire d'effectuer pour construire un additionneur présentant une structure de niveau NH, à partir d'une structure de niveau NH-1, et ainsi de suite jusqu'au niveau 1. De tels additionneurs présenteht une structure en arbre dont les différentes branches comprennent des séries d'additionneurs complets. NH L'additionneur AD représenté sur cette figure permet K de calculer la somme de deux opérandes A et B formés respectivement de données binaires a1, a, a, a et b, b, b ai a' n 12 1 b (avec 1 de poids forts. NH L'additionneur AD comporte de façon récursive, K NH un premier additionneur ADKI, d'ordre K-1 et de niveau NH, construit luimême de façon récursive. Ce premier additionneur comporte des entrées qui reçoivent respectivement les premier et deuxième opérandes AL et BL de poids faibles. Une première sortie de ce premier additionneur fournit l'opérande SL résultant de La sommation des opérandes AL et BL reçus en entrée. Une deuxième sortie de ce premier additionneur fournit un bit COUT de retenue sortante, résultant de la sommation effectuée. NH L'additionneur AD comporte aussi un deuxième NH-1 K additionneur ADP d'ordre K-1 et de niveau NH-1 construit K-1 lui aussi de manière récursive. Ce deuxième additionneur comporte des entrées quireçoivent respectivement les troisième et quatrième opérandes AH et BH constitués par Les données de poids forts. Une entrée CIN de cet additionneur, dite de "retenue entrante" est reliée à la deuxième sortie du premier additionneur NH AD pour recevoir le bit COUT. de retenue sortante de ce K-1 NH-1 premier additionneur. À Ce deuxième additionneur ADP K-1 comporte aussi une première sortie qui fournit un opérande SH de sommation des troisième et quatrième opérandes AH et BH des données de poids forts reçues en entrée. Une deuxième sortie de ce deuxième additionneur fournit un bit P de propagation de la retenue tandis qu'une troisième sortie fournit un bit G de génération de la retenue résultant de la sommation. NH Enfin, L'additionneur AD comporte un sélecteur de K retenue SE. Ce sélecteur de retenue comporte trois entrées 1, 2, 3 qui sont respectivement reliées à la deuxième sortie du premier NH additionneur AD, et aux deuxième et troisième sorties du K-i NH-1 deuxième additionneur ADP1 pour recevoir respectivement les K-1 bits COUT, P et G. Ce sélecteur de retenue fournit sur une NH sortie, un bit de retenue globale de sortie C de NH OUT l'additionneur AD considéré. K Ce bit de retenue globale sortant résulte de la NH sommation logique COUT =G+P.COUT effectuée par le sélecteur SE OUT et dans laquelle le signe + désigne un "OU INCLUSIF" et le signe "." un "ET" logique. La figure 2 repésente schématiquement et de manière NH-1 plus détaillée le deuxième additionneur ADP 1 d'ordre K-1 et K-i de niveau NH-1 de la figure 1. Cette figure permet de mieux comprendre la récursivité de la structure de l'additionneur de la NH-1 figure 1. Le deuxième additionneur ADP1 qui est représenté K-1 sur la figure 2 est lui mime construit de manière récursive et comporte un troisième additionneur noté ADPK, d'ordre K-2 K-2 et de niveau NH-2. Ce troisième additionneur comporte des entrées qui reçoivent respectivement des opérandes AHL et BHL constitués respectivement de données de poids faibles contenues dans les troisième et quatrième opérandes AH et BH. Une entrée CIN de retenue entrante de ce'troisième additionneur et qui est aussi NH-1 L'entrée CIN du deuxième additionneur ADP décrit plus K-1 haut, est reliée à la deuxième sortie du premier additionneur NH AD 1 pour recevoir Le bit COUT de retenue sortante de ce K-i premier additionneur. NH-1 Le troisième additionneur ADP comporte des K-Z première, deuxième et troisième sorties qui fournissent respectivement un opérande SHL de sommation des opérandes AHL et BHL reçus en entrée, un bit 61 de génération de retenue sortante et un bit P1 de propagation de retenue sortante de la sommation effectuée par ce troisième additionneur. NH-I Le deuxième additionneur ADP comporte aussi un K-1 premier sélecteur de retenue intermédiaire SES qui comporte trois entrées. Ces trois entrées sont respectivement reliées à la NH deuxième sortie du premier additionneur AD et à la deuxième K-1 NH-1 et à la troisième sorties du troisième additionneur ADP K-Z pour recevoir respectivement Les bits COUT, 61 et P1. Ce premier sélecteur SES de retenue intermédiaire fournit sur une sortie, un bit C10UT de retenue sortante pour la sommation effectuée par Le NH-I troisième additionneur ADP. Ce bit ClOUT résulte de la K-2 sommation Logique: ClOUT = G1+P1.COUT effectuée par Le premier sélecteur intermédiaire SES. Comme précédemment, Le signe + désigne un "OU INCLUSIF" et le signe "." un "ET" logique. N- Enfin, le deuxième additionneur ADP comporte un NH-2 K-1 quatrième additionneur ADP 2 d'ordre K-2 et de niveau NH-2, K-Z un deuxième sélecteur intermédiaire SEC et une porte Logique "ET" de sortie. Le quatrième additionneur comporte des entrées recevant respectivement des opérandes AHH et BHH constitués respectivement de données de poids forts des troisième et quatrième opérandes AH et BH décritsNH lus haut. Une entrée C2IN du quatrième additionneur ADP est reLiée à la sortie du premier k-235 sélecteur intermédiaire SES pour recevoir e bit de retenue sélecteur Intermédiaire SES pour recevoir Le bit de retenue 16 2628232 sortante ClOUT fourni par ce premier sélecteur intermédiaire. Le quatrième additionneur comporte aussi des première, deuxième et troisième sorties qui fournissent respectivement un opérande SHH de sommation des opérandes d'entrée AHH et BHH, un bit G2 de génération de retenue et un bit P2 de propagation de retenue pour la sommation effectuée par ce quatrième additionneur. Le deuxième sélecteur intermédiaire SEC fournit un bit de retenue G, qui est Le bit de retenue sortante du deuxième NH-1 additionneur ADP N. Le deuxième sélecteur SEC comporte trois K-1 entrées qui sont respectivement reliées à La deuxième sortie de NtH-1 génération du troisième additionneur ADP 2 à La deuxième K-2 NH-2 sortie de génération du quatrième.additionneur ADPK2, et à K-2 La troisième sortie de propagation du quatrième additionneur, pour recevoir respectivement Les bits G1, G2 et P2. Ce deuxième sélecteur intermédiaire SEC, fournit sur une sortie de génération de retenue, qui est aussi La deuxième sortie du deuxième NH-1 additionneur ADPK1, Le bit G de génération de retenue. Ce K-i' bit résulte de la sommation logique G=G2+ P2.G1 effectuée par le deuxième sélecteur SEC et dans laquelle Le signe + désigne L'opération Logique "OU INCLUSIF" et Le signe "." désigne l'opération Logique ET. La porte Logique de sortie notée ET comporte deux S entrées qui sont respectivement reliées aux troisièmes sorties NH-1 NH-2 des troisième et quatrième additionneurs ADP et ADP K-2 K-2 pour recevoir respectivement Les bits de propagation P1, P2. Cette porte Logique fournit sur une sortie qui correspond à la deuxième sortie de propagation du deuxième additionneur NH-1 ADPK1, Le bit de propagation P. Ce bit résuLte de La multiplication Logique P=P1.P2. La figure 3 représente schématiquement L'additionneur ADP d'ordre K et de niveau 1. Cet additionneur est obtenu de K NH-1 manière récursive à partir de L'additionneur ADPK1 d'ordre K-i K-1 et de niveau NH-1. IL permet d'additionner deux à deux des bits d'une tranche de données ai, a +,..., a +,...a +, et 17 2628232 b b 1...b J..bK d'une tranche de données des deux bi+l ' "i+j' '"i+K' opérandes A et B (i étant compris entre 1 et n). Cet additionneur comporte au moins K cellules élémentaires d'addition, de type "addditionneurs complets" (ou en anglais "Futll Adders"). Ces cellules sont représentées en FA, FA i+I,... FAi+,...FAK sur i1 i +J'' Ksu la figure. C'est ainsi que par exemple La celluLe FA comporte i deux entrées pour recevoir respectivement les bits a et b. De i j la mine manière, les bits a et b sont eux aussi appliqués à J J deux entrées de La cellule FAi j, tandis que les bits a et b i+j K K sont appliqués à deux entrées de la cellule FAi+K. Chaque cellule élémentaire d'addition comporte aussi une entrée de retenue entrante pour recevoir un bit de retenue sortante fourni par une première sortie de retenue sortante d'une cellule d'addition précédente, de la succession de cellules. C'est ainsi que la cellule ou additionneur complet FA comporte À t+J une entrée E qui reçoit un bit de retenue entrante r i +J i+J-1 provenant d'une première sortie de l'additionneur FA i+J-1 précédent (non représenté sur la figure). De La mime manière, une entrée Ei+2 de l'additionneur FA, reçoit un bit de retenue sortante ri d'une première sortie de l'additionneur précédent FA i+. Comme on le verra plus loin en détail, l'entrée E. de i retenue entrante du premier additionneur FA de la succession i reçoit un bit de valeur 0, tandis que la sortie de retenue sortante de la succession fournit un bit r =G de génération de i+K retenue pour la succession d'additionneurs. Chaque cellule élémentaire telle que FA comporte I +J- aussi une première et une deuxième sorties qui fournissent respectivement un bit de sommation locale s et un bit de I+J propagation locale P -De façon connue, pour Les cellules d'additionneurs complets ou FuLL Adders, Les bits piJ ri J si+J résultent des i+j, i+i+J opérations logiques suivantes: p a G b i+J i+J-1 i+J r (r =.p) + (a.b) i+J i+J-1 i+J i+J i+J 18 2628232 s =:a { b O r i+J i+J i+J i+J-1 dans ces opérations, '. désigne l'opérateur "ET", est l'opérateur "OU EXCLUSIF" et + est l'opérateur "OU INCLUSIF". L'additionneur ADP représenté sur la figure comporte K aussi un ensemble logique CP de calcul de la propagation de la retenue pour cet additionneur. Cet ensemble comporte des entrées qui sont respectivement reliées aux deuxième et troisième sorties des cellules élémentaires FA, FA,... FA+J,... FA. Cet i i+ 1 i+'i' i+K ensemble reçoit donc les bits de sommations locales si, 5si+1' si+J,... si+K, et les bits de propagation locales p' Pi+l ' ' Pi+K' ''' Pi+K' Il fournit sur sa sortie P, un bit P. =K de propagation de la retenue, pour cet additionneur ADP. Ce bit K résulte de l'opération logique: P =p......p p i+K i+K i+K-1 i+1 i ou encore P = P p i+K i+K-1 i+K Relation dans laquelle le signe "." désigne l'opérateur logique "ET". L'ensemble de calcul de propagation CP comporte des portes logiques de type "ET" notées ET i+, ET,+2... ET sur i+K la figure. Chacune de ces portes comporte deux entrées. Les deux entrées de la première porte ET sont respectivement reliées i +1 aux sorties de propagation pi et p+ de la première paire de cellules FA., FA. La porte ET2 comporte deux entrées qui i i+1 i+2 sont respectivement reliées à la troisième sortie de propagation p2 de La cellule FA et à La sortie de La porte ET Pi+2 d aclueFi+2 t lasrie del ot +1 précédente. De la méme manière, la porte ET comporte deux i +K entrées qui sont respectivement reliées à la troisième sortie de propagation de la cellule FA et à la sortie de la porte i +K ET+K1 précédente. i+K-1 La porte ET par exemple fournit donc un bit it+2. P =Pi.Pi2 et la porte ETi+K fournit un bit P =P +. p. i+2 î+l i+2 K i+K i+K-1 i+K D'une manière générale, on a P =P.p L'additionneur 1 i+J i+J-l i+J ADP comporte aussi un ensemble logique CS de calcul de K sommation, qui fournit sur des sorties, des opérandes S, S 19 2628232 S.+J .. Si+K de sommation des données binaires reçues sur les premières entrées de l'additionneur. Cet ensemble comporte des entrées qui sont respectivement reliées aux deuxièmes sorties s, s..., si+J,..., si+K des cellules élémentaires FA, À FA i+,..., FAi+ J,..--., FA i+K Cet ensemble comporte aussi des entrées qui sont respectivement reliées à des sorties de propagation P+1, P+2,..., P+K de l'ensemble de calcul de propagation CP. Ces sorties sont celles des portes ET des moyens de calcul CP qui fournissent des bits de propagation, de la forme Pi+J=P +J.Pj. La sortie de propagation p. de la première iJ i+J-1' i+J, 1 cellule FA est reliée à l'une des entrées du moyen de calcul CS, i car P =p. Cet ensemble de calcul-de sommation CS comporte aussi i., une entrée CIN de retenue entrante. L'ensemble de calcul de sommation CS fournit sur ses sorties, les opérandes de sommation des données (a., b), (a, - 1 i i+ b *... (ai+K, b +K) reçues en entrée. i+1) i + +K Cet ensemble permet d'effectuer l'opération logique: S = s + (Pi.CIN) en prenant P =1 i+J l+J i+J-1 i-1 L'ensemble CS de calcul de sommation comporte des portes logiques M, M, ..., M, ..., M de type ET à deux i i+l i+J i+K entrées et des portes logiques OU,. OU,. O..., OUi+K de type "OU EXCLUSIF" à deux entrées. L'une des entrées de chaque porte M de type ET i +J reçoit le bit CIN de retenue entrante, tandis que l'autre entrée reçoit le bit de propagation P+ fourni par la sortie i +J correspondante de l'ensemble de calcul CP. Seule la première porte M reçoit sur une entrée d'une part le bit CIN de retenue entrante, et d'autre part, un bit de valeur 1, sur son autre entrée. (voir plus haut la relation p =1). i-1 Les entrées de chaque porte OU. sont respectivement reliées à la sortie de la porte Mi+J correspondante ainsi qu'à la deuxième sortie S de la cellule élémentaire correspondante. i+J C'est ainsi par exemple que la porte OU est reliée à la sortie i +1 2628232 de La porte M1 et à La sortie s51 de la cellule élémentaire i+1 i+ FA i+1 Cet ensemble de propagation fournit bien les opérandes de sommation tels que S =s + (P.CIN). i+J i+J i+J-1 Pour S2 par exemple, on a bien: i +2 s =s S. E (P.CIN) i+2 1si+2 (Pi+l CIN 1 Pour les additionneurs ADP qui traitent des tranches de bits de données de i à i+K (ou i appartient à 1, 2,.., n), le nombre i dépend de la position de l'additionneur ADP dans NH K l'arbre qui constitue l'additionneur AD. D'une manière 1 K générale, les additionneurs ADP comportent au moins k cellules K élémentaires d'addition. La figure 4 représente schématiquement l'additionneur i AD d'ordre K et de niveau 1. Cet additionneur, compte tenu de K la structure récursive décrite plus haut, est en fait constitué i par un additionneur ADP d'ordre K et de niveau 1, dont l'entrée K de retenue entrante CIN reçoit un bit de valeur 0. L'une des sorties de cet additionneur fournit le bit de génération G, tandis que sa sortie P de propagation de retenue n'est pas connectée. L'additionneur AD de départ peut avoir ou non une K- entrée CIN non nulle suivant que l'on souhaite réaliser un additionneur global avec retenue entrante nulle ou non nulle. 21 d2628232 REVENDICATIONS 1. Additionneur de type récursif, pour calculer la somme de deux opérandes A et B formés respectivement de données binaires al, a,...a et b1, b 2,..., b de différents poids, n n les opérandes A et B comprenant un premier et un deuxième opérandes AL et BL formés respectivement par des données de poids faibles et un troisième et un quatrième opérandes AH et BH formés respectivement par des données de poids forts, caractérisé par Le fait que pour un niveau NH de récursivité de l'additionneur (NH étant un nombre entier supérieur ou égal à 1) et pour un ordre K de cet additionneur (K étant un entier définissant un nombre de cellules élémentaires d'additions dans un additionneur de niveau NH 1), cet additionneur étant noté ADK, étant construit de façon K' récursive et comportant: NH - un premier additionneur AD d'ordre K-1 et de K-1 niveau NH construit de façon récursive et comportant des entrées recevant respectivement les premier et deuxième opérandes AL et BL de poids faibles, et une première et une deuxième sorties fournissant respectivement un opérande de sommation SL des premier et deuxième opérandes AL et BL de poids faibles, et un bit de retenue sortante COUT, pour la sommation effectuée; NH-1 - un deuxième additionneur ADP d'ordre K-1 et de K-1 niveau NH-1 construit de manière récursive et comportant des entrées recevant respectivement les troisième et quatrième opérandes AH et BH de poids forts, une entrée (CIN) reliée à La deuxième sortie (COUT) du premier additionneur, et une première, une deuxième et une troisième sorties fournissant respectivement un opérande de sommation SH des troisième et quatrième opérandes AH et BH de poids forts, un bit P de propagation de retenue correspondant à cette sommation et un bit G de génération de cette retenue; - un sélecteur global de retenue (SE) comportant trois entrées (1, 2, 3) respectivement reliées à.la deuxième sortie (COUT) du premier additionneur et aux deuxième et troisième sorties (6, P) du deuxième additionneur, et une sortie NH fournissant un bit C de retenue globale sortante résultant OUT de la sommation logique: NH C = G + P.COUT OUT 2. Additionneur selon la revendication 1, caractérisé NH-1 en ce que le deuxième additionneur ADP est construit de K-i manière récursive et comporte: - NH-1 - un troisième additionneur ADP d'ordre K-2 et K-2 de niveau NH-2 comportant des entrées recevant respectivement des opérandes AHL et BHL constitués respectivement de données de poids faibles des troisième et quatrième opérandes AH et BH, et une entrée (CIN) de retenue entrante reliée à la deuxième sortie du premier additionneur pour recevoir le bit (COUT) de retenue sortante de ce premier additionneur, et des première, deuxième et troisième sorties pour fournir respectivement un opérande (SHL) de sommation des opérandes AHL et BHL reçus en entrée, un bit (G1) de génération de retenue et un bit (Pl) de propagation de retenue de la sommation effectuée; - un premier sélecteur intermédiaire de retenue (SES) comportant trois entrées respectivement reliées à la deuxième sortie (COUT) du premier additionneur, à la deuxième sortie (G1) du troisième additionneur et à la-troisième sortie (P1) du troisième additionneur, ce premier sélecteur de retenue fournissant sur une sortie un bit C OUT de retenue sortante i obéissant à la sommation logique: C OUT = G1 + P1.COUT I NH-2 - un quatrième additionneur ADP d'ordre K-2 et K-2 de niveau NH-2 comportant des entrées recevant respectivement des opérandes AHH et BHH constitués respectivement de données de poids forts des troisième et quatrième opérandes, une entrée (C2IN) de retenue entrante reliée à la sortie du premier sélecteur (SES) pour recevoir le bit de retenue sortante (CLOUT) - de ce sélecteur et des première, deuxième et troisième sorties fournissant respectivement un opérande (SHH) de sommation des opérandes (AHH et BHH) reçus en entrée, un bit (G2) de génération de retenue, et un opérande (P2) de propagation de retenue de la 23 2628232 sommation effectuée; - un deuxième sélecteur intermédiaire (SEC) de génération de retenue, comprenant trois entrées respectivement reliées à la deuxième sortie (G1) de génération de retenue du troisième additionneur à La deuxième sortie (62) de génération de retenue du quatrième additionneur et.à la troisième sortie (P2) de propagation de retenue du quatrième additionneur, ce deuxième sélecteur fournissant sur une sortie correspondant à la troisième sortie du deuxième additionneur, le bit (G) de génération de retenue de ce deuxilèmee additionneur, résultant de la sommation logique: G = 62 + P2.61 - une porte logique de type "ET" à deux entrées respectivement reliées à la troisième sortie (P2) de propagation du quatrième additionneur et à la troisième sortie (P1) de propagation du troisième additionneur, cette porte logique fournissant sur une sortie correspondant à la deuxième sortie du deuxième additionneur, le bit de propagation P de sortie de ce deuxième additionneur, résultant de la multiplication logique P=Pl.P2. 3. Additionneur selon la'revendication 2, caractérisé en ce que l'additionneur ADP1 K d'ordre K et de niveau 1, obtenu NH-1 de manière récursive, à partir de l'additionneur ADP K{-I d'ordre K-1 et de niveau NH-1, capable d'additionner deux à deux des bits d'une tranche de données a;, ai+l,..., a+J ai+K, et b1, b, ..., b1+J. bK des deux opérandes A et B (i étant bi+lK compris entre 1 et n), comporte: - une succession d'au moins K cellules élémentaires d'addition, de type "additionneurs complets", chaque cellule (FA) de rang i+J comportant deux entrées pour recevoir i+J respectivement une paire de bits tels que (a i+j, bi+j), une entrée de retenue entrante pour recevoir un bit de retenue sortante (r) fourni par une première sortie de retenue i+J-1 sortante d'une cetllule élémentaire précédente FA+j1 de ladite succession, l'entre de retenue entrante de la premi6re celule+ succession, L'entrée de retenue entrante de La première cellule élémentaire de ladite succession recevant un bit de valeur 0 et la sortie de retenue sortante de la dernière cellule élémentaire de ladite succession fournissant un bit (G) de génération de retenue pour ladite succession, chaque cellule élémentaire (FA) comportant en outre une deuxième et une troisième sorties i+j fournissant respectivement un bit de sommation locale s et un i+J bit de propagation pi+J, les bits ri+, si+ et pi+j résultant des opérations logiques: riJ = (r.p )+(a.b) i+J i+J-1' i+J i+J i+J p =a a b i+J i+J i+J ( i+J = ai+j)bij+ J i+j-1 dans lesquelles. est l'opérateur "ET", et + est l'opérateur "OU INCLUSIF" et est l'opérateur "OU EXCLUSIF"; - un ensemble logique (CP) de calcul de la propagaton P de la retenue pour cet additionneur comportant des entrées respectivement reliées aux troisièmes sorties (pj) de i +J propagation des cellules élémentaires pour fournir sur une sortie un bit p de propagation pour cet additionneur ADP résultant i +K K de l'opération logique: p = p p. p -P i+k i+k i+k-1 i+l i ou P = P i+k i+k- '1 i+k - un ensemble logique (CS) de calcul de sommation comportant des entrées respectivement reliées aux deuxième sorties de sommation des cellules élémentaires, à des sorties pi+J de propagation de l'ensemble de propagation (CP) fournissant des bits p =p.p , et une entrée de retenue entrante CIN i+J i+J-1 i+J reliées à la sortie de retenue sortante d'un additionneur précédent, cet ensemble de calcul de sommation (CS) fournissant respectivement sur des sorties des opérandes de sommation S, 1 i 30.., S i+,..., Si+K calculés par l'additionneur ADP et résultant de l'opération logjque: S = s @(P.CIN) i+j i+J i+J-1 avec P =1 i-1I 4. Additionneur selon la revendication 3, caractérisé en ce que l'additionneur AD d'ordre K et de niveau 1 est K constitué comme un additionneur ADP d'ordre K et de niveau 1 K dont l'entrée de retenue entrante (CIN) reçoit un bit (CIN) égal à o0. 1/2 AL BL AH BH SE AD ADP ICOI I K1 UTI L _ _. _ _J L''ADi' -SL,SH FIG. 1 AHL_ AH BH BHH B"-L. SESCioUT'1/AHHSEC Vers &Elr _ _., r. I CI/NPf C21, P2. L SHL v 'SHH A)DP N s SHNG. FIG. 2 2/2 ai aial aL+j ai. K aZÉ,.aú2i+1a hi+jbL+K 1 X; -- --w [Ei rL.± n.rK [G FAFL+?1F,.2 _FA+j I rL ",+ i2ELijk+ -- Pl' 1 PiL-- ET_ P L2 Pi+KJ tMi Ml+lF _+2Mi+jLKCS QUt ULi1 OUL+2U4 K Si &+ s&+2 SL+j.Si+K ADPt FIG. 3 bO ADk CouT I. _ P- FIG. 4