Sequential Binary Multiplier
Multiply by repeated add-and-shift over several clocks, using little hardware.
Description
A sequential multiplier computes a product with one adder and shift registers over multiple clocks: examine the multiplier's LSB, conditionally add the multiplicand to the accumulator, then shift right. After n cycles the product appears — trading time for far less hardware than an array multiplier.
- Registers: accumulator A, multiplier Q, multiplicand B, counter P.
- If Q's LSB = 1: A ← A + B.
- Shift {A,Q} right by one (carry into A's MSB).
- Decrement P; repeat until P = 0.
- Product ends up in the {A,Q} register pair.
- One n-bit adder reused each cycle (vs n adders in an array).
- Takes ~n clocks instead of one.
- Classic area-vs-speed trade-off.
- Controlled by a small ASMD/FSM.
- Foundation of Booth and other multiply schemes.
At a glance
What
An add-and-shift multiplier that uses one adder over n clock cycles.
Why
It is far smaller than a combinational array multiplier.
How
If multiplier LSB=1, add multiplicand to accumulator; shift right; repeat n times.
Where
Area-constrained datapaths, simple CPUs, MCUs.
When
When area matters more than single-cycle speed.
Think of it like…
Like long multiplication by hand: look at one digit, maybe add a shifted copy, move over, repeat — one adder doing all the work step by step.
Add-and-shift algorithm
- Registers: accumulator A, multiplier Q, multiplicand B, counter P.
- If Q's LSB = 1: A ← A + B.
- Shift {A,Q} right by one (carry into A's MSB).
- Decrement P; repeat until P = 0.
- Product ends up in the {A,Q} register pair.
Why sequential
- One n-bit adder reused each cycle (vs n adders in an array).
- Takes ~n clocks instead of one.
- Classic area-vs-speed trade-off.
- Controlled by a small ASMD/FSM.
- Foundation of Booth and other multiply schemes.
Datapath registers
| Reg | Holds |
|---|---|
| A | running sum (high product) |
| Q | multiplier (low product) |
| B | multiplicand |
| P | iteration counter |
Functional / block diagram
Functional blocks · arrows animate in the direction data flows
The adder reused each cycle
▶ live simulatorCarry out = 1 · the glowing column is the full-adder stage currently computing; carry ripples right→left.
Real-world applications
The 5 Whys
- 1
Why sequential multiply? One adder instead of n — far less area.
- 2
Why add-and-shift? Mirrors pencil-and-paper multiplication.
- 3
Why shift {A,Q}? Aligns partial products and collects the result.
- 4
Why a counter? Stop after n bits.
- 5
Root cause: reusing one adder over time trades speed for area.
Cheat sheet
Working principle
- If multiplier LSB=1, add multiplicand to accumulator; shift right; repeat n times.
- An add-and-shift multiplier that uses one adder over n clock cycles.
Formulas & Boolean expressions
- if Q0=1: A ← A + B
- shift right {A,Q}
- repeat n times
- If Q's LSB = 1: A ← A + B.
- Decrement P; repeat until P = 0.
- A = running sum (high product)
- Q = multiplier (low product)
- B = multiplicand
Key facts
- Registers: accumulator A, multiplier Q, multiplicand B, counter P.
- One n-bit adder reused each cycle (vs n adders in an array).
Why it exists
- Root cause: reusing one adder over time trades speed for area.