Qu'est-ce que l'algorithme de Booth ? Pouvez-vous l'expliquer avec un exemple ?

L'algorithme de Booth est utilisé pour multiplier deux nombres binaires en réduisant le nombre de 1. il gère uniformément les nombres positifs et négatifs

Algorithme de multiplication de Booth Procédure L'algorithme de Booth consiste à ajouter à plusieurs reprises l'une des deux valeurs prédéterminées A et S à un produit P, puis à effectuer un décalage arithmétique vers la droite sur P. Soit m et r le multiplicande et le multiplicateur, respectivement ; et laissez x et y représentent 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 bits restants (y + 1) avec des zéros. 2. S : Remplir les bits les plus significatifs avec la valeur de (−m) en notation complémentaire à deux. Remplissez les bits restants (y + 1) avec des zéros. 3. P : Remplir les x bits les plus significatifs avec des zéros. A droite de ceci, ajoutez la valeur de r.Remplissez le bit le moins significatif (le plus à droite) avec un zéro. 2. Déterminez les deux bits les moins significatifs (les plus à droite) de P. 1. S'ils sont à 01, trouvez la valeur de P + A. Ignorez tout débordement. 2. S'ils sont au nombre de 10, recherchez la valeur de P + S. Ignorez tout débordement. 3. S'ils sont 00, ne faites rien. Utilisez P directement à l'étape suivante. 4. S'ils ont 11, ne rien faire. Utilisez P directement à l'étape suivante. 3. Décaler arithmétiquement la valeur obtenue à la 2ème étape d'une seule place vers la droite. Soit P maintenant égal à 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 le moins significatif (le plus à droite) de P. C'est le produit de m et r. Exemple Trouver 3 × −4, avec m = 3 et r = −4, et x = 4 et y = 4 : • A = 0011 0000 0 • S = 1101 0000 0 • P = 0000 1100 0 • Réaliser la boucle quatre fois : 1. P = 0000 1100 0. Les deux derniers bits sont 00. P = 0000 0110 0. Décalage arithmétique à droite. 2. P = 0000 0110 0. Les deux derniers bits sont 00.  P = 0000 0011 0. Décalage arithmétique vers la droite. 3. P = 0000 0011 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 1001 1. Les deux derniers bits sont 11.  P = 1111 0100 1. Décalage arithmétique vers la droite. • Le produit est 1111 0100, soit -12. La technique mentionnée ci-dessus est inadéquate lorsque le multiplicande est le plus grand nombre négatif pouvant être représenté (c'est-à-dire si le multiplicande a 8 bits alors cette valeur est de -128). Une correction possible à ce problème consiste à ajouter un bit de plus à gauche de A, S et P. Ci-dessous, nous démontrons la technique améliorée en multipliant -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éaliser la boucle quatre fois : 1. P = 0 0000 0010 0. Les deux derniers bits sont 00.  P = 0 0000 0001 0. Décalage à droite. 2. P = 0 0000 0001 0. Les deux derniers bits sont 10.  P = 0 1000 0001 0. P = P + S.  P = 0 0100 0000 1. Décalage à droite. 3. P = 0 0100 0000 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 0000 0. Les deux derniers bits sont 00.  P = 0 1111 0000 0. Décalage à droite. • Le produit est 11110000 (après élimination du premier et du dernier bit) soit -16. Comment ça marche Considérons un multiplicateur positif constitué 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 le même que En fait,il peut être démontré que toute séquence de 1 dans un nombre binaire peut être divisée en la différence de deux nombres binaires : Par conséquent, nous pouvons réellement remplacer la multiplication par la chaîne de uns dans le nombre d'origine par des opérations plus simples, en ajoutant le multiplicateur, en déplaçant le produit partiel ainsi formé par lieux appropriés, puis en soustrayant enfin le multiplicateur. Il utilise le fait que nous n'avons rien à faire d'autre que le décalage lorsque nous avons affaire à des 0 dans un multiplicateur binaire, et est similaire à l'utilisation de la propriété mathématique que 99 = 100 − 1 en multipliant 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, Booth'L'algorithme s suit ce schéma en effectuant une addition lorsqu'il rencontre le premier chiffre d'un bloc de uns (0 1) et une soustraction lorsqu'il rencontre la fin du bloc (1 0). Cela fonctionne aussi pour un multiplicateur négatif. Lorsque ceux 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 normal.

C'est une méthode directe... il y a un organigramme dans le livre de décrochage...