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

Dans ce chapitre, nous allons voir les circuits capables de faire une addition ou une soustraction, ainsi que quelques circuits spécialisés. Précisons cependant que les fabricants de processeurs 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 circuits 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

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 d'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. 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 et l'additionneur complet

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.

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. Il fournit en sortie deux bits : un bit de somme et une retenue sortante. Ce circuit qui additionne trois bits est appelé un additionneur complet. Voici sa table de vérité :

Retenue entrante	Opérande 1	Opérande 2	Retenue sortante	Bit de somme
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Il est possible d'utiliser un tableau de Karnaugh pour traduire la table de vérité, mais elle donne un résultat légèrement sous-optimal. D'autres méthodes donnent des résultats plus compréhensibles. Nous allons les détailler dans ce qui suit.

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

La solution 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.

Le circuit de calcul de la retenue peut être remplacé par une porte à majorité, mais cette possibilité n'est presque jamais utilisée, on lui préfère le circuit à trois portes logiques.

Les autres implémentations de l'additionneur complet 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 retenue doit absolument être le plus rapide possible,vu que la propagation des retenues est le point limitant pour les performances d'un additionneur.

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

Le circuit précédent est basé sur deux additions 2-bits successives : une première pour additionner deux bits d'opérande, une seconde pour additionner la retenue. Mais il existe une autre façon de faire l'addition, qui est terriblement importante pour la suite du cours. L'idée est de regarder ce que vaut la retenue sortante, en fonction de la retenue entrante. Pour cela, reprenons la table de vérité de l'additionneur complet.

Dans la majorité des cas, la retenue sortante est égale à la retenue entrante. On dit que la retenue entrante est propagée sur la sortie de retenue. Cependant, il y a aussi deux cas où la retenue n'est pas propagée : celui où la retenue sortante est forcée à 1, et celui où elle est forcée à 0. Dans le premier cas, l'addition donne une retenue à 1, quelle que soit la retenue envoyée en entrée (sous-entendu, même si celle-ci vaut 0). On dit que la retenue sortante est générée. Dans le cas inverse, la retenue sortante est forcée à 0, peu importe la retenue entrante. On dit que la retenue entrante est absorbée.

Il y a cependant une petite ambiguïté à dire que la retenue a été propagée, absorbée ou générée. En effet, prenons le cas où la retenue sortante et entrantes valent toutes deux 0 : est-ce que la retenue a été propagée ou bien absorbée, ou les deux ? Idem quand les deux retenues sont à 1. Il y a un choix arbitraire à faire dans ce genre de cas, pour la plupart des lignes de la table de vérité. Cependant, il y a un choix bien précis qui est supérieur aux autres, et c'est celui qui est présenté dans le tableau suivant. Les lignes rouge correspondent à une retenue propagée, celles en bleu à une retenue absorbée, celle en vert à une retenue générée.

Retenue entrante	Opérande 1	Opérande 2	Retenue sortante	Bit de somme
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Avec ce choix, on peut déterminer si la retenue est propagée, absorbée ou générée, sans tenir compte de la retenue elle-même. On peut déterminer dans quel cas on est seulement en regardant les bits d'opérandes nommés A et B.

La retenue est propagée si les deux bits d'opérande sont différents.
La retenue est générée si les deux bits d'opérande sont à 1.
La retenue est absorbée si les deux bits d'opérande sont à 0.

L'additionneur que nous allons voir détermine si la retenue est propagée, absorbée ou générée, et calcule la retenue sortante en fonction de ça. Il génère deux bits, nommés P et G : P pour Propagate, G pour Generate. Le bit P indique que la retenue entrante doit être propagée ou non : il est mis à 1 pour propager la retenue entrante, à 0 si elle ne doit pas être propagée. Le bit G indique si une retenue a été générée ou non : 1 si une retenue générée, 0 sinon. Une retenue est considérée comme absorbée si elle n'est pas ni propagée ni générée, pas besoin d'un troisième bit pour gérer ce cas.

