Mise en oeuvre de l'additionneur à anticipation de retenue

Un moyen d'implanter l'additionneur obtenu est de réaliser un circuit calculant la propagation et la génération de retenue pour un étage en fonction de la propagation et la génération des étages précédents.

Il y a propagation à l'étage j si dans les étages i à j il y a toujours eu propagation :

$$P_{j,i} = p_j \wedge p_{j-1} \ldots p_{i+1} \wedge p_i$$

Il y a génération à l'étage j si c'est l'étage j lui même qui génère, ou si les étages d'avant ont tous généré et propagé :

$$G_{j,i} = g_j \vee p_j \wedge g_{j-1} \vee p_j \wedge p_{j-1}... ...} \vee \ldots \vee p_j \wedge p_{j-1} \ldots p_{i+1} \wedge g_i$$

Donc la retenue à l'étage j peut s'exprimer en fonction de la retenue à l'étage i, i<j :

$$r_{j+1}= G_{j,i} \vee P_{j,i} \wedge r_i$$

Utilisons un circuit pouvant générer les signaux P_1,0, G_1,0 et les retenues r₁, r₂ en fonction des couples (p₀, g₀), (p₁, g₁) et de la retenue entrante r₀.

Pour un tel circuit :

$$G_{1,0} = g_1 \vee p_1 \wedge g_0$$

$$P_{1,0} = p_1 \wedge p_0$$

$$r_1 = g_0 \vee p_0 \wedge r_0$$

Supposons qu'un additionneur un bit nous calcule aussi la propagation et la génération. Il est possible d'organiser un générateur de retenue en arbre, qui permet d'anticiper chaque retenue avant d'additionner.

 

! Un additionneur à anticipation de retenue sur n bits fonctionne en log(n) étapes pour le calcul des n retenues + 1 étape pour l'addition finale.

? Faire fonctionner cet additionneur sur 00101011 + 10110111