Was ist der Booth-Algorithmus? Können Sie ihn anhand eines Beispiels erklären?

Der Booth-Algorithmus wird verwendet, um zwei Binärzahlen zu multiplizieren, indem die Anzahl von 1 reduziert wird. Er behandelt sowohl positive als auch negative Zahlen einheitlich

Booths Multiplikationsalgorithmus Prozedur Booths Algorithmus beinhaltet das wiederholte Addieren eines von zwei vorbestimmten Werten A und S zu einem Produkt P, dann Durchführen einer arithmetischen Verschiebung nach rechts an P. Seien m und r der Multiplikand bzw. der Multiplikator; und lassen x und y die Anzahl von Bits in m und r darstellen. 1. Bestimmen Sie die Werte von A und S und den Anfangswert von P. Alle diese Zahlen sollten eine Länge gleich (x + y + 1) haben. 1. A: Füllen Sie die höchstwertigen (ganz links) Bits mit dem Wert von m. Füllen Sie die restlichen (y + 1) Bits mit Nullen. 2. S: Fülle die höchstwertigen Bits mit dem Wert von (–m) in Zweierkomplementschreibweise. Füllen Sie die restlichen (y + 1) Bits mit Nullen. 3. P: Fülle die höchstwertigen x Bits mit Nullen. Rechts daneben den Wert von r anhängen.Füllen Sie das niedrigstwertige (ganz rechts) Bit mit einer Null. 2. Bestimmen Sie die zwei niedrigstwertigen (ganz rechts) Bits von P. 1. Wenn sie 01 sind, finden Sie den Wert von P + A. Ignorieren Sie jeglichen Überlauf. 2. Wenn sie 10 sind, ermitteln Sie den Wert von P + S. Ignorieren Sie jeglichen Überlauf. 3. Wenn sie 00 sind, tun Sie nichts. Verwenden Sie P direkt im nächsten Schritt. 4. Wenn sie 11 sind, tun Sie nichts. Verwenden Sie P direkt im nächsten Schritt. 3. Verschieben Sie den im 2. Schritt erhaltenen Wert rechnerisch um eine Stelle nach rechts. Sei nun P gleich diesem neuen Wert. 4. Wiederholen Sie die Schritte 2 und 3, bis sie y-mal durchgeführt wurden. 5. Lassen Sie das niedrigstwertige (ganz rechts) Bit von P fallen. Dies ist das Produkt von m und r. Beispiel Finde 3 × −4, mit m = 3 und r = −4 und x = 4 und y = 4: • A = 0011 0000 0 • S = 1101 0000 0 • P = 0000 1100 0 • Führe die Schleife viermal durch : 1. P = 0000 1100 0. Die letzten beiden Bits sind 00. P = 0000 0110 0. Arithmetische Rechtsverschiebung. 2. P = 0000 0110 0. Die letzten beiden Bits sind 00.  P = 0000 0011 0. Arithmetische Rechtsverschiebung. 3. P = 0000 0011 0. Die letzten beiden Bits sind 10. P = 1101 0011 0. P = P + S.  P = 1110 1001 1. Arithmetische Rechtsverschiebung. 4. P = 1110 1001 1. Die letzten beiden Bits sind 11.  P = 1111 0100 1. Arithmetische Rechtsverschiebung. • Das Produkt ist 1111 0100, also −12. Die oben erwähnte Technik ist unangemessen, wenn der Multiplikand die größte negative Zahl ist, die dargestellt werden kann (dh wenn der Multiplikand 8 Bit hat, dann ist dieser Wert –128). Eine mögliche Korrektur dieses Problems besteht darin, links von A, S und P ein weiteres Bit hinzuzufügen. Im Folgenden demonstrieren wir die verbesserte Technik durch Multiplizieren von -8 mit 2 unter Verwendung von 4 Bits für den Multiplikanden und den Multiplikator:• A = 1 1000 0000 0 • S = 0 1000 0000 0 • P = 0 0000 0010 0 • Führen Sie die Schleife viermal durch: 1. P = 0 0000 0010 0. Die letzten beiden Bits sind 00.  P = 0 0000 0001 0. Rechtsverschiebung. 2. P = 0 0000 0001 0. Die letzten beiden Bits sind 10. P = 0 1000 0001 0. P = P + S.  P = 0 0100 0000 1. Rechtsverschiebung. 3. P = 0 0100 0000 1. Die letzten beiden Bits sind 01.  P = 1 1100 0000 1. P = P + A.  P = 1 1110 0000 0. Rechtsverschiebung. 4. P = 1 1110 0000 0. Die letzten beiden Bits sind 00.  P = 0 1111 0000 0. Rechtsverschiebung. • Das Produkt ist 11110000 (nach dem Verwerfen des ersten und des letzten Bits), was −16 ist. Wie es funktioniert Betrachten Sie einen positiven Multiplikator, der aus einem Block von Einsen besteht, die von Nullen umgeben sind. Beispiel: 00111110. Das Produkt ist gegeben durch: Wobei M der Multiplikand ist. Die Anzahl der Operationen kann auf zwei reduziert werden, indem dasselbe wie ines kann gezeigt werden, dass jede Folge von Einsen in einer Binärzahl in die Differenz zweier Binärzahlen zerlegt werden kann: Daher können wir die Multiplikation durch die Einsenkette in der ursprünglichen Zahl tatsächlich durch einfachere Operationen ersetzen, den Multiplikator addieren, verschieben das so gebildete Teilprodukt durch geeignete Stellen und schließlich Subtrahieren des Multiplikators. Es macht sich die Tatsache zunutze, dass wir beim Umgang mit Nullen in einem binären Multiplikator nichts anderes tun müssen als verschieben, und ähnelt der Verwendung der mathematischen Eigenschaft 99 = 100 − 1 beim Multiplizieren mit 99. Dieses Schema kann auf eine beliebige Anzahl von 1er-Blöcken in einem Multiplikator erweitert werden (einschließlich des Falles einer einzelnen 1 in einem Block). Also, Booth'Der Algorithmus folgt diesem Schema, indem er eine Addition durchführt, wenn er auf die erste Ziffer eines Einserblocks trifft (0 1) und eine Subtraktion, wenn er auf das Ende des Blocks (1 0) stößt. Dies funktioniert auch für einen negativen Multiplikator. Wenn die Einsen in einem Multiplikator in lange Blöcke gruppiert werden, führt der Booth-Algorithmus weniger Additionen und Subtraktionen durch als der normale Multiplikationsalgorithmus.

Es ist eine direkte Methode.. es gibt ein Flussdiagramm im Stalling-Buch