79.234.77.211: Änderung 174012327 von 79.234.77.211 rückgängig gemacht;

2018-02-14T18:41:06Z

Änderung 174012327 von 79.234.77.211 rückgängig gemacht;

Neue Seite

Der '''Booth-Algorithmus''' ist ein [[Algorithmus]] für die [[Multiplikation]] zweier Zahlen in [[Zweierkomplement]]-Darstellung. Er wurde 1951 von [[Andrew Donald Booth]] bei Arbeiten zur [[Kristallographie]] am [[Birkbeck, University of London|Birkbeck College]] entwickelt.

== Verfahren ==
* Sei x die Bitanzahl des Multiplikanden und y die Bitanzahl des Multiplikators.
* Zeichne ein dreireihiges Raster mit <math>x+y+1</math> Spalten. Bezeichne die Zeilen mit A (Addition), S (Subtraktion) und P (Produkt).
* Notiere die ersten x Bits jeder Zeile folgendermaßen:
** A: Multiplikand
** S: negierter Multiplikand (im Zweierkomplement)
** P: Nullen
* Die nächsten y Bits jeder Zeile sind folgendermaßen zu füllen:
** A: Nullen
** S: Nullen
** P: Multiplikator
* Die letzte Spalte wird mit Nullen aufgefüllt.
* Führe folgende beide Schritte y-mal durch:
*# Sind die letzten beiden Bits von ''P''
*#* 00 oder 11: Tue nichts
*#* 01 <math>P = P + A</math>. Ignoriere jeglichen Überlauf.
*#* 10 <math>P = P + S</math>. Ignoriere jeglichen Überlauf.
*# [[Schieberegister|Schiebe]] das Produkt arithmetisch um eine Position nach rechts.
* In den vorderen <math>x+y</math> Bits steht nun das Produkt (das letzte Bit wird ignoriert).

== Idee ==
Man macht sich zunutze, dass sich jede Zahl b als Differenz zweier Zahlen c und d darstellen lässt:

<math>\mbox{Sei }b = c-d</math>

Dann lässt sich jede beliebige Multiplikation von b mit einem Faktor a folgendermaßen umformen:

<math>a \cdot b = a\cdot (c-d) = a \cdot c - a \cdot d</math>

Vorteile gegenüber der "Papier und Bleistift"-Methode bietet dieses Verfahren bei Zahlen, die in der Binärdarstellung lange gleichwertige [[Bit]]ketten aufweisen. Diese werden beim Booth-Verfahren „übersprungen“. Darauf basierend erlaubt das Booth-Verfahren auch eine effiziente Multiplikation für Binärzahlen im [[Zweierkomplement]], d. h. der Algorithmus hat den Vorteil, dass man die [[Vorzeichen (Zahl)|Vorzeichen]] der beiden Faktoren nicht beachten muss.

=== Beispiel ===
Will man <math>30_{10} = 00011110_2</math> mit einer Zahl X multiplizieren, benötigte man bei der traditionellen Methode drei Additionen: <math>10_2\cdot X+100_2\cdot X+1000_2\cdot X+10000_2\cdot X</math>.
Das Booth-Verfahren hingegen braucht nur eine:
<math>100000_2\cdot X-10_2\cdot X</math>.

Die Subtraktion lässt sich im Zweierkomplement wie eine Addition rechnen, die Multiplikation mit einem Vielfachen von 2 entspricht nur einer Verschiebung der Stellen nach links (Shift-Operation). Somit dient das Verfahren einer effizienten Multiplikation in Computern.

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 <math>44_{10}=(00101100)_2</math> und <math>17_{10}=(00010001)_2</math>
=== Kodierung eines Faktors nach Booth ===
{| style="border:1px solid #AAAAAA; background-color:#F9F9F9; padding:10px; text-align:center;"
| rowspan="2" style="padding-right:20px;" | '''Schritt 1'''
|0
|1
|0
|1
|1
|0
|'''0'''
| style="color:#888888" |'''0'''
|-
|
|
|
|
|
|
|'''0'''
|-
| rowspan="2" style="padding-right:20px;" | '''Schritt 2'''
|0
|1
|0
|1
|1
|'''0'''
|'''0'''
| style="color:#888888" |0
|-
|
|
|
|
|
|'''0'''
|0
|-
| rowspan="2" style="padding-right:20px;" | '''Schritt 3'''
|0
|1
|0
|1
|'''1'''
|'''0'''
|0
| style="color:#888888" |0
|-
|
|
|
|
|'''-1'''
|0
|0
|-
| rowspan="2" style="padding-right:20px;" | '''Schritt 4'''
|0
|1
|0
|'''1'''
|'''1'''
|0
|0
| style="color:#888888" |0
|-
|
|
|
|'''0'''
| −1
|0
|0
|-
| rowspan="2" style="padding-right:20px;" | '''Schritt 5'''
|0
|1
|'''0'''
|'''1'''
|1
|0
|0
| style="color:#888888" |0
|-
|
|
|'''+1'''
|0
| −1
|0
|0
|-
| rowspan="2" style="padding-right:20px;" | '''Schritt 6'''
|0
|'''1'''
|'''0'''
|1
|1
|0
|0
| style="color:#888888" |0
|-
|
|'''-1'''
| +1
|0
| −1
|0
|0
|-
| rowspan="2" style="padding-right:20px;" | '''Schritt 7'''
|'''0'''
|'''1'''
|0
|1
|1
|0
|0
| style="color:#888888" |0
|-
|'''+1'''
| −1
| +1
|0
| −1
|0
|0
|}

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

