Booth's multiplication algorithm: Difference between revisions

Revision as of 12:12, 20 January 2017

Revision as of 06:27, 23 February 2017

Line 81:

: <math> (\ldots 0 \overbrace{1 \ldots 1}^{n} 0 \ldots)_{2} \equiv (\ldots 1 \overbrace{0 \ldots 0}^{n} 0 \ldots)_{2} - (\ldots 0 \overbrace{0 \ldots 1}^{n} 0 \ldots)_2. </math>

Hence, the multiplication can actually be replaced by the stringstrings of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that it is not necessary to do anything but shift while dealing with 0s in a binary multiplier, and is similar to using the mathematical property that 99&nbsp;=&nbsp;100&nbsp;&minus;&nbsp;1 while multiplying by 99.

This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of a single 1 in a block). Thus,