Booth's multiplication algorithm

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture.

Booth's algorithm examines adjacent pairs of bits of the N-bit multiplier Y in signed two's complement representation, including an implicit bit below the least significant bit, y₋₁ = 0. For each bit y_i, for i running from 0 to N − 1, the bits y_i and y_i−1 are considered. Where these two bits are equal, the product accumulator P is left unchanged. Where y_i = 0 and y_i−1 = 1, the multiplicand times 2ⁱ is added to P; and where y_i = 1 and y_i−1 = 0, the multiplicand times 2ⁱ is subtracted from P. The final value of P is the signed product.

The representations of the multiplicand and product are not specified; typically, these are both also in two's complement representation, like the multiplier, but any number system that supports addition and subtraction will work as well. As stated here, the order of the steps is not determined. Typically, it proceeds from LSB to MSB, starting at i = 0; the multiplication by 2ⁱ is then typically replaced by incremental shifting of the P accumulator to the right between steps; low bits can be shifted out, and subsequent additions and subtractions can then be done just on the highest N bits of P. There are many variations and optimizations on these details.

L'algorithme est souvent décrit comme convertissant les chaînes de 1 du multiplicateur en un +1 de poids fort et un −1 de poids faible aux extrémités de la chaîne. Lorsqu'une chaîne traverse le bit de poids fort, il n'y a pas de +1 de poids fort, et l'effet net est interprété comme l'opposé de la valeur appropriée.

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

1. Déterminez les valeurs de A et S , et la valeur initiale de P. Tous ces nombres doivent avoir une longueur égale à ( x + y + 1).
   1. A : Remplissez les bits les plus significatifs (les plus à gauche) avec la valeur de m . Remplissez les ( y + 1) bits restants avec des zéros.
   2. S : Remplissez les bits de poids fort avec la valeur de (− m ) en complément à deux. Remplissez les ( y + 1) bits restants avec des zéros.
   3. P : Remplissez les x bits de poids fort avec des zéros. À droite, ajoutez la valeur de r . Remplissez le bit de poids faible (le plus à droite) avec un zéro.
2. Déterminez les deux bits de poids faible (les plus à droite) de P.
   1. Si les valeurs sont 01, trouvez la valeur de P + A. Ignorez tout dépassement de capacité.
   2. Si leur valeur est 10, trouvez la valeur de P + S. Ignorez tout dépassement de capacité.
   3. Si la valeur est 00, ne rien faire. Utiliser directement P à l'étape suivante.
   4. S'ils valent 11, ne faites rien. Utilisez P directement à l'étape suivante.
3. Décalez arithmétiquement la valeur obtenue à la deuxième étape d'une position vers la droite. Soit P égale à cette nouvelle valeur.
4. Répétez les étapes 2 et 3 jusqu'à ce qu'elles aient été effectuées y fois.
5. Supprimez le bit de poids faible (le plus à droite) de P. Ceci est le produit de m et r .

Trouvez 3 × (−4), avec m = 3 et r = −4, et x = 4 et y = 4 :

• m = 0011, -m = 1101, r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• Répétez la boucle quatre fois :
  1. P = 0000 110 0 0. Les deux derniers bits sont 00.
     • P = 0000 0110 0. Décalage arithmétique vers la droite.
  2. P = 0000 011 0 0. Les deux derniers bits sont 00.
     • P = 0000 0011 0. Décalage arithmétique vers la droite.
  3. P = 0000 001 1 0. Les deux derniers bits sont 10.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. Décalage arithmétique vers la droite.
  4. P = 1110 100 1 1. Les deux derniers bits sont 11.
     • P = 1111 0100 1. Décalage arithmétique vers la droite.
• Le produit est 1111 0100, ce qui est −12.

La technique mentionnée ci-dessus est inadéquate lorsque le multiplicande est le nombre le plus négatif représentable (par exemple, si le multiplicande est codé sur 4 bits, sa valeur est −8). En effet, un dépassement de capacité se produit alors lors du calcul de −m, la négation du multiplicande, nécessaire pour initialiser S. Une solution possible à ce problème consiste à étendre A, S et P d'un bit chacun, tout en conservant la même valeur. Ainsi, −8, auparavant codé sur quatre bits par 1000, est désormais codé sur cinq bits par 1 1000. Cette implémentation suit celle décrite précédemment, avec des modifications dans la détermination des bits de A et S ; par exemple, la valeur de m , initialement attribuée aux x premiers bits de A, est maintenant étendue à x + 1 bits et attribuée aux x + 1 premiers bits de A. La technique améliorée est illustrée ci-dessous par la multiplication de −8 par 2, en utilisant 4 bits pour le multiplicande et le multiplicateur :

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0
• Répétez la boucle quatre fois :
  1. P = 0 0000 001 0 0. Les deux derniers bits sont 00.
     • P = 0 0000 0001 0. Décalage vers la droite.
  2. P = 0 0000 000 1 0. Les deux derniers bits sont 10.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. Décalage vers la droite.
  3. P = 0 0100 000 0 1 . Les deux derniers bits sont 01.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. Décalage à droite.
  4. P = 1 1110 000 0 0. Les deux derniers bits sont 00.
     • P = 1 1111 0000 0. Décalage à droite.
• Le produit est 11110000 (après avoir supprimé le premier et le dernier bit) qui est −16.

Considérons un multiplicateur positif composé d'un bloc de 1 entouré de 0. Par exemple, 00111110. Le produit est donné par : où M est le multiplicande. Le nombre d'opérations peut être réduit à deux en réécrivant la même expression comme

En fait, on peut démontrer que toute séquence de 1 dans un nombre binaire peut être décomposée en la différence de deux nombres binaires :

Ainsi, la multiplication peut être remplacée par la suite de 1 du nombre initial grâce à des opérations plus simples : l’addition du multiplicateur, le décalage du produit partiel ainsi formé, puis la soustraction du multiplicateur. Cette méthode exploite le fait qu’il suffit de décaler les 0 dans un multiplicateur binaire, ce qui est similaire à l’utilisation de la propriété mathématique 99 = 100 − 1 lors d’une multiplication par 99.

Ce schéma peut être étendu à un nombre quelconque de blocs de 1 dans un multiplicateur (y compris le cas d'un seul 1 dans un bloc). Ainsi,

L'algorithme de Booth reprend ce schéma classique en effectuant une addition lorsqu'il rencontre le premier chiffre d'un bloc de 1 (0 1) et une soustraction lorsqu'il rencontre le dernier chiffre du bloc (1 0). Ceci fonctionne également pour un multiplicateur négatif. Lorsque les 1 d'un multiplicateur sont regroupés en longs blocs, l'algorithme de Booth effectue moins d'additions et de soustractions que l'algorithme de multiplication classique.

Le microprocesseur Pentium d' Intel utilise une variante de l'algorithme de Booth en base 8 dans son multiplicateur matériel 64 bits. Du fait de son implémentation de la multiplication en base 8, il nécessite un circuit auxiliaire complexe pour effectuer le cas particulier de la multiplication par 3 de manière à minimiser la latence, en combinant l'utilisation de l' anticipation de retenue , de la sélection de retenue et de l'addition de Kogge-Stone .