Pour rappel, la retenue est propagée si les deux bits sont différents, n'est pas propagée s'ils sont identiques. Déterminer si deux bits sont identiques ou différents est le comportement d'une banale porte XOR. Le bit P est donc généré par une simple porte XOR. Quant au bit G, il est à 1 si les deux bits d'opérandes sont à 1, ce qui correspond à une porte ET.

Il existe des pseudo-additionneurs qui ne calculent pas la retenue sortante et fournissent à la place les signaux P et G, en plus du résultat. Un tel additionneur est appelé un additionneur P/G (P/G pour propagation/génération). Ils sont très utiles pour créer des additionneurs dits "à anticipation de retenue", comme on le verra dans la suite du chapitre.

Pour créer un additionneur complet avec cette méthode, il faut ajouter un circuit qui calcule la retenue sortante à partir des bits P et G. La retenue finale vaut 1 soit quand la retenue est générée, soit quand la retenue d'entrée vaut 1 et qu'elle est propagée. La traduction en équation logique; puis en circuits, donne un circuit strictement identique à celui basé sur deux demi-additionneurs... Vous remarquerez que les signaux P et G sont calculés par le premier demi-additionneur.

Une méthode alternative donne cependant un circuit différent. Le circuit en question choisit entre les deux situations : soit il propage la retenue, soit il calcule la retenue adéquate. Propager une retenue demande de connecter l'entrée de retenue sur la sortie de retenue. Mais cela ne doit être fait que si les conditions sont réunies, que si la retenue est belle et bien propagée. Si ce n'est pas le cas, il faut connecter la sortie de retenue à un circuit qui calcule la retenue adéquate. Pour cela, on utilise un multiplexeur, commandé par le bit P.

Quand la retenue entrante n'est pas propagée, la retenue sortante vaut 1 si une retenue est générée, 0 sinon. Le circuit qui calcule la retenue doit donc fournir un 0 si les bits d'opérande valent tous les deux 0, un 1 s'ils valent tous les deux 1. Mais si la retenue est propagée, la retenue calculée peut prendre n'importe quelle valeur, vu que le multiplexeur ne choisira pas sa sortie. Suivant quelles valeurs on prend dans ce cas, le circuit obtenu sera différent. Si on suppose que le circuit fournit un 0 si la retenue est propagée, alors la retenue calculée indique une retenue est générée ou non : on peut alors réutiliser le bit G ! Le tout donne alors ce circuit :

Le circuit semble utiliser plus de portes logiques que nécessaires. Cependant, tout dépend de l'implémentation du multiplexeur. En réalité, nous verrons dans quelques chapitres qu'il est possible d'implémenter un multiplexeur avec seulement 6 transistors. L'implémentation utilise des portes à transmission, mais nous en reparlerons dans le chapitre sur les transistors, quand nous verrons les additionneurs à Manchester Carry Chain. Au passage, une variante de ce circuit a été utilisée dans le processeur processeur 8086 d'Intel, comme on le verra dans le chapitre suivant.

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. L'unité de calcul de l'Intel 4004 et de l'Intel 8008 faisaient autrement : le bit du résultat était calculé à 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 ces deux cas, le bit du résultat vaut 0, quelle que 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 un circuit qui vérifie si tous les bits opérande valent 0, un autre s'ils valent tous 1. 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. Notons qu'on peut encore optimiser le circuit en fusionnant les deux portes NOR entre elles, mais c'est là un détail.

À ce stade, vous êtes certainement étonné qu'un tel circuit ait existé. Il utilise beaucoup de portes logiques, a une profondeur logique supérieure : il n'a rien d'avantageux. Sauf qu'il était utilisé sur d'anciens processeurs, qui utilisaient la technologie dite TTL, différente de la technologie CMOS des transistors modernes. Et avec la technologie TTL, il est possible de fusionner plusieurs portes logiques ET et NOR en une seule porte logique ET/OU/NON ! Un additionneur complet construit ainsi ne prenait que deux portes logiques : une pour le calcul de la retenue sortante, une autre pour le reste du circuit.

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. L'addition des nombres codés en complètement à deux sera vu dans une section ultérieure.

