Additionneurs spéciaux


Additionneurs spéciaux

Certains algorithmes arithmétiques peuvent être réalisées en modifiant un additionneur. Par exemple :

  • si A + B < 2n alors S = A + B sinon S = A + B 2n ; // somme modulo 2n
  • si A + B < 2n alors S = A + B sinon S = 2n 1 ; // additionneur à saturation
  • si a/s alors S = A B sinon S = A + B ; // additionneur/soustracteur/comparateur
  • si A > B alors S = A sinon S = B ; // plus grand de A et B
  • S = A + B ; S' = A + B + 1 ; // additionneur à 2 sorties S et S'
  • S = A + B ; S' = A + B + 1 ; S" = A + B + 2 ; // additionneur à 3 sorties
  • si A B ³ 0 alors S = A B sinon S = B A ; // valeur absolue de la différence
  • si A + B < 2n 1 alors S = A + B sinon S = A + B 2n + 1 ; // modulo 2n 1
  • si A + B < 2n + 1 alors S = A + B sinon S = A + B 2n 1 ; // modulo 2n + 1

Le coût et le délai du nouvel opérateur restent proches de ceux d'un additionneur.

Additionneur rapide

Les additionneurs spéciaux de cette page sont construits autour de l'additionneur rapide de Sklansky, qui est rappelé ici pour faciliter la comparaison.
  La sortie des cellules "BK" vaut en général 'P', 'G' ou 'K' (2 bits) cependant les entrées ci des portes "XOR" valent '0' ou '1' (1 bit), 'K' donne '0', 'G' donne '1' et 'P' est impossible car dans cet additionneur la cellule "HA" la plus à droite est modifiée pour exclure la valeur 'P' pour c1.
Les "additionneurs spéciaux" qui suivent dépendent de la façon dont on traite le 'P' .

Addition avec saturation

Si on néglige la retenue sortante cn alors un additionner donne A + B 2n lorsque A + B est trop grand. Pour conserver la continuité de la sortie S et minimiser son erreur moyenne, on préfère parfois à l'addition modulo 2n l'addition avec saturation à la plus grande valeur que l'on peut écrire sur n bits : S = min ( A + B , 2n 1) .

Additionneur/ soustracteur

Les additionneurs exécutent spontanément des additions modulo 2n si on néglige la retenue sortante cn dans la somme S. Pour obtenir l'opposé -B d'un nombre B, on complémente logiquement chacun de ses bits puis on lui ajoute 1. L'addition de B et du -B obtenu ainsi donne 2n c'est à dire 0.
On se sert de la retenue entrante c0 d'un additionneur pour ajouter le signal "a/s" et de portes "XOR" pour complémenter chaque bits bi de B. Cette "boîte à opérations" effectue l'addition si la commande "a/s" = '0' et la soustraction si a./s = '1'.
Un additionneur/soustracteur traite des entiers signés.

Débordement de l'addition/ soustraction d'entiers signés

Si les valeurs de la retenue cn et de la retenue cn-1 diffèrent, il y a un débordement et la somme S est arithmétiquement fausse:

  • '0' '1' : il faut ajouter 2n à la somme S pour la corriger (débordement négatif)
  • '1' '0' : il faut soustraire 2n à la somme S pour la corriger (débordement positif)

Addition/ soustraction avec saturation

Comme pour l'addition avec saturation, les deux retenues cn et cn-1 permettent de choisir le plus grand nombre positif représentable ou le plus petit nombre négatif représentable en cas de débordement. S = min ( max ( A ± B , -2n-1) , 2n-1 1) .

Additionneur/ soustracteur/ comparateur

Lorsqu'on effectue une soustraction S = A B, le signe de S indique A ³ B ou au contraire A < B, mais ne peut indiquer l'égalité. Si pour une soustraction on donne à c0 la valeur 'P', la valeur 'P' de la retenue sortante cn ne peut qu'avoir été propagée sur toutes les positions et indique donc A = B, 'K' indique A < B et 'G' indique A > B. Aux entrées des portes "XOR", 'K' donne '0', 'P' ou 'G' donnent '1' , cette transformation est représentée par un petit carré.

Plus grand de A ou de B
"S = max(A,B)"

Pour comparer deux nombres A et B, il n'est pas nécessaire de calculer complètement leur différence A B. Le signe de la différence, qui est donné par la retenue sortante cn, suffit. Ce comparateur est plus simple (moins de cellules "BK") et plus rapide (moins de sortance) qu'un soustracteur.

Additionneur à retenue entrante retardée

Si la retenue entrante c0 d'un additionneur S = A + B + c0 est prête plus tard que les entrées A et B, un additionneur à retenue entrante retardée est adéquat. Le délai entre l'entrée c0 et les sorties si est petit et indépendant du nombre de bits.
  Si la retenue entrante c0 arrivait en même temps que les entrées A et B, un arbre de cellules "BK" semblable à cellui de l'additionneur/soustracteur serait plus indiquée car moins coûteux en cellules "BK".

Additionneur à deux sorties
A+B et A+B+1

Pour obtenir cet additionneur, on duplique les portes "XOR" de l'additionneur à retenue entrante retardée S = A + B + c0 . Puis pour la sortie S on substitue à c0 la valeur '0' et pour l'autre sortie S' on substitue à c0 la valeur '1'. On construit ainsi un additionneur calculant simultanément S = A + B et S' = A + B + 1 .
 

La sortie des cellules "BK" vaut 'P', 'G' ou 'K' (2 bits) 'K' donne '0', 'G' donne '1' .

  • Pour le calcul de S = A + B, 'P' donne '0' .
  • Pour le calcul de S' = A + B + 1, 'P' donne '1'.

