- 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.
Inhaltsverzeichnis
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.
- 310 = 000000112
- 8910 = 010110012
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 - 01000010112 = 26710 = 310 * 8910
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.
Quellen
- Arithmetic Multiplication Circuits (engl.)
- T. N. Rajashekhara und O. Kal: Fast multiplier design using redundant signed-digit numbers. International Journal of Electronics, Heft 69, Ausgabe 3, September 1990, S. 359 bis 368, doi:10.1080/00207219008920321.
Wikimedia Foundation.
