Additionneurs

L'addition est une opération très courante dans un microprocesseur. Outre dans l'unité arithmétique, elle sert pour incrémenter le compteur de programme et pour les calculs d'adresses. Il est donc important qu'elle soit optimisée pour être rapide. Malgré la simplicité apparente du problème, il existe de multiples façons de construire des additionneurs efficaces en temps et en nombre de portes logiques utilisées.

Semi-additionneur

Ce premier circuit est la brique de base. Il prend en entrée deux bits A et B et calcule la somme S et la retenue C (pour Carry en anglais). Les bits C et S peuvent aussi être vus comme les bits de poids fort et de poids faible de l'écriture sur deux bits de la somme A + B.

EntréesSorties
ABCS
0000
0101
1001
1110

On remarque sur la table de vérité que S est le ou exclusif des deux entrées A et B, i.e. S = A ⊕ B et que C vaut 1 lorsque les deux entrées valent 1, c'est-à-dire C = A ∧ B.

Schéma d'un Semi-additionneur
Schéma et symbole d'un semi-additionneur (HA)

Additionneur complet 1 bit

Pour construire un additionneur sur plusieurs bits, plusieurs additionneurs 1 bit sont mis en cascade. Chacun de ces addionneurs prend en entrée deux bits A et B ainsi que la retenue précédente C0. Il calcule la somme S de ces trois valeurs binaires ainsi que la retenue C1. Comme pour le semi-additionneur, ces bits C1 et S peuvent aussi être vus comme les bits de poids fort et de poids faible de l'écriture sur deux bits de la somme A + B + C0. Cette somme s'écrit justement sur deux bits car elle est comprise entre 0 et 3.

EntréesSorties
ABC0 C1S
00000
01001
10001
11010
00101
01110
10110
11111

On peut remarquer sur la table de vérité que S est le ou exclusif des trois entrées A, B et C0, i.e. S = A ⊕ B ⊕ C0 et que la retenue C1 vaut 1 dès que deux des trois entrées valent 1, c'est-à-dire C1 = AB ∨ AC0 ∨ BC0.

Additionneur complet
Schéma à partir des formules d'un additionneur complet

Ce circuit peut aussi être construit en assemblant deux semi-additionneurs en cascade. Le premier semi-additionneur calcule d'abord la somme de A et B puis le second calcule la somme du premier résultat et de C0. La retenue C1 vaut 1 s'il y a au moins une retenue à une des deux sommes effectuées.

Additionneur complet
Schéma et symbole d'un additionneur complet (SC)

Additionneur par propagation de retenue

L'additionneur par propagation de retenue est le plus simple. Il est calqué sur l'algorithme manuel pour effectuer l'addition. Les paires de bits sont additionnés colonne par colonne et les retenues sont propagées vers la gauche.

En mettant en cascade k additionneurs complets 1 bits, on construit un additionneur k bits appelé additionneur par propagation de retenue car la retenue se propage d'additionneur en additionneur.

L'additionneur est formé de k additionneurs 1 bit numérotés de 0 à k-1 de la droite vers la gauche. L'additionneur i reçoit en entrées les bits Ai et Bi des entrées A et B ainsi que la retenue Ci engendrée par l'additionneur i-1. Il calcule le bit Si de la somme et la retenue Ci+1 qui est transmise à l'additionneur i+1.

L'additionneur 0 reçoit une retenue C0 qui est normalement à 0 pour effectuer une addition. L'utilité de cette entrée est double. Elle permet d'une part de cascader les additionneurs pour former des additionneurs sur plus de bits. Elle permet d'autre part d'effectuer la soustraction.

Le nombre de portes logiques utilisées par un additionneur par propagation de retenue k bits est proportionnel au nombre k. Le temps de propagation de la retenue est également proportionnel au nombre k. Pour cette raison, cet additionneur est impraticable pour des nombres élevés de bits comme 16 ou 64. Il est seulement utilisé pour des petits nombres de bits, comme 4. Par contre, il peut servir de brique de base à des additionneurs plus sophistiqués comme l'additionneur hybride.

Additionneur complet
Additionneur 4 bits

Calcul des indicateurs

Dans tout micro-processeur, il existe des indicateurs ou flags qui sont des registres 1 bit pouvant prendre les valeurs 0 ou 1. Ils sont mis à jour dès qu'un chargement ou une opération logique ou arithmétique est effectuée. Ces indicateurs peuvent ensuite être testés par les branchement conditionnels.

Les principaux indicateurs utilisés sont les indicateurs N, Z, C et O décrits ci-dessous. Chacun de ces indicateurs concerne le résultat de la dernière opération effectuée (chargement, logique ou arithmétique).

