Français
Menu

Additionneur à propagation de retenue vs additionneur à retenue anticipée vs additionneur à retenue conservée : délai, surface et usages

Ces trois additionneurs sont construits à partir d’additionneurs complets, mais ils traitent les retenues différemment. Un additionneur à propagation de retenue enchaîne des additionneurs complets, si bien que la retenue passe tour à tour du bit de poids faible au bit de poids fort, et le délai croît proportionnellement à la largeur n (O(n)). Un additionneur à retenue anticipée calcule toutes les retenues en parallèle à partir des signaux de génération et de propagation de chaque bit, et avec une anticipation hiérarchique le délai ne croît qu’en O(log n). Un additionneur à retenue conservée réduit trois nombres à deux, un mot de somme et un mot de retenue, sans propager les retenues : son délai est celui d’un seul additionneur complet, quelle que soit la largeur. Les multiplieurs réduisent les produits partiels avec des arbres d’additionneurs à retenue conservée (comme les arbres de Wallace) et additionnent les deux derniers nombres avec un additionneur rapide.

CritèreAdditionneur à propagation de retenue (ripple-carry)Additionneur à retenue anticipée (carry-lookahead)Additionneur à retenue conservée (carry-save)
Entrées et sortiesAdditionne deux nombres (et une retenue entrante) pour donner une somme et une retenue sortanteAdditionne deux nombres (et une retenue entrante) pour donner une somme et une retenue sortanteRéduit trois nombres à deux, un mot de somme S et un mot de retenue Cy (A + B + C = S + Cy)
Traitement de la retenueChaque additionneur complet attend la retenue du bit inférieur et la transmet tour à tour vers le hautUtilise la génération g = a·b et la propagation p = a ⊕ b et développe c(i+1) = g(i) + p(i)·c(i) pour calculer les retenues en parallèleLes retenues ne passent pas au bit voisin ; elles vont à l’étage suivant sous forme d’un mot décalé d’un bit vers la gauche
Croissance du délaiO(n) ; dans le pire cas, la retenue va du bit de poids faible jusqu’au bit de poids fortO(log n) (avec une anticipation hiérarchique)O(1) ; le délai d’un additionneur complet, quelle que soit la largeur
Chiffres pour 64 bitsLa retenue traverse 64 additionneurs completsTrois niveaux de blocs de 4 bits ; dans un additionneur à préfixe parallèle de Kogge-Stone, le calcul des retenues prend log₂64 = 6 étagesUn étage correspond au délai d’un additionneur complet ; un arbre de Wallace qui réduit 64 produits partiels à deux demande 10 étages
SurfaceLa plus petite : n additionneurs complets pour n bitsPlus grande à cause de la logique d’anticipation ; les versions plus rapides utilisent plus de portes et de câblage (environ n log n pour Kogge-Stone)Un étage compte n additionneurs complets sans chaîne de retenue ; l’arbre complet d’un multiplieur croît avec le nombre de bits des produits partiels (environ n²)
Format du résultatBinaire ordinaireBinaire ordinaireForme redondante, répartie entre un mot de somme et un mot de retenue ; un additionneur ordinaire est nécessaire à la fin pour obtenir une seule valeur
Usages typiquesPetits circuits ou circuits basse consommation où la vitesse n’est pas critique ; dans les FPGA, souvent construit sur une logique de chaîne de retenue dédiéeALU des CPU, calcul d’adresses, unités à virgule flottante, addition finale dans les multiplieursRéduction des produits partiels dans les multiplieurs (arbres de Wallace et de Dadda), accumulation dans les unités de multiplication-accumulation, addition de nombreux nombres
Architectures apparentéesAdditionneurs à saut de retenue et à sélection de retenue (intermédiaires en vitesse et en surface)Additionneurs à préfixe parallèle (Kogge-Stone, Brent-Kung et autres)Compresseurs 4:2, combinaison avec l’algorithme de Booth pour réduire les produits partiels

Les valeurs indiquées sont des ordres de grandeur typiques et varient selon la génération de procédé et le produit.

Quand choisir l'un ou l'autre ?

