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:
00000011 310x +10 −1 0 −100 +1Kodierung des 2. Faktors +000000000000011 310 +00000000000000keine Addition +0000000000000keine Addition +1111111111012er Komplement von 310 +00000000000keine Addition +11111111012er Komplement von 310 +000000000keine Addition +00000011 310000000100001011Ergebnis ohne Überlauf222222211000000Ü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)
Kategorie:Algorithmus Kategorie:Rechnerarchitektur