L'additionneur série

Il est possible d'additionner deux nombres bit par bit,colonne par colonne, avec un additionneur complet. Cela demande de coupler un additionneur complet avec plusieurs registres à décalages. Les opérandes sont placées chacune dans un registre à décalage, afin de passer d'un bit au suivant, d'une colonne à la suivante, à chaque cycle. Même chose pour le résultat, qui a sont propre registre à décalage. 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.

L'additionneur série a été utilisé sur d'anciens prototypes dans les années 50-60, et quelques ordinateurs commerciaux très rares.

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 ${\text{R}}_{\text{Entrée}}$ sur l'additionneur. L'additionneur le plus à droite est bien un additionneur complet, et non un demi-additionneur,c e qui fait qui l'additionneur a une entrée de retenue. Tous les additionneurs ont une entrée de retenue de ce type. Elle est très utile pour 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.

L'avantage est qu'il utilise très peu de portes logiques et est assez économe en transistors, ce qui fait qu'il était utilisé sur certains processeurs 8 et 16 bits assez anciens. Bien que très simple, 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. La raison 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.

L'addition étant une opération fréquente, il vaut mieux utiliser d'autres méthodes d'addition, plus rapides. Pour cela, les autres additionneurs utilisent diverses optimisations : calculer les retenues en parallèle, éliminer certaines opérations inutiles quand c'est possible, accélérer le calcul de la retenue avec des techniques d'anticipation de retenue, etc. Mais ces optimisations demandent d'utiliser plus de circuits, quitte à gagner quelque peu en rapidité. Si on met de côté les additionneurs de type Manchester carry chain, qu'on ne peut pas encore expliquer à ce stade du cours, il existe plusieurs solutions, qui donnent respectivement les additionneurs à saut de retenue, à sélection de retenue, et à anticipation de retenue. Nous allons les voir dans les sections suivantes.

Les accélérations de la propagation de retenue

Dans cette section, nous allons voir quelques additionneurs qui visent à accélérer la propagation de la retenue, mais en gardant la base de l'additionneur de propagation de retenue. Avant de poursuivre, partons du principe que l'additionneur est conçu en assemblant des additionneurs à plus simples, qui additionnent environ 4 à 5 bits, parfois plus, parfois moins. Ces additionneurs simples seront nommés blocs dans ce qui suit, et l'un d'entre eux est illustré ci-contre. Chaque bloc prend en entrée un morceau des deux opérandes à additionner, mais aussi une retenue d'entrée. Il fournit en sortie un résultat codé sur 4/5 bits, mais aussi une retenue sortante.

Dans un bloc, la retenue sortante est plus ou moins calculée à part du résultat. L'enjeu est de calculer la retenue sortante d'un bloc rapidement, plus rapidement qu'un additionneur à propagation de retenue. Le calcul du résultat n'a pas besoin d'être accéléré, on garde des additionneurs à propagation de retenue. En enchaînant plusieurs blocs les uns à la suite des autres, la retenue sortante d'un bloc est connectée sur l'entrée de retenue du bloc suivant, la retenue est propagée d'un bloc au suivant.

Les blocs sont tous identiques dans le cas le plus simple, mais il est possible d'utiliser des blocs de taille variable. Par exemple, le premier bloc peut avoir des opérandes de 6 bits, le second des opérandes de 7 bits, etc. Faire ainsi permet de gagner un petit peu en performances, si la taille de chaque bloc est bien choisie. La raison est une question de temps de propagation des retenues. La retenue met plus de temps à se propager à travers 8 blocs qu'à travers 4, ce qui prend plus de temps qu'à travers 2 blocs, etc. En tenir compte fait que la taille des blocs tend à augmenter ou diminuer quand on se rapproche des bits de poids fort.

