Visualization of Booth Multiplication
A = 3
00011
B = -7
11001
Bits =
| Step | Sub Step | Action | Partial Product | Additional Bit |
|---|
| 0 | 0 | Init | 00000011001 | 0 |
| 0 | 1 | Sub | 11110111001 | 0 |
| 1 | 2 | Shift | 11111011100 | 1 |
| 1 | 3 | Add | 00000111100 | 1 |
| 2 | 4 | Shift | 00000011110 | 0 |
| 3 | 5 | Shift | 00000001111 | 0 |
| 3 | 6 | Sub | 11110101111 | 0 |
| 4 | 7 | Shift | 11111010111 | 1 |
| 5 | 8 | Shift | 11111101011 | 1 |
Answer is -21
Algorithm
- `Partial Product` is initialized to `B` (zero extension).
- For each step after `Init` or `Shift`, check the LSB of `Partial Product` and `Additional Bit` to determine the next step.
- `Add` or `Substract` `A` shifted by `Bits` or `Shift` again.
- Repeat until `Shift` `Bits`-times.
Caveats
- `Partial Product` has an additional sign bit to handle `A` = -2^{n-1} case.
- `Step` column is counted by the number of `Shift` steps.