Apprendre › Chapitre 7

Additionneurs binaires : demi-additionneur, complet et à propagation de retenue

8 min de lecture · Équipe bitGateLab

L'addition est l'opération la plus importante d'un ordinateur : elle sert à soustraire, à multiplier, à calculer des adresses mémoire et à compter des événements. Vous allez construire ici un additionneur en partant de zéro : d'abord le demi-additionneur à un bit, puis l'additionneur complet qui accepte une retenue, ensuite l'additionneur de plusieurs bits en cascade et, pour finir, la façon dont ce même circuit soustrait grâce au complément à 2.

Additionner en binaire à la main

Les règles d'addition de deux bits sont au nombre de quatre : 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 et 1 + 1 = 10₂, c'est-à-dire 0 avec une retenue de 1 vers la colonne suivante. Si une retenue arrive en plus, 1 + 1 + 1 = 11₂ : résultat 1 et retenue 1. Comme en décimal, on additionne colonne par colonne, de droite à gauche, en reportant la retenue vers la gauche.

Demi-additionneur

Le demi-additionneur additionne deux bits, A et B, et fournit deux sorties : la somme S et la retenue C.

A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

La colonne S est la table d'une XOR et la colonne C est celle d'une AND. Par conséquent :

S = A ⊕ B C = AB

Demi-additionneur : la XOR fournit la somme S et la AND fournit la retenue C. Les points indiquent l'endroit où chaque entrée se divise vers les deux portes.

On l'appelle « demi » parce qu'il n'a pas d'entrée pour la retenue venant d'une colonne précédente ; il ne convient donc que pour le bit de poids faible.

Additionneur complet

L'additionneur complet additionne trois bits : A, B et la retenue d'entrée C_in. Il fournit la somme S et la retenue de sortie C_out. Remarquez que la paire (C_out, S) est, en binaire, le nombre de uns présents sur les entrées.

A	B	C_in	C_out	S
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

S vaut 1 lorsque le nombre de uns est impair : S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ C_in. C_out vaut 1 lorsqu'il y a deux uns ou plus : C_out = Σm(3, 5, 6, 7), ce qui, une fois simplifié, donne la fonction majorité :

C_out = AB + AC_in + BC_in

Si vous essayez de regrouper dans le tableau de Karnaugh de S, vous verrez qu'aucun 1 n'a de voisin à 1 : c'est le motif en damier typique de la XOR, qui ne se simplifie pas en somme de produits.

Additionneur complet avec deux demi-additionneurs

Une façon pratique de le réaliser consiste à enchaîner deux demi-additionneurs et une OR :

Premier demi-additionneur : P = A ⊕ B et G = AB.
Second demi-additionneur, avec P et C_in : S = P ⊕ C_in et une retenue partielle P·C_in.
C_out = G + P·C_in = AB + (A ⊕ B)C_in.

Cette expression est équivalente à celle de la majorité : si A et B valent 1, AB donne déjà la retenue ; si exactement l'une des deux vaut 1, la retenue dépend de C_in. G est appelé signal de génération et P signal de propagation.

Additionneur à propagation de retenue

Pour additionner des nombres de n bits, on relie n additionneurs complets à la file : le C_out de chaque étage devient le C_in du suivant. Le C_in du premier étage est mis à 0, et le C_out du dernier est la retenue finale. Cette structure s'appelle additionneur à propagation de retenue, ou ripple carry, parce que la retenue « se propage » d'étage en étage comme une onde. Dans la famille 74HC, il existe une puce qui contient quatre additionneurs complets déjà reliés de cette façon (le 74HC283).

Exemple 1 : 1011 + 0110 avec un additionneur 4 bits. En décimal, c'est 11 + 6.

Étage	A_i	B_i	C_in	S_i	C_out
0	1	0	0	1	0
1	1	1	0	0	1
2	0	1	1	0	1
3	1	0	1	0	1

Somme : S₃S₂S₁S₀ = 0001 avec une retenue finale de 1, soit 10001₂ = 17. Correct : 11 + 6 = 17, qui ne tient pas sur 4 bits, d'où la retenue finale.

Le prix à payer, c'est le temps. L'étage 3 ne peut pas fournir son résultat définitif tant qu'il n'a pas reçu la retenue de l'étage 2, qui attend lui-même celle de l'étage 1. Si chaque étage met deux niveaux de portes à produire sa retenue, un additionneur de n bits met de l'ordre de 2n temps de propagation de porte dans le pire des cas. Pour 64 bits, c'est trop lent ; c'est pourquoi les processeurs utilisent des additionneurs à retenue anticipée, qui calculent les retenues en parallèle à partir des signaux G et P. Dans le chronogramme du simulateur, vous pouvez voir les sorties changer par paliers avant de se stabiliser.

