Algorithme de multiplication de Booth

L’algorithme de Booth examine les paires adjacentes de bits du multiplicateur Y à N bits dans la représentation signée en complément à deux, incluant un bit implicite en dessous du bit le moins significatif (LSB), y₋₁ = 0. Pour chaque bit y_i, pour i allant de 0 à N − 1, les bits y_i et y_i−1 sont considérés. Lorsque ces deux bits sont égaux, l’accumulateur stockant le produit P reste inchangé. Lorsque y_i = 0 et y_i−1 = 1, le multiplicande multiplié par 2ⁱ est ajouté à P ; lorsque y_i = 1 et y_i−1 = 0, le multiplicande multiplié par 2ⁱ est soustrait de P. La valeur finale de P est le produit signé.

Les représentations du multiplicande et du produit ne sont pas spécifiées ; typiquement, ils sont aussi représentés en complément de deux, comme le multiplicateur, mais tout système de nombres supportant l’addition et la soustraction fonctionnera également. Comme indiqué ici, l’ordre des étapes n’est pas déterminé. Typiquement, elle va du LSB vers le MSB, en commençant à i = 0 ; la multiplication par 2ⁱ est alors généralement remplacée par un déplacement incrémental de l’accumulateur P vers la droite entre les étapes ; les bits de poids faible peuvent être ignorés, et les additions et soustractions suivantes peuvent alors être effectuées uniquement sur les N bits de poids les plus forts de P^[2]. Il existe de nombreuses variations et optimisations sur ces détails.

L’algorithme est souvent décrit comme convertissant des chaînes de 1 dans le multiplicateur en un +1 d’ordre élevé et un −1 d’ordre bas aux extrémités de la chaîne. Lorsqu’une chaîne passe par le MSB, il n’y a pas de +1 d’ordre élevé, et l’effet net est interprété comme une valeur négative de la valeur appropriée.

L'algorithme de Booth peut être implémenté en ajoutant de façon répétée (avec l'addition binaire ordinaire non signée) une des deux valeurs prédéterminées A et S à un produit P, puis en réalisant un décalage arithmétique vers la droite sur P. Soient m et r le multiplicande et le multiplicateur, respectivement ; et x et y qui représentent le nombre de bits de m et de r.

1. Déterminer les valeurs de A et de S et la valeur initiale de P. Tous ces nombres doivent avoir une longueur égale à (x + y + 1).
   1. A : Remplir les bits les plus significatifs (les plus à gauche) avec la valeur de m. Remplir les (y + 1) bits restants avec des zéros.
   2. S : Remplir les bits les plus significatifs avec la valeur de (−m) en notation complément à deux. Remplir les (y + 1) bits restants avec des zéros.
   3. P : Remplir les bits les plus significatifs x avec des zéros. A leur droite, ajouter la valeur de r. Remplir le bit le moins significatif (le plus à droite) avec un zéro.
2. Déterminer les deux bits les moins significatifs (les plus à droite) de P.
   1. S'ils valent 01, calculer la valeur de P + A. Ignorer tout débordement.
   2. S'ils valent 10, calculer la valeur de P + S. Ignorer tout débordement.
   3. S'ils valent 00, ne rien faire. Utiliser P directement dans l'étape suivante.
   4. S'ils valent 11, ne rien faire. Utiliser P directement dans l'étape suivante.
3. Décaler arithmétiquement la valeur obtenue dans la deuxième étape d'une seule place vers la droite. P est fixé égal à cette nouvelle valeur.
4. Répéter les étapes 2 et 3 jusqu'à ce qu'elles soient parcourues y fois.
5. Ignorer les bits les moins significatifs (les plus à droite) de P. C'est le produit de m et de r.

Soit à calculer 500×A ; 500 = 256+128+64+32+16+4 = 111110100₂. On peut donc remplacer un train d'additions binaires par une addition de tête et une soustraction de queue. Précisément, l'algorithme de Booth écrit 500 comme (512 - 16) + (8 - 4) = 1000011100₂.

Cela revient à utiliser une transcription simplifiée du multiplicateur dans un système binaire symétrique utilisant les chiffres signés (1, 0, 1) ; le but est de multiplier les zéros (non-action) ; 1 commandant une addition convenablement cadrée du multiplicande, 1 = -1 celle de son opposé (une soustraction). Soit ici 4 opérations au lieu de 6.

Pour un multiplicande signé en complément à deux, le signe s'interprète comme l'opposé de la puissance de 2 du poids du bit le plus significatif : -2⁸ pour un octet, -2¹⁶ pour un mot de 16 bits etc. Dans ce cas, un signe négatif entraîne une soustraction initiale.