Brevet FR2665275A1 — publié le 19920131

i Multiplieur cellulaire en arbre de type gradin inversé et son procédé de réalisation L'invention est relative à un multiplieur cellu- laire en arbre de type gradin inversé. L'architecture des multiplieurs rapides est par- ticulièrement importante dans le domaine des systèmes numériques Ces progrès dans le mode de calcul, en ce qui concerne l'architecture de ces multiplieurs, sont déterminants non seulement en ce qui concerne la seule architecture elle-même de ces derniers, mais aussi les accumulateurs de multiplieurs, les éléments internes d'ordinateurs, les filtres numériques et, d'une manière générale, tous les opérateurs mettant en oeuvre la sommation de multiples opérandes. Initialement, les multiplieurs cellulaires en arbre ont fait l'objet d'études approfondies par C.S Wallace, ces études ayant abouti à la mise en oeu- vre de multiplieurs cellulaires rapides dits multi- plieurs en arbre de Wallace. De manière générale, ces multiplieurs sont divi- sés en trois parties: le codeur de Booth modifié, l'additionneur d'opérandes multiples, ou réducteur en produits partiels, et l'additionneur final La caracté- ristique essentielle la plus remarquable de ce type de multiplieur apparait au niveau de l'additionneur d'opé- randes, les N opérandes étant sommés en deux nombres, cette opération étant désignée ci-après par sommation (N,2), au lieu d'un selon la pratique usuelle L'addi- tionneur d'opérandes multiples (N,2) est, à cet effet, constitué par un arrangement cellulaire en arbre d' ad- ditionneurs à retenue conservée (arbre de Wallace) Une telle structure de ce type d'additionneurs évite ainsi la propagation horizontale des retenues Une telle architecture permet la mise en oeuvre très rapide de la sommation (N,2) dans un intervalle de temps proportion- nel à log 3/2 N Pour une description plus complète de ce type d'additionneur, on pourra se reporter à l'ar- ticle de C S Wallace "A suggestion for a fast multi- plier" IEEE Transaction Electronic Computers, Vol 13 p 14-17 Fev 1964). Au plan théorique, C S Wallace, au cours de ses travaux, a ouvert la voie à l'obtention de la valeur li- mite la plus faible de temps de calcul nécessaire à la mise en oeuvre d'une sommation (N,2) lors de l'utilisa- tion d'additionneurs à retenue conservée. Cependant, la mise en oeuvre des structures en arbre de Wallace est rendue délicate et peu aisée, du fait de leur interconnexion complexe intriquée, en par- ticulier lors de leur réalisation selon une topologie plane en très haute densité d'intégration (VLSI) dans laquelle une pluralité d'additionneurs à retenue conser- vée est superposée en un arrangement par strates. Pour cette raison, la plupart des réalisateurs de circuits intégrés a ainsi préféré des structures de sommateurs (N,2) permettant une architecture régulière aux structures en arbre de Wallace, en acceptant cepen- dant un compromis relativement au temps de calcul Parmi ces architectures différentes, les plus représentatives, sont le réseau itératif d'additionneurs à retenue con- servée, décrit par J Y Lee, H L Garvin et C W Slayman dans l'article intitulé "A high speed high density sili- con 8 x 8 bit parallel multiplier" publié en Février 1987 dans la revue IEEE J Solid-State Circuits, vol. SC-22, No 1, pp 35-40, les structures en arbre de Zuras-Mc Allister décrites dans l'article intitulé "Balanced delay trees and combinatorial division in VLSI", de D Zuras, et W,H, Mc Allister publié dans la revue IEEE J Solid State Circuits Vol 21 p 814-819 N 5 en Octobre 1986, et enfin les structures en arbre dites 4-2 décrites par W Li, J Burr, M Santoro et M Horowitz, correspondant à la demande de brevet US 088096 déposée le 21 Août 1987 Ces trois types de structures présentent respectivement un temps de calcul proportionnel à N, N 1/2 et log (N). Le réseau itératif d'additionneurs à retenue conservée conduit à l'architecture la plus régulière et nécessite uniquement des interconnexions de couches voisines, mais présente l'inconvénient d'être le plus lent. Les structures en arbre de Zuras-Mc Allister, arbre ZM, nécessitent la mise en oeuvre d'intercon- nexions inter-couches, du fait que la sortie d'un ad- ditionneur à retenue conservée n'est pas connectée à l'additionneur voisin mais aux autres additionneurs. Ceci a pour effet une accélération du processus de cal- cul, au prix toutefois d'une augmentation de la surface de silicium nécessaire à l'implantation d'une telle ar- chitecture Il faut cependant souligner que les conne- xions inter-couches dans les arbres ZM sont d'exécution simple et peu onéreuse, deux conducteurs de connexion inter-couches étant seuls nécessaires Le nombre de conducteurs inter-couche est en outre défini comme une mesure de la transparence entre couches d'additionneurs à retenue conservée, les structures en arbre de trans- parence constante pouvant conduire à une topographie très compacte Mais, les arbres ZM s'écartent très ra- pidement de la limite inférieure de Wallace, lorsque le nombre d'opérandes N augmente. En outre, la catégorie des arbres de type 4-2 apparaît particulièrement adaptée à la mise en oeuvre de sommations ( 2 m,2), lesquelles sont très courantes dans beaucoup d'applications Ce type d'arbre peut conduire à un temps de calcul proportionnel à log N égal ou voisin de la limite inférieure de Wallace Cependant, 2 (m-2) conducteurs inter-couches sont nécessaires, ce qui a pour effet une croissance rapide de la surface de silicium. Plus récemment, un multiplieur cellulaire à structure en arbre dit en racine pième a été décrit dans la demande de brevet français N O 88 02701 Cette struc- ture est formée par des additionneurs à retenue conser- vée interconnectés par des connecteurs à quatre entrées. Bien que s'approchant de la limite inférieure de Wallace pour les faibles valeurs du nombre d'opérandes N, le temps de calcul n'est plus optimum pour les valeurs de nombre d'opérandes importantes. La présente invention a pour objet de remédier aux inconvénients précités par la mise en oeuvre d'un muliplieur cellulaire en arbre permettant d'atteindre ou approcher, pour les valeurs de nombre d'opérandes impor- tantes, la limite inférieure de Wallace, le temps de calcul du multiplieur cellulaire en arbre objet de l'in- vention étant sensiblement optimisé. Un autre objet de la présente invention est la mise en oeuvre d'un multiplieur cellulaire en arbre, permettant de modifier le nombre d'interconnexions inter-couches en comparaison du nombre d'interconnexions inter-couches des multiplieurs cellulaires en arbre ZM, afin d'augmenter cependant la vitesse de traitement. Le multiplieur cellulaire en arbre de type gra- din inversé, objet de la présente invention, comporte une pluralité d'additionneurs à retenue conservée inter- connectés Il est remarquable en ce que pour constituer un multiplieur d'ordre p et de hauteur n+l, celui-ci est formé par une racine, constituée par un additionneur à retenue conservée, et par un corps de multiplieur d'or- dre p et de hauteur N o p désigne un paramètre de temps de traitement de sommation de la forme N 1/(P+ 1), N désignant le nombre d'opérandes à traiter Le corps de multiplieur est formé d'une part, par un opérateur connecteur à cinq entrées de rang q, noté C(n,q). L'opérateur connecteur de rang 1, C(n,l), est interconnecté à la racine L'opérateur connecteur de rang q, C(n,q) comporte un premier et un deuxième additionneur à retenue conservée connectés en cascade Le premier et le deuxième addi- tionneur à retenue conservée, comportent chacun trois entrées, une sortie somme et une sortie retenue, la sortie retenue du premier additionneur est connectée à une entrée du deuxième additionneur L'opérateur connecteur C(n,q) comporte trois sorties constituées par la sortie somme du premier additionneur, la sortie somme et la sortie retenue du deuxième additionneur. Le corps de multiplieur est d'autre part formé par un arbre d'ordre p-i et de hauteur n-2 constitué par un agencement d'additionneurs à retenue conservée intercon- nectés, les sorties somme et retenue de l'additionneur à retenue conservée constituant racine de cet arbre, étant respectivement connectées à une entrée du premier addi- tionneur de l'opérateur connecteur de rang q et par un corps de multiplieur d'ordre p et de hauteur inférieure n-l, ce corps de multiplieur étant formé de manière ana- logue au corps de multiplieur de hauteur supérieure n. Le multiplieur cellulaire en arbre, objet de la présente invention, trouve application à tout système de calcul numérique, tels que calculateurs utilisant des multiplieurs itératifs rapides ou des multiplieurs à structure dite "pipe-line". Le multiplieur cellulaire en arbre selon l'in- vention, sera décrit plus en détail dans la description ci-après et dans les dessins dans lesquels outre la fi- gure 1, relative à une structure de Zuras Mc Allister dite structure en arbre ZM de l'art antérieur, la figure 2 a représente un multiplicateur cel- lulaire en arbre conforme à l'objet de la pré- sente invention, la figure 2 b représente un mode de réalisation particulier avantageux non limitatif du multi- plieur objet de l'invention, représenté en figure 2 a ou 2 b, la figure 2 c représente un détail de réalisa- tion d'éléments constitutifs du multiplieur cellulaire tel que représenté en figure 2 b, la figure 3 a représente un mode de réalisation avantageux d'une topologie du multiplieur cellulaire selon l'invention en vue de son in- tégration sur une puce de circuit intégrée, les figures 3 b et 3 c représentent des détails de réalisation de la figure 3 a, la figure 4 a représente un multiplieur cellu- laire en arbre conforme à l'objet de la pré- sente invention de hauteur sept, permettant d'assurer une sommation S( 24,2) sur vingt- quatre opérandes, la figure 4 b représente un multiplieur cellu- laire en arbre d'ordre 2 conforme à l'objet de la présente invention de hauteur sept, permet- tant d'assurer une sommation S( 28,2) sur vingt huit opérandes, la figure 5 a représente un schéma bloc d'un multiplieur cellulaire en arbre d'ordre p et de hauteur n, conformément à l'objet de la présente invention, la figure 5 b représente un schéma bloc d'un multiplieur cellulaire en arbre de type hybri- de de hauteur n, incorporant dans le corps hybride de multiplieur une structure en arbre ZM et une structure en arbre de type gradin inversé d'ordre p, et en dehors du corps hy- bride de multiplieur, un multiplieur en arbre hybride de type gradin inversé et en arbre ZM, la figure 6 a représente un diagramme compara- tif des différentes structures en arbre possi- bles relativement au nombre N d'opérandes susceptibles d'être traités en fonction de la hauteur N du multiplieur, vis-à-vis de la li- mite inférieure de Wallace, la figure 6 b donne une table de valeurs cor- respondantes du diagramme de la figure 6 a. Préalablement à la description proprement dite du multiplieur cellulaire en arbre objet de la présente invention, quelques définitions seront rappelées en liaison avec la figure 1 relative à l'art antérieur re- lativement aux structures en arbre réalisées à partir de circuits ou éléments tels que des additionneurs à rete- nue conservée, désignés ci-après par additionneurs ARC. Sur la figure 1, en partie gauche de celle-ci, on a représenté de manière schématique un additionneur à retenue conservée ARC lequel comporte trois entrées el e 2 et e 3, recevant les opérandes à traiter, une sortie retenue notée R et une sortie somme notée S Ces élé- ments de circuit sont connus sous le vocable anglo-saxon de "carry save adder" En outre, une structure en arbre comportant de tels additionneurs, tels que représentés en figure 1, comporte habituellement une racine notée r généralement constituée par un additionneur précité, et un corps de multiplieur noté CO comportant un agencement particulier d'une pluralité de ces additionneurs ARC. On désigne par degrés, notés Dq, l'agencement dans le corps de multiplieur d'une pluralité d'addition- neurs ARC en cascade, un arrangement en cascade corres- pondant d'une part en la liaison d'une sortie retenue R ou somme S à la même entrée de l'additionneur ARC suc- cessif suivant, dans le sens de traitement des opérandes ou des résultats de ces traitements, et d'autre part à un niveau commun d'intégration dans des circuits inté- grés à plusieurs niveaux d'intégration ainsi qu'il sera décrit ultérieurement dans la description On notera en outre que l'indice q définit ainsi le rang d'un degré ou d'élément constitutif de ce degré dans la topologie du circuit intégré correspondant et dans la représentation de cette topologie ainsi que représentée en figure 1, le rang 1, q=l, étant, par convention purement arbitraire, attribué par exemple au degré correspondant comportant la racine r par exemple. Le multiplieur cellulaire en arbre de type gra- din inversé objet de la présente invention sera mainte- nant tout d'abord décrit en liaison avec la figure 2 a. Bien entendu, le multiplieur objet de l'inven- tion comporte une pluralité d'additionneurs ARC inter- connectés. Ainsi qu'on l'a représenté sur la figure 2 a, pour constituer un multiplieur d'ordre p et de hauteur n+ 1, la hauteur définissant le chemin critique suivi par les opérandes à traiter pour obtenir le résultat de traitement, cette hauteur correspondant au nombre maxi- mum d'additionneurs ARC que chaque opérande doit traver- ser pour ainsi contribuer au résultat du traitement, ce multiplieur est formé par une racine notée R constituée par un additionneur ARC Le multiplieur cellulaire en arbre objet de l'invention est également formé par un corps de multiplieur noté CO(p,n) d'ordre p et de hau- teur n L'indice p désigne un paramètre de temps de traitement de sommation de la forme N 1/P o N désigne le nombre d'opérandes à traiter, p étant désigné comme l'ordre de la structure en arbre correspondante L'indi- ce N désigne la hauteur du corps de multiplieur. Ainsi qu'il apparaîtra à l'observation de la figure 2 a, le corps de multiplieur CO(p,n) est formé par un opérateur connecteur à cinq entrées, cet opérateur connecteur étant noté C(n,q), l'opérateur connecteur de rang 1 noté C(n,1) étant interconnecté à la racine R On comprendra bien sûr que l'opérateur connecteur de rang 1 C(n,l) est implanté dans le degré de rang 1 o q=l. Ainsi qu'on l'a représenté d'ailleurs en figure 2 a, l'opérateur connecteur C(n,q) comporte un premier et un deuxième additionneur à retenue conservée ARC notés respectivement 1 et 2 connectés en cascade Le premier et le deuxième additionneur ARC 1 et 2 comportent chacun trois entrées, une sortie somme et une sortie retenue, et la sortie retenue du premier additionneur ARC 1 est connectée à une entrée du deuxième additionneur ARC 2. L'opérateur connecteur C(n,q) comporte ainsi trois sor- ties constituées par la sortie somme du premier addi- tionneur ARC 1 et par la sortie somme et la sortie rete- nue du deuxième additionneur ARC 2. Ainsi qu'on l'a représenté en figure 2 a, les trois sorties de l'opérateur connecteur C(n,q) pour q=l, soit l'opérateur connecteur C(n,l), sont ainsi reliées respectivement à une entrée de la racine R. Ainsi qu'on l'a en outre représenté en figure 2 a, le corps de multiplieur CO(p,n) comporte également un arbre d'ordre p-l et de hauteur n-2, cet arbre étant noté A(p-l,n-2) De manière générale, cet arbre peut être constitué par un agencement d'additionneurs ARC interconnectés Bien entendu, les sorties somme et rete- nue de l'additionneur ARC, constituant racine r de l'ar- bre précité A(p-l,n-2), sont respectivement intercon- nectées à une entrée du premier additionneur ARC 1 de l'opérateur connecteur C(n,q) en particulier de l'opéra- teur connecteur C(n, 1). Sur la figure 2 a on a représenté l'arbre précité A(p-l,n-2) par un nombre d'additionneurs ARC limité à trois, afin de ne pas surcharger le dessin Il est bien entendu que l'arbre A(p-l,n-2) peut en fait être cons- titué par tout type d'arbre d'ordre p-l et de hauteur n-2 pour constituer un degré Dq correspondant, en parti- culier un degré Dl de rang 1 et de hauteur n+l compor- tant l'arbre précité, l'opérateur connecteur C(n,q), avec q=l, et la racine R Différents exemples de réali- sation mettant en oeuvre les arbres de nature différente pour constituer l'arbre A(p-l,n-2) seront donnés ultérieurement dans la description. En outre, ainsi qu'on l'a également représenté en figure 2 a, le corps de multiplieur CO(p,n) d'ordre p et de hauteur N comporte également un corps de multi- plieur d'ordre p et de hauteur inférieure n-1, ce corps de multiplieur étant noté CO(p,n-1) Bien entendu, le corps de multiplieur de hauteur inférieure n-l est formé de manière semblable au corps de multiplieur de hauteur supérieure N précédemment décrit, et ce de manière ré- cursive. De l'observation de la figure 2 a, on comprendra bien entendu que chaque corps de multiplieur noté CO(p,n) est ainsi formé d'un arbre noté A(p-l,n-2) et d'un corps de multiplieur de hauteur inférieure noté CO(p,n-1), l'arbre et le corps de hauteur inférieure précités étant interconnectés par l'intermédiaire d'un connecteur noté C(n,q) pour constituer le corps de mul- tiplieur de hauteur supérieure noté CO(p,n). La loi de récurrence de formation du corps de multiplieur objet de la présente invention, peut alors être établie de la façon ci-après: CO(p, n)=CO(p,n-1)+A(p-l,n-2). L'on comprendra bien sûr que le symbole + de la relation précitée représente la liaison de l'arbre A(p-l,n-2), et du corps de multiplieur CO(p,n-l) par l'intermédiaire du connecteur de rang considéré C(n,q). Sur la figure 2 a la loi de récurrence précitée de la structure en arbre du multiplieur, objet de l'in- vention, est représentée par la subdivision de cette structure d'une part en traits pointillés au niveau de chaque degré de rang q, et d'autre part au niveau des traits mixtes verticaux, lesquels représentent chacun des corps CO d'ordre p et de hauteur différente N à n-(q-l). Ainsi qu'il résulte d'ailleurs de la figure 2 a, le corps de multiplieur d'ordre p et de hauteur infé- rieure n-1 noté CO(p,n-l) comporte bien entendu un opé- rateur connecteur à cinq entrées noté C(n-l,q+ 1) de rang supérieur q+l et les trois sorties de l'opérateur con- necteur précitées sont connectées respectivement à une il entrée du premier et du deuxième additionneur ARC 1,2 constituant l'opérateur connecteur de rang inférieur C(n,q) Bien entendu, le corps de multiplieur CO(p,n-l) de hauteur inférieure n-l comporte également un arbre noté A(p-l,n-3) d'ordre inférieur p-l et hauteur infé- rieure n- 3, ainsi qu'un corps de multiplieur de même ordre p et de hauteur inférieure n-2, ce corps étant noté CO(p,n-2) Il en est de même pour les corps de multiplieurs successifs formés par les degrés d'ordre supérieur. En ce qui concerne les conditions aux limites de la structure telle que représentée en figure 2 a, on notera en ce qui concerne le degré de rang 1, c'est-à-dire pour q=l, que la hauteur n-2 de l'arbre A(p-l,n-2) définit d'une part le nombre de degrés de rang supérieur, ce nombre de degrés étant par exemple égal à Q avec Q=n-1. On notera bien sûr que la hauteur de chaque ar- bre A(p-1,n-q) étant décroissante en fonction du rang q de chaque degré, les arbres des degrés q=Q et q=Q-1 sont sensiblement réduits, ces degrés étant alors respecti- vement constitués par: un additionneur ARC pour le degré d'ordre q=Q et par un connecteur à cinq entrées pour le degré de rang q=Q- 1, l'additionneur ARC constituant le degré de rang q=Q présentant respectivement sa sortie somme S et retenue Re respectivement connectées à une entrée de l'additionneur ARC 2 constitutif du connecteur formant le degré de rang inférieur q=Q-1. Une description plus détaillée d'un mode de réa- lisation particulier du multiplieur cellulaire en arbre de type gradin inversé, objet de la présente invention, sera maintenant donnée en liaison avec la figure 2 b, dans le cas o chaque arbre d'ordre p-l et de hauteur décroissante, noté A(p-1,n-(q+ 1)), est constitutif d'un corps de multiplieur CO(p,n-(q-1)) dans les conditions précédemment décrites, chaque arbre étant constitué par une pluralité d'additionneurs ARC en cascade. Conformément à la figure 2 b, et afin d'alléger la notation, les différents opérateurs connecteurs uti- lisés seront notés avec un seul indice les caractéri- sant, l'indice de rang, étant entendu que l'indice de hauteur pour ces opérateurs connecteurs n'est représen- tatif que de la hauteur du degré correspondant et pas de l'opérateur connecteur lui-même. Ainsi, sur la figure 2 b, pour un degré Dq, la notation simplifiée de l'opérateur connecteur correspon- dant est: Cq Bien entendu, cet opérateur connecteur comporte à 1 ' identique un premier et un deuxième addi- tionneur ARC notés 1 respectivement 2 Sur la figure 2 b, le degré courant, noté Dq, est par exemple le degré de rang immédiatement supérieur au rang du degré comportant la racine R, noté Dq-1. Sur la figure 2 b on pourra remarquer que les additionneurs ARC sont agencés en degrés de hauteur N et de rang q Chaque degré Dq est formé pour q additionneurs successifs. Ainsi qu'on pourra le constater à 11 observation de la figure 2 b, un opérateur connecteur Cq à cinq en- trées, formé ainsi que précédemment décrit au moyen de deux additionneurs ARC, est interconnecté d'une part à la branche Bq pour former le degré Dq de hauteur n, n représentant en fait le nombre d'additionneurs de ce de- gré et d'autre part à l'opérateur connecteur Cq+g de rang supérieur, de façon à former pour le sous-ensemble constitué par les Q-q degrés de rang supérieur, un corps de multiplieur cellulaire en arbre de structure arbores- cente correspondante ainsi que décrit précédemment dans la description en liaison avec la figure 2 a. Bien entendu, les degrés de rang Q-1 et Q sont respectivement constitués par un connecteur à cinq en- trées et par un additionneur ARC. La racine R est elle-même formée par un addi- tionneur de sortie constitué par un additionneur ARC. L'opérateur connecteur Cl est interconnecté à l'addi- tionneur ARC formant la racine R. Ainsi, chaque branche Bq de rang q comporte n-2 additionneurs successifs et comprend N entrées d'opéran- des disponibles, ce qui permet d'assurer le traitement d'un nombre important d'opérandes ainsi qu'il sera dé- * crit ultérieurement dans la description. Dans le mode de réalisation de la figure 2 b, pour constituer une branche Bq de rang q, les sorties de somme et de retenue d'un aditionneur ARC noté h sont reliées aux entrées correspondantes de l'additionneur ARC h+l successives suivant, les notations h et h+l correspondant au sens de traitement des opérandes. Une description plus détaillée de l'interconne- xion entre les éléments additionneurs ARC d'un degré Dq de rang q aux éléments correspondants additionneus ARC des degrés adjacents Dq-1 de rang q-1 et Dq+l de rang q+l sera donnée également en liaison avec la figure 2 b. Selon la figure précitée, chaque opérateur con- necteur Cq d'ordre q pour kq Bq correspondante et à la sortie somme du premier addi- tionneur ARC notée C(q+ 1),1 de l'opérateur connecteur de rang supérieur q+l, opérateur connecteur noté C(q+l). En outre, la sortie retenue et la sortie somme du premier additionneur ARC sont respectivement reliées à une entrée opérande du deuxième additionneur et à une entrée opérande du premier additionneur ARC de l'opéra- teur connecteur C(q-1) de rang inférieur q-1, ce premier additionneur ARC étant noté C(q-1),l. Enfin, deux entrées opérandes du deuxième addi- tionneur du connecteur Cq, deuxième additionneur ARC no- té Cq,2 sont respectivement reliées à la sortie somme et à la sortie retenue du deuxième additionneur noté C(q+l),2 de l'opérateur connecteur C(q+l) de rang supé- rieur q+ 1. L'interconnexion précitée entre connecteurs des degrés de rang q-1, q et q+ 1 est valable quel que soit le type d'arbre utilisé pour former ces degrés, en par- ticulier dans le cas o les arbres précités sont consti- tués par des branches ainsi que représentés en figure 2 b et décrits précédemment. Sur la figure 2 c on a représenté de façon plus détaillée la constitution d'un opérateur connecteur tel que l'opérateur connecteur Cl par exemple, et celle d'une branche la branche Bl de la figure 2 a On notera en particulier à l'observation de la figure précitée, que les cinq entrées de l'opérateur connecteur considéré sont formées par les entrées All Bll Cll du premier additionneur ARC 1 et par deux entrées Dll Ell du deu- xième additionneur ARC 2 Les trois sorties de l'opéra- teur connecteur Cl notées A 22 B 22 C 22 sont respecti- vement formées par la sortie somme du premier addition- neur ARC et par la sortie somme et la sortie retenue du deuxième additionneur ARC 2. Une description plus détaillée d'une topologie préférentielle de mise en oeuvre du multiplieur cellu- laire en arbre de type gradin inversé objet de la pré- sente invention, tel que représenté en figure 2 a ou 2 b, sous forme de circuit intégré, sera maintenant donnée en liaison avec les figures 3 a, 3 b, 3 c. D'une manière générale, un additionneur ARC est un opérateur d'additions au niveau mot, chaque mot étant constitué de S bits Ainsi, un additionneur ARC additionne trois opérandes constitués chacun par un mot et délivre deux sorties Chaque additionneur ARC est composé de plusieurs additionneurs complets notés AC, o "full adder" en langage anglo-saxon dont le nombre est déterminé par la largeur des mots constituant les opé- randes précités Ainsi un additionneur complet est un opérateur d'addition au niveau bits, lequel additionne ainsi trois bits de même poids de trois opérandes diffé- rents et délivre en sortie deux bits de poids différent, ces bits correspondant respectivement à un bit somme S et un bit retenue Re. Conformément à un aspect particulièrement avan- tageux du multiplieur objet de la présente invention, les additionneurs ARC, ainsi que représentés en figure 3 a et en particulier les arbres et les connecteurs cons- tituant les degrés Dl à D 5 de rang 1 à 5, sont disposés selon une topologie plane et verticale En effet, les degrés D 5 constitué par la branche B 5, D 4 constitué par l'opérateur connecteur C 4, D 3 constitué par l'opérateur connecteur C 3 et la branche B 3, D 2 constitué par l'opé- rateur connecteur C 2 et la branche B 2 et Dl constitué par l'opérateur connecteur Cl et la branche Bl, ainsi que la racine R constituant l'élément de sortie Acs, sont surperposés selon la dimension verticale du bloc de silicium, la direction Z sur la figure 3 a Les degrés successifs D 5 à Dl peuvent alors être organisés en cou- ches successives d'intégration. Ainsi qu'on l'a en outre représenté en figure 3 a, l'une des dimensions de la surface du circuit inté- gré, la dimension X par exemple, peut alors correspondre à la dimension d'alignement des bits de même poids des mots constituant chaque opérande, alors que la dimension Y au contraire peut correspondre à l'alignement des bits des différents poids constitutifs des mots précités. Le mode de réalisation sous forme de circuit in- tégré tel que représenté en figure 3 a du multiplieur ob- jet de la présente invention apparait ainsi particuliè- rement avantageux dans la mesure o la complexité de la structure correspondante se développe finalement sur une seule dimension de la puce de circuit intégré, la dimen- sion Z, l'implantation du multiplieur objet de la pré- sente invention étant de ce fait essentiellement monodi- mensionnelle En outre, on constatera que les fils de liaison intercouches appelés TLW en référence à leur désignation de "translayer wires" en language anglo- saxon sont au plus au nombre de trois entre deux couches successives, ce qui permet d'obtenir un facteur de transparence constant. Sur les figures 3 b et 3 c on a représenté respec- tivement une vue de la structure représentée en figure 3 a respectivement relativement en ce qui concerne les additionneurs ARC opérant au niveau mots, puis relative- ment aux additionneurs complets opérant au niveau bits. Les structures précitées sont bien entendu semblables à celles de la figure 3 a puisque, en fait, l'on passe de la structure telle que représentée en figure 3 c à celle de la figure 3 b par duplication de la précédente selon l'axe des X, le passage de la structure de la figure 3 b à celui de la figure 3 a étant alors obtenu par duplica- tion de cette figure selon la dimension Y. On notera en particulier que la structure du multiplieur cellulaire en arbre objet de la présente in- vention permet la modification du nombre de fils de connection intercouches d'une unité par rapport à des structures de l'art antérieur telles que représentées en figure 1, ce qui bien entendu permet, bien qu'en augmen- tant la perte de superficie utilisable effectivement pour assurer l'intégration dans la dimension X,Y de surface du circuit intégré, d'augmenter la rapidité du traitement. On notera en particulier que les multiplieurs cellulaires en arbre de type gradin inversé objet de la présente invention permettent de réaliser un traitement d'opérandes de type sommation S (N,2) avec un temps de traitement plus proche de la limite inférieure de Wallace que ne le permettent les structures en arbre ZM par exemple, lesquelles n'autorisent qu'un temps de traitement proportionnel à N 112, ainsi qu'il sera décrit ultérieurement dans la description. Ainsi qu'on pourra le remarquer à l'observation de la figure 2 a ou 2 b, le multiplieur cellulaire en ar- bre de type gradin inversé, tel que représenté sur ces figures, peut constituer avantageusement un multiplieur cellulaire en arbre réalisant une sommation de type S ( 18,2) Les degrés du gradin inversé comportent respec- tivement pour les degrés Dl à D 5 5,4,3,2,1 additionneurs ARC Le multiplieur cellulaire en arbre tel que repré- senté sur les figures précitées présente une hauteur de 6 additionneurs ARC, laquelle est identique à celle d'un arbre de Wallace idéal permettant d'assurer une somma- tion de type S ( 18,2) On notera au contraire qu'un ar- bre de type ZM permettant d'assurer une sommation S ( 18,2) nécessite une hauteur de 7 additionneurs ARC, ce qui montre que le multiplieur cellulaire en arbre de type gradin inversé, objet de la présente invention, permettant d'assurer une sommation S ( 18,2), est plus proche de la limite inférieure de Wallace que ne l'est l'arbre ZM équivalent Ceci est encore vrai pour les valeurs supérieures du nombre d'opérandes N ainsi qu'il sera décrit ultérieurement dans la description. En ce qui concerne la structure générale des multiplieurs cellulaires en arbre objet de la présente invention, on notera qu'un corps de multiplieur CO tel que représenté en figure 2 a, de hauteur n, est composé de n-l degrés, un degré de hauteur 1 étant constitué par un additionneur ARC tel que le degré de rang Q sur les figures 2 a ou 2 b et un d'un degré de hauteur 2 étant composé d'un opérateur connecteur tels que les degrés de rang Q-1 sur ces mêmes figures Le corps de multiplieur lui-même est alors de hauteur n-1 et un corps de multi- plieur de hauteur N peut alors être construit à partir d'un corps de hauteur n-i auquel est associé un degré de hauteur n, ce degré étant constitué par un arbre de hauteur n-2 plus un opérateur connecteur ainsi que dé- crit précédemment en liaison avec la figure 2 a ou 2 b. Il est alors possible de déterminer pour un ar- bre de type gradin inversé de hauteur n, le nombre d'o- pérandes N en fonction de la hauteur du multiplieur: N(n)=N(n-l)+n-1 avec la condition initiale N( 1)= 3. Le nombre d'additionneurs ARC nécessaire à la mise en oeuvre d'un multiplieur en arbre de type gradin inversé objet de la présente invention peut alors être défini par la relation: NARC(n)=NARC(n-l)+n-1 avec la condition initiale NARC(l)= 1- On démontre alors que le nombre N d'opérandes succeptible d'être traité par un multiplieur cellulaire de type gradin inversé objet de la présente invention de hauteur N est alors donné à partir des relations précé- dentes selon la nouvelle relation N 2 n N= + 3 2 2 A titre d'exemple on notera qu'un multiplieur cellulaire en arbre de type gradin inversé objet de la présente invention est susceptible de permettre le trai- tement d'au plus 24 opérandes pour un multiplieur cellu- laire en arbre de hauteur 7, alors qu'un multiplieur cellulaire de type gradin inversé selon l'invention de hauteur 8 peut permettre le traitement d'au plus 31 opé- randes. Une variante de réalisation d'un multiplieur cellulaire en arbre de type gradin inversé objet de la présente invention, de hauteur n= 7 et d'ordre 1 à 24 opérandes est représentée en figure 4 a. Il comporte un premier degré Dl formé d'une part par un opérateur connecteur C dont les trois sorties sont reliées à la racine R et d'autre part, un arbre formant branche B constitué par quatre additionneurs ARC en cascade L'additionneur ARC formant racine de l'ar- bre, additionneur noté r, est connecté aux trois bornes d'entrée du premier additionneur ARC constitutif de l'o- pérateur connecteur C. Le multiplieur cellulaire en arbre tel que re- présenté sur cette figure comporte également un corps de multiplieur noté CO formant multiplieur élémentaire Me 2 de type gradin inversé formé par cinq degrés successifs notés D 2 à D 6 L'opérateur connecteur C 2 du degré D 2 est interconnecté aux deux entrées du deuxième additionneur ARC constitutif de l'opérateur connecteur C. La structure en arbre constituant le multiplieur cellulaire de type gradin inversé objet de la présente invention, telle que décrite successivement en référence aux figures précédentes, apparaît particulièrement avan- tageuse puisque celle-ci peut permettre la mise en oeu- vre de configurations de multiplieurs cellulaires correspondants, tout à fait différentes et adaptatives en fonction du nombre N d'opérandes à traiter En particulier, ainsi qu'il sera décrit ultérieurement dans la description, on notera que la structure des multiplieurs cellulaires en arbre objet de la présente invention peut être adaptée en vue de rendre optimales ces structures, en fonction du nombre d'opérandes traités par comparaison à la limite inférieure de Wallace ainsi qu'il sera décrit ultérieurement dans la description. En effet, il est possible, ainsi que représenté en figure 4 b, de réaliser un multiplieur cellulaire en arbre de type gradin inversé de hauteur identique n= 7 à celui de la figure 4 a, mais pour un nombre d'opérandes plus important, N étant égal à 28 Ainsi qu'on pourra le constater à l'observation de la figure 4 b, le nombre d'entrées d'opérandes au niveau du degré de rang 2 D 2 peut être augmenté de 5 à 6, alors que le nombre d'en- trées d'opérandes au niveau du degré de rang 1 Dl peut être augmenté de 6 à 9. Dans les modes de réalisation des figures 4 a et 4 b on notera que l'ordre p est supérieur à 1, le temps de traitement des arbres de type gradin inversé repré- senté sur les figures précitées étant proportionnel respectivement à N" 2 et N" 3. Dans le mode de réalisation tel que représenté en figure 4 b, les degrés de rang 1 et 2 du mode de réa- lisation de la figure 4 a ont été remplacés par un pre- mier multiplieur cellulaire élémentaire noté Mel de hauteur n-3 et d'ordre p-l, les degrés de rang q> 3 étant arrangés de façon à constituer un deuxième multiplieur cellulaire élémentaire Me 2 de hauteur n-2 et d'ordre p. Les premier et deuxième multiplieurs élémentaires Mel et Me 2 sont interconnectés à un connecteur C. Ainsi qu'on l'a en outre représenté en figure 4 b, le premier degré Dl est alors formé d'une part par l'opérateur connecteur C dont les trois sorties sont re- liées à la racine R, et d'autre part par un arbre de ty- pe gradin inversé Ainsi que représenté sur la figure précitée, cet arbre comprend un opérateur connecteur Cell et un additionneur de sortie noté ACSI, lequel constitue la racine r de l'arbre précité On comprendra bien entendu que l'arbre précité constitue en fait une ramure pour l'arbre général, cette ramure comprenant une première sous-ramure formée par une branche Bel connec- tée à l'opérateur connecteur Cell et une deuxième sous- ramure formée par un opérateur connecteur noté Cel 2, lequel est connecté à l'opérateur connecteur Cell cons- tituant la ramure L'arbre constituant la ramure de l'arbre général précité comporte également une troisième sous-ramure formée par une branche notée Be 3, laquelle est formée par un additionneur ARC, cette branche étant connectée à l'opérateur connecteur Cel 2 de la deuxième sous-ramure. De la même manière, le multiplieur élémentaire Me 2 constitue en fait un corps de multiplieur de manière analogue au corps CO du mode de réalisation de la figure 4 a. Le multiplieur élémentaire Me 2, ainsi que repré- senté en figure 4 b, comporte un opérateur connecteur noté Ce 2 l auquel est connecté d'une part un arbre tel que défini précédemment, constituant première ramure, et un corps de multiplieur de hauteur inférieure consti- tuant deuxième ramure Ainsi qu'on l'a représenté sur la figure précitée, la première ramure du multiplieur élé- mentaire Me 2 comprend une première et une deuxième sous- ramure La première sous-ramure est formée par un opéra- teur connecteur noté Ce 2 ll et par un additionneur de sortie noté AC 52 formant racine r pour la première ramu- re L'additionneur de sortie AC 52 formant racine r est connecté d'une part à l'opérateur connecteur Ce 2 l du deuxième multiplieur élémentaire Me 2, et à l'opérateur connecteur Ce 2 ll de la première sous-ramure La deuxième sous-ramure de la première ramure formée par une branche notée Be 22 formée par un unique additionneur ARC connec- té à l'opérateur connecteur Ce 2 ll de la première sous- ramure. La deuxième ramure du multiplieur élémentaire Me 2 est alors formée par une structure d'arbre en gradin de type inversé telle que représentée précédemment en figure 2 a, 2 b ou 4 a, cette structure étant formée par quatre degrés de rang Q, Q-1, Q-2 et Q-3 La structure en arbre du multiplieur cellulaire de type gradin inver- sé telle que représentée en figure 4 b peut alors être qualifiée de structure en arbre de type gradin inversé multiple d'ordre supérieur p> 2, dans la mesure o la structure générale en arbre de type gradin inversé est utilisée pour engendrer une ou plusieurs structures en arbre de type gradin inversé auxiliaire, notamment au niveau des degrés de rang 1 et 2 par exemple, afin de permettre une optimisation de la structure générale précitée On montre, ainsi qu'il sera décrit ultérieu- rement dans la description, que la structure générale obtenue telle que représentée en figure 4 b est celle d'un arbre de hauteur 7 permettant d'assurer le traite- ment de 28 opérandes, cette structure atteignant la li- mite inférieure de Wallace Ce résultat indique qu'il est possible à partir d'une structure en arbre de type gradin inversé, telle que représentée en figure 2 a et 2 b par exemple, d'optimaliser localement les degrés 1 et 2, c'est-à-dire les degrés correspondant à la racine et le degré le plus proche de la racine, de façon à optimaliser les paramètres de l'ensemble de la structure générale. Des études théoriques ont montré que pour des structures en arbre multiple, c'est-à-dire d'arbre d'or- dre p> 2 tel que représenté en figure 4 b, le nombre maxi- mum d'opérandes Np(n) succeptible d'être traité par un arbre multiple d'ordre p et de hauteur N est donné par la relation récurrente suivante: Np(n)=N p(n-l)+N p_,(n-3). Dans la relation précédente, la condition ini- tiale pour un multiplieur cellulaire en arbre de type gradin inversé d'ordre O correspond au réseau itératif d'additionneurs ARC On montre également que les mul- tiplieurs cellulaires en arbre de type gradin inversé d'odre p nécessitent un temps de traitement proportion- nel à N 1/(P+ 1) o p représente l'ordre du multiplieur. Bien entendu, une optimisation du point de vue de la limite inférieure de Wallace en ce qui concerne le temps de traitement des multiplieurs en gradin de type inversé objets de la présente invention peut être envi- sagée par la mise en oeuvre de multiplieurs d'ordre p> 2 ainsi que décrit précédemment Cependant, un inconvé- nient de la généralisation précédente vient du fait que le nombre de connecteurs inter-couches augmente avec l'ordre du multiplieur en arbre de type gradin inversé précité Ceci a pour inconvénient bien entendu d'aug- menter la perte de surface de circuit intégré suscepti- ble d'être utilisée pour réaliser effectivement l'inté- gration. Des études antérieures ont montré que les struc- tures d'arbre ZM sont optimales pour des nombres d'opé- randes N faibles, c'est-à-dire N=f 3-8,10,11,14}, alors que celles-ci ne requièrent que deux fils de connexion inter-couches. Conformément à un aspect particulièrement remar- quable du multiplieur cellulaire en arbre de type gradin inversé objet de la présente invention, il est avanta- geux, afin d'optimaliser les degrés de rangs voisins du degré initial comportant la racine R, d'utiliser de tels types de structures en arbre ZM dans les degrés préci- tés, les arbres constituant ramure et première ramure des multiplieurs élémentaires Mel et Me 2 de la figure 4 b, étant alors remplacés par des structures en arbre ZM par exemple. Ainsi qu'on l'a représenté de manière schémati- que en figure 5 a et 5 b respectivement, pour la réalisa- tion d'un multiplieur cellulaire d'ordre supérieur p> 2, celui-ci peut être réalisé au moyen d'un connecteur C, relié à un additionneur connecteur de sortie ACS formant racine R, et à un multiplieur en arbre de type gradin inversé d'ordre p-l de hauteur n-3, constituant un multiplieur élémentaire Mel Le connecteur C est en outre connecté à un corps de multiplieur de hauteur n-2 d'un multiplieur en arbre de type gradin inversé de hauteur n-l constituant en fait le multiplieur élémentaire M e 2. Pour constituer au contraire un multiplieur cel- lulaire de type hybride gradin inversé/Zuras Mc Allister de hauteur N et d'ordre p> 2, ainsi que représenté en fi- gure 5 b, le premier multiplieur cellulaire élémentaire Met de degré n-3 est constitué par un multiplieur hybride de type gradin inversé d'ordre p-1 et d'un multiplieur de type Zuras Mc Allister, alors que le deuxième multiplieur cellulaire élémentaire est lui constitué par une structure de type gradin inversé d'ordre p de hauteur n-2 et par un multiplieur de type Zuras Mc Allister. Une étude comparative des propriétés des multi- plieurs cellulaires en arbre de type gradin inversé d'ordre p= 2 ou d'ordre p plus grand que 2, par rapport au multiplieur théorique de Wallace, et par rapport à des structures de multiplieur en arbre de types connus de l'art antérieur tels que notamment les réseaux itéra- tifs d'additionneurs ARC, les arbres ZM, ou les multi- plieurs de type 4-2, sera maintenant décrite en liaison avec les figures 6 a, 6 b. Sur la figure 6 a on a représenté un diagramme de variation du nombre N d'opérandes susceptible d'être traité par des différents types d'arbres précités en fonction de la hauteur N de ces multiplieurs dans les structures d'arbres précédemment mentionnées Ainsi, sur la figure 6 a ont été successivement représentés: 1) Multiplieur théorique de Wallace, 2) Multiplieur de type 4-2, 3) Multiplieur cellulaire de type gradin inversé d'ordre 3 noté, en référence à la désignation anglo- saxonne "d'overturned stairs" pour gradin inversé O 53, 4) Multiplieur hybride gradin inversé d'ordre 2 052 plus arbre ZM, O 52 + ZM, ) Gradin inversé d'ordre 2 052, 6) Multiplieur hybride gradin inversé OS plus arbre ZM, OS+ZM, 7) Arbre ZM d'ordre 2, ZM 2, 8) Multiplieur cellulaire en arbre de type gradin inversé OS, 9) Multiplieur en arbre ZM. Sur la figure 6 b on a représenté un tableau des valeurs donnant respectivement dans la colonne A la va- leur de la hauteur n, puis dans les colonnes B à K res- pectivement les mêmes valeurs de nombre d'opérandes ma- ximum susceptibles d'être traitées par les structures 1 à 9 déjà désignées en figure 6 a Les valeurs contenues dans la colonne à gauche de la colonne A sont les va- leurs de la hauteur du multiplieur, compte tenu de la racine R. De l'observation des figures 6 a et 6 b on peut déduire que les structures en arbre ZM atteignent la li- mite de Wallace et sont donc aussi performantes que les structures de Wallace pour des nombres d'opérandes N compris inclusivement entre 3 et 8, 10-11 et pour N= 14 en terme de hauteur nécessaire correspondante des ar- bres On constate également que les structures en arbre ZM sont cependant très éloignées de la structure théori- que de Wallace pour les valeurs supérieures de N. De même, en ce qui concerne le multiplieur cel- lulaire en arbre de type gradin inversé tel que repré- senté en figure 2 b par exemple, objet de la présente invention, celui- ci permettant de réaliser une sommation S ( 18,2), la hauteur de la structure en arbre correspon- dante est égale à 6, cette hauteur étant égale à celle d'un arbre de Wallace théorique idéal permettant d'assu- rer une sommation de type S( 19-2), alors qu'une struc- ture en arbre ZM nécessite, pour réaliser une sommation S ( 18-2), une hauteur n= 7 On conclut ainsi que la structure en arbre de type gradin inversé objet de la présente invention, permettant de réaliser une sommation S ( 18,2) est plus proche de la limite inférieure de Wallace que la structure équivalente en arbre ZM Cette constatation est également vraie pour les autres valeurs de N. En outre, l'étude de la figure 6 b montre que les multiplieurs cellulaires en arbre de type gradin inver- sé, objets de la présente invention atteignent la limite inférieure de Wallace pour N compris entre 3 et 18, 20 et 24, et 29 et 31. Par contre l'observation de la même figure 6 b montre que les multiplieurs en arbre de type gradin in- versé, objet de la présente invention n'atteignent pas l'optimum par rapport à la limite inférieure de Wallace pour les valeurs de N telles N= 19, 25 32. En ce qui concerne les multiplieurs cellulaires en arbre de type hybride OS+ZM, l'observation de la figure 6 b montre également que ces structures atteignent la limite inférieure de Wallace pour un nombre d'opérandes N tel que: N= 19, 25 On notera en outre, que les structures préci- tées, par rapport aux structures de type arbre ZM de l'art antérieur, nécessitent seulement un fil de connection inter-couches en plus que les structures en arbre ZM précitées. En ce qui concerne la mise en oeuvre des multi- plieurs cellulaires en arbre de type gradin inversé, ob- jets de la présente invention, tels que décrit précédem- ment dans la description, celle-ci peut être réalisée par intégration sur un substrat de silicium par exemple. * Le processus d'intégration peut alors être facilité et optimisé par le choix de la structure la plus appro- priée, structure en arbre simple de type gradin inversé ou structure hybride, le choix de ces structures étant dicté, d'une part, en fonction de l'optimisation de la structure vis-à-vis de la limite inférieure de Wallace ainsi que décrit précédemment en liaison avec les figu- res 6 a et 6 b, et, d'autre part, en liaison avec le gain en nombre de fils de connexion inter-couches pour chaque structure, ainsi qu'il sera décrit en liaison avec les tableaux 1 et 2 joints en annexe de la présente description. Sur le tableau 1 on a porté dans la première colonne les différentes structures telles que déjà men- tionnées sur la figure 6 b dans les colonnes B à K, dans la colonne 2 on a représenté le nombre de fils de con- nexion inter-couches désigné par TLW, en colonne 3 le temps de sommation ou de traitement ST, et en colonne 4 le nombre N d'opérandes susceptibles d'être traités en fonction de la hauteur N de l'arbre. Le tableau 2 de l'annexe précitée indique le nombre de fils de connexion inter-couches TLW nécessaire dans un multiplieur cellulaire de type N,2 optimal uti- lisant des structures en arbre de transparence constan- te On rappelle que la transparence désigne pour une structure en arbre déterminée, le nombre minimum de fils de connexion inter-couches nécessaire pour chaque degré constitutif de la structure précitée On remarquera que le nombre porté entre parenthèses sur la colonne TLW du tableau 2 indique les différences de hauteur entre les structures précitées et les structures en arbre de Wallace théoriques. Afin de réaliser un multiplieur cellulaire en arbre sous forme de circuit intégré, un procédé conforme à l'objet de la présente invention peut consister à éta- blir un multiplieur cellulaire en arbre en tranches de bits selon une topologie verticale ainsi que représentée en figure 3 c, pour constituer un ou plusieurs degrés d'un multiplieur cellulaire au niveau bits, puis à répé- ter l'opération précitée en nombre de fois correspondant au nombre de bits constitutifs d'un mot, représentatif d'un opérande à multiplier pour constituer un ou plu- sieurs degrés d'un multiplieur cellulaire au niveau mot. En référence à la figure 3 a, l'opération précitée peut être réalisée dans une des directions de la surface de la puce constituant le circuit intégré, par exemple la dimension Y. Ensuite, le procédé objet de la présente inven- tion consiste à établir un arrangement des degrés d'un multiplieur cellulaire au niveau mot selon une topologie horizontale, la dimension X par exemple selon la figure 3 a pour constituer un multiplieur cellulaire en arbre de type gradin inversé. Bien entendu, la mise en oeuvre du procédé pré- cité peut être optimisée par le choix de la structure réelle en arbre simple ou en arbre hybride ainsi que mentionné précédemment Le nombre minimum de fils de connexion inter-couches peut alors être choisi en réfé- rence au tableau 2 joint en annexe, pour les valeurs de nombre d'opérandes N pondantes étant ainsi minimales On notera que par ce choix, les multiplieurs cellulaires en arbre et leurs variantes hybrides mises en oeuvre conformément au pro- cédé, objet de l'invention, sont alors aussi performan- tes que les arbres de Wallace théoriques correspondants. Bien que les arbres ainsi mis en oeuvre ne puissent pré- tendre atteindre la limite inférieure de Wallace pour N= 42,61 à 63,89 à 94 ainsi qu'il résulte de l'observa- tion du tableau 2, la distance minimum est indiquée pour les cas précités Les arbres de structure en arbre de type gradin inversé, objet de la présente invention constituent alors les meilleurs approximations des structures théoriques de Wallace parmi les solutions disponibles. On notera enfin que les multiplieurs cellulaires en arbre objet de la présente invention, de type gradin inversé, peuvent être utilisés pour la mise en oeuvre d'additionneurs multiopérandes. On a ainsi décrit un multiplieur cellulaire en arbre de type gradin inversé et son procédé de mise en oeuvre, lesquels permettent d'atteindre dans la majorité des cas des configurations optimales proches des struc- tures correspondantes théoriques dites en arbre de Wallace On notera en outre que les structures en arbre de type gradin inversé, objet de la présente invention nécessitent des configurations d'inter-connexions inter- couches simples et régulières, lesquelles peuvent être optimisées de façon à rendre la structure résultante équivalente aux structures en arbre de Wallace dans les cas les plus usuels. Annexe: Tableau i TLW ST N o 2 ( log 2 N-2) ? O(N) O( 2 N 1/2) 0 ( 2 N)1/2) 0 ( 2 ( 3 N)1/3) O( ( 12 N)1/3) O(( 6 N)1/3) 0 ( 2 ( 3 N)1/4) O( ( 24 N)1/4) 0 ( 210 og 2 N) O(log 3/2 N) n+ 2 n 2/4 +n/2 +l 17-( -1)nl/8 n 2/2-n/2 + 3 n 3/24 +l 43-3 (-1)nln/48 + 2 n 3/12-3 N 2/8 + 29 n/12-l 1-(-l)nl/16 n3/6-3 N 2/2 + 22 n/3-7 n 4/48-n 3/3 + 35 N 2/12-29 n/3 + 17 +l 1-( 1)nl/32 n 4/24-11 N 3/12 + 215 N 2/24-445 n/12 + 63 2 n/2 + 1 2 ( 3/2)n11 Tableau 2 N 43-52 53-59 61-63 64-70 71-83 84-87 89-92 93-94 -114 -125 126-129 ICSA ZM OS ZM 2 OS+ZM O 52 +ZM 4-2 Wallace N 3-4 -8 -11 12-13 -18 -24 -27 29-31 32-38 39-41 TLW O TLW 6 (+ 1) (+ 1) (+ 1) 6 (+ 1) REVENDICATIONS 1 Multiplieur cellulaire en arbre de type gra- din inversé, comportant une pluralité d'additionneurs à retenue conservée interconnectés, caractérisé en ce que, pour constituer un multiplieur d'ordre p et de hauteur n+l celui-ci est formé par: une racine (R) constituée par un additionneur à retenue conservée, un corps de multiplieur CO(p,n) d'ordre p et de hauteur N o p désigne un paramètre de temps de trai- tement de sommation de la forme N 1/(p+ 1),N désignant le nombre d'opérandes à traiter, ledit corps étant formé par: un opérateur connecteur à cinq entrées de rang q, noté C(n,q), l'opérateur connecteur de rang 1 C(n,1) étant interconnecté à ladite racine R, ledit opérateur connecteur C(n,q) compor- tant un premier et un deuxième additionneur à retenue conservée connectés en cascade, le premier et le deuxième additionneur à retenue conservée comportant chacun trois entrées, une sortie somme et une sortie retenue, la sortie retenue dudit premier additionneur étant con- nectée à une entrée dudit deuxième addition- neur, l'opérateur connecteur C(n,q) comportant trois sorties constituées par la sortie somme du premier additionneur, la sortie somme et la sortie retenue du deuxième additionneur, un arbre d'ordre p-1 et de hauteur n-2 consti- tué par un agencement d'additionneurs à rete- nue conservée interconnectés, les sorties somme et retenue de l'additionneur à retenue conservée constituant racine (r) de cet arbre étant respectivement connectées à une entrée du premier additionneur dudit opérateur con- necteur C(n,q), un corps de multiplieur CO(p,n-1) d'ordre p et de hauteur inférieure (n-1), ledit corps de multiplieur étant formé de manière analogue au corps de multiplieur de hauteur supérieure n, et connecté audit opérateur connecteur C(n,q). 2 Multiplieur selon la revendication 1, carac- térisé en ce que lesdits additionneurs sont agencés en degrés de hauteur N et de rang q, chaque degré Dq étant formé, pour q un opérateur connecteur Cq à cinq entrées com- portant un premier et un deuxième additionneur connectés en cascade, ledit opérateur connecteur Cq étant inter- connecté, d'une part, à ladite branche Bq pour former ledit degré Dq de hauteur n, o N représente le nombre d'additionneurs de ce degré, et, d'autre part à l'opéra- teur connecteur Cq+l de rang supérieur de façon à for- mer, pour le sous-ensemble constitué par les Q-q degrés de rang supérieur, un corps de multiplieur cellulaire en arbre de structure arborescente correspondante, les degrés de rang Q-1 et Q étant respectivement constitués par un connecteur et par un additionneur, ledit multi- plieur comportant en outre: un additionneur de sortie ARC, l'opérateur connecteur de rang 1, Cl, étant interconnecté audit additionneur de sortie ARC. 3 Multiplieur selon la revendication 2, carac- térisé en ce que chaque branche Bq de rang q comportant n-2 additionneurs successifs, comprend N entrées d'opé- randes. 4 Multiplieur selon la revendication 3, carac- térisé en ce que les sorties de somme et de retenue d'un additionneur h de chaque branche Bq sont reliées aux entrées correspondantes de l'additionneur h+l successif suivant. Multiplieur selon l'une des revendications 3 ou 4, caractérisé en ce que chaque opérateur connecteur Cq d'ordre q tel que 1 additionneur C(q+l),l de l'opérateur connec- teur de rang supérieur Cq+l, la sortie retenue et la sortie somme du pre- mier additionneur sont respectivement reliées à une entrée opérande du deuxième additionneur et à une entrée opérande du premier addition- neur C(q-1),l de l'opérateur connecteur Cq-l de rang inférieur q-1, deux entrées opérande du deuxième additionneur Cq,2 sont respectivement reliées à la sortie somme et à la sortie retenue du deuxième addi- tionneur C(q+ 1),2 de l'opérateur connecteur Cq+ 1 de rang supérieur q+ 1. 6 Multiplieur selon l'une des revendications précédentes, caractérisé en ce que lesdits additionneurs sont disposés selon une topologie plane et verticale. 7 Multiplieur selon l'une des revendications précédentes, caractérisé en ce que, en vue de constituer un multiplieur cellulaire en arbre de type gradin inver- sé de hauteur n= 7 et d'ordre 1 à 24 opérandes celui-ci comporte: un premier degré (D 1) formé par d'une part, un opérateur connecteur C dont les trois sorties sont reliées à la racine R, et, d'autre part, un arbre formant une branche B constituée par quatre additionneurs ARC en cascade, l'addi- tionneur ARC formant racine r dudit arbre étant connecté aux trois bornes d'entrée du premier additionneur ARC constitutif dudit opérateur connecteur C, un corps de multiplieur CO formant multiplieur élémentaire de type gradin inversé formé par cinq degrés successifs D 2 à D 6, l'opérateur connecteur C 2 du degré D 2 étant interconnecté aux deux entrées du deuxième additionneur ARC constitutif dudit opérateur conecteur C. 8 Multiplieur selon la revendication 7, carac- térisé en ce que, en vue de constituer un multiplieur cellulaire de hauteur N d'ordre p > 2, lesdits degrés de rang 1 et 2 sont remplacés par un premier multiplieur cellulaire élémentaire (Mel) de hauteur n-3 et d'ordre p-l, lesdits degrés de rang q > 3 étant arrangés de fa- çon à constituer un deuxième multiplieur cellulaire élé- mentaire (Me 2) de hauteur n-2 et d'ordre p, les premier et deuxième multiplieur élémentaire étant interconnectés à un connecteur (C). 9 Multiplieur selon la revendication 8, carac- térisé en ce que, en vue de constituer un multiplieur cellulaire de hauteur 7 et d'ordre 2 à 28 opérandes, ledit premier multiplieur élémentaire comprend une ra- mure comportant: un opérateur connecteur (Cell) et un addi- tionneur de sortie (AC Sl) connecté à cet opérateur connecteur, ladite ramure compor- tant, une première sous-ramure formée par une bran- che Bel connectée à cet opérateur connecteur, une deuxième sous-ramure formée par un opéra- teur connecteur (Ce 12) connecté à l'opérateur connecteur (Cell) de ladite ramure, une troisième sous-ramure formée par une bran- che (Be 3) connectée audit opérateur connecteur (Ce 12) de ladite deuxième sous-ramure, ledit additionneur de sortie (AC Sl) étant con- necté audit opérateur connecteur (C) pour for- mer le degré de rang 1 pour le multiplieur. Multiplieur selon la revendication 8 ou 9, caractérisé en ce que, en vue de constituer ledit multi- plieur cellulaire de hauteur 7 d'ordre 2 à 28 opéran- des, ledit deuxième multiplieur élémentaire comprend un opérateur connecteur (Ce 21), ledit deuxième multiplieur élémentaire (Me 2) comportant en outre: une première ramure comportant une première et une deuxième sous-ramure, ladite première sous-ramure étant formée par un opérateur con- necteur (Ce 211) et par un additionneur de sor- tie (AC 52) connecté d'une part à l'opérateur connecteur (Ce 21) du deuxième multiplieur élémentaire (Me 2) et à l'opérateur connecteur (Ce 211) de ladite première sous-ramure, ladite deuxième sous- ramure étant formée par une branche (be 22) connectée audit opérateur connecteur (Ce 211) de ladite première sous-ramure, une deuxième ramure formée par quatre degrés de rang Q Q-i, Q-2, Q-3 selon la revendica- tion 1. 11 Multiplieur selon l'une des revendications 8 à 10 précédentes, caractérisé en ce qu'en vue de réali- ser un multiplieur cellulaire de type hybride gradin- inversé/Zuras-Mc Allister de hauteur N d'ordre p > 2 ledit premier multiplieur cellulaire élémentaire de de- gré n-3 est constitué par un multiplieur de type gradin inversé d'ordre p-l et d'un multiplieur de type Zuras-Mc Allister, ledit deuxième multiplieur cellulaire élémen- taire, étant constitué par un multiplieur de type gradin-inversé, d'ordre p, de hauteur n-2, et par un multiplieur de type Zuras-MC Allister. 12 Procédé de mise en oeuvre d'un multiplieur cellulaire en arbre formé par une pluralité d'addition- neurs à retenue conservée interconnectés, caractérisé en ce que ledit procédé consiste: a) à établir un multiplieur cellulaire en ar- bre en tranches de bits selon une topologie verticale, pour constituer un ou plusieurs degrés d'un multiplieur cellulaire au niveau bit, b) à répéter l'opération a) un nombre de fois correspondant à un nombre de bits constitutif d'un mot représentatif d'un opérande à multiplier pour constituer un ou plusieurs degrés d'un multiplieur cellulaire au niveau mot, c) à établir un arrangement desdits degrés d'un multiplieur cellulaire au niveau mot selon une to- pologie horizontale pour constituer un multiplieur cel- lulaire en arbre de type gradin-inversé. 13 Utilisation d'un multiplieur cellulaire en arbre de type gradin inversé, selon l'une des revendica- tions 1 à 11, pour la mise en oeuvre d'un additionneur multiopérandes.