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.

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 fournit en sortie deux bits : un bit de somme et une retenue sortante. 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 assez compliqué. La retenue et le bit de somme sont calculés à part. La retenue est calculée avec trois portes ET et une porte OU. Le bit de somme est calculé lui avec 4 portes ET, une porte OU, et trois portes NON.

Le circuit obtenu est pas loin d'être optimal, que ce soit en termes de rapidité que de portes logiques utilisées. Mais il est assez compliqué à comprendre, vu que c'est une traduction littérale de la table de vérité. D'autres implémentations alternatives donnent des résultats plus compréhensibles. Nous allons les voir dans la suite de cette section.

L'additionneur complet basé sur des demi-additionneurs

Nous avons déjà vu comment additionner deux bits dans le chapitre sur les incrémenteurs, mais quelques rappels ne seront pas de trop. Le demi-additionneur est un circuit qui additionne deux bits. Il 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.

Mais un demi-additionneur n'additionne que deux bits, il manque de quoi additionner la retenue. Une solution pour cela est d'enchaîner deux demi-additionneurs : un qui additionne les deux bits de données, et un second qui additionne la retenue au résultat du précédent. La retenue finale se calcule en combinant les sorties de retenue des deux demi-additionneurs, avec une porte OU. Le résultat est un additionneur complet fabriqué avec deux demi-additionneurs. Pour vous en convaincre, établissez la table de vérité de ce circuit, vous verrez que ça marche.

L'implémentation naïve d'un demi-additionneur utilise une porte XOR et une porte ET, comme illustré ci-contre. Le circuit s'obtient en faisant uen traduction littérale de la table de vérité du circuit. Si je dis qu'elle est naïve, c'est car il est possible de l'optimiser, de manière à éliminer des redondances cachées. Mais nous avions déjà vu cela dans le chapitre sur les incrémenteurs, aussi laissons cela pour plus tard.

En combinant deux demi-additionneurs de ce type, on obtient l'additionneur complet suivant. Les deux sorties de retenue des demi-additionneurs sont combinées avec une porte OU, pour calculer la retenue finale.

Le fait de combiner les deux retenues avec une porte OU n'est pas ce qu'il y a de plus intuitif. La table de vérité nous dit que ça fonctionne, mais on comprend mal pourquoi. Mais tout devient plus clair quand on sait que les deux retenues ne peuvent pas être à 1 en même temps. Même dans l'addition 1 + 1 + 1, seule une retenue est à 1. Soit l'addition des deux bits d'opérande donne naissance à une retenue, soit c'est l'addition résultat + retenue entrante. La retenue sortant est donc à 1 quand une des deux addition donne une retenue. D'où l'usage d'une porte OU. Remarquez qu'une porte XOR donne le même résultat, vu que le cas où les deux retenues sont à 1 n'est jamais rencontré.

La propagation et la génération des retenues

L'additionneur complet que nous allons voir dans cette section sert à introduire les concepts de propagation, génération et absorption de retenue. Il s'agit de concepts très importants quand on étudie les additionneurs. l'idée part d'un principe très simple : la retenue sortante dépend de la retenue d'entrée. La relation entre les deux se résume à trois cas, qui dépendent de la valeur des deux bits additionnés, nommés A et B.

Dans le premier cas, la retenue entrante est égale à la retenue sortante. On dit que la retenue entrante est propagée par l'additionneur.
Dans le second cas, la retenue est forcée à 0 : la retenue sortante vaut 0, peu importe la valeur de la retenue entrante.
Dans le troisième cas, la retenue est forcée à 1 : la retenue entrante vaut 1, peu importe la valeur de la retenue entrante.

Signaux P et G fournis par un demi-additionneur

Maintenant, créons un circuit qui nous dise si une retenue est propagée ou générée. Il a deux bits de sortie, nommés P et G : P pour Propagate, G pour Generate. Le bit P est à 1 si la retenue entrante est propagée, il est à 0 sinon. Le bit G est à 1 si une retenue est 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.

Il se trouve que ce circuit n'est autre qu'un demi-additionneur ! Pour vous en rendre compte, regardez la table de vérité d'un additionneur complet, illustrée ci-dessous. Lorsque les deux bits d'opérande sont à 0, la retenue sortante vaut toujours 0. Si ils sont tous deux à 1, alors la retenue sortante vaut 1. S'ils sont différents, alors retenues sortante et entrante sont égales. 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 se trouve que ces deux portes forment un demi-additionneur !

