Bit-Pair-Verfahren
# Bit-Pair-Verfahren

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.

## Idee

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

* $2x-x=x$

Analog:

* $-2x+x=-x$

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.

## Verfahren

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.

### Beispiel

Es soll $3*89$ berechnet werden.

* $3_{10}=00000011_{2}$
* $89_{10}=01011001_{2}$

Auf den Faktor $89_{10}$ werden nacheinander die entsprechenden Verfahren angewandt:

| $89_{10}=$ | 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 | $3_{10}$ |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 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 | $3_{10}$ |
| + | 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 $3_{10}$ |
| + | 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 $3_{10}$ |
| + | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | | | | | | keine Addition |
| + | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | | | | | | | | $3_{10}$ |
| | 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 |

* $0100001011_{2}=267_{10}=3_{10}*89_{10}$

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.