Additionneur à propagation de retenue
Pour les faibles largeurs, ou quand la surface et la consommation comptent plus que la vitesse. Sa structure simple et régulière s’implante efficacement sur les composants dotés de chemins de retenue rapides dédiés, comme les FPGA.
Additionneur à retenue anticipée
Quand une addition à deux opérandes doit se terminer rapidement, comme dans les ALU des CPU et les additionneurs du chemin critique. La hiérarchie et le choix de la structure à préfixe parallèle arbitrent entre nombre d’étages, surface et câblage.
Additionneur à retenue conservée
Pour additionner trois nombres ou plus. Il réduit leur nombre sans attendre les retenues et effectue une seule addition finale avec un additionneur à retenue anticipée ou similaire : il est donc rentable dans les multiplieurs qui additionnent de nombreux produits partiels et dans les unités MAC qui accumulent de façon répétée.

Questions fréquentes

Quelle est en pratique la différence entre O(n) et O(log n) ?

Sur 64 bits, la retenue d’un additionneur à propagation de retenue traverse 64 additionneurs complets, tandis qu’un additionneur à préfixe parallèle de Kogge-Stone calcule les retenues en log₂64 = 6 étages. Le délai par étage diffère selon les circuits, ce n’est donc pas un simple rapport, mais l’écart se creuse quand la largeur augmente, et un additionneur à propagation de retenue est trop lent pour une addition sur 64 bits dans un processeur de la classe du GHz.

Comment vérifier un additionneur à retenue conservée avec des nombres ?

Entrez les valeurs sur 4 bits 5 (0101), 6 (0110) et 7 (0111). Le mot S formé de la somme de chaque bit vaut 0100 (4), et le mot Cy formé de la retenue de chaque bit, décalé d’un bit vers la gauche, vaut 1110 (14). 4 + 14 = 18, soit 5 + 6 + 7. Chaque bit est un additionneur complet indépendant : rien n’attend de retenue.

Comment détermine-t-on le nombre d’étages d’un arbre de Wallace ?

Chaque étage d’additionneurs à retenue conservée transforme trois nombres en deux : leur nombre diminue donc d’environ un tiers par étage. Avec h produits partiels, un étage en laisse 2⌊h/3⌋ + (h mod 3) ; il faut 4 étages pour 8, 6 pour 16, 8 pour 32 et 10 pour 64 pour arriver à deux. Le nombre d’étages croît à peu près comme le logarithme de la largeur, et l’addition des deux derniers nombres par un additionneur rapide termine le produit.

Pourquoi n’utilise-t-on pas directement l’équation d’anticipation complète pour les additionneurs larges ?

Développer complètement les équations de retenue ajoute des termes à chaque bit de rang supérieur et exige vite des portes à trop d’entrées. On forme plutôt des groupes d’environ 4 bits qui produisent une génération de groupe G et une propagation de groupe P, et le niveau suivant applique la même logique d’anticipation à ces signaux. Les additionneurs à préfixe parallèle généralisent cette idée.

Vérifier vos connaissances

Quel est l'inconvénient de l'additionneur à propagation de retenue (ripple carry), qui enchaîne des additionneurs complets en série ?

  1. AIl ne peut pas traiter les nombres négatifs
  2. BLa retenue se propageant successivement depuis les rangs inférieurs, le délai augmente proportionnellement au nombre de bits
  3. CLa taille du circuit ne change pas quand le nombre de bits augmente
Afficher la réponse et l'explication

Réponse : B. La retenue se propageant successivement depuis les rangs inférieurs, le délai augmente proportionnellement au nombre de bits

Dans un additionneur à propagation de retenue, chaque additionneur complet attend la retenue du rang inférieur pour calculer ; la retenue se propage du bit de poids faible au bit de poids fort, et le délai croît proportionnellement au nombre de bits. Sur 64 bits, le délai équivaut à 64 étages d'additionneurs complets, trop lent pour un CPU fonctionnant à plusieurs GHz. Petit et simple, il est utilisé lorsque la vitesse n'importe pas. Pour accélérer, on utilise des additionneurs à anticipation de retenue, à sélection de retenue ou à préfixe parallèle (Kogge-Stone, etc.).

Pourquoi l'additionneur à anticipation de retenue (carry lookahead) est-il rapide ?

  1. AParce qu'il réduit le nombre de bits de l'addition
  2. BParce qu'il double la fréquence d'horloge
  3. CParce qu'il calcule la retenue de chaque bit en parallèle à partir des entrées, sans attendre sa propagation depuis les rangs inférieurs