Opérande 1	Opérande 2	Retenue entrante	Retenue sortante
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Ensuite, créons un circuit qui prend ces deux sorties P et G, et calcule la retenue sortante en fonction. Le circuit en question a trois entrées : la retenue entrante, les deux bits P et G. La retenue sortante vaut 1 soit si une retenue est générée, soit si la retenue entrante est propagée et qu'elle vaut 1. En notant ${C_{in}}$ et ${C_{out}}$ les retenues entrantes et sortante, on a :

{C_{out}}=G+\left(P.C_{in}\right)

Le circuit est donc composé d'une porte OU et d'une porte ET. En combinant un demi-additionneur avec le circuit de calcul de retenue sortante vu plus haut, on a :

Certes, on retombe sur le circuit vu plus haut. Mais il est possible de remplacer le circuit en orange par un autre. Par exemple, il est possible de le remplacer par multiplexeur, qui choisit entre la retenue générée et la retenue entrante (propagée). Le choix se fait selon la valeur du bit P, qui chosiit entre propager la retenue et la générer.

Le circuit exact est illustré ci-dessous. Il semble utiliser plus de portes logiques que l'additionneur complet précédent. Cependant, nous verrons dans quelques chapitres qu'il est possible d'implémenter un multiplexeur avec seulement 6 transistors, voire moins ! 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.

Pour finir, sachez qu'il existe des additionneurs qui fournissent : le bit de résultat, deux sorties P et G qui indiquent si l'addition propage ou génère une retenue. Il ne s'agit pas d'additionneurs complets, car il manque de quoi calculer la retenue sortante. De tels additionneurs seront appelés des additionneurs partiels. De tels additionneurs sont utilisés dans certains additionneurs pour gagner en performance.

Enfin, il existe aussi ce que j'ai décidé d'appeler des additionneurs P/G, qui sont des additionneurs complets auxquels on a ajouté deux sorties P et G, en plus de la sortie de retenue. Leur circuit est le même que celui d'un additionneur complet, auquel on a ajouté deux fils. Vu que ces deux sorties sont fournies par le premier demi-additionneur, ajouter ces deux sorties demande d'ajouter des fils, pas de portes logiques. De tels additionneurs sont aussi utilisés dans certains additionneurs pour gagner en performance.

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

Maintenant, voyons une dernière implémentation possible de l'additionneur complet. Mais avant de voir comment l'additionneur est implémenté, nous allons devoir faire un petit focus sur la retenue sortante. Reprenons la table de vérité, et regardons ce qu'il en est pour la retenue sortante uniquement.

Retenue entrante	Opérande 1	Opérande 2	Retenue sortante
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Vous remarquerez que la retenue sortante est égale au bit majoritaire, parmi les trois bits d'opérande. Si deux ou trois bits sont à 1, la retenue sortante vaut 1. Et réciproquement avec 0. Le circuit de calcul de la retenue peut donc être remplacé par une porte à majorité.

Mais une porte à majorité est assez gourmande en circuit, ce qui fait qu'un additionneur pareil ne serait pas pratique, ni utile. Du moins, ce serait le cas s'il n'y avait pas une possibilité d'optimisation extrêmement intéressante. Il est possible de calculer le 'bit de somme' à partir de la retenue sortante ! En effet, le bit de somme est l'inverse de la retenue sortante, sauf dans deux cas : les trois bits d'entrée sont à 0, où ils sont tous à 1. Le bit de somme vaut 0 dans le premier cas, 1 dans le second cas.

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

En clair, 6 lignes de la table de vérité sur 8 peuvent se calculer avec une porte à majorité, le reste demandant quelques portes logiques pour faire la correction. L'implémentation en circuit demande donc trois choses :

de calculer la retenue sortante et de quoi l'inverser ;
un circuit qui vérifie si tous les bits opérande valent 0 : une porte NOR ou OU fait l'affaire ;
un circuit qui vérifie s'ils valent tous 1, à savoir une porte ET.

Ensuite, on combine le résultat des trois circuits précédents pour obtenir le résultat final. La combinaison est le fait du circuit en jaune dans le schéma ci-dessous.

