Der Booth-Algorithmus ist ein Multiplikationsalgorithmus, der es uns ermöglicht, die beiden vorzeichenbehafteten binären Ganzzahlen jeweils im Zweierkomplement zu multiplizieren. Es wird auch verwendet, um die Leistung des Multiplikationsprozesses zu beschleunigen. Es ist auch sehr effizient. Es funktioniert mit den Nullen der String-Bits im Multiplikator, der kein zusätzliches Bit erfordert, sondern nur die ganz rechten String-Bits und eine Folge von Einsen in einem Multiplikatorbit mit der Gewichtung 2 verschiebt^kGewicht 2^Mdas kann als angesehen werden 2^{k+ 1}- 2^M .

Es folgt die bildliche Darstellung des Booth-Algorithmus:

Im obigen Flussdiagramm zunächst Wechselstrom Und Q_{n + 1} Bits werden auf 0 gesetzt und die SC ist ein Sequenzzähler, der die Gesamtzahl der gesetzten Bits darstellt N, was gleich der Anzahl der Bits im Multiplikator ist. Es gibt BR die repräsentieren die Multiplikandenbits, und QR repräsentiert das Multiplikatorbits . Danach stießen wir auf zwei Bits des Multiplikators als Q_Nund Q_{n + 1}, wobei Qn das letzte Bit von QR darstellt und Q_{n + 1}stellt das um 1 erhöhte Bit von Qn dar. Angenommen, zwei Bits des Multiplikators sind gleich 10; Das bedeutet, dass wir den Multiplikator vom Partialprodukt im Akkumulator AC subtrahieren und dann die arithmetische Schiebeoperation (ashr) durchführen müssen. Wenn die beiden Multiplikatoren gleich 01 sind, bedeutet das, dass wir die Addition des Multiplikanden zum Partialprodukt im Akkumulator AC durchführen und dann die arithmetische Schiebeoperation durchführen müssen ( Ashr ), einschließlich Q_{n + 1} . Die arithmetische Schiebeoperation wird im Booth-Algorithmus verwendet, um AC- und QR-Bits um eins nach rechts zu verschieben und das Vorzeichenbit in AC unverändert zu lassen. Und der Sequenzzähler wird kontinuierlich dekrementiert, bis die Rechenschleife wiederholt wird, und zwar entsprechend der Anzahl der Bits (n).

Arbeiten am Booth-Algorithmus

1. Stellen Sie die Binärbits Multiplikand und Multiplikator auf M bzw. Q ein.
2. Zunächst stellen wir AC und Q ein_{n + 1}Registriert den Wert auf 0.
3. SC stellt die Anzahl der Multiplikatorbits (Q) dar und ist ein Sequenzzähler, der kontinuierlich dekrementiert wird, bis er der Anzahl der Bits (n) entspricht oder 0 erreicht.
4. Ein Qn stellt das letzte Bit von Q dar, und das Q_n+1zeigt das um 1 erhöhte Bit von Qn.
5. Bei jedem Zyklus des Booth-Algorithmus Q_Nund Q_{n + 1}Bits werden für die folgenden Parameter wie folgt überprüft:
   1. Wenn zwei Bits Q_Nund Q_{n + 1}00 oder 11 sind, führen wir einfach die arithmetische Rechtsverschiebungsoperation (ashr) zum Partialprodukt AC durch. Und die Bits von Qn und Q_{n + 1}wird um 1 Bit erhöht.
   2. Wenn die Bits von Q_Nund Q_{n + 1}Ist der Wert 01, werden die Multiplikandenbits (M) zum AC (Akkumulatorregister) hinzugefügt. Danach führen wir die rechte Verschiebungsoperation zu den AC- und QR-Bits um 1 durch.
   3. Wenn die Bits von Q_Nund Q_{n + 1}Ist der Wert 10, werden die Multiplikandenbits (M) vom AC (Akkumulatorregister) subtrahiert. Danach führen wir die rechte Verschiebungsoperation zu den AC- und QR-Bits um 1 durch.
6. Die Operation funktioniert kontinuierlich, bis wir n – 1 Bit im Booth-Algorithmus erreicht haben.
7. Die Ergebnisse der Multiplikations-Binärbits werden in den AC- und QR-Registern gespeichert.

Im Booth-Algorithmus werden zwei Methoden verwendet:

F-String-Python

1. RSC (Right Shift Circular)

Es verschiebt das ganz rechte Bit der Binärzahl und fügt es dann am Anfang der Binärbits hinzu.

2. RSA (Rechtsverschiebungsarithmetik)

Es addiert die beiden Binärbits und verschiebt das Ergebnis dann um eine 1-Bit-Position nach rechts.

Abschlag durchgestrichen

Beispiel : 0100 + 0110 => 1010, nach der Addition der Binärzahl jedes Bit um 1 nach rechts verschieben und das erste Bit der Resultierenden an den Anfang des neuen Bits setzen.

Beispiel: Multiplizieren Sie die beiden Zahlen 7 und 3 mit dem Multiplikationsalgorithmus von Booth.

Jahre . Hier haben wir zwei Zahlen, 7 und 3. Zunächst müssen wir 7 und 3 in Binärzahlen wie 7 = (0111) und 3 = (0011) umwandeln. Stellen Sie nun 7 (in Binärzahl 0111) als Multiplikand (M) und 3 (in Binärzahl 0011) als Multiplikator (Q) ein. Und SC (Sequence Count) stellt die Anzahl der Bits dar, und hier haben wir 4 Bits, also setzen Sie SC = 4. Außerdem zeigt es die Anzahl der Iterationszyklen der Booth-Algorithmen an und dann werden die Zyklen SC = SC - 1 Mal ausgeführt.

Das numerische Beispiel des Booth-Multiplikationsalgorithmus ist 7 x 3 = 21 und die binäre Darstellung von 21 ist 10101. Hier erhalten wir das Ergebnis in binärer Form 00010101. Jetzt wandeln wir es in eine Dezimalzahl um, als (000010101).₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

So ermitteln Sie die Anzeigegröße

Beispiel: Multiplizieren Sie die beiden Zahlen 23 und -9 mit dem Multiplikationsalgorithmus von Booth.

Hier ist M = 23 = (010111) und Q = -9 = (110111)

Q_{n + 1} = 1 bedeutet, dass die Ausgabe negativ ist.

Daher ist 23 * -9 = 2er-Komplement von 111100110001 => (00001100111)