Voici la réalisation standard d'un additionneur complet 1-bit (Full Adder) qui calcule la somme S de trois bits x, y, z modulo 2, et la retenue C (carry).
Pour réaliser un circuit qui additionne deux entiers A et B de n bits, le plus simple est de placer en cascade n circuits analogues au précédent ; voici un additionneur 4-bits réalisé selon ce principe (ripple-carry adder) — sur le diagramme FA est l'abréviation de Full Adder :
On peut diminuer le délai de calcul au prix d'une augmentation de la complexité du circuit, avec une partie dédiée au calcul simultané de toutes les retenues (Carry Lookahead Generator) ; voici à gauche un additionneur 4 bits réalisé selon ce principe (Carry Lookahead Adder), avec à droite le détail partiel (il manque un étage) de la partie centrale du circuit (générateur de retenues) :
L'absence du dernier étage du générateur de retenues sur la partie droite de la figure n'est pas une erreur ; on peut en effet dessiner cet étage sur le modèle des précédents pour calculer C4 , mais de tels additionneurs 4-bits devront être disposés en cascade pour construire par exemple un additionneur 16-bits. Il y a une meilleure idée : en remplaçant la sortie C4 par deux sorties P et G bien conçues, on peut alors relier 4 additionneurs 4-bits par un générateur de retenues supplémentaire (mais identique aux précédents) pour construire un additionneur 16-bits rapide.
Table de vérité :
x | y | z | x y | x ⊕ y | (x ⊕ y) z | Γ |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 0 | 0 | 1 |
On voit que Γ = 1 si et seulement si au moins deux des trois variables x, y, z valent 1, autrement dit si la majorité de ces trois variables vaut 1, et dans ce cas l'addition produit une retenue.
La majorité vaut 1 si et seulement si l'un des couples (x, y), (x, z), (y, z) vaut (1, 1). La fonction maj s'écrit donc :
x y + x z + y z = x y + ( x + y ) z .
La formule est la même pour Γ sauf que la disjonction (opérateur +) est remplacée par la disjonction exclusive (addition modulo 2 ⊕). Les deux formules diffèrent donc a priori lorsque x = y = 1, mais dans ce cas la conjonction x y vaut 1 ; on a donc :
x y + (x + y) z = x y + (x ⊕ y) z
et on peut employer au choix l'une de ces deux expressions pour calculer la retenue.
δ ( S0 ) = 2 et δ ( C1 ) = 3.
δ ( S1 ) = 4 et δ ( C2 ) = 5 ; en effet le calcul de S1 peut démarrer dès l'instant 0, mais avant de "traverser" la seconde porte xor il faut "attendre" le signal C1 ; le délai de calcul vaut donc 4. Noter qu'il n'y a pas véritablement attente : à l'instant 3 le signal z prend la valeur C1 , ce qui entraîne éventuellement la modification du signal S à l'instant 4 ; auparavant la valeur de S n'est pas fiable car z peut être différent de C1 .
On a les formules récurrentes suivantes :
δ ( Si ) = 1 + δ ( Ci ) , δ ( Ci+1 ) = 2 + δ ( Ci )
d'où δ ( S2 ) = 6 , δ ( C3 ) = 7 , δ ( S3 ) = 8 , δ ( C4 ) = 9.
Dans le cas général d'un additionneur n bits, on a par récurrence :
δ ( Sn-1 ) = 2 n , δ ( Cn ) = 2 n + 1
On a de même C2 = G1 + P1 C1 . En reportant la valeur de C1 on obtient :
C2 = G1 + P1 G0 + P1 P0 C0 .
C'est bien le signal calculé par le générateur de retenues.
On doit avoir C4 = G + P C0 . Or on sait que :
C4 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0
d'où :
G =
G3 +
P3
G2 +
P3
P2 G1 +
P3
P2
P1 G0 ,
P =
P3
P2
P1
P0
Le circuit contient 4 générateurs bas (ceux de gauche sur la figure ci-contre) et un générateur haut (celui de droite sur la figure ci-contre). Calcul des délais :
Le gain n'est donc pas énorme par rapport au circuit constitué de 4 additionneurs 4-bits en cascade (question 11), mais la complexité du circuit est presque la même : on a juste ajouté un générateur 4-bits. Et on est prêt à construire un additionneur 64-bits en reliant 4 additionneurs 16-bits par un générateur 4-bits, sans augmenter sensiblement le délai de calcul.