Algorithme de multiplication de Booth

L'algorithme de Booth a pour but de multiplier deux nombres binaires signés représentés en complément à deux, en supposant les opérations de décalage nettement moins onéreuses que les additions/soustractions.

Cet algorithme a été inventé par Andrew Booth en 1950 alors qu'il effectuait des recherches en cristallographie.

Principe

Soit à calculer 500×A ; 500 = 256+128+64+32+16+4 = 111110100₂ . Mais 1 = 2-1 ; 3 = 4-1; 7=8-1; 127 = 128-1 etc. 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 traite 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é. 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, 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.

Voir aussi

Articles connexes

• Unité arithmétique et logique
• Multiplieur
• Architecture (informatique)

Références

1. Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2, 1951 [1]