I was going through the text "Computer Organization" by Hamacher et. al. Where I came across the following section about bit-pair recoding technique of multipliers:

A technique called bit-pair recoding of the multiplier results in using at most one summand for each pair of bits in the multiplier.

It is derived directly from the Booth algorithm. Group the Booth-recoded multiplier bits in pairs, and observe the following.

The pair (+1 −1) is equivalent to the pair (0 +1). That is, instead of adding −1 times the multiplicand M at shift position i to +1 × M at position i + 1, the same result is obtained by adding +1 × M at position i.

Other examples are: (+1 0) is equivalent to (0 +2), (−1 +1) is equivalent to (0 −1), and so on.

Thus, if the Booth-recoded multiplier is examined two bits at a time,starting from the right, it can be rewritten in a form that requires at most one version of the multiplicand to be added to the partial product for each pair of multiplier bits.

enter image description here

Be it (+1 0) or (0 +2), for the bit pair, M is added only once to the partial produce.. then why are we considering (0 +2) to be a replacement for (+1 0)? We could have just used (+1 0)... or is it so that our main aim is to produce a pair of the form (0 x) for a pair (p q)? where x=-1, +1, 0, +2, -2; p=0,+1,-1; q=0,+1,-1;

  • \$\begingroup\$ I'd like to see less "quoting from a book" and more active discussion from you about the context and what you already see. Do you understand Booth's algorithm and what basic ideas it incorporates and uses? (Two key ideas.) There are only a few sentences from you and more from a book I do not own, nor have I read. So, some context that you have gathered from reading it would also help. \$\endgroup\$
    – jonk
    Nov 8, 2021 at 3:20
  • \$\begingroup\$ The answer, of course, is that you can perform fewer additions. But you need to work out a few examples to illustrate exactly why this works better. Doesn't the book provide some such examples? \$\endgroup\$
    – jonk
    Nov 8, 2021 at 3:45
  • \$\begingroup\$ @jonk, I know about the basics of Booth's algorithm. A sequence of x bits of 1s is recoded as (2^k-1). What possible benefit we can get is instead of k times addition of the summand, now only 1 subtraction and 1 addition is required. Now this being said, there are certain multipliers for which Booth's algorithm performs worst, in the sense that it would require more additions/subtractions than usual multiplication. A specific example is a sequence of alternating 0s and 1s in the multiplier. We could have done better than not recoding by Booth's algorithm, which recodes it as a sequence of +1-1 \$\endgroup\$ Nov 8, 2021 at 7:00
  • \$\begingroup\$ @jonk, it is this sequence of +1 -1 pairs, for which the bit pair recoding technique obviously gives a lesser no. of additions. As (+1 -1) => (0 +1). So instead of two addition/subtraction, we now have to do only one addition for this pair.I have no issues with this. The place where I am having the problem is bit pairs like (+1 0) or (-1 0), which are recoded to (0 +2) or (0 -2) respectively. In the original pair, we are performing only 1 addition/subtraction, and in the modified pair we are doing the same, and most probably in the same manner. \$\endgroup\$ Nov 8, 2021 at 7:05
  • \$\begingroup\$ @jonk, [i.e. I guess when we see (0 +2), we implement it as first left shifting the partial product by 1 bit to the right and then adding the multiplicand to the higher n bits of the partial product.] This I guess is exactly how (+1 0) would have been implemented. Now this being said, what extra benefit we are getting by using (0 +2) or (0 -2) for (+1 0) or (-1 0) respectively? This is what I cannot get. The answer, of course, is that you can perform fewer additions., I can see this is clearly true for (+1 -1) type of pairs, but that it is also true for (+1 0), I am unable to figure out. \$\endgroup\$ Nov 8, 2021 at 7:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.