Bit pair process

from Wikipedia, the free encyclopedia

The bit-pair method ( bit-pair recoding ) is an algorithm for accelerating the computer-aided multiplication of two numbers in two's complement representation. It is an extension of the Booth algorithm .

idea

If a number is multiplied by 2 and then subtracted from the resulting number, the result is again :

Analogous:

The Booth algorithm, however, may generate code that would perform such (unnecessary) calculations. This can be simplified with the bit-pair method.

Procedure

Adjacent "* (+ 1)" and "* (- 1)" in the booth code are summarized as follows:

Booth code: ... +1 −1 ...
after simplification: ... 0 +1 ...
Booth code: ... −1 +1 ...
after simplification: ... 0 −1 ...

There is no addition. The calculation becomes more efficient.

example

It should be calculated.

The corresponding procedures are applied successively to the factor 89 10 :

89 10 = 0 1 0 1 1 0 0 1
after using the Booth algorithm: +1 −1 +1 0 −1 0 +1 −1
after using the bit-pair procedure: +1 0 −1 0 −1 0 0 +1

The calculation is analogous to the Booth algorithm:

0 0 0 0 0 0 1 1 3 10
x +1 0 −1 0 −1 0 0 +1 Coding of the 2nd factor
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 3 10
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 no addition
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 no addition
+ 1 1 1 1 1 1 1 1 1 1 0 1 2nd complement of 3 10
+ 0 0 0 0 0 0 0 0 0 0 0 no addition
+ 1 1 1 1 1 1 1 1 0 1 2nd complement of 3 10
+ 0 0 0 0 0 0 0 0 0 no addition
+ 0 0 0 0 0 0 1 1 3 10
0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 Result without overflow
2 2 2 2 2 2 2 1 1 0 0 0 0 0 0 transfer

The result is correct, but executed with 4 addition operations instead of 6. It should be noted that 89 instead of 3 have been simplified with the algorithms here for example purposes only. In practice it would of course be most efficient to calculate 89 * 3 “directly” in this case. That would only require 2 additions.

literature