Le circuit en jaune est assez simple. Quand la porte ET sort un 1, la sortie doit être forcée à 1. Par contre, quand la porte OU sort un zéro, la sortie doit être forcée à 0. Il suffit donc d'enchainer un circuit de mise à 1 et un circuit de mise à 0. Nous avons vu dans le chapitre sur les opérations de masquage qu'il s'agit respectivement d'une porte OU et d'une porte ET.

Divers processeurs utilisaient des additionneurs complets de ce type : le fameux Z80, l'Intel 4004 et de l'Intel 8008 sont les exemples les plus notables. Pourtant, on pourrait s'étonner 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'interface d'un additionneur est illustrée ci-contre. Un additionneur prend deux opérandes sur deux entrées séparées, et fournit le résultat sur une sortie dédiée. De plus, il a une entrée sur laquelle envoyer une retenue entrante, et a une sortie pour la retenue sortante. La sortie de retenue indique que le résultat de l'addition a débordé (au sens d'un débordement d'entier). Pour l'entrée de retenue, son utilité deviendra plus claire dans ce qui suit, mais souvenez-vous qu'elle existe.

L'entrée et la sortie de retenue sont parfois utilisées pour combiner plusieurs petits additionneurs, pour former un additionneur plus grand. Nous verrons de nombreux exemples dans ce qui suit. Il est assez commun de créer des additionneurs pour des opérandes de 16/32/64 bits, avec des additionneurs de 4/5 bits.

L'additionneur série

Il est possible d'additionner deux nombres bit par bit, grâce à un additionneur complet associé à plusieurs registres à décalages. Les opérandes sont placées chacune dans un registre à décalage, et l'additionneur complet utilise les bits sortants de ces registres à décalage. Le bit du résultat est envoyé au registre à décalage 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. Il a été utilisé sur d'anciens ordinateurs dans les années 50-60, aussi bien des prototypes que des ordinateurs commerciaux.

L'additionneur à propagation de retenue

L'additionneur à propagation de retenue est aussi appelé l'additionneur ripple carry, c'est son nom anglais. J'utiliserais occasionnellement le nom anglais dans ce qui suit, car celui-ci est plus court. Ilutilise un additionneur complet pour chaque colonne de l'addition. Pour gérer les retenues, il suffit ainsi de câbler des additionneurs complets les uns à la suite des autres, chacun envoyant sa retenue à la colonne suivante.

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, à droite du schéma précédent, l'entrée de retenue ${\text{R}}_{\text{Entrée}}$ . 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.

Cet additionneur utilise très peu de portes logiques, ce qui fait qu'il était utilisé sur certains processeurs 8 et 16 bits, dont le budget en portes logiques était limité. Bien que très simple, cet additionneur est cependant peu performant. Son temps de calcul est proportionnel à la taille des opérandes. Par exemple, additionner deux opérandes de 32 bits prendra deux fois plus de temps que pour des opérandes de 16 bits. La raison est que les retenues doivent se propager à travers le circuit, du premier additionneur jusqu'au dernier.

L'addition étant une opération fréquente, d'autres additionneurs ont été inventés. Ils utilisent des optimisations qui utilisent plus de circuits pour gagner en rapidité. Mais avant de voir ces optimisations, nous allons voir s'il est possible d'optimiser les additionneurs à propagation de retenue.

L'additionneur à saut de retenue

L'additionneur à propagation de retenue peut être optimisé de deux manières. La première accélère la propagation de la retenue, en agissant au niveau des additionneurs complets. La Manchester carry chain est une optimisation de ce type, mais on ne peut pas encore expliquer à ce stade du cours, car elle optimisait les additionneurs complets au niveau des transistors eux-mêmes. Elle a été utilisée sur de nombreux processeurs connus, comme le 8086 d'Intel ou le Z80.

La seconde manière rend l'addition plus rapide dans certains cas. Le résultat est un additionneur dont le temps de calcul est variable. Le calcul prendra quelques cycles d'horloges avec certains opérandes, mais d'autres opérandes ne verront aucune amélioration. 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 d'autres cas, il permet d'avoir le résultat en avance. L'optimisation en question donne l'additionneur à saut de retenue (carry-skip adder).

Il est composé en enchainant plusieurs additionneurs plus petits, qui additionnent 4/5 bits, rarement plus. De tels additionneurs de petite taille sont appelés des blocs, dans ce qui suit. L'idée est de détecter précocement si la retenue entrante est propagée à travers tout le bloc. Si la retenue est propagée dans tous le bloc, on peut directement l'envoyer sur la sortie de retenue, la retenue saute le bloc entier. Dans le cas contraire, on doit calculer la retenue normalement. Le choix entre les deux est le fait d'un multiplexeur. Toute la difficulté est de savoir comment commander le multiplexeur.

