Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes informatiques

Arithmétique des ordinateurs : additionneurs, retenue anticipée et multiplication

L'additionneur complet avec démonstration, retenue propagée, retenue anticipée, soustraction en complément à deux, dépassement de capacité et indicateurs, multiplieurs.

https://www.electronics-engineering.com/fr/arithmetique-des-ordinateurs-additionneurs-retenue-anticipee/

Pas encore de vote : soyez le premier à noter cette page.

L’unité arithmétique et logique fait ses calculs avec des portes logiques. En Fondements de l’informatique, nous avons vu comment les nombres sont représentés en binaire et en complément à deux ; ici nous voyons comment le matériel additionne, soustrait, détecte les erreurs et multiplie, et pourquoi la façon dont les retenues se propagent décide de la vitesse d’un processeur.

L’additionneur complet

Additionner deux nombres binaires colonne par colonne demande, pour chaque bit, d’additionner trois chiffres : les deux bits A et B et la retenue C_{in} de la colonne précédente. Le résultat est un bit de somme S et une retenue C_{out} pour la colonne suivante.

Théorème.

    \[ S = A \oplus B \oplus C_{in},\qquad C_{out} = AB + C_{in}(A \oplus B) \]

Démonstration. On vérifie sur la table de vérité des huit combinaisons. S vaut 1 quand le nombre d’entrées à 1 est impair (1 ou 3), ce qui est la définition du OU exclusif de trois bits. C_{out} vaut 1 quand au moins deux entrées valent 1 : soit A et B le sont tous deux (AB), soit exactement l’un des deux l’est (A \oplus B) et C_{in} aussi. Les deux cas sont disjoints et couvrent toutes les possibilités. ∎

Additionneur complet construit avec des portes logiques et additionneur à propagation de retenue de quatre bits
En haut l’additionneur complet : deux portes XOR produisent la somme, deux portes ET et une porte OU produisent la retenue. En bas quatre additionneurs complets en ligne : la retenue de chacun entre dans le suivant, de droite à gauche.

Propagation de la retenue

En plaçant n additionneurs complets en ligne, avec chaque sortie de retenue reliée à l’entrée de retenue suivante, on obtient l’additionneur à propagation de retenue (ripple-carry). Il est simple, mais lent : le bit de poids fort n’est valide qu’après que la retenue a parcouru toute la chaîne. Si chaque étage ajoute un retard de deux portes, un additionneur de 64 bits en accumule 128, bien trop pour un processeur qui tourne à quelques gigahertz.

Retenue anticipée

Pour chaque colonne, on définit deux signaux qui ne dépendent que de A_i et B_i :

    \[ g_i = A_iB_i\ \ \text{(generate)},\qquad p_i = A_i \oplus B_i\ \ \text{(propagate)} \]

La colonne génère une retenue à elle seule si les deux bits valent 1 ; elle propage celle qui arrive si exactement un des deux vaut 1. Donc c_{i+1} = g_i + p_ic_i, et en substituant :

    \[ c_2 = g_1 + p_1g_0 + p_1p_0c_0,\qquad c_3 = g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_0 \]

Chaque retenue est calculée directement à partir des entrées, avec deux niveaux de portes, sans attendre les précédentes. Les portes deviennent très larges quand n croît, donc on travaille par groupes de 4 bits et on répète l’idée de façon hiérarchique : le retard croît comme \log_2 n au lieu de n. Les additionneurs des processeurs modernes sont des variantes de cette idée (additionneurs à préfixes, comme Kogge-Stone).

Soustraction et dépassement de capacité

En complément à deux, -B s’obtient en inversant tous les bits et en ajoutant 1. Donc

    \[ A - B = A + \overline{B} + 1 \]

et le même additionneur soustrait aussi : il suffit de mettre des portes XOR sur les entrées B (pour les inverser quand il le faut) et de mettre la retenue initiale c_0 à 1. C’est l’une des raisons pour lesquelles le complément à deux a supplanté toute autre représentation des nombres négatifs.

Dépassement de capacité. En additionnant deux nombres de même signe, le résultat peut sortir de la plage représentable : avec 8 bits, 100 + 100 = 200 dépasse 127 et apparaît comme −56. On le reconnaît parce que le signe du résultat diffère de celui des deux opérandes ; en matériel, de façon équivalente, la retenue entrant dans le bit de poids fort diffère de celle qui en sort : V = c_{n} \oplus c_{n-1}.

L’ALU signale le résultat des opérations par quelques bits d’état, les indicateurs (flags) : Z (résultat nul), N (négatif), C (retenue, utile pour les nombres non signés), V (dépassement, pour les nombres signés). Les branchements conditionnels des architectures qui les utilisent reposent sur ces bits.

Multiplication

La multiplication binaire est plus simple que la décimale : chaque produit partiel est soit le multiplicande, soit zéro, selon le bit du multiplicateur, décalé à la position correspondante. Les n produits partiels sont ensuite additionnés.

  • La méthode la plus lente, décalage et addition, utilise un seul additionneur pendant n cycles.
  • Les multiplieurs en arbre additionnent tous les produits partiels ensemble avec des additionneurs disposés en arbre (arbres de Wallace), et multiplient deux nombres de 64 bits en quelques cycles d’horloge.

La division est plus difficile et se fait avec des algorithmes itératifs qui produisent un ou plusieurs chiffres du quotient par cycle : c’est pourquoi, dans les programmes où la vitesse est critique, les compilateurs remplacent les divisions par des constantes par des multiplications et des décalages. Les nombres à virgule flottante (norme IEEE 754, leçon de Calcul numérique) ont une unité dédiée, qui aligne les exposants, opère sur les mantisses et normalise le résultat.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x