Brevet FR2775531A1 — publié le 19990903

ADDITIOCEUR NURIQUE RAPIDE La présente invention concerne le domaine des addition- neurs numériques et plus particulièrement les additionneurs numériques utilisant une technique à anticipation de retenue (carry look-ahead). La figure 1 représente de manière schématique et partielle un additionneur 8 bits à anticipation de retenue classique permettant de calculer A + B = S o A, B et S sont codés sur huit bits. Un premier bloc 1 de l'additionneur comprend huit cellules 11 identiques ayant chacune deux entrées et un couple de sorties. Une cellule 11 de rang i est connectée pour recevoir sur sa première entrée le bit Ai et sur sa deuxième entrée le bit Bi. Elle produit un premnier signal Pi tel que Pi = Ai + Bi et un signal de sortie Gi tel que Gi = Ai Bi. Un deuxième bloc de l'additionneur reçoit les 8 couples de signaux {P1, G1} à {P8, G8} provenant du bloc 1. Le bloc 2 est composé de cellules élémentaires identiques 21 connectées pour calculer à partir des huit couples de signaux {Pl, G1} à {P8, G8}, huit couples de signaux de sortie {Pl, g1} à {P8, g8}. Si k est compris entre 2 et 8, Pk est tel que k Pk = Pi, avec pl=Pl, =et gk est tel que et gk est tel que k - 1 k -1 Gi ri+ Pj +G k avec gl--G1 Les 8 couples {Pl, gj} à {P8, g8} produits par le bloc 2 permettent de calculer la sonmme S telle que A + B = S. Si CO est la retenue entrante de l'opération A+B, chaque terme Si de la somme Sest donné par la formule Sk = (Co Pk-1 + gk-l) G Ak e Bk, avec S1 = CO e Ak e Bk. De même, si Cn est la retenue sortante de l'opération A+B, Cn est donnée par la formule Cn = CO pn + gn. Le calcul des termes Sk et Cn est effectué par un bloc 3 de l'additionneur, de structure bien connue de l'état de la tech- nique. Une cellule élémentaire 21 comprend deux couples d'entrées {El, E2} et {E3, E4} et un couple de sorties {O1, 02}. La sortie 01 est telle que 01 = El E3 et la sortie 02 est telle que 02 = E2 À E4 + E3. On remarque qu'il ne faut aucune cellule 21 pour calculer le couple {Pl, gl} car {Pl, g1} = {P1, G1}. Par contre, une cellule 21 est nécessaire pour calculer {P2, g2} à partir de {Pl, G1} et {P2, G2}. De même, il faut une cellule 21 supplémentaire pour calculer {p3, g3} à partir de {P2, g2} et {P3, G3}. L'additionneur considéré est un additionneur 8 bits. On a 8 = 23 et on peut considérer que le bloc 2 est organisé en une matrice de huit rangées et trois colonnes, un emplacement de la matrice étant occupé par une cellule 21 ou laissé vide. On remar- que que les cellules 21 de la troisième colonne du bloc 2 reçoivent sur leur premier couple d'entrées {El, E2} le couple de sorties {01, 02} produit par la dernière cellule 21 de la pre- mière moitié de la deuxième colonne du bloc 2. De même, si l'on considérait un additionneur 16 bits, le bloc 2 de l'additionneur 16 bits comporterait quatre colonnes et seize rangées, et les huit cellules de la quatrième colonne du bloc 2 recevraient sur leur premier couple d'entrées {El, E2} le couple de sorties {01, 02} de la dernière cellule 21 de la pre- mière moitié de la troisième colonne. Un inconvénient majeur de cette architecture est qu'elle comporte un chemin critique dans lequel une cellule 21 successive commande deux fois plus de cellules que la cellule précédente. Plus spécifiquement, une cellule 1il commande une seule cellule de la première colonne. Certaines cellules de la première colonne commandent chacune deux cellules de la deuxième colonne. Certaines cellules de la deuxième colonne commandent chacune quatre cellules de la troisième colonne, etc. Pour ne pas augmenter le temps de propagation entre une première cellule qui commande n cellules et l'une de ces n cellules, la sortance de la première cellule doit être de n, c'est-à-dire que les transistors de sortie de la première cellule doivent avoir une taille n fois supérieure à la taille minimale. Toutefois, l'augmentation de la taille des transistors de sortie d'une cellule augmente le temps de propagation de la cellule, puisque les capacités de grille de ces transistors seront plus élevées et plus longues à charger. Ainsi, on ne parviendra pas à rendre le temps de propagation d'un chemin critique aussi faible que celui d'un chemin non-critique, sauf à adapter la taille de tous les transistors se trouvant sur le chemin critique, ce qui est pratiquement irréalisable. De plus, le circuit comprendra des cellules 21 de fonc- tion identique mais de taille différente. Ces cellules 21 de tailles différentes devront être créées dans une bibliothèque spéciale d'un système de conception, ce qui augmente le nombre de cellules à gérer par le concepteur. De même, lors de la conception d'un additionneur, l'implantation physique des diverses cellules 21 devra être faite avec grand soin pour optimiser au mieux le temps de propagation du chemin critique. Un objet de la présente invention est de proposer une architecture permettant de réaliser un additionneur à anticipa- tion de retenue ayant un fonctionnement particulièrement rapide. Un autre objet de la présente invention est de proposer un tel additionneur n'occupant pas une surface plus élevée qu'un additionneur à anticipation de retenue classique. Un autre objet de la présente invention est de proposer une telle architecture d'additionneur simplifiant la gestion d'une bibliothèque d'un système de conception. Ces objets ainsi que d'autres sont atteints par un additionneur numérique permettant d'additionner un premier opérande A de n bits et un deuxième opérande B de n bits, avec n=2m, comprenant: un premier bloc calculant des couples de signaux Pq et Gq à partir des bits de rang q, Aq et Bq, du premier et du deuxième opérande avec Pq = Aq + Bq et Gq = Aq Bq; un deuxième bloc formé d'une matrice de cellules élémentaires de fonctions identiques disposées en n rangées et m colonnes, une cellule élémentaire ayant deux couples d'entrées {El, E2} et {E3, E4} et un couple de sorties {01, 02}, fournis- sant 01 = El E3 et 02 = E2 E4 + E3; une cellule élémentaire normale, c'est-à-dire d'une colonne i et d'une rangée j, j étant compris entre k2i - 2i-1 + 1 et k2i, avec k variant entre 1 et 2m-i, recevant: sur son premier couple d'entrées le couple {Pj-l, Gj-l} si i=l et le couple de sorties provenant de la cellule élémentaire de colonne i-l et de rangée (k-1)2i + 1 sinon, sur son second couple d'entrées le couple {Pj, Gj} si j = k2i - 2i-1 + 1 ou i = 1, et le couple de sorties provenant de la cellule élémentaire de rangée j et de colonne r+l, r étant défini de sorte que 2r+l élémentaire de colonne i-1 et de rangée k2i - 2i-1 + 1 sinon. Selon un autre aspect de la présente invention, les cellules normales ont une taille inférieure à celle des cellules auxiliaires. Selon un autre aspect de la présente invention, l'additionneur numérique comprend des moyens pour, au moins dans la colonne de rang le plus élevé, sélectionner en tant que sortie les couples de sortie des cellules normales ou bien les seconds couples d'entrées de ces cellules. Ces objets, caractéristiques et avantages, ainsi que d'autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles: la figure 1 représente schématiquement l'architecture d'un additionneur à anticipation de retenue classique; la figure 2 représente schématiquement l'architecture d'un additionneur à anticipation de retenue selon la présente invention; et la figure 3 représente une variante de l'additionneur de la figure 2. En figure 2, un additionneur 8 bits à anticipation de retenue selon la présente invention comprend un bloc 1 composé de cellules 11 produisant huit couples de signaux {Pi, Gi} à partir des bits Ai et Bi des opérandes A et B. La structure du bloc 1 est la même que celle du bloc 1 classique de la figure 1. Un bloc 2 reçoit les 8 couples de signaux {Pl, G1} à {P8, G8} provenant du bloc 1 et génère 8 couples de sorties {Pl, gl} à {P8, g8} tels que ceux décrits en relation avec la figure 1. Le bloc 2 est organisé en une matrice de cellules 21 identiques, et de même fonction qu'en figure 1. La matrice comprend huit rangées et trois colonnes pour un additionneur 8 bits, avec 8 = 23. Pour un additionneur n bits avec n = 2m, le bloc 2 de l'additionneur est organisé en une matrice de cellules 21 de n rangées et m colon- nes. On distinguera par leur connexion deux types de cellules 21 dans le bloc 2: les cellules normales et les cellules auxiliaires. Les cellules normales sont blanches et les cellules auxiliaires sont hachurées en figure 2. Une cellule normale est une cellule 21 existant dans un additionneur classique, c'est à dire de colonne i et de rangée j, j étant compris entre k2i - 2i-1 + 1 et k2i, avec k variant entre 1 et 2m-i. En d'autres termes, les cellules normales sont celles que l'on retrouve aux rangs pairs de la première colonne, aux couples de rangs pairs de la deuxième colonne, aux quadruplets de rangs pairs de la troisième colonne, . aux 2i-1-uplets de rangs pairs de la ième colonne. En l'occurrence, k désigne le numéro dans la colonne i du 2i-l1-uplet de cellules normales contenant la..DTD: cellule de rangée j. Si une cellule normale appartient à la première colonne, elle reçoit sur son premier couple d'entrées {El, E2} un couple {Pj-, Gji} provenant du bloc 1 et sur son deuxième couple d'entrées {E3, E4} un couple {Pj, Gj} provenant du bloc 1. Si une cellule normale ne fait pas partie de la pre- mière colonne, elle reçoit sur son premier couple d'entrées {El, E2} le couple de sorties {01, 02} provenant de la cellule 21 de colonne i-l et de rangée (k-1)2i+l. Si j est tel que j = k2i - 2i- 1 + 1, c'est-à-dire si la cellule normale est la première d'un 2i-1-uplet de rang pair de la ième colonne, la cellule normale reçoit sur son second couple d'entrées {E3, E4} le couple {Pj, Gj} provenant du bloc 1. Sinon, la cellule normale reçoit sur son second couple d'entrées {E3, E4} le couple de sorties {O1, 02} provenant de la cellule 21 de rangée j et de colonne r+l o r est calculé à partir de j, tel que 2r+l {01, 02} de la cellule de colonne 1 et de rangée 8, avec j - (k-l)2i - 2i-1 = 2, et r = 0. On remarquera que les cellules élémentaires normales sont toutes connectées de manière classique à l'exception des premiers couples d'entrées {El, E2} des cellules normales n'ap- partenant pas à la première colonne. On remarquera également que, selon la présente invention, le couple de sorties {01, 02} d'une cellule normale ne commande au plus qu'une seule cellule 21. Une cellule auxiliaire est une cellule 21 de colonne i et de rangée j, j étant compris entre (k-1)2i + 1 et k2i - 2i-l o k varie entre 1 et 2m-i. En d'autres termes, les cellules auxiliaires sont celles que l'on retrouve aux rangs impairs de la pre- mière colonne, aux couples de rangs impairs de la deuxième colonne, aux quadruplets de rangs impairs de la troisième colonne... aux 2i-1-uplets de rangs impairs de la colonne i. Conmme pour les cellules normales, k désigne le numéro dans la colonne i du 2i-1- uplet de cellules auxiliaires contenant la cellule de rangée j. Selon la présente invention, toutes les cellules 21 auxiliaires consécutives dans une colonne sont connectées en parallèle par leurs entrées et leurs sorties. Les cellules auxi- liaires de la première colonne, associées chacune à une valeur différente de k, reçoivent chacune sur leur premier couple d'entrées {El, E2} un couple {Pj, Gj} provenant du bloc 1 et sur leur second couple d'entrées {E3, E4} un couple {Pj+i, Gj+i} provenant du bloc 1. Les cellules auxiliaires des autres colonnes (i dif- férent de 1) reçoivent chacune sur leur premier couple d'entrées {El, E2} le couple de sorties {O1, 02} provenant de la cellule de colonne i-1 et de rangée (k-1)2i+l et sur leur deuxième couple d'entrées {E3, E4} le couple de sorties {01, 02} provenant de la cellule de colonne i-1 et de rangée k2i - 2i-1 + 1. Par exemple, dans la figure 2, les cellules de colonne 3 et de rangées 1, 2, 3 et 4 du bloc 2 reçoivent chacune sur leur premier couple d'entrées {El, E2} le couple de sorties {(01, 02} produit par la cellule de colonne 2 et de rangée 1 et sur leur deuxième couple d'entrées {E3, E4} le couple de sorties {01, 02} produit par la cellule de colonne 2 et de rangée 5. On remarquera que la cellule de colonne 2 et de rangée 1 et la cellule de colonne 2 et de rangée 2 reçoivent les mêmes entrées, et produisent ensemble le même couple de sorties {O1, 02} et présentent donc une sortance double. En observant les connexions des cellules élémentaires du bloc 2, on remarquera également que le couple de sorties {01, 02} produit en parallèle par les cellules de colonne 2 et des rangées 1 et 2 est une copie, produite avec une sortance double, du couple de sorties {01, 02} produit par la cellule de colonne 2 et de rangée 4. Le couple de sorties {01, 02} produit en parallèle par les cellules de colonne 2 et de rangées 1 et 2 est fourni au premier couple d'entrées {El, E2} des cellules normales de troi- sième colonne à la place, dans une structure classique, du couple de sorties {01, 02} produit par la cellule de colonne 2 et de rangée 4. En d'autres termes, la présente invention consiste, dans le bloc 2, à générer au moyen des cellules auxiliaires des copies des couples de sorties {01, 02} qui, dans l'art antérieur, servaient chacun à commander plusieurs cellules élémentaires. On remarque également que plus le nombre de colonnes de l'additionneur considéré est élevé, plus on dispose de cellules auxiliaires pour créer les copies des couples de sorties. Si l'on reprend l'exemple d'un additionneur 32 bits, le chemin critique traverse 8 cellules 21 parallèles conmmandant 32 cellules, 4 cellules 21 parallèles commandant 16 cellules, 2 cellules 21 parallèles commandant 8 cellules, une cellule 21 commandant 4 cellules et une cellule 11 commandant 2 cellules. Ainsi, la sortance maximale nécessaire est de 4, contre 16 dans l'état de la technique. Le temps de traversée de chaque étage du chemin critique se trouve ainsi réduit au temps de traversée d'une cellule 21 de sortance 4, et la vitesse de l'additionneur selon la présente invention est notablement accrue par rapport à l'art antérieur. De plus, on remarque que toutes les cellules 21 utili- sées selon la présente invention ont une sortance de 4. En d'autres termes, elles sont de même taille, ce qui facilite leur disposition en matrice. On pourra réaliser un additionneur dont la taille ne dépasse pas la taille d'un additionneur selon l'art antérieur, organisé en matrice de m colonnes et n rangées, puisque les cellules ajoutées selon la présente invention n'occupent que les emplacements qui sont généralement laissés vides dans l'architecture classique. La taille unique des cellules 21 utilisées selon la présente invention évite de devoir créer et gérer une sous- bibliothèque spéciale contenant toutes les cellules 21 de taille différente, et permet de supprimer les problèmes liés au compromis sortance/temps de propagation lors de la conception d'un additionneur. D'autre part, les cellules normales ne commandant qu'une seule cellule, leur sortance peut être divisée par 4 par rapport à la sortance d'une cellule auxiliaire. Une telle diminu- tion de sortance s'accompagne d'une diminution de taille et de l'entrance, c'est-à-dire du temps de propagation, de la cellule. La moitié des cellules 21 commandées par un groupe de cellules auxiliaires connectées en parallèle étant des cellules normales, une diminution de l'entrance des cellules normales permet de diminuer la sortance des cellules auxiliaires, et d'augmenter leur vitesse de fonctionnement. Il est ainsi possible, en utili- sant une taille différente pour les cellules 21 normales et les cellules 21 auxiliaires, d'augmenter encore la vitesse de fonc- tionnement de l'additionneur selon la présente invention. Un aspect remarquable de la présente invention est qu'elle se prête particulièrement bien à une architecture d'un additionneur permettant d'effectuer des opérations sur un nombre variable de bits. La figure 3 représente de manière schématique l'archi- tecture d'un additionneur de taille variable selon la présente invention. L'additionneur représenté en figure 3 permet, en fonction d'un bit de commande COM, d'additionner deux opérandes A et B de huit bits ou quatre opérandes A, B et C, D de quatre bits. Les mêmes références désignent les mêmes éléments en figure 3 et en figure 2. Les cellules de colonne 3 et de rangées 5 à 8 du bloc 2 de l'additionneur sont des cellules 22 d'un type particulier, recevant un bit de commande COM. Une cellule 22 reçoit deux couples d'entrées {El, E2} et {E3, E4}, tout commne une cellule 21, mais sa sortie {O1, 02} reçoit, en fonction du bit de commande COM, soit des signaux tels que O1=El-E3 et 02=E2.E4+03, soit des signaux tels que 01 = E3 et 02 = E4. En d'autres termes, une cellule 22 possède les mêmes fonctions qu'une cellule 21 et peut de surcroît devenir transparente vis-à-vis de son deuxième couple d'entrées, {E3, E4} en réponse au signal de conmmande COM. Lorsque le signal COM est inactif, les cellules 22 se comportent de la même manière que les cellules 21, et l'addition- neur représenté en figure 3 permet d'additionner deux opérandes de huit bits, et lorsque le signal COM est actif, les cellules 22 sont transparentes vis-à-vis de leur deuxième couple d'entrées {E3, E4}, et l'additionneur représenté en figure 3 permet, commne cela a été représenté, d'additionner deux couples A, B et C, D de quatre bits. On remarquera aisément qu'il est possible, en rem- plaçant les cellules 21 de la deuxième colonne de l'additionneur de la figure 3 par les cellules 22 commandées par un deuxième signal de commande, de passer d'un additionneur de deux fois quatre bits à un additionneur de quatre fois deux bits. De même, on adaptera aisément la présente description à des additionneurs seize bits, trente deux bits ou soixante quatre bits. Pour des raisons de clarté, la présente invention a été décrite en relation avec un additionneur huit bits, mais l'inté- rêt de la présente invention sera d'autant plus grand que le nombre de bits de l'additionneur sera élevé. De même, la présente invention est susceptible de nombreuses variantes et modifications qui apparaîtront à l'homme du métier. A titre d'exemple, la présente invention utilise un nombre égal de cellules normales et de cellules auxiliaires dans le bloc 2 de l'additionneur, mais le nombre de cellules auxi- liaires pourra éventuellement être réduit ou augmenté en fonction des besoins. De même, la présente invention a été décrite en5 relation avec des additionneurs ayant un nombre de bits égal à une puissance de 2, mais l'homme de l'art pourra sans difficulté adapter la présente description à des additionneurs traitant un nombre différent de bits. REVENDICATIONS 1. Additionneur numérique permettant d'additionner un premier opérande A de n bits et un deuxième opérande B de n bits, avec n=2m, comprenant: un premier bloc (1) calculant des couples de signaux Pq et Gq à partir des bits de rang q, Aq et Bq, du premier et du deuxième opérande avec Pq = Aq + Bq et Gq = Aq Bq; un deuxième bloc (2) formé d'une matrice de cellules élémentaires de fonctions identiques disposées en n rangées et m colonnes, une cellule élémentaire ayant deux couples d'entrées {El, E2} et {E3, E4} et un couple de sorties {O1, 02}, fournis- sant 01 = E1 E3 et 02 = E2 E4 + E3; une cellule élémentaire normale, c'est-à-dire d'une colonne i et d'une rangée j, j étant compris entre k2i - 2i-1 + 1 et k2i, avec k variant entre 1 et 2m-i, recevant: sur son premier couple d'entrées le couple {Pj_1, Gj-1} si i=1 et le couple de sorties provenant de la cellule élémentaire de colonne i-1 et de rangée (k-1)2i + 1 sinon, sur son second couple d'entrées le couple {Pj, Gj} si j = k2i - 2i-1 + 1 ou i = 1, et le couple de sorties provenant de la cellule élémentaire de rangée j et de colonne r+1, r étant défini de sorte que 2r+l élémentaire de colonne i-1 et de rangée k2i - 2i-1 + 1 sinon. 2. Additionneur numérique selon la revendication 1, caractérisé en ce que les cellules normales ont une taille inférieure à celle des cellules auxiliaires. 3. Additionneur numérique selon la revendication 1 ou 2, caractérisé en ce qu'il comprend des moyens pour, au moins dans la colonne de rang le plus élevé, sélectionner en tant que sortie les couples de sortie des cellules normales ou bien les seconds couples d'entrées de ces cellules.