Pour savoir si une retenue est propagée dans un bloc entier, il faut utiliser des additionneurs complets, qui ont en plus une sortie P indiquant que l'additionneur propage la retenue. Le bloc propage une retenue si chaque additionneur complet propage la retenue, donc s'ils ont tous leur sortie P à 1. Un simple ET logique suffit à déterminer si c'est le cas. Le signal de commande du multiplexeur est donc un vulgaire ET entre toutes les sorties P des additionneurs complets du bloc.

Voici ce que ça donne pour un bloc de 4 bits :

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

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.

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.

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

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

Les additionneurs à anticipation de retenue

Les additionneurs à anticipation de retenue calculent chaque retenue sans avoir à propager les retenues précédentes. Au lieu de calculer les retenues une par une, ils calculent toutes les retenues en parallèle, à partir des bits des opérandes. 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 les retenues, sans les propager, directement à partir des opérandes ;
d'une couche d'additionneurs complets, qui additionnent chacun deux bits d'opérande et la retenue pré-calculée.

Le calcul des retenues se fait en deux étapes. La première détermine si les retenues sont propagées ou générées, pour chaque colonne. Elle détermine, pour chaque colonne, les bits P et G qui indiquent respectivement : qu'une retenue a été générée sur cette colonne, que la colonne propage la retenue précédente. La seconde étape utilise ces signaux P et G pour déterminer la retenue sur chaque colonne. Le circuit de calcul des retenues est donc composé de deux parties : une couche de demi-additionneurs pour générer les signaux P et G, un circuit de calcul des retenues proprement dit.

Circuit complet d'un additionneur à anticipation de retenue.

Pour rappel, la retenue de la colonne i, notée $C_{i}$ est égale à :

G_{i}+(P_{i}.C_{i-1})

, avec G le signal de génération de retenue, P le signal de propagation de retenue.

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é.

Plus haut, j'ai dit que le circuit était composé de trois couches : une couche de demi-additionneur pour les signaux P et G ; un circuit d'anticipation de retenue, puis l'addition finale. Mais les deux bits d'opérandes sont déjà additionnés dans la couche de demi-additionneur, autant réutiliser le résultat pour l'additionner à la retenue. Pour éliminer toute redondance de ce type, il est possible d'utiliser des additionneurs partiels (des additionneurs où la sortie de retenue a été remplacée par deux sorties P et G). L'additionneur final est alors composé de plusieurs additionneurs complets de ce type, couplé à un circuit d'anticipation de retenue.

Les additionneurs à anticipation de retenue sont plus rapides que les additionneurs à propagation de retenue. La raison est que les retenues sont calculées rapidement, dans un temps plus petit qu'en propageant la retenue. Pour rentrer dans les détails mathématiques, le temps de calcul n'est pas proportionnel au nombre de bits, mais proportionnel au logarithme de ce nombre de bits. Par contre, le gain en temps de calcul s'accompagne d'un cout en portes logiques conséquent. Le circuit qui calcule les retenues anticipées utilise beaucoup de portes logiques.

Les additionneurs à calcul parallèle de préfixe

Du fait du cout en portes logiques, utiliser un additionneur à anticipation de retenue est une solution pratique pour additionner 4 ou 8 bits. Mais pour des opérandes plus grands, de 16 ou 32 bits, cela utiliserait trop de portes logiques. Une partie de ce cout en portes logiques est cependant lié à des redondances. Si on analyse deux retenues différentes, à des colonnes différentes. Les circuits qui calculent ces deux retenues seront différents, mais ils contiendront des sous-circuits identiques. Pour vous en rendre compte, reprenons les quatre équations obtenues précédemment et essayez de trouver des redondances :

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 ).

Vous devriez trouver :

le terme P0 · C0 dans toutes les lignes ;
les termes P1 · P0 · C0 et P1 · P0 dans les trois dernières lignes ;
le terme P2 · P1 · P0 · C0 ; P2 · P1 · G0 et P2 · G1 dans les deux dernières lignes.

