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.
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 :
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 :
L'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.
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é. Évidemment, cette porte logique est actuellement fabriquée à partir de portes logiques simples (ET, OU, NON, NAND, NOR). Il existe plusieurs possibilités pour cela, qui sont presque toutes plus simples que le circuit précédent. La plus simple utilise une couche de portes ET suivie par une porte OU à plusieurs entrées. En voici une autre :
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.
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.
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.
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.
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 :
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.
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.
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 formula_1 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.
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.
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.
Ces additionneurs sont composés de deux parties :
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 :
Il ne nous reste plus qu'à voir comment fabriquer le circuit qui reste. Pour cela, il faut remarquer que la retenue est égale :
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 :
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.
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.
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 :
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 :
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.
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 :
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.
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.
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.
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.
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.
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 formula_2, 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 : formula_3. Or, le résultat correct serait formula_4. 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 formula_5. Or, le résultat correct serait formula_6. 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 à formula_7. 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 formula_8 à formula_9. 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 formula_10 , alors que la valeur basse vaut formula_11 (avec formula_9 et formula_8 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.
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 :
L'équation de ce circuit est la suivante, avec formula_14 et formula_15 les signes des deux opérandes, et formula_16 la retenue de la colonne précédente :
En simplifiant, on obtient alors :
Or, il se trouve que formula_19 est tout simplement la retenue en sortie du dernier additionneur, que nous noterons formula_20. On trouve donc :
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 :
 formula_22 formula_23 formula_24 formula_25 formula_26 formula_27 formula_28 formula_29 
 + 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.
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
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 :
Les trois portes sont fusionnées, de manière à donner une porte NOR couplée à une porte NON.
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 :
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 :
Si on met la retenue à zéro, on a :
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 :
Sachant que formula_33, 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.
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.
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.
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é.
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.