2.1 Why Booth's Algorithm?
Naive shift-and-add multiplication adds the multiplicand once per 1-bit of the multiplier and cannot handle negative numbers directly. Booth's algorithm fixes both: it works natively in 2's complement, and it recodes runs of 1s — the run 0111 (7) becomes 1000 − 0001 (8 − 1), replacing three additions with one add and one subtract. Hardware: registers A (accumulator), Q (multiplier), an extra bit Q₋₁, register M (multiplicand), and an arithmetic shift right (ASR) of the combined A,Q,Q₋₁ — ASR preserves the sign bit of A, which is what keeps 2's complement semantics intact.
Decision rule (inspect Q₀Q₋₁ each cycle):
| Q₀ Q₋₁ | Meaning | Action before shifting |
|---|---|---|
| 0 0 / 1 1 | middle of a run | nothing |
| 1 0 | start of a run of 1s | A ← A − M |
| 0 1 | end of a run of 1s | A ← A + M |
Then ASR(A, Q, Q₋₁); repeat n times for n-bit operands.
2.2 Full Worked Example: 7 × (−3), 4 Bits
M = 0111 (7), so −M = 1001. Q = 1101 (−3). Initially A = 0000, Q₋₁ = 0, count = 4.
| Cycle | Q₀Q₋₁ | Operation | A | Q | Q₋₁ |
|---|---|---|---|---|---|
| init | — | — | 0000 | 1101 | 0 |
| 1 | 1 0 | A ← A − M = 1001; then ASR | 1100 | 1110 | 1 |
| 2 | 0 1 | A ← A + M = 1100 + 0111 = 0011; ASR | 0001 | 1111 | 0 |
| 3 | 1 0 | A ← A − M = 0001 + 1001 = 1010; ASR | 1101 | 0111 | 1 |
| 4 | 1 1 | shift only; ASR | 1110 | 1011 | 1 |
Result = A,Q = 1110 1011. Check: invert → 0001 0100, +1 → 0001 0101 = 21, so the product is −21 = 7 × (−3). ✓
Traps that cost marks: (1) the shift is arithmetic — A's sign bit is copied, not zero-filled; (2) carries out of A during A ± M are discarded; (3) exactly n cycles, even when the last action is "shift only"; (4) Q₋₁ starts at 0.
2.3 Restoring Division
Setup for n-bit unsigned division: A = 0 (partial remainder), Q = dividend, M = divisor. Repeat n times: shift AQ left 1; A ← A − M; if A < 0 (sign bit 1) → restore A ← A + M and set Q₀ = 0, else Q₀ = 1. After n steps Q = quotient, A = remainder.
Worked: 7 ÷ 3 (Q = 0111, M = 0011, 4 cycles). Subtraction done as A + (−M), −M = 1101.
| Step | After SHL (A : Q) | A − M | Decision | A | Q |
|---|---|---|---|---|---|
| 1 | 0000 : 111_ | 1101 (neg) | restore, Q₀=0 | 0000 | 1110 |
| 2 | 0001 : 110_ | 1110 (neg) | restore, Q₀=0 | 0001 | 1100 |
| 3 | 0011 : 100_ | 0000 (≥ 0) | keep, Q₀=1 | 0000 | 1001 |
| 4 | 0001 : 001_ | 1110 (neg) | restore, Q₀=0 | 0001 | 0010 |
Quotient Q = 0010 = 2, remainder A = 0001 = 1. Indeed 7 = 3×2 + 1. ✓
2.4 Non-Restoring Division
Restoring wastes an addition whenever the trial subtraction fails. Non-restoring merges the restore with the next step:
- If A ≥ 0: shift AQ left, then A ← A − M.
- If A < 0: shift AQ left, then A ← A + M (instead of restore-then-subtract).
- After each operation: Q₀ = 1 if A ≥ 0, else Q₀ = 0.
- Final correction: if A ends negative, A ← A + M to fix the remainder.
Why it works: restoring then shifting then subtracting computes 2(A + M) − M = 2A + M — exactly what "shift then add M" does in one operation. Result: one add/sub per cycle guaranteed, versus up to two for restoring.
| Property | Restoring | Non-restoring |
|---|---|---|
| Ops per iteration | 1 or 2 (sub + possible restore) | exactly 1 |
| Final correction | never | if remainder negative |
| Control logic | simpler | slightly more complex |
🎯 Exam Focus
- Multiply (−7) × 3 using Booth's algorithm with 4-bit operands; show the full A/Q/Q₋₁ table.
- Why does Booth's algorithm use arithmetic shift right instead of logical shift right?
- Explain how Booth recoding turns the multiplier 0111 into fewer ALU operations.
- Divide 13 by 4 using the restoring algorithm (A, Q, M registers); show every step.
- Derive why non-restoring division's "shift and add" is equivalent to restore-shift-subtract.
- Compare restoring and non-restoring division on operations per cycle and final correction.