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₁₀ = 00000011₂
• 89₁₀ = 01011001₂

Auf den Faktor 89₁₀ 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

• 0100001011₂ = 267₁₀ = 3₁₀ * 89₁₀

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.