Bit pair process
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
- Arithmetic Multiplication Circuits (English; PDF file; 134 kB)
- TN Rajashekhara, O. Kal: Fast multiplier design using redundant signed-digit numbers . In: International Journal of Electronics . tape 69 , no. 3 , September 1990, ISSN 0368-1947 , p. 359-368 , doi : 10.1080 / 00207219008920321 .