Le calcul parallèle de la retenue

L'optimisation la plus évidente est de calculer la retenue sortante en parallèle de l'addition. Chaque bloc contient, à côté d'un additionneur proprement dit, un circuit qui calcule la retenue sortante. Il existe de nombreuses manières de calculer la retenue sortante. La plus simple consiste à établir la table de vérité de l'entrée de retenue et d'utiliser les techniques du chapitre sur les circuits combinatoires. Cela marche si les blocs sont de petite taille, mais elle devient difficile si le bloc a des opérandes de 2/3 bits ou plus. Mais des techniques alternatives existent.

Un exemple est celui de l'additionneur CMOS 4008, un additionneur de 4 bit. Il est intéressant de voir comment fonctionne ce circuit. Aussi, voici son implémentation. Le circuit est décomposé en trois sections. Une première couche de demi-additionneurs, le circuit de calcul de la retenue sortante, le reste du circuit qui calcule l'addition en propageant les retenues. Le circuit de calcul de la retenue sortante prend les résultats des demi-additionneurs, et les utilise pour calculer la retenue sortante. C'est là une constante de tous les circuits qui vont suivre.

Le point important à comprendre est que les demi-additionneurs génèrent les signaux P et G, qui disent si l'additionneur propage ou génère une retenue. Ces signaux sont alors combinés pour déterminer la retenue sortante. La méthode de combinaison des signaux P et G dépend fortement de l'additionneur utilisé. La méthode utilisée sur le 4008 utilise à la fois les signaux P et G, ce qui fait que c'est un hybride entre un additionneur à propagation de retenue, et un additionneur à anticipation de retenue qui sera vu dans la suite du chapitre. Mais il existe des techniques alternatives pour calculer la retenue sortante.

L'additionneur à saut de retenue

L'additionneur à saut de retenue (carry-skip adder) est un additionneur dont le temps de calcul est variable. Le calcul prendra quelques cycles d'horloges avec certains opérandes, tandis qu'il sera aussi long qu'avec un additionneur à propagation de retenue avec d'autres. Il n'améliore pas le pire des cas, dans lequel la retenue doit être propagée du début à la fin, du bit de poids faible au bit de poids fort. Mais dans les autres cas, le circuit détecte quand le résultat de l'addition est disponible, quand la retenue a fini de se propager. Il permet d'avoir le résultat en avance, plutôt que d'attendre suffisamment pour couvrir le pire des cas.

L'additionneur à saut de retenue est lui aussi composé de blocs qui additionnent 4/5 bits. Il peut, sous certaines conditions, sauter complètement la propagation de la retenue dans le bloc. L'idée est de calculer si un bloc génère une retenue sortante, ou si la retenue entrante est simplement propagée. Dans le second cas, le bloc ne fait que recopier la retenue entrante sur la sortie de retenue. La propagation de retenue entre blocs est alors skippée (mais elle a quand même lieu). Si une retenue est générée dans le bloc, on envoie cette retenue sur la retenue sortante. Le choix entre les deux est le fait d'un multiplexeur.

Toute la difficulté est de savoir comment commander le multiplexeur. Pour cela, on doit savoir si le circuit propage une retenue ou non. Le bloc propage une retenue si chaque additionneur complet propage la retenue. Les additionneurs complets doivent donc fournir le résultat, mais aussi indiquer s'ils propagent la retenue d'entrée ou non. Le signal de commande du multiplexeur est généré assez simplement : il vaut 1 si tous les additionneurs complets du bloc propagent la retenue précédente. C'est donc un vulgaire ET entre tous ces signaux.

L'additionneur à saut de retenue est construit en assemblant plusieurs blocs de ce type.

L'additionneur à sélection de retenue

L'additionneur à sélection de retenue utilise aussi des blocs, comme les additionneurs précédents. L'addition se fait 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