=== Multiplikation ===
{|class="wikitable" style="text-align:center"
|-
| style="width:2em" |
| style="width:2em" |
| style="width:2em;background:#CCC" |
| style="width:2em;background:#CCC" |
| style="width:2em;background:#CCC" |
| style="width:2em;background:#CCC" |
| style="width:2em;background:#CCC" |
| style="width:2em;background:#CCC" |
| style="width:2em;background:#CCC" |
| style="width:2em;background:#AAA" |0
| style="width:2em;background:#AAA" |0
| style="width:2em;background:#AAA" |0
| style="width:2em;background:#AAA" |1
| style="width:2em;background:#AAA" |0
| style="width:2em;background:#AAA" |0
| style="width:2em;background:#AAA" |0
| style="width:2em;background:#AAA" |1
| style="text-align:left" | 2. Faktor
|-
|x
|
|style="background:#CCC" |
|style="background:#CCC" |
|style="background:#CCC" |
|style="background:#CCC" |
|style="background:#CCC" |
|style="background:#CCC" |
|style="background:#CCC" |
|style="background:#AAA" |0
|style="background:#AAA" | +1
|style="background:#AAA" | −1
|style="background:#AAA" | +1
|style="background:#AAA" |0
|style="background:#AAA" | −1
|style="background:#AAA" |0
|style="background:#AAA" |0
|style="text-align:left" | Kodierung des 1. Faktors
|-
| +
|
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|0
|0
|0
|0
|0
|0
|0
|0
|style="text-align:left" | keine Addition
|-
| +
|
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|0
|0
|0
|0
|0
|0
|0
|0
|style="background:#CCC"|
|style="text-align:left" | keine Addition
|-
| +
|
|style="background:#CCC" |1
|style="background:#CCC" |1
|style="background:#CCC" |1
|style="background:#CCC" |1
|style="background:#CCC" |1
|1
|1
|1
|0
|1
|1
|1
|1
|style="background:#CCC"|
|style="background:#CCC"|
|style="text-align:left" | 2er-Komplement (2. Faktor)
|-
| +
|
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|0
|0
|0
|0
|0
|0
|0
|0
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="text-align:left" | keine Addition
|-
| +
|
|style="background:#CCC" |0
|style="background:#CCC" |0
|style="background:#CCC" |0
|0
|0
|0
|1
|0
|0
|0
|1
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="text-align:left" | 2. Faktor
|-
| +
|
|style="background:#CCC" |1
|style="background:#CCC" |1
|1
|1
|1
|0
|1
|1
|1
|1
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="text-align:left" | 2er-Komplement (2. Faktor)
|-
| +
|
|style="background:#CCC" |0
|0
|0
|0
|1
|0
|0
|0
|1
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="text-align:left" | 2. Faktor
|-
| +
|
|0
|0
|0
|0
|0
|0
|0
|0
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|style="background:#CCC"|
|keine Addition
|-
|style="background:#CCC"|1
|style="background:#CCC"|0
|style="background:#AAA"|0
|style="background:#AAA"|0
|style="background:#AAA"|0
|style="background:#AAA"|0
|style="background:#AAA"|0
|style="background:#AAA"|1
|style="background:#AAA"|0
|style="background:#AAA"|1
|style="background:#AAA"|1
|style="background:#AAA"|1
|style="background:#AAA"|0
|style="background:#AAA"|1
|style="background:#AAA"|1
|style="background:#AAA"|0
|style="background:#AAA"|0
|style="text-align:left" | 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 genauso viele 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

== Quellen ==
*[http://www.dcs.bbk.ac.uk/about/history/booth.php The work of Professor Andrew D. Booth], Department of Computer Science and Information Systems, Birkbeck College (engl.)

== Weblinks ==
* [http://www.ecs.umass.edu/ece/koren/arith/simulator/Booth/ automatisches Ausrechnen einer Booth-Multiplikation]

[[Kategorie:Algorithmus]]
[[Kategorie:Rechnerarchitektur]]

Booth-Algorithmus - Versionsgeschichte

79.234.77.211: Änderung 174012327 von 79.234.77.211 rückgängig gemacht;