Algorithme de cabines et décalage à droite

Question

Je connais le fonctionnement de l'algorithme des cabines.

Supposons que nous ayons multiplicande M = 01011

et multiplicateur Q = 01110

On peut écrire Q en tant que (2^4-2^1).

Ainsi, la multiplication se réduit à 2^4 (M) + 2 (-M)

règles de l'algorithme Maintenant, les cabines sont: -

Si Q = 0 et Q (-1) = 0 alors l'arithmétique bon décalage.

Si Q = 1 et Q (-1) = 0 alors faire A-M et le décalage arithmétique à droite.

Si Q = 0 et Q (-1) = 1, faites A + M et le décalage arithmétique vers la droite.

Si Q = 1 et Q (-1) = 1, effectuez alors un décalage arithmétique vers la droite.

Ici A est initialisé à 00000 et Q (-1) est initialisé à 0.

Si nous voyons l'algorithme puis dans toutes les étapes que nous faisons décalage à droite. Mais selon le calcul ci-dessus qui est 2^4 (M) + 2 (-M), nous multiplions par 16 et 2 ce qui nécessite un décalage vers la gauche. Alors, comment l'algorithme des cabines fonctionne-t-il avec le bon décalage? Je ne suis pas capable de comprendre l'intuition.

Answer 1

Cette variante de l'algorithme de Booth produit les W bits supérieurs de la multiplication M * Q, où M et Q ont W bits.

Le résultat sera placé sur Accumulateur A, ayant également W bits. Il est également possible de récupérer les bits faibles, en particulier dans l'assembleur, en utilisant la séquence SHR acc, 1; RCR low, 1.