Cette page prolonge la description de la fin du Chapitre 15.
Dans le chapitre 14, nous avons étudié la réalisation d’un circuit additionneur à partir de portes logiques. Dans le chapitre 15, nous avons vu en quoi l’additionneur est devenu un des constituants essentiels des ordinateurs dès les années 1930, et comment sa construction a profité des progrès technologiques permettant de produire des portes logiques à partir de tubes, puis de transistors, puis de circuits intégrés.
Quelle que soit la technologie, une porte logique se caractérise par un délai de propagation prédéfini. C’est le temps nécessaire pour qu’un changement d’état en entrée soit répercuté sur la sortie. Si des portes sont connectées en cascade (logique séquentielle), les délais s’additionnent.
Nous avons vu que l’additionneur à la fin du chapitre 14 utilisait des additionneurs 1 bit en cascade. Chacun peut générer une retenue Carry dont l’étage suivant a besoin. C’est une retenue propagée (ripple carry). La vitesse de calcul d’un additionneur à retenue propagée (ARP) est la somme des délais de ses étages.
La fin du chapitre 15 présente un générateur de retenue anticipée (look-ahead carry generator). On parle aussi d’additionneur à retenue anticipée (ARA) ou d’additionneur rapide (voyez aussi la page Additionneur sur Wikipedia). Ce circuit permet de calculer plus vite en évaluant la retenue autrement.
Un circuit logique peut a priori fonctionner plus vite s’il utilise moins de portes dans une recherche d’efficacité. Néanmoins, il arrive que pour rendre le circuit plus rapide, il faille ajouter et non enlever des portes logiques. C’est le cas de ce générateur de retenue anticipée. Les portes ajoutées se chargent de gérer plus vite les bits de retenue Carry.
L’additionneur suivant est bâti à partir de deux demi-additionneurs qui utilisent chacun une porte OU exclusif (XOR) pour calculer la somme SUM et une porte ET pour la retenue CO (Carry Out).
Comme dans tous les autres schémas, vous cliquez dans un bouton carré pour inverser l’état logique des entrées A et B à gauche et de l’entrée de retenue CI en haut (Carry In).
Cette version du circuit détaille le trio de portes logiques NAND, OR et AND qui constitue chacune des deux portes XOR.
Ce circuit reste proche de l’additionneur complet 1 bit du chapitre 14. Les positions des portes OR et NAND dans la porte XOR ont été échangées de sorte que la porte NAND est au-dessus de l’autre, mais cela n’a aucun impact sur le fonctionnement. C’est une simple retouche cosmétique destinée à rendre la prochaine évolution du circuit plus lisible.
Les huit combinaisons possibles des états des deux entrées A et B et de l’entrée de retenue CI (Carry In) sont listées dans le tableau suivant. Le résultat de l’addition correspond à Sum et la sortie de retenue à CO (Carry Out).
| Entrée | Sortie | |||
|---|---|---|---|---|
| A | B | CI | Sum | CO |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Pour concevoir un additionneur à retenue anticipée (look-ahead carry), nous devons d’abord découvrir dans quelles conditions le bit de sortie de retenue CO passe dans l’état 1.
On dit que la retenue CO est générée lorsque son état découle de celui des deux entrées A et B. Dans le cas d’une addition, CO passe à 1 seulement si A et B sont toutes deux à 1.
On dit que la retenue CO est propagée lorsque son état découle de l’état à 1 de l’entrée de retenue CI en combinaison avec les deux entrées A et B. Le tableau suivant détaille les cinq cas de changement d’état de CO, deux cas de génération et trois de propagation.
| Entrée | Sortie | Type de retenue | ||||
|---|---|---|---|---|---|---|
| A | B | CI | Sum | CO | Générée | Propagée |
| 0 | 0 | 0 | 0 | 0 | ||
| 0 | 1 | 0 | 1 | 0 | ||
| 1 | 0 | 0 | 1 | 0 | ||
| 1 | 1 | 0 | 0 | 1 | ✓ | |
| 0 | 0 | 1 | 1 | 0 | ||
| 0 | 1 | 1 | 0 | 1 | ✓ | |
| 1 | 0 | 1 | 0 | 1 | ✓ | |
| 1 | 1 | 1 | 1 | 1 | ✓ | ✓ |
Choisissons deux lettres pour symboliser la nature de la retenue : G pour Générée et P pour Propagée.
G vaut 1 si les deux A et B valent 1. Cela indique que l’état 1 de CO a été généré.
P vaut 1 si soit A soit B vaut 1.
Une valeur 1 pour P ne suffit pas pour conclure que le bit de retenue a été propagé; (en toute logique) il faut aussi que l’entrée de retenue CI soit à 1.
La colonne de droite du tableau suivant montre comment le bit de sortie de retenue CO est calculé à partir de G, de P et de l’entrée de retenue CI.
| Entrée | Sortie | Calcul de retenue | |||||
|---|---|---|---|---|---|---|---|
| A | B | CI | Sum | CO | G = A AND B | P = A OR B | CO = G OR (P AND CI) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Remarquons que cet additionneur 1 bit ne calcule pas le bit de retenue CO exactement comme le prétend la dernière colonne du tableau. Le circuit peut être retouché pour qu’il le fasse.
Il est intéressant de noter que ce circuit est un peu plus rapide que le précédent. La sortie de retenue CO est évaluée par une séquence de trois portes (en bas de circuit) au lieu des quatre portes du circuit précédent. Un certain progrès !
Supposons quatre additionneurs 1 bit devant servir à des additions de deux nombres binaires sur 4 bits. Chacune des quatre étapes d’addition est désignée par un indice, 0 pour le bit de poids faible (LSB), puis 1, 2 et enfin 3 pour le bit de poids fort (MSB).
Pour chacun des quatre additionneurs 1 bit, le bit de sortie de retenue CO peut être déterminé au moyen de la formule montrée en tête de colonne dans le tableau précédent.
Le bit de sortie de retenue CO de chaque étage est le bit d’entrée de retenue CI de l’étage suivant. Les bits d’entrée CI peuvent donc être trouvés ainsi:
Vous aurez remarqué que la formule de CI2 se termine par CI1, alors que la formule de la première ligne montre que CI1 est le fruit de la combinaison de G0, P0 et CI0. Nous pouvons de ce fait récrire la deuxième formule ainsi:
La formule ne mentionne plus CI1, ce qui signifie que CI2 peut être connu sans l’aide du bit de retenue précédent.
Les formules devenant touffues, nous allons tirer profit d’une notation plus concise que les termes OR et AND. La notation algébrique propose le signe + pour le OU logique et le point médian · pour le ET logique (Alt-0183 sous Windows). Chacun des bits d’entrée de retenue CI équivaut à une combinaison des états G et P et de l’entrée CI0. Pour une addition sur quatre bits, CI0 est normalement forcé à 0, mais optons pour une approche plus générique:
Le même raisonnement s’applique pour plus de quatre bits.
Le circuit suivant est double : il réunit deux additionneurs 4 bits. Celui du haut est de type ARP, à retenue propagée (ripple carry). Celui du bas est de type ARA, à retenue anticipée (look-ahead carry). Les quatre formules que nous venons de voir pour déduire par anticipation les bits d’entrée de retenue CI du circuit ARA sont incarnées par des portes OR et AND en bas de schéma.
Les deux rangées de quatre boutons de basculement d’état en haut servent à déterminer les deux nombres sur 4 bits à additionner. Le bit de poids faible est sur la droite et celui de poids fort à gauche (comme lorsque vous écrivez une valeur). Vous disposez bien sûr d’un basculeur pour l’état de l’entrée de retenue CI à droite.
La somme résultante est signifiée par deux rangées d’afficheurs binaires. La première rangée correspond au circuit ARP du haut, et l’autre au circuit ARA du bas. Les deux afficheurs tout à fait à gauche sont ceux du bit de sortie de retenue Carry de chacun des deux circuits.
La simulation des circuits a été paramétrée pour un délai de propagation unitaire de porte égal à 250 millisecondes soit 1/4 s. Cette lenteur relative permet de juger de l’écart de performances entre les deux approches ARA et ARP.
Pour bien voir cet écart, donnez la valeur 1 aux quatre bits des entrées A (la première rangée à 1111) puis armez l’entrée de retenue à droite CI. Vous verrez que le circuit ARA est bien plus rapide.
La partie supérieure, au-dessus des afficheurs de sortie, est celle de la variante à propagation ARP. Le circuit est le même que celui de l’additionneur 1 bit vu plus haut. La sortie de retenue CO d’un étage est injectée comme entrée de retenue CI de l’étage suivant.
Les quatre portes tout en haut sous les rangées de basculeurs sont communes aux deux variantes. Elles se chargent de trouver la somme des bits, et produisent également les deux signaux G et P indispensables au circuit ARA du bas. Les trois signaux Sum, G et P sont acheminés par les liaisons verticales à gauche des afficheurs de sortie.
Les trois petites portes sous les afficheurs du bas servent à injecter le bit de retenue Carry à la somme. Pour tous les bits sauf le premier à droite, cette retenue est calculée par le groupe de portes OR et AND en bas.