Bit-Pair-Verfahren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das Bit-Pair-Verfahren (eng. Bit-Pair-Recoding) ist ein Algorithmus zur Beschleunigung computergestützter Multiplikation zweier Zahlen in Zweierkomplement-Darstellung. Er stellt eine Erweiterung des Booth-Algorithmus dar.

Wird eine Zahl mit 2 multipliziert und anschließend von der entstandenen Zahl subtrahiert, ergibt sich wieder :

Analog:

Der Booth-Algorithmus allerdings generiert unter Umständen Code, der solche (unnötigen) Berechnungen durchführen würde. Das lässt sich durch das Bit-Pair-Verfahren vereinfachen.

Benachbarte „*(+1)“ und „*(-1)“ im Booth-Code werden wie folgt zusammengefasst:

Booth-Code: +1 −1
nach Vereinfachung: 0 +1
Booth-Code: −1 +1
nach Vereinfachung: 0 −1

Es entfällt eine Addition. Die Berechnung wird effizienter.

Es soll berechnet werden.

Auf den Faktor 8910 werden nacheinander die entsprechenden Verfahren angewandt:

8910= 0 1 0 1 1 0 0 1
nach Anwendung des Booth-Algorithmus: +1 −1 +1 0 −1 0 +1 −1
nach Anwendung des Bit-Pair-Verfahrens: +1 0 −1 0 −1 0 0 +1

Die Berechnung erfolgt analog zum Booth-Algorithmus:

0 0 0 0 0 0 1 1 310
x +1 0 −1 0 −1 0 0 +1 Kodierung des 2. Faktors
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 310
+ 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 keine Addition
+ 1 1 1 1 1 1 1 1 1 1 0 1 2er Komplement von 310
+ 0 0 0 0 0 0 0 0 0 0 0 keine Addition
+ 1 1 1 1 1 1 1 1 0 1 2er Komplement von 310
+ 0 0 0 0 0 0 0 0 0 keine Addition
+ 0 0 0 0 0 0 1 1 310
0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 Ergebnis ohne Überlauf
2 2 2 2 2 2 2 1 1 0 0 0 0 0 0 Übertrag

Das Ergebnis ist korrekt, ausgeführt allerdings mit 4 Additionsoperationen, statt mit 6. Es sei angemerkt, dass hier nur zu Beispielzwecken 89 statt 3 mit den Algorithmen vereinfacht wurde. Praktisch wäre es natürlich in diesem Fall am effizientesten 89 * 3 „direkt“ zu berechnen. Das würde nur 2 Additionen erfordern.