TD Circuits Combinatoires : Additionneurs

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

Full adder
  1. Ecrire la formule Γ qui donne la valeur de C en fonction de x, y, z telle qu'elle est calculée par ce circuit.
  2. Construire la table de vérité de Γ et vérifier que c'est bien celle de la fonction maj (majorité).
  3. La fonction maj s'écrit d'habitude x y + x z + y z ; comparer avec Γ et expliquer pourquoi ces deux formules décrivent la même fonction.

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 :

4-bits ripple-carry adder
  1. Calculer le délai de calcul δ des signaux S0 , C1 , S1 , C2 etc. c'est-à-dire le nombre de portes traversées avant que chacun de ces signaux prenne la valeur correcte, une fois les valeurs des signaux d'entrée Ai et Bi disponibles simultanément à l'instant 0.
  2. Dans le cas général d'un additionneur n bits, quel est le délai de calcul de Sn-1 et de Cn ?

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

4-bits Carry Lookahead Adder
  1. Exprimer Pi et Gi en fonction de Ai et Bi en utilisant la partie gauche de la figure.
  2. Exprimer C1 en fonction de C0 , P0 et G0 (partie droite de la figure). Vérifier qu'on trouve bien la même formule que pour l'additionneur 1-bit (cf. question 1).
  3. Exprimer C2 en fonction de C1 , P1 et G1 (en raisonnant, sans utiliser la figure). Reporter la valeur de C1 issue de la question précédente et comparer le résultat avec la valeur calculée par le générateur de retenues (partie droite de la figure).
  4. Expliquer de la même façon le calcul de C3 .
  5. Quel est le délai de calcul des 5 signaux de sortie S0 , S1 , S2 , S3 et C4 ? Quelle est la différence fondamentale avec le résultat de la question 4 ?

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.

  1. Quel est le délai de calcul de 4 additionneurs 4-bits placés en cascade ? Quelle est la formule générale pour un additionneur n bits ainsi réalisé, avec n multiple de 4 ?
  2. Ecrire l'équation qui doit relier C4 , P , G et C0 .
  3. Compléter le générateur de retenues sur la partie droite de la figure pour qu'il calcule les signaux de sortie P et G.
  4. Dessiner le schéma d'un additionneur 16-bits rapide ; les additionneurs 4-bits qui le composent seront représentés par des rectangles et des broches pour les entrées et les sorties. Quel est le délai de calcul de ce circuit ?

Corrigé

  1. Γ = x y + (xy) z
  2. Table de vérité :

    x y z x y xy (xy) z Γ
    000 000 0
    001 000 0
    010 010 0
    011 011 1
    100 010 0
    101 011 1
    110 100 1
    111 100 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.

  3. 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 + (xy) z

    et on peut employer au choix l'une de ces deux expressions pour calculer la retenue.

  4. δ ( 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.

  5. Dans le cas général d'un additionneur n bits, on a par récurrence :

    δ ( Sn-1 ) = 2 n , δ ( Cn ) = 2 n + 1

  6. Pi = AiBi , Gi = Ai Bi .
  7. C1 = G0 + P0 C0 .
  8. 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.

  9. C3 = G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0 .
  10. Le délai de calcul des signaux de sortie S1 , S2 , S3 est uniforme et vaut 4 ; le délai de calcul de S0 vaut 2 et celui de la retenue finale C4 vaut 3.
  11. En disposant en cascade 4 additionneurs 4-bits, le second doit "attendre" la retenue issue du premier à l'instant 3 ; le délai de calcul des signaux de sortie S5 , S6 et S7 vaut donc 6, et celui de C8 vaut 5. Et ainsi de suite : les délais augmentent de 2 avec chaque additionneur. Si n = 4 m le délai final vaut 2 m + 2, soit 10 dans le cas d'un additionneur 16-bits (ce qui est quand même beaucoup mieux que la valeur 32 trouvée en réponse à la question 5).
  12. 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

  13. Voir figure ci-dessous ; la disposition des broches et l'orientation de la figure ne sont pas les mêmes que sur les figures précédentes, désolé.
4-bits carry look-ahead generator 16-bits high-speed adder
  1. 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.