Booth-Algorithmus

Der Booth-Algorithmus ist ein Algorithmus für die schnelle (wenige Additionen) rechnergestütze Multiplikation zweier Zahlen und wurde um 1951 von Andrew D. Booth entwickelt.

Dabei macht man sich zu Nutze, dass sich jede Zahl b als Differenz zweier Zahlen c und d darstellen lässt: $a\cdot b=a\cdot (c-d)=a\cdot c-a\cdot d$. Vorteile gegenüber der "Papier und Bleistift"-Methode bietet dieses Verfahren bei Zahlen, die in der Binärdarstellung lange gleichwertige Bitkolonen aufweisen. Diese werden beim Booth-Verfahren "übersprungen". Darauf basierend erlaubt dieses Booth-Verfahren auch eine effiziente Multiplikation für Binärzahlen im Zweierkomplement. Außerdem hat der Algorithmus den Vorteil, dass man die Vorzeichen der beiden Faktoren nicht beachten muss.

Will man $30_{10}=00011110_{2}$ mit einer Zahl X multiplizieren, bräuchte man bei der traditionellen Methode, aufgrund der vielen Einsen, 4 Additionen: $10_{2}\cdot X+100_{2}\cdot X+1000_{2}\cdot X+10000_{2}\cdot X$. Das Booth-Verfahren hingegen braucht nur 2: $100000_{2}\cdot X-1_{2}\cdot X$.

Der Booth-Algorithmus bietet eine effiziente Möglichkeit, zu einer Zahl die entsprechend zu benutzende Kodierung zu ermitteln. Man geht dabei von rechts nach links durch die Binärzahl. Wechselt die Binärstelle von der letzten zur aktuellen Position von 0 nach 1, wird eine -1, bei einem Wechsel von 1 nach 0 eine +1 und bei keinem Wechsel eine 0 gesetzt. Im ersten Schritt wird sich an die Zahl rechts eine 0 dazu gedacht.

Beispiele

Multipliziere $44_{10}=(00101100)_{2}$ und $17_{10}=(00010001)_{2}$

Kodierung eines Faktors nach Booth

Schritt 1	0	1	0	1	1	0	0	0
							0
Schritt 2	0	1	0	1	1	0	0	0
						0	0
Schritt 3	0	1	0	1	1	0	0	0
					-1	0	0
Schritt 4	0	1	0	1	1	0	0	0
				0	-1	0	0
Schritt 5	0	1	0	1	1	0	0	0
			+1	0	-1	0	0
Schritt 6	0	1	0	1	1	0	0	0
		-1	+1	0	-1	0	0
Schritt 7	0	1	0	1	1	0	0	0
	+1	-1	+1	0	-1	0	0

Formal: Dem mittels Booth zu kodierenden Operand $Y=(y_{n-1},\dots ,y_{0})$ füge man eine weitere "Stelle" $y_{-1}$ an, die auf Null gesetzt wird. Die weiteren Stellen ${y'}_{i},i\in \left\{0,\dots ,n-1\right\}$ des neuen $Y':=(y'_{n-1},\dots ,y'_{0},y_{-1})$ werden wie folgt berechnet: ${y'}_{i}=y_{i-1}-y_{i}\ \forall i\in \{0,\dots ,n-1\}$.

Multiplikation

									0	0	0	1	0	0	0	1	2. Faktor
x									0	+1	-1	+1	0	-1	0	0	Kodierung des 1. Faktors
+		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	keine Addition
+		0	0	0	0	0	0	0	0	0	0	0	0	0	0		keine Addition
+		1	1	1	1	1	1	1	1	0	1	1	1	1			2er Komplement (2. Faktor)
+		0	0	0	0	0	0	0	0	0	0	0	0				keine Addition
+		0	0	0	0	0	0	1	0	0	0	1					2. Faktor
+		1	1	1	1	1	0	1	1	1	1						2er Komplement (2. Faktor)
+		0	0	0	0	1	0	0	0	1							2. Faktor
+		0	0	0	0	0	0	0	0								keine Addition
1	0	0	0	0	0	0	1	0	1	1	1	0	1	1	0	0	Ergebnis ohne Überlauf

Statt mit 0100000, 0001000 und 0000100 zu multiplizieren und die Ergebnisse zu addieren, wird nun also mit 1000000, 0100000, 0010000 und 0000100 multipliziert und entsprechend die Ergebnisse addiert bzw. subtrahiert.

Wie man am Beispiel sieht, kann sich die Anzahl der Additionen auch erhöhen (im Beispiel von 3 auf 4), was ja aber gerade nicht erwünscht ist. Im statistischen Durchschnitt werden im Booth-Verfahren genausoviele Additionen gebraucht wie ohne Booth-Verfahren. Der Vorteil liegt aber darin, dass in der Informatik keine Gleichverteilung von Zahlen vorliegt. Vielmehr gibt es häufig Zahlen mit vielen Nullen und durch das Zweierkomplement bei negativen Zahlen häufig viele Einsen am Anfang. Nur durch diese Tatsache hat das Booth-Verfahren Vorteile gegenüber einer normalen Multiplikation.

Die Erweiterung des Booth-Verfahrens ist das Bit-Pair-Verfahren, bei dem immer zwei Stellen zusammengefasst werden.

Siehe auch

• APEXC-Computer

Weblinks

Tutorium zum Booth-Algorithmus