Fonctionnement d'un ordinateur/Les circuits pour l'addition et la soustraction

Tout circuit de calcul peut être conçu par les méthodes vues dans les chapitres précédents. Mais les circuits de calcul actuels manipulent des nombres de 32 ou 64 bits, ce qui demanderait des tables de vérité démesurément grandes : plus de 4 milliards de lignes en 32 bits ! Il faut donc ruser, pour créer des circuits économes en transistors et rapides. Dans ce chapitre, nous allons voir les circuits capables de faire une addition ou une soustraction, ainsi que quelques circuits spécialisés, comme les additionneurs multi-opérande. Précisons cependant que les constructeurs de processeurs, ainsi que des chercheurs en arithmétique des ordinateurs, travaillent d'arrache-pied pour trouver des moyens de rendre ces circuits de calcul plus rapides et plus économes en énergie. Autant vous dire que les circuits que vous allez voir sont vraiment des circuit qui font pâle figure comparé à ce que l'on peut trouver dans un vrai processeur commercial !

Les circuits pour additionner 2 ou 3 bits

Pour rappel, l'addition se fait en binaire de la même manière qu'en décimal. On additionne les chiffres/bits colonne par colonne, une éventuelle retenue est propagée à la colonne d'à côté. La soustraction fonctionne sur le même principe, sur le même modèle qu'en décimal.

Exemple d'addition en binaire.

En clair, additionner deux nombres demande de savoir additionner 2 bits et une retenue sur chaque colonne, et de propager les retenues d'une colonne à l'autre. La propagation des retenues est quelque chose de simple en apparence, mais qui est sujet à des optimisations extraordinairement nombreuses. Aussi, pour simplifier l'exposition, nous allons voir comment gérer une colonne avant de voir comment sont propagées les retenues. Le fait que les additionneurs soient organisés de manière à séparer les deux nous aidera grandement. En effet, tout additionneur est composé d'additionneurs plus simples, capables d'additionner deux ou trois bits suivant la situation. Ceux-ci gèrent ce qui se passe sur une colonne.

Le demi-additionneur

Un additionneur deux bits implémente la table d'addition, qui est très simple en binaire. Jugez plutôt :

• 0 + 0 = 0, retenue = 0 ;
• 0 + 1 = 1, retenue = 0 ;
• 1 + 0 = 1, retenue = 0 ;
• 1 + 1 = 0, retenue = 1 ;

Un circuit capable d'additionner deux bits est donc simple à construire avec les techniques vues dans les premiers chapitres. On voit immédiatement que la colonne des retenues donne une porte ET, alors que celle du bit de somme est calculé par un XOR. Le circuit obtenu est appelé un demi-additionneur. Le voici :

Demi-addtionneur.

Circuit d'un demi-addtionneur.

L'additionneur complet

Additionneur complet.

Si on effectue une addition en colonne, on doit additionner les deux bits sur la colonne, mais aussi additionner une éventuelle retenue. Il faut donc créer un circuit qui additionne trois bits : deux bits de données, plus une retenue. Ce circuit qui additionne trois bits est appelé un additionneur complet. Il est possible d'en concevoir de plusieurs manières différentes, qui donnent des circuits équivalents, mais avec une organisation en portes logiques différentes. La plus simple consiste à utiliser un tableau de Karnaugh, mais elle donne un résultat sous-optimal.

L'additionneur complet conçu avec deux demi-additionneurs

La solution la plus simple consiste à enchaîner deux demi-additionneurs : un qui additionne les deux bits de données, et un second qui additionne la retenue au résultat. La retenue finale se calcule en combinant les sorties de retenue des deux demi-additionneurs, avec une porte OU. Pour vous en convaincre, établissez la table de vérité de ce circuit, vous verrez que ça marche.

Circuit de calcul de la retenue sortante.

Avec ce circuit, la somme est calculée avec deux portes XOR l'une à la suite de l'autre. La retenue sortante, quant à elle, est calculée avec un circuit assez complexe, représenté ci-contre, qui contient une porte XOR, une porte OU et deux portes ET. Les autres additionneurs que nous allons voir sont des dérivés de ce circuit, auquel on a appliqué quelques simplifications. Les simplifications portent surtout sur le circuit de calcul de la retenue. En effet, le calcul de la somme n'est pas simplifié, car on ne peut pas vraiment simplifier deux portes XOR qui se suivent simplement. Par contre, le calcul de la retenue sortante est un cas particulier d'un calcul qui revient souvent en électronique, comme nous allons le voir dans la section suivante.

L'additionneur complet basé sur une porte à majorité

Il est possible de calculer la retenue sortante assez simplement, mais à condition de remarquer quelque chose. La retenue sortante vaut 1 seulement si une condition particulière est respectée : au moins 2 des 3 bits d'entrée doivent être à 1. Dit autrement, plus de la moitié des bits d'entrées doivent être à 1. Or,n il existe une porte logique qui fonctionne comme cela : elle met sa sortie à 1 si plus de moitié des entrées vaut 1, et sort un 0 sinon. Cette porte logique complexe s'appelle une porte à majorité. On obtient donc un additionneur en combinant deux portes XOR pour calculer la somme, et une porte à majorité pour la retenue sortante.

L'additionneur complet basé sur la propagation et la génération de retenue

Une autre solution calcule la retenue finale d'une autre manière, en combinant le résultat de deux circuits séparés. Le premier vérifie si l'addition génère une retenue, l'autre si la retenue en entrée est propagée en sortie.

• Une retenue est dite générée si l'addition donne une retenue, quelle que soit la retenue envoyée en entrée (sous-entendu, même si celle-ci vaut 0). Cela arrive quand les bits additionnés valent tous deux 1 : la retenue sera alors de 1, seul le bit du résultat changera. On peut donc calculer si une retenue est générée en faisant un ET entre les deux bits d'entrée.
• Une retenue est propagée si la retenue en sortie est égale à la retenue en entrée. En clair, la retenue n'existe que si on envoie une retenue en entrée. Dans ce cas, la retenue finale vaut 1 quand un seul des deux bits d'entrée vaut 1, et vaut 0 sinon. En clair, on peut déterminer si une retenue est propagée en faisant un XOR entre les deux bits d'entrée.

Ces deux circuits fournissent deux signaux : un signal G qui indique si une retenue est générée, et un signal P qui indique si une retenue est propagée. En combinant les deux, on peut calculer la retenue finale. Elle vaut 1 dans l'un des deux cas suivant : soit quand la retenue est générée, soit quand la retenue d'entrée vaut 1 et qu'elle est propagée. Dans les autres cas, elle vaut zéro. La traduction en équation logique dit qu'il suffit de faire un ET entre la retenue d'entrée et le bit P, puis de faire un OU avec le bit G. Le circuit obtenu est strictement identique au circuit précédent.

Additionneur complet avec propagation et génération de retenue.

