Booth's Algorithmus

Ablauf des Algorithmus - Schritt für Schritt

1. Festlegen von Multiplikand (M) und Multiplikator (Q)

   • Für den Booth-Algorithmus ist es sinnvoll, Multiplikand und Multiplikator geschickt zu wählen
   • Die Zahl mit weniger Bitwechseln (01/10-Übergänge) nimmt man als Multiplikator (Q)
   • Dadurch sind im Verlauf des Algorithmus weniger Rechenoperationen (Add/Sub) notwendig
   • Multiplikand und Multiplikator können grundsätzlich auch getauscht werden, das Ergebnis wird dadurch nicht beeinflusst – nur der Ablauf

2. Initialisierung

   • Die Eingabewerte werden in Zweierkomplement-Binärzahlen umgewandelt.
   • Register werden vorbereitet:
   • A: initialisiere mit 0
   • Q: initialisiere mit Multiplikator
   • Q-1: ein zusätzliches Bit, initialisiert mit 0
   • M: initialisiere mit Multiplikand

3. Schleife über n Bits

   • In jedem Schleifendurchgang wird das Bitmuster Q₀ Q₋₁ geprüft:
   • 10 → Subtrahiere (A = A - M), danach arithmetische Rechtsverschiebung des kombinierten Registers (A, Q, Q₋₁)
   • 01 → Addiere (A = A + M), danach arithmetische Rechtsverschiebung des kombinierten Registers (A, Q, Q₋₁)
   • 00 oder 11 → nur arithmetische Rechtsverschiebung
   • Überläufe während der Addition/Subtraktion werden verworfen (Registerbreite bleibt konstant).

4. Wiederholung

   Wiederhole Schritt 3: n-mal.

5. Ergebnis

   • Nach n Durchgängen ergibt sich das finale Produkt von X*Y in der Kombination A | Q
   • Dieses Ergebnis liegt als Zweierkomplement vor, Q₋₁ ist nicht weiter relevant