Les additionneurs à anticipation de retenue accélèrent le calcul des retenues en les calculant sans les propager. Au lieu de calculer les retenues une par une, ils 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 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.

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.

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 améliorés pour gagner en performances. Les additionneurs à anticipation de retenue générent des signaux propagate et generate pour un bit, sous-entedu 1 bit par opérande. L'optimisation apportée est de générer des signaux propagate et generate pour un bit, mais aussi pour des groupes de 2, 3, 4, ..., N bits. Par exemple, il est possible de générer un signal P 0 vers 7, qui précise si la retenue de la seconde colonne est propagée jusqu'à la 7ème colonne ou non. Un autre exemple est un signal de génération qui indique si les colonnes 4 à 7 génèrent une retenue ou non.

En clair, les signaux P et G ont maintenant un intervalle, qui précise de quelle colonne vers quelle colonne se fait la propagation, ou entre quelles colonnes se fait la génération. De plus, les signaux pour un intervalle peuvent se calculer en combinant les signaux pour des intervalles plus restreints. Par exemple, pour calculer P pour les colonnes 0 à 10 peuvent se calculer à partir des deux signaux P des colonnes 0-4 et 5-10.

Néanmoins, il y a plusieurs manières pour subdiviser les intervalles en intervalles plus petits et combiner le tout. Et elles donnent chacune des additionneurs différent, comme l'additionneur de Ladner-Fisher, l'additionneur de Brent-Kung, l'additionneur de Kogge-Stone, ou tout design hybride. Ils ont des caractéristiques différentes. 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. Les autres ont des performances un peu plus variables, mais utilisent plus de portes logiques.

Additionneur de Kogge-Stone pour 4 bits.

L'additionneur Kogge-Stone est illustré ci-contre. Il est composé de plusieurs couches de portes logiques. La toute première calcule les signaux P et G pour chaque colonne, comme le ferait un additionneur à anticipation de retenue. Il s'agit de la couche en rouge dans le schéma ci-dessous. Les circuits en jaune combinent ces signaux de manière à calculer les signaux P et G pour plusieurs colonnes. En vert, les circuits calculent la retenue finale.

Voici le circuit pour 8 bits :

Additionneur de Kogge-Stone pour 8 bits.

L'addition signée et la soustraction

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 de 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 de l'addition, 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.

La 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. Il ressemble beaucoup à un demi-additionneur, les différences se résumant à une porte NON ajoutée pour le calcul de la retenue.

Comme pour l'additionneur, seux demi-soustracteurs peuvent être combinés pour donner un soustracteur complet. Le calcul de la retenue se fait en combinant les deux retenues des demi-soustracteurs avec une porte OU. Les soustracteurs complets sont utilisés pour créer des soustracteurs à propagation de retenue ou tout autre circuit soustracteur, sur le même modèle que les additionneurs.

Il est possible de créer un circuit capable de faire à la fois des additions et des soustractions. Il suffit de modifier les additionneurs complets pour qu'ils supportent la soustraction. Concrètement, la seule différence est la présence des deux portes NON dans le schéma précédent : ils sont absents sur un additionneur complet. Une modification simple remplace ces deux portes NON par deux inverseurs commandable. Cependant, il y a une meilleure manière de faire, qu'on va détailler dans ce qui suit.

L'additionneur-soustracteur pour opérandes codées en complément à deux

Étudions 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.

Additionneur-soustracteur en complément à deux.

Une implémentation alternative est la suivante. Elle remplace l'inverseur commandable par un multiplexeur.

L'additionneur-soustracteur pour opérandes codées en signe-magnitude

Passons maintenant aux nombres codés en signe-valeur absolue, les deux opérandes étant notées 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). Une astuce est que 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, reste à corriger le résultat. Il suffit de lui ajouter un inverseur commandable pour obtenir le circuit d'addition finale.

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 (A + B et −A − B) ne pose aucun problème, autant les soustractions posent problème (A − B et −A + B). Suivant que $A<B$ ou que $A>B$ , le signe du résultat ne sera pas le même. Déterminer le signe du résultat se fait en regardant les bits de débordement d'entier, comme on le verra plus bas.