Soustraire avec le même additionneur

Comme expliqué dans systèmes de numération, en complément à 2 l'opposé de B est B + 1. On a donc :

A − B = A + B + 1

Pour l'obtenir, il suffit de placer une XOR sur chaque bit de B, avec l'autre entrée reliée à une ligne de commande M, et de relier aussi M au C_in du premier étage. Avec M = 0, les XOR laissent passer B et C_in = 0 : le circuit additionne. Avec M = 1, les XOR inversent B et C_in = 1 apporte le « +1 » : le circuit soustrait.

Exemple 2 : soustractions sur 4 bits.

9 − 5 : A = 1001, B = 0101, B = 1010. 1001 + 1010 + 1 = 1 0100. On ignore la retenue finale : 0100 = 4.
5 − 9 : A = 0101, B = 1001, B = 0110. 0101 + 0110 + 1 = 0 1100. Pas de retenue finale. 1100 en complément à 2 vaut −8 + 4 = −4.

Lorsque vous soustrayez des nombres non signés, la retenue finale indique s'il y a eu un emprunt : 1 signifie que A ≥ B et 0 signifie que A < B.

Pour les nombres signés, le dépassement de capacité se détecte avec une seule XOR : V = C₃ ⊕ C₄, où C₃ est la retenue qui entre dans le dernier étage et C₄ celle qui en sort. Si elles sont différentes, le résultat ne tient pas sur 4 bits signés.

Erreurs fréquentes

Utiliser un demi-additionneur dans les étages intermédiaires. Tout étage qui reçoit une retenue a besoin d'un additionneur complet.
Laisser flottant le C_in du premier étage. Il doit être relié à 0 pour additionner, ou à M dans un additionneur-soustracteur.
Confondre retenue finale et dépassement de capacité. Pour les nombres signés, la retenue finale est ignorée ; le dépassement se détecte avec C₃ ⊕ C₄.
Oublier le « +1 » de la soustraction et ne câbler que les inverseurs : le résultat est trop petit d'une unité.
Écrire S = A + B + C_in avec des OR. La somme sur un bit est une XOR, pas une OR.

Essayez dans le simulateur

Réaliser un additionneur dans l'éditeur est la meilleure passerelle entre les portes et l'arithmétique. Commencez par un bit, puis montez jusqu'à quatre.

Placez deux entrées, une XOR et une AND, et reliez-les comme sur le schéma du demi-additionneur. Générez sa table de vérité.
Réalisez un additionneur complet avec deux demi-additionneurs et une OR, puis vérifiez ses 8 lignes avec la table de cet article.
Copiez l'additionneur complet quatre fois et chaînez les retenues. Mettez le premier C_in à 0.
Réglez les entrées sur 1011 et 0110 et vérifiez que la sortie vaut 0001 avec une retenue finale de 1.
Ouvrez le chronogramme, changez une entrée qui oblige la retenue à traverser les quatre étages (par exemple 1111 + 0001) et observez comment les sorties se stabilisent.

Exercices

Calculez S et C_out pour un additionneur complet avec A = 1, B = 0, C_in = 1.
Réponse
Il y a deux uns : S = 0 et C_out = 1 (1 + 0 + 1 = 10₂).
Additionnez 0111 + 0101 avec un additionneur 4 bits et indiquez les retenues de chaque étage.
Réponse
Étage 0 : 1 + 1 = 0, retenue 1. Étage 1 : 1 + 0 + 1 = 0, retenue 1. Étage 2 : 1 + 1 + 1 = 1, retenue 1. Étage 3 : 0 + 0 + 1 = 1, retenue 0. Résultat 1100 = 12 (7 + 5).
Avec un additionneur-soustracteur 4 bits, calculez 6 − 3 et indiquez la valeur de M.
Réponse
M = 1. 0110 + 1100 + 1 = 1 0011. On ignore la retenue : 0011 = 3.
En interprétant les valeurs comme des nombres signés sur 4 bits, y a-t-il dépassement de capacité dans 0111 + 0101 ?
Réponse
Oui. 7 + 5 = 12 ne tient pas dans la plage −8 à +7. Le résultat 1100 se lirait −4. Les retenues sont C₃ = 1 et C₄ = 0, et V = 1 ⊕ 0 = 1.