Autrement dit 'K' donne '0' '0', 'P' donne '0' '1', et 'G' donne '1' '1' , cette transformation des ci est représentée par un petit carré .

Additionneur à trois sorties

On veut calculer S = A + B, S' = A + B + 1, S" = A + B + 2. Pour calculer S et S" on calcule préalablement sans propagation de retenue deux nombres X et Y tels que X + Y = A + B et X pair. On obtient ainsi s0 et s"0 qui ont la même valeur y0. Ensuite on additionne les n-1 bits poids forts de X et Y avec l'additionneur à deux sorties précédent.
 

Où est la troisième sortie S' = A + B + 1 ? Le calcul de S' à partir de S et S", soit S' = S + 1 ou bien S' = S" 1, ne demande qu'un inverseur et des multiplexeurs à 2 entrées..

  • Le bit poids faible s'0 est le complément de s0.
  • Pour les autres bits : si s0 = '0' alors s'i = si sinon s'i = s"i .
  De semblable façon on peut également calculer S = A + B 1, S' = A + B, S" = A + B + 1 en calculant deux nombres X et Y tels que X + Y = A + B + 2n 1 avec les cellules HA' , duales des cellules HA.

Valeur absolue de la différence

Avec quatre légères modifications l'additionneur de Sklansky à retenue entrante retardée rend S = ½ A  B ½.

  • insérer des inverseurs pour complémenter B (ou bien A)
  • modifier la cellule "BK" calculant cn pour éliminer la valeur 'P' dans le signal "rebouclage" ('K' donne '0', 'P' ou 'G' donnent '1' ).
  • insérer une ligne de cellules "BK" avec "rebouclage" en entrée (en jaune).
  • modifier ces dernières cellules pour complémenter logiquement le résultat S ('K' ou 'P' donnent '1' ) si "rebouclage" = '0' ou bien lui ajouter 1 ( 'P' ou 'G' donnent '1' ) si "rebouclage" = '1' .

Pour résumer, si "rebouclage" = '1' alors S = A  B sinon S = B  A .

Addition en représentation "signe valeur absolue"

Soit sa et sb les signes de A et B respectivement et Ma et Mb leurs valeurs absolues aussi appelées "magnitudes". L'addition de A et B est réalisée par l'addition de Ma et Mb si A et B sont de même signe, et par leur soustraction dans le cas contraire. Dans tous les cas le signe du résultat S est le signe de l'addende de plus grande magnitude.

si (saÅ sb) alors { Ms = Ma + Mb , ss = sa } // mêmes signes
sinon si Ma ³ Mb alors { Ms = Ma Mb , ss = sa }
sinon { Ms = Mb Ma , ss = sb }

L'additionneur de représentations "signe/valeur absolue" hérite à la fois de l'additionneur/soustracteur et de l'opérateur de valeur absolue de la différence.

  La ligne horizontale "rebouclage" contrôle les cellules "BK" modifiées du bas (en jaune) :
si "rebouclage" = '2' alors Ms = Ma + Mb; // 'P' donne '0', 'G' donne '1' et 'K' donne '0'
si "rebouclage" = '1' alors Ms = Ma Mb; // 'P' donne '1', 'G' donne '1' et 'K' donne '0'
si
"rebouclage" = '0' alors Ms = Mb Ma; // 'P' donne '1', 'G' donne '0' et 'K' donne '1'

Additionneur modulo 2n 1

Un additionneur rend spontanément une somme modulo 2n. Avec une légère modification l'additionneur de Sklansky à retenue entrante retardée rend une somme modulo 2n 1.

  • si A + B < 2n 1 alors S = A + B ;
  • si A + B ³ 2n 1 alors S = ½ A + B + 1 ½ modulo 2n ;

Dans les deux cas on a S = ½ A + B ½ modulo (2n 1).
La condition du test est donnée par la retenue cn: si cn = 'K' alors A + B < 2n 1, si cn = 'P' alors A + B = 2n 1, si cn = 'G' alors A + B > 2n 1.
Donc pour le signal "rebouclage" qui contrôle " +1" , 'K' donne '0', 'P' ou 'G' donnent '1' , comme pour la valeur absolue ci-dessus.

Additionneur modulo 2n+ 1

  • si A + B < 2n + 1 alors S = A + B ;
  • si A + B ³ 2n + 1 alors S = ½ A + B 1 ½ modulo 2n ;

On se ramène à l'additionneur modulo 2n en calculant préalablement sans propagation de retenue deux nombres X et Y tels que X + Y = A + B + 2n 1 + c0 avec les cellules HA' , duales de HA. La retenue entrante c0 vaut '0'.

  • si X + Y < 2n+1 alors S = ½ X + Y + 1 ½ modulo 2n ;
  • si X + Y ³ 2n+1 alors S = ½ X + Y ½ modulo 2n ;

Donc le signal "rebouclage" horizontal qui contrôle "+1" est le "nand" de xn et (cn = 'G' ). Le bit poids fort sn est le "and" de xn et (cn = 'P' ) .

  Les valeurs de A et B vont de 0 à 2n. Les bits an et bn manquent en entrée de l'additionneur ci-dessus. Ces deux bits manquant indiquent A = 2n et B = 2n respectivement.
si A = 2n et B = 2n alors ( A + B ) modulo 2n + 1 = 2n 1.
si A = 2n et B < 2n alors A se réécrit ( 2n 1 ) + 1, c'est à dire tous les bits ai sont forcés à '1' ainsi que la retenue entrante c0.
si A < 2n et B = 2n alors B se réécrit ( 2n 1 ) + 1, c'est à dire tous les bits bi sont forcés à '1' ainsi que la retenue entrante c0.