Il existe plusieurs manières d'exploiter de telles redondances, exploitées dans les additionneurs à calcul parallèle de préfixe. L'optimisation apportée est de générer des signaux propagate et generate pour des groupes de 2, 3, 4, ..., N colonnes. Par exemple, il est possible de générer un signal P 0 vers 3, qui indique si la retenue de la première colonne est propagée jusqu'à la 4ème colonne. Un autre exemple est un signal qui indique qu'une retenue a été générée entre 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.

Il est possible de combiner les signaux P et G de deux groupes de colonne, s'ils sont contiguës (ils peuvent aussi se recouvrir). Par exemple, il est possible de calculer les bits P et G pour les colonnes 0 à 10, à partir des deux signaux P/G des colonnes 0-4 et 5-10. Pour cela, les équations sont assez simples. Si je prends deux groupes nommés A et B, avec A pour les colonnes de poids fort et B celles de poids faible, on a :

P_{sortie}=P_{A}.P_{B}

G_{sortie}=G_{A}.P_{A}.G_{B}

Pour les bits des colonnes 2, 4, 8, 16, 32, 64, et autres, le calcul est simple. L'idée est de grouper les colonnes par groupes de 2. Puis, on calcule chaque groupe de 4 bits à partir de deux groupes de 2. Puis les groupes de 8 bits sont calculés à partir de deux groupes de 4 bits, et ainsi de suite pour toute puissance de deux.

Les seules difficultés surviennent pour les colonnes dont le nombre n'est pas une puissance de deux. Il y a plusieurs manières pour subdiviser ces colonnes en intervalles plus petits et combiner le tout. Et elles donnent chacune des additionneurs différents. Ils portent les noms d'additionneur de Ladner-Fisher, d'additionneur de Brent-Kung, d'additionneur de Kogge-Stone, etc. Dans le cas général, l'additionneur de Kogge-Stone est un des plus rapide, mais aussi un des plus gourmand en circuits, alors que c'est l'inverse pour l'additionneur de Brent-Kung. Les deux additionneurs sont illustrés ci-dessous, pour des opérandes de 8 bits. Dans ceux-ci, chaque losange calculent les bits P et G, à partir des signaux P et G de deux groupes précédents.

Le calcul parallèle de la retenue

L'anticipation de retenue est très rapide, mais utilise beaucoup de circuits, même en utilisant le calcul parallèle de préfixe. Les additionneurs à propagation de retenue font eux le compromis inverse. Mais il existe des intermédiaires, qui visent à obtenir un compromis entre performance et cout en portes logiques.

Un de ces compromis découpe un additionneur de 16/32/64 bits en additionneurs de 4/5 bits, qui sont enchainés en utilisant la propagation de retenue. Par contre, ces petits additionneurs de 4/5 bits utilisent l'anticipation de retenue. Ces additionneurs simples seront nommés blocs dans ce qui suit. Par exemple, on peut utiliser 4 additionneurs à anticipation de retenue de 4 bits, et propager les retenues entre eux. Le premier bloc calcule une retenue, qui est propagée au second bloc. Le second bloc calcule lui aussi une retenue, qui est propagée au troisième bloc, etc.

Le gain en performance est significatif, mais il est possible de faire presque aussi rapide, tout en économisant beaucoup de circuits. L'idée est de simplifier les additionneurs 4 bits, afin de ne pas utiliser une anticipation de retenue complète. L'anticipation de retenue n'est utilisée que pour la retenue sortante, alors que les bits de somme sont calculées avec propagation de retenue. La retenue sortante est donc calculée 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.

Le gain en portes logiques est assez significatif. En effet, on se passe de circuits d'anticipation de retenue pour les 4 bits de somme, on ne garde que celui pour la retenue sortante. Le fait d'utiliser la propagation de retenue pour calculer les 4 bits de somme est censé avoir un léger cout en performance, mais il se trouve que ce cout est très faible. En effet, le résultat n'est connu qu'une fois les retenues propagées jusqu'au dernier bloc. Et malgré l'anticipation des retenues, la propagation est assez lente. les additionneurs à propagation de retenue auront terminé leur travail bien avant.

Un exemple est celui de l'additionneur CMOS 4008, un additionneur de 4 bit. Il est composé en trois sections. Une première couche de demi-additionneurs calcule les signaux P et G utilisés à la fois pour l'anticipation de la retenue sortante, que pour calculer les bits de somme. Le circuit de calcul de la retenue sortante utilise l'anticipation de retenue. Le reste du circuit fait l'addition en propageant les retenues.