L'additionneur-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 qui donne ceci :

(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 : un pour additionner/soustraire les représentations binaires des opérandes, et un autre pour ajouter/retirer le biais en trop/manquant.

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, une sorte d'équivalent BCD de l'additionneur complet. 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). Les deux opérandes sont des chiffres BCD codés sur 4 bits et sont additionnés en binaire par un additionneur des plus normaux, similaire à ceux vus plus haut. Le résultat est alors un entier codé en binaire, sur 5 bits, qu'on corrige/convertit pour obtenir un chiffre BCD et une retenue sortante.

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 un circuit diviseur par 10 utilise beaucoup de portes logiques, ce qui ne vaut pas le coup. 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, qui calcule 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.

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.

On peut maintenant implémenter l'additionneur BCD, en combinant le comparateur avec 10, le circuit de correction, et l'additionneur. La première solution calcule deux versions du résultat : la version corrigée, la version normale. Le choix entre les deux est réalisée par un multiplexeur, commandé par le comparateur.

L'autre solution utilise un circuit commandable qui soit additionne 6, soit ne fait rien. Le choix entre les deux est commandé par le bit calculé par le comparateur.

Une version alternative du circuit précédent est la suivante. Il contient deux additionneurs : un pour additionner les deux chiffres BCD, un autre pour additionner 6 si besoin. Le résultat du comparateur est directement utilisé pour générer l'opérande du second additionneur : 0 ou 6. Le circuit est simple à concevoir, mais gaspille beaucoup de circuit. Idéalement, il vaudrait mieux utiliser un circuit combinatoire d'addition avec une constante.

Pour obtenir un additionneur BCD complet, il suffit d’enchaîner les additionneurs précédents, comme on le ferait avec les additionneurs complets dans un additionneur à propagation de retenue. Au final, l'additionneur BCD est beaucoup plus compliqué qu'un additionneur normal, car il rajoute un comparateur ">9", un petit additionneur pour ajouter 6 et éventuellement d'autres circuits. 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.

La soustraction en BCD se fait comme en binaire : le nombre à soustraire est remplacé par son complément, le circuit additionne le complément et l'autre opérande, le débordement d'entier fait que le résultat marche. Sauf qu'ici, le complément est un complément à 9. Il se calcule chiffre par chiffre : chaque chiffre est remplacé par (9 - le chiffre en question).

L'additionneur BCD par ajustement décimal

L'additionneur BCD précédent effectuait son travail chiffre BCD par chiffre BCD, mais il existe des additionneurs BCD qui font autrement. Sur les premiers processeurs x86, il n'y avait pas d'opération d'addition BCD proprement dit, seulement une addition binaire normale de 8, 16 ou 32 bits. Par contre, elle était secondée par une opération dite d'ajustement décimal qui transformait un nombre binaire en nombre codé en BCD. L'opération d'ajustement décimal prenait un opérande de 8 bits codé en binaire et fournissait un résultat de la même taille, c'est à dire deux chiffres 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'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 6, à 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. L'opération d'ajustement décimal calcule automatiquement la constante. Elle découpe l'opérande en nibbles, vérifie si chaque nibble est supérieur ou égal à 10, puis 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.

L'additionneur biquinaire

Les entiers BCD ne sont qu'un des encodages hybrides entre décimal et binaire. L'encodage biquinaire est l'un d'entre eux et nous allons faire un rappel rapide à ce sujet. Pour simplifier, un chiffre encodé en biquinaire est composé de deux parties : un bit, couplé à une partie quinaire encodée en représentation one-hot. La partie quinaire encode un nombre allant de 0 à 4, ce qui prend 5 bits (0, 1, 2, 3 et 4). Le bit indique s'il faut ou non ajouter 5 à la valeur encodée par la partie quinaire. Ainsi, on peut coder tous les nombres de 0 à 9.