L'additionneur en Manchester carry chain est une modification de l'additionneur précédent, où les portes logiques en orange dans le schéma précédent sont remplacées par un circuit plus simple, composé de quelques transistors et d'une porte NON. Néanmoins, ce circuit fonctionne en pass transistor logic, avec tous les défauts que cela implique. Le principal est que, vu que la retenue d'entrée est envoyée sur la sortie à travers des interrupteurs/transistors, la tension sur la retenue de sortie est plus faible que la tension de la retenue d'entrée. Ce qui pose des problèmes quand on doit enchainer plusieurs additionneurs de ce type, mais laissons cela pour plus tard. Il existe une version de cet additionneur en logique dynamique, où les transistors sont utilisés comme des condensateurs et sont préchargés avant de faire leurs calculs, mais nous n'en parlerons pas ici.

Manchester carry chain

Les premiers circuits d'addition que nous allons voir utilisent des additionneurs complets. Mais les suivants utilisent des additionneurs qui ne calculent pas la retenue finale. Par contre, ils calculent les signaux P et G qui disent si l'addition de deux bits génère une retenue, ou si elle propage une retenue provenant d'une colonne précédente. Ils fournissent ces deux signaux sur deux sorties P et G pour indiquer s'il y a propagation et génération de retenue. Un tel additionneur est appelé un additionneur P/G (P/G pour propagation/génération). Ils seront très utiles pour créer des circuits additionneurs comme on le verra plus bas.

L'additionneur complet basé sur une modification de la retenue sortante

Dans les circuits précédents, la retenue sortante et le bit du résultat sont calculés séparément, même si quelques portes logiques sont partagées entre les deux. Une autre méthode, utilisée dans l'unité de calcul de l'Intel 4004 et de l'Intel 8008, fonctionnait autrement. Avec elle, la retenue sortante et calculée en premier, puis on détermine le bit du résultat à partir de la retenue sortante. En effet, le bit du résultat est l'inverse de la retenue sortante, sauf dans deux cas : les trois bits d'entrée sont à 0, où ils sont tous à 1. Dans les deux cas d'exception, le bit du résultat vaut 0, quelque soit la retenue sortante. L'implémentation de cette idée en circuit est assez simple.

Au circuit de calcul de la retenue sortante, il faut ajouter deux circuits, un pour vérifie si tous les bits additionner valent 0, l'autre s'ils valent tous 1. Leur sortie vaut 1 si c'est le cas. Le premier est une simple porte ET, l'autre une porte NOR. Ensuite, on combine le résultat des trois circuits précédents pour obtenir le résultat final. Si un seul des trois circuits a sa sortie à 1, alors la sortie finale doit être à 0. Elle est à 1 sinon. C'est donc une porte NOR qu'il faut utiliser. Le circuit final est donc celui-ci.

Full adder basé sur une modification de la retenue

Notons qu'on peut encore optimiser le circuit en fusionnant les deux portes NOR entre elles, mais c'est là un détail.

A ce stade, vous êtes certainement étonné qu'un tel circuit ait pu être utilisé. Il utilise beaucoup plus de portes logiques que le circuit précédent, a une profondeur logique supérieure : il n'a rien d'avantageux. Sauf qu'il était utilisé sur d'anciens processeurs, qui utilisaient des transistors de type TLL, et non des transistors CMOS comme les microprocesseurs actuels. Et avec ces transistors, il est possible d'implémenter des portes logiques complexes, comme les portes ET/OU/NON que nous avons évoqué rapidement dans le chapitre sur les transistors ! Un additionneur complet construit ainsi ne prenait que deux à trois transistors. Par exemple, l'unité de calcul de l'Intel 8008 utilisait trois transistors : un pour une porte NAND, et deux qui implémentaient chacun une porte ET-OU-NON à plusieurs entrées. Après, l'ALU de ce processeur utilisait un circuit légèrement différent, pour deux raisons. La première est que le circuit prend en entrée l'inverse des bits à additionner, pour des raisons obscures. L'autre est qu'il était capable d'additionner trois bits, mais aussi de faire des opérations logiques dessus, comme des XOR, des ET ou des OU, sans ajouter un seul transistor. le Z-80 utilisait aussi un additionneur de ce type.

Pour ceux qui veulent en savoir plus sur les circuits de calcul de l'Intel 8008, voici un lien qui pourrait vous intéresser :

• Reverse-engineering the surprisingly advanced ALU of the 8008 microprocessor

Les autres implémentations

Les implémentations précédentes utilisent des portes logiques, ce qui est simple et facile à comprendre, mais pas forcément le top du top en termes de performances. Mais les additionneurs des processeurs modernes sont nettement plus optimisés que ça. Et pour cela, ils sont optimisés directement au niveau des transistors. Cela permet de les rendre plus rapides, notamment au niveau du calcul de la retenue. Là où l'addition des deux bits d'opérande se doit d'être rapide, le calcul de la retenue doit absolument être le plus rapide possible, c'est crucial pour les circuits qui vont suivre. Outre les optimisations en termes de rapidité, une implémentation à base de transistors peut économiser des transistors. Tout dépend de l'objectif visé, certains circuit optimisant à fond pour la vitesse, d'autres pour le nombre de transistors, d'autres font un compromis entre les deux. Les circuits de ce genre sont très nombreux, trop pour qu'on puisse les citer.

Mais il existe aussi des cas plus rares, où l'implémentation des additionneurs fait au plus simple. C'est le cas sur le premier processeur ARM, l'ARM1, qui implémente ses additionneurs avec des multiplexeurs et des portes NON. Pour rappel, on peut implémenter n'importe quel circuit avec des multiplexeurs. Et sur l'ARM1, les concepteurs ont décidé d'implémenter certains circuits avec des multiplexeurs, additionneurs inclus. La raison n'est pas une question de performance, d'économie de transistors, ou quoique ce soit du genre. C'est juste que c'était plus pratique à fabriquer, sachant que les concepteurs de la puce utilisaient une forme particulière d'implémentation, appelée des pass transistors logic. Il est très simple de fabriquer des portes XOR et des multiplexeurs avec cette méthode, ce qui a aussi l'avantage d'utiliser peu de transistors, ce qui fait qu'il était intéressant d'implémenter les additionneurs avec. Pour en savoir plus à ce sujet, voici un lien intéressant :

Counting bits in hardware: reverse engineering the silicon in the ARM1 processor

L'addition non signée

Voyons maintenant un circuit capable d'additionner deux nombres entiers: l'additionneur. Dans la version qu'on va voir, ce circuit manipulera des nombres strictement positifs (et donc les nombres codés en complètement à deux, ou en complément à un).

L'additionneur série

Avec un additionneur complet, il est possible d'additionner deux nombres bit par bit. Dit autrement, on peut effectuer l'addition colonne par colonne. Cela demande de coupler l'additionneur avec plusieurs registres à décalages. Les opérandes vont être placées chacune dans un registre à décalage, afin de passer à chaque cycle d'un bit au suivant, d'une colonne à la suivante. Même chose pour le résultat. La retenue de l'addition est stockée dans une bascule de 1 bit, en attente du prochain cycle d'horloge. Un tel additionneur est appelé un additionneur série.

Additionneur série.

