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 <math>x</math> mit 2 multipliziert und anschließend von der entstandenen Zahl subtrahiert, ergibt sich wieder <math>x</math>:
- <math>2x - x = x</math>
Analog:
- <math>-2x + x = -x</math>
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 <math>3 * 89</math> berechnet werden.
- <math>3_{10} = 00000011_2</math>
- <math>89_{10} = 01011001_2</math>
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 |
- <math>0100001011_2 = 267_{10} = 3_{10} * 89_{10}</math>
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.
Literatur
- Arithmetic Multiplication Circuits (engl.; PDF-Datei; 134 kB)
- {{#invoke:Vorlage:Literatur|f}}