Additionner deux nombres de biquinaire demande donc d'additionner deux parties quinaires encodées en one-hot et d'additionner deux bits. Mais attention : il faut tenir compte de la retenue de l'addition des parties quinaires. Et idéalement, il faut aussi tenir compte d'une retenue entrante, provenant de l'addition de la colonne de chiffres précédente. Toute la difficulté vient de la création de l'additionneur one-hot. Heureusement, vu qu'il n'y a que 4-5 bits à additionner, il est souvent fabriqué à partir de sa table de vérité.

Un avantage du biquinaire est que le calcul du complément à 9 est très simple. Il faut pour cela : inverser la partie binaire avec une porte NON, puis inverser l'ordre des bits de la partie quinaire. Concrètement, le bit de poids faible devient le bit de poids fort, et ainsi de suite. Par exemple, une partie quinaire 01000 devient 00010, 10000 devient 00001, 00100 ne change pas, etc. Le tout peut se calculer avec une porte NON et 5 multiplexeurs.

L'additionneur BCD avec calculs intermédiaires en biquinaire

L'ordinateur IBM 1401, un ancien mainframe des années 60, utilisait un additionneur BCD un peu particulier. Les nombres étaient encodés en BCD dans la mémoire de l'ordinateur, mais les circuits de calcul utilisaient la représentation biquinaire. Lors d'un calcul, le processeur de l'ordinateur traduisait les chiffres BCD en représentation biquinaire, faisait une addition en biquinaire, avant de traduire le résultat en BCD normal.

Pour être précis, l'IBM 1401 utilisait une variante du biquinaire. L'encodage biquinaire de l'IBM 1401 est le suivant : la partie binaire disait si le chiffre était pair ou non, la partie quinaire encodait les valeurs 0, 2, 4, 6 et 8. Le chiffre se calculait en additionnant la partie binaire (0 ou 1) au nombre pair encodé par la partie quinaire. Si l'IBM 1401 utilisait cette variante du biquinaire, c'est car elle donnait des circuits de conversion BCD-biquinaire plus économes en portes logiques et plus rapides.

La partie binaire est le bit de poids faible du chiffre BCD, la partie biquinaire est calculée par un simple décodeur qui prend en entrée le chiffre BCD, amputé de son bit de poids faible. La traduction inverse demande d'utiliser un encodeur, à la place du décodeur. Par contre, le circuit d'addition biquinaire était plus compliqué du fait de la gestion des retenues. L'addition des parties binaires et quinaires se faisait en parallèle, dans deux additionneurs séparés. Cependant, l'addition des parties binaire fournit une retenue, qu'il faut prendre en compte. Pour cela, l'IBM 1401 disposait d'un troisième additionneur qui fournissait le résultat final, encodé en biquinaire.

Une implémentation moderne demanderait d'utiliser des portes ET combinées à des portes OU, le circuit pouvant être construit simplement à partir de sa table de vérité. Sur l'IBM 1401, le circuit était cependant différent, en raison de l'utilisation de OU câblés, des croisements de fils qui fonctionnent comme des portes OU, que nous n'avons pas encore vu pour le moment, mais qui seront détaillés dans quelques chapitres. Les OU câblés étaient utilisés pour simplifier le design du circuit, mais demandaient des portes logiques spécifiques, ce qui collait avec le fait que ce mainframe utilisait des transistors en Germanium. L'implémentation exacte est décrite dans cet article de blog, mais je ne recommande sa lecture qu'à ceux qui savent ce qu'est un OU câblé :

Qui-binary arithmetic: how a 1960s IBM mainframe does math.

L'incrémenteur

L'incrémenteur est un circuit capable d'incrémenter un nombre. De tels circuits é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. Le circuit incrémenteur se construit sur la même base qu'un additionneur, qu'on simplifie. 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. En clair : un incrémenteur est un additionneur normal, dont on a remplacé les additionneurs complets par des demi-additionneurs. Le 1 le plus à droite est injecté sur l'entrée de retenue entrante de l'additionneur. Et cela marche avec tous les types d'additionneurs, que ce soit des additionneurs à propagation de retenue, à anticipation de retenue, etc.