Indicateur N (pour Négatif)
Il indique si le résultat est négatif. Comme les entiers sont représentés en compléments à 2, il est égal au bit de poids fort du résultat.
Indicateur Z (pour Zéro)
Il indique si le résultat est égal 0. Il est donc égal au complémentaire du ou logique (c'est-à-dire un nor) de tous les bits du résultat.
Indicateur C (pour Carry)
Il indique si l'opération a provoqué une retenue. Il est peut donc uniquement être positionné par les opérations arithmétiques. Il est mis à 1 lorsqu'il y a une retenue. Ceci correspond à un débordement pour une addition de nombres non signés.
Indicateur O (pour Overflow)
Il indique un débordement lors d'une addition de nombres signés. Ce débordement intervient lorsque la somme de deux nombres positifs est supérieure à 2k-1 ou lorsque la somme de deux nombres négatifs est inférieure à -2k-1-1. Cet indicateur est égal au ou exclusif Ck ⊕ Ck-1 des deux dernières retenues.

Calcul des indicateurs
Calcul des indicateurs

Additionneur par anticipation de retenue

La lenteur de l'additionneur par propagation de retenue impose d'utiliser d'autres techniques pour des additionneurs ayant un nombre important de bits. Comme cette lenteur est due au temps nécessaire à la propagation de la retenue, toutes les techniques ont pour but d'accélérer le calcul des retenues. La première technique appelée anticipation de retenue consiste à faire calculer les retenues par un circuit extérieur.

Afin de faciliter le calcul des retenues, on introduit deux quantités appelées G (pour Generate en anglais) et P (pour Propagate en anglais). Pour deux quantités binaires A et B, les quantités G et P sont définies de la façon suivante.

G = AB et P = A + B

Soient A = An-1…A0 et B = Bn-1…B0 deux entrées de n bits. On note Ci la retenue de l'addition des i bits de poids faible de A et B. Pour accélérer le calcul des Ci, on introduit les deux quantités Gi et Pi associées aux entrées Ai et Bi par les formules suivantes.

Gi = AiBi et Pi = Ai + Bi

La valeur Gi est la retenue engendrée par l'addition des deux bits Ai et Bi et la valeur de Pi détermine si la retenue de Ci se propage. On a donc la formule suivante qui exprime simplement que la retenue Ci+1 provient soit directement de l'addition des bits Ai et Bi soit de la propagation de la retenue Ci.

Ci+1 = Gi + PiCi

En utilisant plusieurs fois cette formule, on peut obtenir les formules suivantes qui expriment Ci+1 en fonction d'une retenue précédente et des valeurs Gj et Pj intermédiaires.

Ci+1 = Gi + PiGi-1 + PiPi-1Ci-1
Ci+1 = Gi + PiGi-1 + PiPi-1Gi-2 + PiPi-1Pi-2Ci-2

Le circuit suivant permet de calculer la somme ainsi que les deux quantités Gi et Pi.

Cellule de calcul de S, G et P
Cellule de calcul de S, G et P.

Calcul anticipé des retenues

En utilisant les formules ci-dessus, on obtient les formules suivantes pour les retenues C1, C2, C3, et C4 à partir de C0 et des signaux G0, P0, G1, P1, G2, P2 G3 et P3.

C1 = G0 + P0C0
C2 = G1 + P1G0 + P1P0C0
C3 = G2 + P2G1 + P2P1G0 + P2P1P0C0
C4 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C0

Comme la retenue C4 n'est pas nécessaire pour calculer les sommes S0, S1, S2 et S3, celle-ci peut-être calculée en utilisant la formule suivante.

C4 = G3 + P3C3

L'utilisation de cette dernière formule ne retarde pas les calculs des sommes et économise des portes.

Circuit de calcul des retenues
Circuit de calcul des retenues

Additionneur 4 bits avec calcul anticipé des retenues

Additionneur 4 bits
Additionneur 4 bits avec calcul anticipé des retenues

Additionneur 16 bits avec calcul anticipé des retenues

Plus généralement, on note pour deux indices i et j, Gj,i et Pj,i la retenue engendrée par l'addition des bits de i à j et la possibilité qu'une retenue se propage à travers les bits de i à j. On a donc la formule suivante qui exprime la retenue Cj+1 en fonction de Gj,i, Pj,i et Ci.

Cj+1 = Gj,i + Pj,iCi

Circuit de calcul des retenues
Circuit de calcul des retenues et de G et P

Additionneur 16 bits
Additionneur 16 bits avec calcul anticipé des retenues

Additionneur 64 bits avec calcul anticipé des retenues

Additionneur 64 bits
Additionneur 64 bits avec calcul anticipé des retenues

Additionneur récursif

On commence par définir une opération binaire sur les paires (G,P). Cette opération notée ∗ prend en paramètre deux paires (G, P) et (G', P') de valeurs binaires et retourne une nouvelle paire (G'', P'') = (G, P) ∗ (G', P') définie par les formules suivantes.

G'' = G + PG' et P'' = PP'

Cette opération n'est pas commutative mais elle est associative. Les deux calculs de ((G, P) ∗ (G', P')) ∗ (G'', P'') ou de (G, P) ∗ ((G', P') ∗ (G'', P'')) donnent en effet la paire suivante. Il s'agit pour les connaisseurs d'un produit semi-direct.

(G+PG'+PP'G'', PP'P'')

Cette opération ∗ permet des calculs rapides de toutes les valeurs G et P en utilisant les formules ci-dessous.

Pour i = k, on a Gi,i = Gi et Pi,i = Pi. Pour i ≤ j ≤ k, on a la formule suivante qui permet de calculer récursivement toutes les valeurs Gk,i et Pk,i.

(Gk,i, Pk,i) = (Gk,j+1, Pk,j+1) ∗ (Gj,i, Pj,i).

Le circuit GP ci-dessous calcule l'opération ∗. Il prend en entrée deux paires (Gk,j+1, Pk,j+1) et (Gj,i, Pj,i) et calcule la paire (Gk,i, Pk,i) en utilisant la formule ci-dessus.

Cellule de calcul de G et P
Cellule de calcul des Gk,i et Pk,i

Le circuit GP peut être utilisé pour former un arbre de calcul des valeurs Gk,i et Pk,i. Cet arbre ne calcule pas toutes les valeurs Gk,i et Pk,i mais seulement celles nécessaires au calcul des retenues.

Arbre de calcul de G et P
Arbre de calcul des Gk,i et Pk,i

Le circuit GP peut être étendu en un circuit GPC qui effectue en outre le calcul de la retenue en utilisant la formule suivante déjà donnée ci-dessus.

Cj+1 = Gj,i + Pj,iCi.

Le circuit GPC prend donc entrée deux paires (Gk,j+1, Pk,j+1) et (Gj,i, Pj,i) et une retenue Ci et calcule la paire (Gk,i, Pk,i) et la retenue Cj+1.

Schéma cellule de calcul de G et P
Cellule de calcul des Gk,i, Pk,i et Cj

Si on remplace les circuit GP par des circuits GPC dans l'arbre de calcul ci-dessus, on obtient un circuit qui calcule en outre les retenues.

Schéma additionneur par anticipation de retenue
Additionneur récursif 8 bits

Pour un circuit travaillant sur des entrées de k bits, la profondeur de l'arbre est égale à log k. Le nombre de portes du circuit est donc de l'ordre de k. Le temps de calcul des retenues est proportionnel à log k. Les signaux G et P doivent descendre jusqu'à la racine de l'arbre puis les calculs de retenues doivent remonter jusqu'aux feuilles.

Additionneur hybride

L'idée générale d'un additionneur hybride est de combiner des techniques différentes de calcul de retenues pour construire un gros additionneur. Une première technique comme la propagation de la retenue peut être utilisée pour construire des petits additionneurs qui sont ensuite regroupés en utilisant une autre technique comme le calcul anticipé de la retenue. On construit ci-dessous un additionneur 16 bits en combinant 4 additionneurs 4 bits par propagation de retenue. Ces 4 additionneurs 4 bits sont assemblés autour d'un circuit d'anticipation de retenue qui calcule leurs 4 retenues d'entrée.

Afin de pouvoir utiliser un circuit d'anticipation de retenue, il faut disposer d'un circuit calculant les valeurs G et P associées à chacun des blocs de 4 bits. Ce circuit GP prend en entrée les 8 valeurs G0, G1, G2, G3, P0, P1, P2, et P3 associées aux 4 paires de bits et produit les valeurs G3,0 et P3,0 du bloc de 4 bits.

On construit 4 additionneurs par propagation de retenue qui calculent également les valeurs G0, G1, G2, G3, P0, P1, P2, et P3 associées aux 4 paires de bits.

Schéma additionneur 4 bits
Additionneur 4 bits et calcul de G et P

Les quatre additionneurs par propagation de retenue 4 bits 4SGP sont combinés au circuit d'anticipation de retenue 4C par l'intermédiaire des circuits GP de calcul des valeurs G et P des blocs. Le circuit global obtenu est un additionneur hybride 16 bits.

Schéma additionneur hybride
Additionneur hybride 16 bits

Additionneur par sélection de retenue

L'idée générale de l'additionneur par sélection de retenue est d'effectuer en parallèle le calcul avec une retenue de 0 et le calcul avec une retenue de 1 puis de sélectionner le bon résultat lorsque la retenue est enfin connue.

Schéma additionneur par sélection de retenue
Additionneur par sélection de retenue 16 bits

Soustracteur

Pour calculer la différence A - B de deux nombre signés A et B, on utilise un circuit qui calcule d'abord l'opposé -B de B puis effectue la somme de A avec -B grâce à un additionneur. Le calcul de -B est réalisé en prenant la négation de B bit à bit puis en ajoutant 1 au résultat obtenu. Ce dernier 1 est en fait ajouté directement à la somme de A et -B en l'injectant comme retenue C0 à l'additionneur.

Le circuit ci-dessous effectue une somme ou une différence suivant la valeur de la commande Cmd. Si Cmd vaut 0, le circuit calcule la somme A + B. Si, au contraire, Cmd vaut 1, le circuit calcule la différence A - B. En effet, chacune des portes xor effectue la négation ou non d'une entrée Bi suivant la valeur de Cmd.

La différence est ici calculée avec un simple additionneur par propagation de retenue mais tout autre additionneur plus sophistiqué aurait pu aussi être utilisé.

Schéma soustracteur 4 bits
Soustracteur 4 bits