Afficher la réponse et l'explication

Réponse : C. Parce qu'il calcule la retenue de chaque bit en parallèle à partir des entrées, sans attendre sa propagation depuis les rangs inférieurs

L'additionneur à anticipation de retenue utilise pour chaque bit la génération G = A·B (produit toujours une retenue) et la propagation P = A⊕B (laisse passer la retenue inférieure), et calcule les retenues de chaque rang en parallèle à partir des entrées : C1 = G0 + P0·C0, C2 = G1 + P1·G0 + P1·P0·C0, etc. Le délai ne croît plus qu'avec le logarithme du nombre de bits. Les expressions s'allongeant toutefois, on combine hiérarchiquement des blocs d'environ 4 bits.

Dans un additionneur à anticipation de retenue, quelle combinaison des définitions du signal de génération g et du signal de propagation p de chaque rang (a, b étant les entrées du rang) et de l'expression de la retenue vers le rang supérieur c(i+1) est correcte ?

  1. Ag = a + b, p = a·b, c(i+1) = p + g·c(i)
  2. Bg = a·b, p = a ⊕ b, c(i+1) = g + p·c(i)
  3. Cg = a ⊕ b, p = a·b, c(i+1) = g·p·c(i)
Afficher la réponse et l'explication

Réponse : B. g = a·b, p = a ⊕ b, c(i+1) = g + p·c(i)

Si a et b valent tous deux 1 dans un rang, une retenue est générée quelle que soit la retenue entrante : le signal de génération est g = a·b. Si un seul des deux vaut 1, la retenue entrante est transmise telle quelle vers le haut : le signal de propagation est p = a ⊕ b (parfois défini comme un OR). On a donc c(i+1) = g(i) + p(i)·c(i) ; en développant, la retenue de chaque rang s'obtient en parallèle, en deux niveaux logiques, à partir des seuls g·p et de la retenue du rang de poids faible. Les expressions inversant génération et propagation ne calculent pas correctement.

  1. Quelle est la principale raison de l'emploi d'additionneurs à retenue conservée pour additionner les nombreux produits partiels d'un multiplieur ?
  2. Quelle caractéristique de l'arbre de Wallace utilisé dans les multiplieurs rapides est correcte ?
  3. Quelle combinaison correspond aux entrées d'un additionneur complet ?

Questions d'entraînement sur Arithmétique des ordinateurs

Termes clés expliqués

Additionneur complet
Circuit qui additionne trois entrées (deux bits et la retenue du rang inférieur) et fournit la somme et la retenue vers le rang supérieur. Sans entrée de retenue, c'est un demi-additionneur. Mis en série, il forme un additionneur multibit.
Additionneur à retenue anticipée
Additionneur qui calcule les retenues en parallèle à partir des signaux de génération g = a·b et de propagation p = a ⊕ b de chaque rang, sans attendre leur propagation depuis les rangs inférieurs. Le délai reste faible même pour de nombreux bits. Aussi appelé additionneur carry-lookahead.
Additionneur à retenue conservée (carry-save)
Additionneur qui réduit trois nombres en deux, une « somme » et une « retenue », sans propager la retenue. Constitué simplement d'additionneurs complets juxtaposés, son délai est constant ; il sert dans les multiplieurs à additionner de nombreux produits partiels.
Arbre de Wallace
Architecture de multiplieur qui réduit en parallèle de nombreux produits partiels à l'aide d'un arbre d'additionneurs à retenue conservée. Le nombre d'étages est de l'ordre du logarithme du nombre de bits ; utilisé dans les multiplieurs rapides. Les deux derniers nombres sont additionnés par un additionneur classique.
Algorithme de Booth
Méthode de multiplication qui découpe les bits du multiplicateur par groupes (de 2 bits, etc.) et les remplace par des chiffres signés pour réduire le nombre de produits partiels. En Booth de base 4, ceux-ci sont presque divisés par deux.
Chemin critique
Chemin présentant le plus grand retard d'un circuit, qui fixe la fréquence d'horloge maximale. En STA, c'est le chemin au plus petit slack, et accélérer une conception commence par réduire son retard.

Comparatifs associés