L'incrémenteur à propagation de retenue

Un incrémenteur à propagation de retenue 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 remplacé tous les additionneurs complets par des demi-additionneurs. L'entrée de retenue entrante est forcément mise à 1, sans quoi l'incrémentation n'a pas lieu.

Quelques incrémenteurs permettent cependant de configurer l'entrée de retenue de l'incrémenteur. Il est ainsi possible de la mettre à 0 ou à 1, ce qui effectue soit : une opération identité (l'opérande est recopié sur la sortie), soit une incrémentation. Un tel circuit est nommé un incrémenteur commandable. Nous aurons à utiliser une fois ou deux de tels incrémenteurs commandables dans la suite du cours.

L'incrémenteur à propagation de retenue était utilisé sur le processeur Intel 8085, avec cependant une optimisation très intéressante. Un demi-additionneur usuel est construit comme ci-dessous

Regardons ce que cela donne quand on enchaine deux demi-additionneurs l'un à la suite de l'autre.

Les ingénieurs ont réussit à se débarrasser de la porte NON, pour une colonne sur deux. Les trois portes en jaune dans le schéma précédent 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 à chaque colonne, il traverse une seule porte : une porte NAND pour les colonnes paires, une porte NOR pour les colonnes impaires. Mine de rien, cette optimisation économisait des portes logiques et rendait le circuit deux fois plus rapide.

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.

Les incrémenteurs plus complexes sont rares

Pour résumer, ce circuit ne paye pas de mine, mais il était largement suffisant sur les premiers microprocesseurs, qui géraient des opérandes de 8 bits. 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 débordements d'entier lors d'une addition/soustraction

Les instructions arithmétiques manipulent des entiers codés sur un nombre fixe de bits, 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$ . Pour les nombres négatifs, l'intervalle est différent et dépend de la représentation utilisée. 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, le circuit 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.

D'autres circuits utilisent ce qu'on appelle l'arithmétique saturée : si un calcul génère 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 plus complexes, 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 et le corrige 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 couche 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 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. 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.

La détection des débordements entiers

Quand un débordement d'entier a eu lieu, il vaut mieux que l'additionneur prévienne ! Pour cela, l'additionneur a une sortie de débordement, parfois nommée Overflow, dont la valeur indique si l'addition a généré 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é ou signé.

Pour les additionneur non-signés, l'additionneur calcule un bit de plus que ce qui est supporté par l'ordinateur. Par exemple, un additionneur 32 bits fournit un résultat sur 33 bits, un débordement d'entier a lieu quand le 33ème bit est à 1. Précisément, la sortie de débordement n'est autre que la retenue finale, celle fournie par le dernier additionneur complet. Le seul type de débordement possible est un débordement par le haut, où le résultat dépasse la valeur maximale. Avec l'arithmétique saturée, le circuit de saturation consiste en une seule couche de multiplexeurs, voire en un circuit de mise à la valeur maximale tel que vu dans le chapitre sur les opérations bits à bits.

Pour les additionneurs non-signés, la gestion des débordements d'entiers dépend fortement de la représentation signée. Nous allons étudier le cas du complément à deux. Si vous vous rappelez le chapitre 1, les calculs sur des nombres en complètement à deux utilisent les règles de l'arithmétique modulaire, c'est une condition nécessaire. À priori, on peut 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 écrase le bit de poids fort, il y a un débordement d'entiers. Il existe une règle simple qui permet de détecter ces débordements d'entiers. L'addition de deux nombres positifs ne peut pas être un nombre négatif. Si on additionne deux nombres dont le bit de signe est à 0 et que le bit de signe du résultat est à 1, on est en face d'un débordement d'entiers. Même chose pour deux nombres négatifs : 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é.

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.

◄ Retour vers « Les circuits de décalage et de rotation »

Sommaire du livre

Continuer vers « Les circuits de comparaison » ►