Les additionneurs à anticipation de retenue multi-niveau

Les additionneurs précédents mixent anticipation et propagation de retenue. Ceux que nous allons voir utilisent des blocs, mais utilisent l'anticipation de retenue entre les blocs. Les blocs utilisés peuvent être un additionneur à propagation de retenue, ou à anticipation de retenue, peu importe. Ce qui compte est que la retenue entrante de chaque bloc est calculée par anticipation de retenue.

Par exemple, il est possible de créer un additionneur 16 bits en utilisant 4 additionneurs/blocs de 4 bits, couplé à un circuit d’anticipation de retenue par bloc. Pour cela, les additionneurs de 4 bits doivent fournir deux sorties P et G. Les deux sorties indiquent que le bloc soit a généré une retenue, soit a propagé la retenue entrante. Par propagé, on veut dire que la retenue entrante du bloc s'est retrouvée sur la sortie de retenue du bloc. C'est le cas si les 4 colonnes propagent la retenue, ce qui signifie que :

P_{\text{4 bits}}=P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}

Pour la génération, cela veut dire qu'une colonne a générée une retenue, qui a été propagée jusqu'à la sortie. En clair, pour chaque colonne, il faut que le G = 1, et que les signaux P des colonnes soient à 1. Pour les 4 colonnes, cela donne :

G_{\text{4 bits}}=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{3}\cdot P_{2}+G_{0}\cdot P_{3}\cdot P_{2}\cdot P_{1}

Pour combiner 4 blocs de 4 bits, on devra donc combiner 4 bits P et G, avec un circuit d'anticipation de retenue.

Il est même possible d'aller plus loin et de combiner 4 additionneurs précédents pour obtenir un additionneur 64 bits.

Le résultat est un additionneur à plusieurs niveaux d’anticipation de retenue. Une anticipation de retenue dans un blocs de 4 bits (facultative), entre blocs de 4 bits, entre blocs de 16 bits. La même logique peut être utilisée avec des blocs de taille différente de 4, 16 et 64 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 à propagation de retenue

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. En clair, une soustraction en binaire demande de faire deux soustraction : pour chaque bit de la première opérande, on soustrait le bit associé de la seconde, puis on soustrait la retenue entrante.

Dans le chapitre sur les incrémenteurs/décrémenteurs, nous avons vu un circuit qui soustrait deux bits, appelé le 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. Il implémente la table de soustraction, qui est très simple en binaire :

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

Comme pour les additionneurs, deux 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. Là encore, si on regarde les sorties des deux demi-soustracteurs, il est impossible d'avoir les deux sorties de retenues à 1 en même temps.

Le circuit précédent peut se simplifier pour ne garder qu'une seule porte NON.

Les soustracteurs complets sont utilisés pour créer des soustracteurs à propagation de retenue, sur le même modèle que les additionneurs. Et je précise bien "à propagation de retenue", car l'anticipation de retenue et les autres optimisations ne marchent pas exactement pareil entre addition et soustraction. Les signaux de propagation et de génération de retenue ne sont pas générés pareil, idem pour la manière de les combiner.

Il est possible de fusionner un additionneur à propagation de retenue et un soustracteur de même type. Pour cela, il suffit de remarquer que les demi-soustracteurs et les demi-additionneurs se ressemblent beaucoup. La seule différence entre les deux est une vulgaire porte NON. En remplaçant cette porte NON par un inverseur commandable, on obtient un circuit qui sert soit de demi-additionneur, soit de demi-soustracteur, suivant ce qu'on envoie sur l'entrée de commande. Ci-dessous est illustré ce que donne ce remplacement pour un soustracteur complet. Le résultat est un additionneur/soustracteur à propagation de retenue.

Il est donc possible de fusionner un additionneur avec un soustracteur, ce qui donne un additionneur/soustracteur. Mais comme je l'ai dit plus haut, cela ne marche que si l'additionneur-/soustracteur utilise la propagation de retenue. Dès qu'on souhaite utiliser l'anticipation de retenue ou tout autre technique, les choses sont plus compliquées. Le calcul des retenues étant différent entre addition et soustraction, mutualiser les circuits d'anticipation de retenue pour les deux opérations ne donnera pas un résultat très propre. Ce qui n'est pas le cas avec les solutions que nous allons voir 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. 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.

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.

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

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 » ►