Using the standard multiplication algorithm, a run of 1s in the multiplier in means that we have to add as many successively shifted multiplicand values as the number of 1s in the run.

`
0010 _{two}
x 0111_{two}
--------
+ 0010 multiplicand shifted by 0 bits
left
+ 0010 multiplicand shifted by 1 bit
left
+ 0010 multiplicand shifted by 2 bits
left
+ 0000
--------
00001110_{two}
`

We can rewrite `2 ^{i} - 2^{i-j}` as:

2
^{i} - 2^{i-j} | =
| 2
^{i-j} x (2^{j} - 1) |

=
| 2
^{i-j} x (2^{j-1} + 2^{j-2} + ... +
2^{0}) | |

=
| 2
^{i-1} + 2^{i-2} + ... + 2^{i-j} |

For example `0111 _{two} = 2^{3}_{ten} -
2^{0}_{ten}`. So

`0010 _{two} x (1000_{two} - 0001_{two})`

Or to make it look like the multiplication before:

`
0010 _{two}
x 0111_{two}
--------
- 0010 = 0010_{two} x -
0001_{two}
+ 0000
+ 0000
+ 0010 = 0010_{two} x +
1000_{two}
--------
00001110_{two}
`

The core of Booth's algorithm is examining two bits of the multiplicand at each step. The following diagram is the third multiplication algorithm in the textbook, only modified a little.

Note that Booth's algorithm uses an extra bit on the right of the least significant bit in the product register. This bit starts out as 0 because:

- if bit 0 is a 1, we want to subtract the multiplicand from the product register
- if bit 0 is a 0, we do not want to perform any operations

When the shift in step 2 in the diagram is performed, the rightmost (least significant) bit in the product register is placed into this extra bit.

Why does Booth's algorithm work for negative numbers? To see why, we need to rewrite a multiplication into the steps that Booth's algorithm operates on.

Booth's algorithm looks at adjacent pairs of bits. Suppose that
`a _{i}` is bit

a
_{i} | a
_{i-1} | Operation | a
_{i-1} - a_{i} |
---|---|---|---|

0 | 0 | Do nothing | 0 |

0 | 1 | Add b
| 1 |

1 | 0 | Subtract b
| -1 |

1 | 1 | Do nothing | 0 |

The rightmost column is the value we multiply the shifted value of `b`
by before adding it to the Product register.

We can rewrite the product `a x b` as:

`
(a _{-1} - a_{0}) x b x 2^{0}`

+ (a_{0} - a_{1}) x b x 2^{1}

+ (a_{1} - a_{2}) x b x 2^{2}

...

+ (a_{30} - a_{31}) x b x 2^{31}

which can be simplified to (using the equation for `2 ^{i} -
2^{i-j}` and the fact that

`
b x (a _{31} x -2^{31} + a_{30} x 2^{30} +
a_{29} x 2^{29} + ... + a_{1} x 2^{1} +
a_{0} x 2^{0})
`

We are multiplying `b` by the two's complement representation of
`a`!

Main Page Section Notes Page