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 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.
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 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.
Literatur
- Arithmetic Multiplication Circuits (engl.; PDF-Datei; 134 kB)
- T. N. Rajashekhara, O. Kal: Fast multiplier design using redundant signed-digit numbers. In: International Journal of Electronics. Band 69, Nr. 3, September 1990, ISSN 0368-1947, S. 359–368, doi:10.1080/00207219008920321.