Bien que très simple et économe en transistors, cet additionneur est cependant peu performant. Le temps de calcul est proportionnel à la taille des opérandes. Par exemple, additionner deux nombres de 32 bits prendra deux fois plus de temps que l'addition de deux nombres de 16 bits. L'addition étant une opération fréquente, il vaut mieux utiliser d'autres méthodes d'addition, plus rapides. C'est pour cela que la totalité des autres additionneurs préfère utiliser plus de circuits, quitte à gagner quelque peu en rapidité.

L'additionneur à propagation de retenue

L'additionneur à propagation de retenue pose l'addition comme en décimal, en additionnant les bits colonne par colonne avec une éventuelle retenue. Évidemment, on commence par les bits les plus à droite, comme en décimal. Il suffit ainsi de câbler des additionneurs complets les uns à la suite des autres.

Additionneur à propagation de retenue.

Notons la présence de la retenue sortante, qui est utilisée pour détecter les débordements d'entier, ainsi que pour d'autres opérations. Le bit de retenue final est souvent stocké dans un registre spécial du processeur (généralement appelé carry flag). Notez aussi, sur le schéma précédent, la présence de l’entrée de retenue ${\text{R}}_{\text{Entrée}}$ sur l'additionneur. Presque tous les additionneurs ont une entrée de retenue comme celle-ci, afin de faciliter l'implémentation de certaines opérations comme l'inversion de signe, la soustraction, l'incrémentation, etc. Certains processeurs sont capables de faire une opération appelée ADC, ADDC ou autre nom signifiant Addition with Carry, qui permet de faire le calcul A + B + Retenue (la retenue en question est la retenue sortante de l'addition précédente, stockée dans le registre carry flag). Son utilité principale est de permettre des additions d'entiers plus grands que ceux supportés par le processeur. Par exemple, cela permet de faire des additions d'entiers 32 bits sur un processeur 16 bits.

Ce circuit utilise plus de portes logiques que l'additionneur série, mais est un peu plus rapide. Il utilise très peu de portes logiques et est assez économe en transistors, ce qui fait qu'il était utilisé sur les tous premiers processeurs 8 et 16 bits. Un défaut de ce circuit est que le calcul des retenues s'effectue en série, l'une après l'autre. En effet, chaque additionneur doit attendre que la retenue de l'addition précédente soit disponible pour donner son résultat. Les retenues doivent se propager à travers le circuit, du premier additionneur jusqu'au dernier. On garde donc un défaut de l'additionneur série, à savoir : le fait que le temps de calcul est proportionnel à la taille des opérandes. Pour éviter cela, les autres additionneurs utilisent diverses solutions : soit calculer les retenues en parallèle, soit éliminer certaines opérations inutiles quand c'est possible.

Une solution est d'utiliser des additionneurs complets de type Manchester carry chain. Avec de tels additionneurs, il n'y a pas besoin de calculer une retenue en fonction de la précédente. Chaque additionneur de type Manchester carry chain calcule les signaux propagation/génération de retenue indépendamment, et les utilise pour ouvrir ou fermer ses transistors/interrupteurs interne. Pas besoin d'attendre de connaitre la retenue précédente pour fermer ou ouvrir les interrupteur. Néanmoins, l'additionneur de type Manchester carry chain fonctionne en pass transistor logic, avec tous les défauts que cela implique quand on en enchaine plusieurs. L'entrée de retenue est directement connectée sur la sortie de retenue, sans passage par une porte logique. Donc, la tension d'entrée est envoyée directement sur la sortie, sans amplification ou régénération. Si on enchaine plusieurs additionneurs complets de ce type, la tension diminue à chaque passage dans un additionneur complet, ce qui est un défaut de ce type de circuit. On peut difficilement enchainer plus de 4 à 8 additionneurs de type Manchester carry chain à la suite.

L'additionneur à saut de retenue

L'additionneur à saut de retenue (carry-skip adder), améliore les performances de l'additionneur à propagation de retenue. Celui-ci a cependant un temps de calcul variable, qui dépend des nombres à additionner. Certains calculs prendront quelques cycles d'horloges, tandis que d'autres prendront autant de temps qu'avec un additionneur à propagation de retenue.

Cet additionneur se construit à partir de plusieurs additionneurs de quelques bits (4 à 5 bits, parfois plus, parfois moins), additionneurs qui seront nommés blocs dans ce qui suit. Chaque bloc peut soit générer une retenue, soit propager celle du bloc précédent, soit ne pas fournir de retenue (celle-ci vaut 0). Si le bloc génère une retenue ou qu'il n'en fournit pas, le fonctionnement du circuit est identique à un additionneur à propagation de retenue. Par contre, si le bloc ne fait que propager la retenue du bloc précédent, on peut directement envoyer cette retenue au bloc suivant. Pour cela, on utilise un multiplexeur pour décider s'il faut envoyer la retenue calculée par le bloc ou celle du bloc précédent. Ce multiplexeur est commandé par un signal qui indique si le bloc propage la retenue, signal qui est généré assez simplement : il vaut 1 si tous les additionneurs P/G du bloc propagent la retenue précédente.

Additionneur à saut de retenue : principe.

En enchaînant plusieurs blocs les uns à la suite des autres, on obtient l'additionneur à saut de retenue.

L'additionneur à sélection de retenue

L'additionneur à sélection de retenue adapte le principe précédent, mais d'une autre manière. Cet additionneur va découper nos deux nombres à additionner en blocs, qui se feront additionner en deux versions : une avec la retenue du bloc précédent valant zéro, et une autre version avec la retenue du bloc précédent valant 1. Il suffira alors de choisir le bon résultat avec un multiplexeur, une fois cette retenue connue. On gagne ainsi du temps en calculant à l'avance les valeurs de certains bits du résultat, sans connaître la valeur de la retenue. Petit détail : sur certains additionneurs à sélection de retenue, les blocs de base n'ont pas la même taille. Cela permet de tenir compte des temps de propagation des retenues entre les blocs.

Additionneur à sélection de retenue avec seulement deux blocs.

Dans les exemples du dessus, chaque sous-additionneur étaient des additionneurs à propagation de retenue. Mais ce n'est pas une obligation, et tout autre type d’additionneur peut être utilisé. Par exemple, on peut faire en sorte que les sous-additionneurs soient eux-mêmes des additionneurs à sélection de retenue, et poursuivre ainsi de suite, récursivement. On obtient alors un additionneur à somme conditionnelle, plus rapide que l'additionneur à sélection de retenue, mais qui utilise beaucoup plus de portes logiques.

Les additionneurs à anticipation de retenue

Au lieu de calculer les retenues une par une, certains additionneurs calculent toutes les retenues en parallèle à partir de la valeur de tout ou partie des bits précédents. Une fois les retenues pré-calculées, il suffit de les additionner avec les deux bits adéquats, pour obtenir le résultat. Ces additionneurs sont appelés des additionneurs à anticipation de retenue.

Additionneur à anticipation de retenue.

Ces additionneurs sont composés de deux parties :

• un circuit qui pré-calcule la valeur de la retenue d'un étage ;
• et d'un circuit qui additionne les deux bits et la retenue pré-calculée : il s'agit d'une couche d'additionneurs complets simplifiés, qui ne fournissent pas de retenue.

Additionneur à anticipation de retenue.

Le circuit qui détermine la valeur de la retenue est lui-même composé de deux grandes parties, qui ont chacune leur utilité. La première partie réutilise des additionneurs qui donnent les signaux de propagation et génération de retenue. L'additionneur commence donc à prendre forme, et est composé de trois parties :

• un circuit qui crée les signaux P et G ;
• un circuit qui déduit la retenue à partir des signaux P et G adéquats ;
• et une couche d'additionneurs qui additionnent chacun deux bits et une retenue.

Circuit complet d'un additionneur à anticipation de retenue.

Il ne nous reste plus qu'à voir comment fabriquer le circuit qui reste. Pour cela, il faut remarquer que la retenue est égale :

• à 1 si l'addition des deux bits génère une retenue ;
• à 1 si l'addition des deux bits propage une retenue ;
• à zéro sinon.

Ainsi, l'addition des bits de rangs i va produire une retenue Ci, qui est égale à Gi+(Pi·Ci−1). Si on utilisait cette formule sans trop réfléchir, on retomberait sur un additionneur à propagation de retenue inutilement compliqué. L'astuce des additionneurs à anticipation de retenue consiste à remplacer le terme Ci−1 par sa valeur calculée avant. Par exemple, je prends un additionneur 4 bits. Je dispose de deux nombres A et B, contenant chacun 4 bits : A3, A2, A1, et A0 pour le nombre A, et B3, B2, B1, et B0 pour le nombre B. Si j'effectue les remplacements, j'obtiens les formules suivantes :

• C1 = G0 + ( P0 · C0 ) ;
• C2 = G1 + ( P1 · G0 ) + ( P1 · P0 · C0 ) ;
• C3 = G2 + ( P2 · G1 ) + ( P2 · P1 · G0 ) + ( P2 · P1 · P0 · C0 ) ;
• C4 = G3 + ( P3 · G2 ) + ( P3 · P2 · G1 ) + ( P3 · P2 · P1 · G0 ) + ( P3 · P2 · P1 · P0 · C0 ).

Ces formules nous permettent de déduire la valeur d'une retenue directement : il reste alors à créer un circuit qui implémente ces formules, et le tour est joué. On peut même simplifier le tout en fusionnant les deux couches d'additionneurs.

Additionneur à anticipation de retenue de 4 bits.

Ces additionneurs sont plus rapides que les additionneurs à propagation de retenue. Ceci dit, utiliser un additionneur à anticipation de retenue sur des nombres très grands (16/32bits) utiliserait trop de portes logiques. Pour éviter tout problème, nos additionneurs à anticipation de retenue sont souvent découpés en blocs, avec soit une anticipation de retenue entre les blocs et une propagation de retenue dans les blocs, soit l'inverse.

Additionneur à anticipation de retenue de 64 bits.

L'additionneur à calcul parallèle de préfixes

Les additionneurs à calcul parallèle de préfixes sont des additionneurs à anticipation de retenue quelque peu améliorés, pour gagner en performances. Ceux-ci sont toujours découpés en trois couches :

• un circuit qui crée les signaux P et G ;
• un circuit qui déduit la retenue à partir des signaux P et G adéquats ;
• et une couche d'additionneurs qui additionnent chacun deux bits et une retenue.

Simplement, ils vont concevoir le circuit de calcul des retenues différemment. Avec eux, le calcul Gi + (Pi · Ci−1) va être modifié pour prendre en entrée non pas la retenue Ci−1, mais les signaux Gi−1 et Pi−1. Dans ce qui va suivre, nous allons noter ce petit calcul o. On peut ainsi écrire que :

Ci = ((((Gi , Pi) o (Gi−1 , Pi−1) ) o (Gi−2 , Pi−2 )) o (Gi−3 , Pi−3)) …

Si on utilisait cette formule sans trop réfléchir, on retomberait sur un additionneur à propagation de retenue inutilement compliqué. Le truc, c'est que o est associatif, et que cela peut permettre de créer pas mal d'optimisations : il suffit de réorganiser les parenthèses. Cette réorganisation peut se faire de diverses manières qui donnent des additionneurs différents. Les diverses réorganisations donnent l'additionneur de Ladner-Fisher, l'additionneur de Brent-Kung, l'additionneur de Kogge-Stone, ou tout design hybride. L'additionneur de Brent-Kung est le plus lent de tous les additionneurs cités, mais c'est celui qui utilise le moins de portes logiques. L'additionneur de Ladner-Fisher est théoriquement le plus rapide de tous, mais aussi celui qui utilise le plus de portes logiques. Les autres sont des intermédiaires.

Additionneur de Kogge-Stone.

Additionneur de Ladner-Fisher.

La soustraction et l'addition signée

Après avoir vu l'addition, il est logique de passer à la soustraction, les deux opérations étant très proches. Si on sait câbler une addition entre entiers positifs, câbler une soustraction n'est pas très compliqué. De plus, la soustraction permet de faire des additions de nombres signés.

Le soustracteur pour opérandes entiers

Pour soustraire deux nombres entiers, on peut adapter l'algorithme e soustraction utilisé en décimal, celui que vous avez appris à l'école. Celui-ci ressemble fortement à l'algorithme d'addition : on soustrait les bits de même poids, et on propage éventuellement une retenue sur la colonne suivante. La différence est que la retenue est soustraite, et non ajoutée. La table de soustraction nous dit quel est le résultat de la soustraction de deux bits. La voici :

• 0 - 0 = 0 ;
• 0 - 1 = 1 et une retenue ;
• 1 - 0 = 1 ;
• 1 - 1 = 0.

Cette table de soustraction peut servir de table de vérité pour construire un circuit qui soustrait deux bits. Celui-ci est appelé un demi-soustracteur.

Demi-soustracteur.

Celui-ci peut être complété afin de prendre en compte une éventuelle retenue, ce qui donne un soustracteur complet. On remarque que le soustracteur complet et composé de deux demi-soustracteurs placés en série. Le calcul de la retenue se fait en combinant les deux retenues des demi-soustracteurs avec une porte OU.

Soustracteur complet.

Celui-ci permet de créer des soustracteurs sur le même patron que pour les additionneurs. On peut ainsi créer un soustracteur série, un soustracteur à propagation de retenue, et ainsi de suite.

Le soustracteur pour opérandes codées en complément à deux

Étudions maintenant le cas de la soustraction en complément à deux, dans l'objectif de créer un circuit soustracteur. Vous savez sûrement que a−b et a+(−b) sont deux expressions équivalentes. Et en complément à deux, − b = not(b) + 1. Dit autrement, a − b = a + not(b) + 1. On pourrait se dire qu'il faut deux additionneurs pour faire le calcul, mais la majorité des additionneurs possède une entrée de retenue pour incrémenter le résultat de l'addition. Un soustracteur en complément à deux est donc simplement composé d'un additionneur et d'un inverseur.

Soustracteur en complément à deux.

Il est possible de créer un circuit capable d'effectuer soit une addition, soit une soustraction : il suffit de remplacer l'inverseur par un inverseur commandable, qui peut être désactivé. On a vu comment créer un tel inverseur commandable dans le chapitre sur les circuits combinatoires. On peut remarquer que l'entrée de retenue et l'entrée de commande de l'inverseur sont activées en même temps : on peut fusionner les deux signaux en un seul.

Additionneur-soustracteur en complément à deux.

Additionneur-soustracteur en complément à deux, version alternative.

Le soustracteur pour opérandes codées en signe-magnitude

Passons maintenant aux nombres codés en signe-valeur absolue.

Étudions tout d'abord un circuit d'addition de deux opérandes en signe-magnitude, les deux opérandes étant notée A et B. Suivant les signes des deux opérandes, on a quatre cas possibles : A + B, A − B (B négatif), −A + B (A négatif) et −A − B (A et B négatifs). On remarque que B − A est égal à − (A − B), et − A − B vaut − (A + B). Ainsi, le circuit n'a besoin que de calculer A + B et A − B : il peut les inverser pour obtenir − A − B ou B − A. A + B et A − B peuvent se calculer avec un additionneur-soustracteur. Il suffit de lui ajouter un inverseur commandable pour obtenir le circuit d'addition finale. On peut transformer ce circuit en additionneur-soustracteur en signe-valeur absolue, mais le circuit combinatoire devient plus complexe.

Additionneur en signe-valeur absolue.

Toute la difficulté tient dans le calcul du bit de signe du résultat, quand interviennent des soustractions. Autant l'addition de deux nombres de même signe ne pose aucun problème, autant l'addition de nombres de signes différents ou les soustractions posent problème. Suivant que $A<B$ ou que $A>B$, le signe du résultat ne sera pas le même. Intuitivement, on se dit qu'il faut ajouter des comparateurs pour déterminer le signe du résultat. Diverses optimisations permettent cependant de limiter la casse et d'utiliser moins de circuits que prévu. Mais rien d'extraordinaire.

Le soustracteur pour opérandes codées en représentation par excès

Passons maintenant aux nombres codés en représentation par excès. On pourrait croire que ces nombres s'additionnent comme des nombres non-signés, mais ce serait oublier la présence du biais, qui pose problème. Dans les cas de nombres signés gérés avec un biais, voyons ce que donne l'addition de deux nombres : $(n_{1}+biais)+(n_{2}+biais)=n_{1}+n_{2}+2\times biais$. Or, le résultat correct serait $n_{1}+n_{2}+biais$. En effectuant l'addition telle quelle, le biais est compté deux fois. On doit donc le soustraire après l'addition pour obtenir le résultat correct. Même chose pour la soustraction $(n_{1}+biais)-(n_{2}+biais)=n_{1}-n_{2}$. Or, le résultat correct serait $(n_{1}-n_{2})+biais$. Il faut rajouter le biais pour obtenir l'exposant correct. On a donc besoin de deux additionneurs/soustracteurs pour implémenter la multiplication et la division. Ainsi, l'additionneur/soustracteur en représentation par excès est composé de deux additionneurs/soustracteurs : un pour additionner/soustraire les nombres, et un autre pour gérer le biais.

Les débordements d'entier lors d'une addition/soustraction

Les instructions arithmétiques et quelques autres manipulent des entiers de taille fixe, qui ne peuvent prendre leurs valeurs que dans un intervalle. Pour les nombres positifs, un ordinateur qui code ses entiers sur n bits pourra coder tous les entiers allant de 0 à $2^{n}-1$. Tout nombre en dehors de cet intervalle ne peut pas être représenté. Dans le cas où l'ordinateur gère les nombres négatifs, l'intervalle est différent. Dans le cas général, l'ordinateur peut coder les valeurs comprises de $N_{\text{min}}$ à $N_{\text{max}}$. Si le résultat d'un calcul sort de cet intervalle, il ne peut pas être représenté par l'ordinateur et il se produit ce qu'on appelle un débordement d'entier.

La valeur haute de débordement désigne la première valeur qui est trop grande pour être représentée par l'ordinateur. Par exemple, pour un ordinateur qui peut coder tous les nombres entre 0 et 7, la valeur haute de débordement est égale à 8. On peut aussi définir la valeur basse de débordement, qui est la première valeur trop petite pour être codée par l'ordinateur. Par exemple, pour un ordinateur qui peut coder tous les nombres entre 8 et 250, la valeur basse de débordement est égale à 7. Pour les nombres entiers, la valeur haute de débordement vaut $N_{\text{max}}+1$ , alors que la valeur basse vaut $N_{\text{min}}-1$ (avec $N_{\text{max}}$ et $N_{\text{min}}$ respectivement la plus grande et la plus petite valeur codable par l'ordinateur).

La correction des débordements d'entier : l'arithmétique saturée

Quand un débordement d'entier survient, tous les circuits de calcul ne procèdent pas de la même manière. Dans les grandes lignes, il y a deux réactions possibles : soit on corrige automatiquement le résultat du débordement, soit on ne fait rien et on se contente de détecter le débordement.

Si le débordement n'est pas corrigé automatiquement par le circuit, celui-ci ne conserve que les bits de poids faibles du résultat. Les bits en trop sont simplement ignorés. On dit qu'on utilise l'arithmétique modulaire. Le problème avec ce genre d'arithmétique, c'est qu'une opération entre deux grands nombres peut donner un résultat très petit. Par exemple, si je dispose de registres 4 bits et que je souhaite faire l'addition 1111 + 0010 (ce qui donne 15 + 2), le résultat est censé être 10001 (17), ce qui est un résultat plus grand que la taille d'un registre. En conservant les 4 bits de poids faible, j’obtiens 0001 (1). En clair, un résultat très grand est transformé en un résultat très petit. Cela peut poser problèmes si on travaille uniquement avec des nombres positifs, mais c'est aussi utilisé pour coder des nombres en complément à deux. En clair, faire ainsi est parfois une bonne idée, parfois non.

D'autres circuits utilisent ce qu'on appelle l'arithmétique saturée : si un résultat est trop grand au point de générer un débordement, on arrondi le résultat au plus grand entier supporté par le circuit. Les circuits capables de calculer en arithmétique saturée sont un peu tout petit peu plus complexes que leurs collègues qui ne travaillent pas en arithmétique saturée, vu qu'il faut rajouter des circuits pour corriger le résultat en cas de débordement. Il suffit généralement de rajouter un circuit de saturation, qui prend en entrée le résultat en fournit en sortie une version saturée en cas de débordement. Ce circuit de saturation met la valeur maximale en sortie si un débordement survient, mais se contente de recopier le résultat du calcul sur sa sortie s'il n'y a pas de débordement. Typiquement, il est composé d'une ou de deux couches de multiplexeurs, qui sélectionnent quelle valeur mettre sur la sortie : soit le résultat du calcul, soit le plus grand nombre entier géré par le processeur, soit le plus petit (pour les nombres négatifs/soustractions).

L'arithmétique saturée est surtout utilisée pour les additions et soustractions, mais c'est plus rare pour les multiplications/divisions. Une des raisons est que le résultat d'une addition/soustraction prend un bit de plus que le résultat, là où les multiplications doublent le nombre de bits. Cette large différence se traduit par une grande différence pour les résultats qui débordent. Quand une addition déborde, le résultat réel est proche de la valeur maximale codable. mais quand une multiplication déborde, le résultat peut parfois valoir 200 à 60000 fois plus que la valeur maximale codable. Les calculs avec une valeur saturée/corrigée sont donc crédibles pour une suite d'additions, mais pas pour une suite de multiplications. Raison pour laquelle l'arithmétique saturée est utilisée pour les additions/soustractions, là où on préfère corriger les multiplications/divisions par des méthodes logicielles.

La détection des débordements d'entier

Et quand un débordement d'entier a eu lieu, il vaut mieux que le circuit prévienne ! Pour cela, les circuits de calculs ont une sortie nommée Overflow, dont la valeur indique si le calcul a donné un débordement d'entier ou non. Reste que détecter un débordement ne se fait pas de la même manière selon que l'on parle d'un additionneur non-signé, d'un additionneur signé, d'un multiplieur non-signé, etc.

Les opérations sur des nombres non-signés

Pour le cas des nombres positifs, la détection des débordements dépend assez peu de l'opération. L'idée générale est que le circuit de calcul calcule tous les bits du résultat, quitte à dépasser ce qui est supporté par l'ordinateur. Par exemple, un additionneur 32 bits fournit un résultat sur 33 bits, un multiplieur 32 bits fournit des résultats sur 64 bits, etc. Le circuit de calcul a donc des bits qui sont en trop et doivent être oubliés. Un débordement a lieu quand ces bits oubliés sont pertinents, à savoir quand au moins l'un d'eux est à 1. Par exemple, une addition sur 32 bits déborde quand le 33ème bit est à 1, une multiplication sur 32 bits déborde quand un des 32 bits de poids fort est à 1, etc.

Pour les additionneurs non-signés, la sortie Overflow n'est autre que la retenue finale, celle fournie par le dernier additionneur complet. De plus, le seul type de débordement possible est un débordement par le haut, où le résultat dépasse la valeur maximale. Le circuit de saturation est alors très simple. Il consiste au pire en une seule couche de multiplexeurs. Une solution encore plus simple consiste à utiliser le circuit de mise à la valeur maximale vu dans le chapitre sur les opérations bits à bits.

Gestion des débordements d'entiers lors d'une addition non-signée.

Les opérations signées

Pour les additionneurs non-signés, la gestion des débordements d'entiers dépend fortement de la représentation signée. Dans les grandes lignes, rien ne change avec les représentations en signe-magnitude et par excès, dont les débordements sont gérés de la même manière que pour les nombres positifs. Par contre, il n'en est pas de même pour le complément à deux. Si vous vous rappelez le chapitre 1, j'ai clairement dit que les calculs sur des nombres en complètement à deux utilisent les règles de l'arithmétique modulaire : les calculs sont faits avec un nombre de bits fixé une fois pour toute. Si un résultat dépasse ce nombre de bits fixé, on ne conserve pas les bits en trop. C'est une condition nécessaire pour pouvoir faire nos calculs. À priori, on peut donc penser que dans ces conditions, les débordements d'entiers sont une chose parfaitement normale, qui nous permet d'avoir des résultats corrects. Néanmoins, certains débordements d'entiers peuvent survenir malgré tout et produire des bugs assez ennuyeux.

Si l'on tient en compte les règles du complément à deux, on sait que le bit de poids fort (le plus à gauche) permet de déterminer si le nombre est positif ou négatif : il indique le signe du nombre. Tout se passe comme si les entiers en complément à deux étaient codés sur un bit de moins, et avaient leur longueur amputé du bit de poids fort. Si le résultat d'un calcul a besoin d'un bit de plus que cette longueur, amputée du bit de poids fort, le bit de poids fort sera écrasé; donnant un débordements d'entiers. Il existe une règle simple qui permet de détecter ces débordements d'entiers. L'addition (ou la multiplication) de deux nombres positifs ne peut pas être un nombre négatif : on additionne deux nombres dont le bit de signe est à 0 et que le bit de signe du résultat est à 1, on est certain d'être en face d'un débordements d'entiers. Même chose pour deux nombres négatif : le résultat de l'addition ne peut pas être positif. On peut résumer cela en une phrase : si deux nombres de même signe sont ajoutés, un débordement a lieu quand le bit du signe du résultat a le signe opposé. On peut préciser que cette règle s'applique aussi pour les nombres codés en complément à 1, pour les mêmes raisons que pour le codage en complément à deux. Cette règle est aussi valable pour d'autres opérations, comme les multiplications.

Modifier les circuits d'au-dessus pour qu'ils détectent les débordements en complément à deux est simple comme bonjour : il suffit créer un petit circuit combinatoire qui prenne en entrée les bits de signe des opérandes et du résultat, et qui fasse le calcul de l'indicateur de débordements. Si l'on rédige sa table de vérité, on doit se retrouver avec la table suivante :

Entrées	Sortie
000	0
001	1
010	0
011	0
100	0
101	0
110	1
111	0

L'équation de ce circuit est la suivante, avec $S_{a}$ et $S_{b}$ les signes des deux opérandes, et $C_{i}$ la retenue de la colonne précédente :

$(S_{a}.S_{b}.{\overline {C_{i}}})+({\overline {S_{a}}}.{\overline {S_{b}}}.C_{i})$

En simplifiant, on obtient alors :

$(S_{a}.S_{b})\oplus C_{i}$

Or, il se trouve que $S_{a}.S_{b}$ est tout simplement la retenue en sortie du dernier additionneur, que nous noterons $C_{o}$. On trouve donc :

$C_{o}\oplus C_{i}$

Il suffit donc de faire un XOR entre la dernière retenue et la précédente pour obtenir le bit de débordement.

Les extensions et simplifications de l'additionneur

Dans cette section, nous allons nous intéresser à quelques circuits similaires à l'additionneur, qui ont été utilisés dans les premiers processeurs 8 bits. Nous allons voir comment réaliser un circuit qui est capable de faire au choix : un XOR, ou une addition. Nous allons aussi voir un circuit capable d'incrémenter un nombre, appelé l'incrémenteur.

L'incrémenteur

Maintenant, nous allons voir un circuit capable d'incrémenter un nombre, appelé l'incrémenteur. Les circuits incrémenteurs étaient très utilisés sur les premiers processeurs 8 bits, comme le Z-80, le 6502, les premiers processeurs x86 comme le 8008, le 8086, le 8085, et bien d'autres. Il s'agit d'un circuit assez simple, mais qu'il peut être intéressant d'étudier.

Le circuit incrémenteur se construit sur la même base qu'un additionneur, qu'on simplifie. En effet, incrémenter un nombre A revient à calculer A + 1. En clair, l'opération effectuée est la suivante :

   $a_{7}$ $a_{6}$ $a_{5}$ $a_{4}$ $a_{3}$ $a_{2}$ $a_{1}$ $a_{0}$ 
+  0  0  0  0  0  0  0  1
------------------------------

Le calcul alors très simple : il suffit d'additionner 1 au bit de poids faible, sur la colonne la plus à droite, et propager les retenues pour les autres colonnes. En clair, on n'additionne que deux bits à chaque colonne : un 1 sur celle tout à droite, la retenue de la colonne précédente pour les autres. Un incrémenteur est donc constitué de demi-additionneurs enchaînés les uns à la suite des autres. Le circuit incrémenteur basique est équivalent à un additionneur à propagation de retenue, mais où on aurait remplacer tous les additionneurs complets par des demi-additionneurs.

Circuit incrémenteur.

On peut légèrement optimiser le demi-additionneur le plus à droite, vu qu'il n'y a pas de retenue entrante. Il est en effet possible de le remplacer par un circuit qui incrémente le bit d'entrée. Si on établit sa table de vérité, on voit rapidement que la somme est l'inverse du bit d'entrée, alors que la retenue est égale au bit d'entrée.

Ce circuit incrémenteur à propagation de retenue était utilisé sur le processeur Intel 8085, avec cependant une optimisation très intéressante. Pour la comprendre, rappelons que les portes logiques sont construites à partir de transistors. Les portes les plus simples à implémenter avec des transistors CMOS et TTL sont les portes NON, NAND et NOR. Le demi-additionneur est donc construit comme ci-dessous

Demi-additionneur en CMOS, les portes coloriées en jaunes sont construites avec un seul transistor CMOS/TTL.

Les ingénieurs ont tenté de se débarrasser de la porte NON, et ont réussit à s'en débarrasser pour une colonne sur deux. L'idée est de prendre les demi-additionneurs deux par deux, par paires. On peut alors regrouper les portes logiques comme ceci :

Brique de base de l'incrémenteur du 8085

Les trois portes sont fusionnées, de manière à donner une porte NOR couplée à une porte NON.

Brique de base de l'incrémenteur du 8085 - les portes en jaune sont faites avec un seul transistor

On peut optimiser le tout en fusionnant la porte XOR avec la porte NON pour le calcul de la somme, la porte XOR étant une porte composite. Mais nous n'en parlerons pas plus que ça ici.

Le résultat est que la propagation de la retenue est plus rapide. Au lieu de passer par une porte NAND et une porte NON, il traverse une seule porte : une porte NAND pour les colonnes paires, une porte NOR pour les colonnes impaires. Avec cette optimisation, la retenue se propage presque deux fois plus vite. Mine de rien, cette optimisation économisait des portes logiques et rendait le circuit deux fois plus rapide.

Pour résumer, ce circuit ne paye pas de mine, mais il était largement suffisant sur les premiers microprocesseurs. Ils utilisaient généralement un incrémenteur capable de traiter des nombres de 8 bits, guère plus. Ces processeurs étaient très peu puissants, et fonctionnaient à une fréquence très faible. Ainsi, ils n'avaient pas besoin d'utiliser de circuits plus complexes pour incrémenter un nombre, et se contentaient d'un incrémenteur à propagation de retenues. Il existe cependant des processeurs qui utilisaient des incrémenteurs complexes, avec anticipation de retenues, voir du carry skip. Par exemple, le processeur Z-80 de Zilog utilisait un incrémenteur pour des nombres de 16 bits, ce qui demandait des performances assez élevées. Et cet incrémenteur utilisait à la fois anticipation de retenues et carry skip. Pour ceux qui veulent en savoir plus sur cet incrémenteur, voici un lien sur le sujet :

• The Z-80's 16-bit increment/decrement circuit reverse engineered .

Les liens entre l'addition et l'opération XOR

Dans cette section, nous allons nous intéresser à un circuit qui effectue un XOR ou un NXOR en plus de l'addition. Le choix d'utiliser à la fois une addition et un XOR/NXOR peut sembler bizarre. Certes, les deux sont des opérations très simples à implémenter en binaire (encore que, l'addition est quand même compliquée). Mais la raison est qu'il est assez facile de générer un XOR/NXOR à partir d'une addition, en bidouillant les retenues. En effet, une opération XOR est identique à une addition binaire dont on ne tiendrait pas compte des retenues. Cela fonctionne car un additionneur complet additionne trois bits, en faisant deux XOR :

$(A\oplus B)\oplus {\text{Retenue}}$

Si on met la retenue à zéro, on a :

$(A\oplus B)\oplus 0=A\oplus B$.

Maintenant, que se passe-t-il si on met toutes les retenues à 1 ? Dans ce cas, pour chaque additionneur complet, le bit du résultat est :

$(A\oplus B)\oplus 1$

Sachant que $X\oplus 1={\overline {X}}$, on se rend compte que le circuit calcule le NXOR des deux entrées.

On a donc un moyen pour implémenter un XOR avec un additionneur : il suffit de mettre à zéro toutes les retenues. Le faire est très simple sur les additionneurs à anticipation de retenue, sur lesquels il suffit de modifier le circuit d'anticipation de retenues. Le circuit d'anticipation de retenues prend alors une à deux entrées supplémentaires, qui précisent quelle est l'opération à effecteur : un XOR/NXOR ou une addition. Le circuit génère alors les retenues adéquates : les retenues pour l'addition, des retenues toutes à 1 ou toutes à 0 pour un XOR/NXOR. Ce genre de bidouille est utilisé dans l'unité de calcul 74181.

Mais il existe une solution encore plus simple sur les additionneurs à propagation de retenue, qui permet d'implémenter un XOR en plus de l'addition. Pour cela, supposons que le circuit prenne en entrée un bit qui précise s'il faut faire un XOR ou une addition. Ce bit vaut 0 pour un XOR et 1 pour une addition. Avec ce choix, on peut intercaler des portes ET avant l'entrée de retenue, qui font un ET entre ce bit et la retenue. Si le bit est à 0, l'entrée de retenue des additionneurs complets sera mise à 0, et vaudra la retenue sinon. Cette méthode marche avec tous les additionneurs, mais elle est plus simple à implémenter avec les additionneurs à anticipation de retenue.

Circuit qui fait ADD et XOR.

L'additionneur BCD

Maintenant, voyons un additionneur qui additionne deux entiers au format BCD. Pour cela, nous allons devoir passer par deux étapes. La première est de créer un circuit capable d'additionneur deux chiffres BCD. Ensuite, nous allons voir comment enchaîner ces circuits pour créer un additionneur BCD complet.

L'additionneur BCD qui fait l'opération chiffre par chiffre

Nous allons commencer par voir un additionneur qui additionne deux chiffres en BCD. Il fournit un résultat sur 4 bits et une retenue qui est mise à 1 si le résultat dépasse 10 (la limite d'un chiffre BCD). L'additionneur BCD se base sur un additionneur normal, pour des entiers codés en binaire, auquel on ajoute des circuits pour gérer le format BCD. Les deux chiffres sont codés sur 4 bits et sont additionnés en binaire par un additionneur des plus normal, similaire à ceux vus plus haut. Le résultat est alors un entier codé en binaire, sur 5 bits, qu'on cherche à corriger/convertir pour obtenir un chiffre BCD. Pour corriger le résultat, une idée intuitive serait de prendre le résultat et de faire une division par 10. Le quotient donne la retenue, alors que le reste est le résultat, le chiffre BCD . Mais faire ainsi prendrait beaucoup de circuits, ce qui ne vaut pas le coup. Il existe une autre méthode beaucoup plus simple.

Une autre méthode détecte si le résultat est égal ou supérieur à 10, ce qui correspond à un "débordement" (on dépasse les limites d'un chiffre BCD). Si le résultat est plus petit que 10, il n'y a rien à faire : le résultat est bon et la retenue est de zéro. Par contre, si le résultat vaut 10 ou plus, il faut corriger le résultat et générer une retenue à 1. Il faut donc ajouter un circuit qui détecte si le résultat est supérieur à 9. La retenue s'obtient facilement : le circuit qui détecte si le résultat est supérieur à 9 donne directement la retenue. Ce circuit peut se fabriquer simplement à partir de sa table de vérité, ou en utilisant les techniques que nous verrons dans un chapitre ultérieur sur les comparateurs. LA solution la plus simple est clairement d'utiliser la table de vérité, ce qui est très simple, assez pour être laissé en exercice au lecteur.

Additionneur BCD

Pour comprendre comment corriger le résultat, établissons une table de vérité qui associe le résultat et le résultat corrigé. L'entrée vaut au minimum 10 et au maximum 9 + 9 = 18. On considère la sortie comme un tout, la retenue étant un 5ème bit, le bit de poids fort.

Entrée							Retenue	Résultat corrigé (sans retenue)	interprétation de la sortie en binaire (retenue inclue)
0	1	0	1	0	(10)		1	0000	(16)
0	1	0	1	1	(11)		1	0001	(17)
0	1	1	0	0	(12)		1	0010	(18)
0	1	1	0	1	(13)		1	0011	(19)
0	1	1	1	0	(14)		1	0100	(20)
0	1	1	1	1	(15)		1	0101	(21)
1	0	0	0	0	(16)		1	0110	(22)
1	0	0	0	1	(17)		1	0111	(23)
1	0	0	1	0	(18)		1	1000	(24)

En analysant le tableau, on voit que pour corriger le résultat, il suffit d'ajouter 6. La raison est que le résultat déborde d'un nibble à 16 en binaire, mais à 10 en décimal : il suffit d'ajouter la différence entre les deux, à savoir 6, et le débordement binaire fait son travail. Donc, la correction après une addition est très simple : si le résultat dépasse 9, on ajoute 6. Il suffit d'ajouter un circuit qui additionne 6, assez facile à concevoir avec un additionneur qu'on simplifie et le tour est joué. Au final, une autre version possible du circuit est celle illustrée ci-dessous. Dans celle-ci, le circuit de correction peut soit ne rien faire, soit ajouter 6 au résultat. Le choix entre les deux est commandé par un bit d'entrée, un bit de commande dédié.

Additionneur BCD, seconde version

Pour obtenir un additionneur BCD complet, il suffit d’enchaîner les additionneurs précédents, comme on le ferait avec les additionneurs complet dans un additionneur à propagation de retenue. La seule chose importante est que le circuit précédent est altéré de manière à ce qu'on puisse prendre en compte la retenue. Pour cela, rien de plus simple : il suffit d'utiliser l'entrée de retenue de l'additionneur binaire. Au final, l'additionneur BCD est beaucoup plus compliqué qu'un additionneur normal. Il rajoute des circuits à un additionneur normal, à savoir un circuit pour détecter si chaque chiffre binaire est >9, un petit additionneur pour ajouter 6 et un multiplexeur. De plus, il est difficile d'appliquer les optimisations disponibles sur les additionneurs non-BCD. Notamment, les circuits d'anticipation de retenue sont totalement à refaire et le résultat est relativement compliqué. c'est ce qui explique pourquoi le BCD a progressivement été abandonné au profit du binaire simple.

L'additionneur BCD par ajustement décimal

L'additionneur BCD précédent effectuait son travail chiffre BCD par chiffre BCD. Il additionne et corrige le résultat un chiffre BCD après l'autre, en commençant par le chiffre BCD de poids faible. Mais il existe des additionneurs BCD qui font autrement. L'idée est d’additionner les deux opérandes avec une addition binaire normale, puis de corriger le résultat. Le tout se fait donc en deux étapes : l'addition, puis la correction du résultat. Les deux étapes traitent des opérandes complètes, de 8, 16, voire 32 bits, et non des chiffres BCD seuls.

Une telle technique était utilisée dans le processeur Intel 8085, et de manière générale sur les premiers processeurs x86. Sur ce processeur, les deux étapes d'addition et de correction du résultat étaient séparées dans deux opérations distinctes. Il n'y avait pas d'opération d'addition BCD proprement dit, seulement une addition binaire normale. Par contre, l'addition était secondée par une opération dite d'ajustement décimal qui transformait un nombre binaire en nombre codé en BCD. Effectuer une addition BCD demandait donc de faire deux opérations à la suite : une addition binaire simple, suivie par l'opération d'ajustement décimal. Cela permettait de gérer des nombres entiers en binaire usuel et des entiers BCD sans avoir deux instructions d'addition séparées pour les deux, sans compter que cela simplifiait aussi les circuits d'addition. L'opération d'ajustement décimal lisait l'opérande à manipuler dans un registre (l’accumulateur), et mémorisait le résultat dans ce même registre. Elle prenait une opérande de 8 bits, soit deux chiffres BCD, et fournissait un résultat de la même taille. Elle avait son propre circuit, assez simple, que nous allons voir dans ce qui suit.

L'ajustement décimal s'effectue en ajoutant une constante bien précise à l'opérande à convertir en BCD. L'idée est que la constante est découpée en morceaux de 4 bits, correspondant chacun à un chiffre BCD de l'opérande, chaque morceau contenant soit un 0, soit 6. Cela permet d'ajouter soit 0, soit, à chaque chiffre BCD, et donc de le corriger. La propagation des retenues d'un chiffre à l'autre est effectuée automatiquement par l'addition binaire de la constante. La constante est calculée en deux étapes, sur un principe similaire à celui vu dans l'additionneur précédent. D'abord, on découpe l'opérande en nibbles et on vérifie si chaque nibble est supérieur ou égal à 10. Ensuite, la seconde étape rend les résultats de ces comparaisons et détermine la valeur de chaque nibble de la constante finale. Par exemple, si je prends l'opérande 1001 1110, le nibble de poids faible déborde, alors que celui de poids fort non. La constante sera donc 0000 0110 : 0x06. Inversement, si le nibble de poids fort déborde et pas celui de poids faible, la constante sera alors 0x60. Et la constante est de 0x66 si les deux nibbles débordent, de 0x00 si aucun ne déborde.

Le circuit d’ajustement décimal est donc composé de trois étapes : deux étapes pour calculer la constante, et un circuit d'addition pour additionner cette constante au nombre de départ. La première étape découpe l'opérande en morceaux de 4 bits, en chiffres BCD, et vérifie si chacun d'entre eux vaut 10 ou plus. La seconde étape prend les résultats de la première étape, et les combine pour calculer la constante. Enfin, on trouve l'addition finale, qui était réalisée par un circuit d'addition utilisé à la fois pour l'ajustement décimal et l'addition binaire. La différence entre une addition normale et une opération d'ajustement décimal tient dans le fait que les deux premières étapes sont désactivées dans une addition normale.

Additionneur BCD parallèle