Shift-and-Add Multiplier Datapath

Shift-and-Add Multiplier

A sequential multiplication architecture that processes one multiplier bit per iteration while reusing an adder across clock cycles.

ShiftAddMultiplier

The project's iterative multiplication datapath that stores the working multiplicand, working multiplier, accumulated result, and output product.

Trading Space for Time

The architectural strategy of reusing arithmetic hardware across multiple clock cycles instead of performing all partial-product work concurrently.

State Is the Price of Reuse

The principle that spreading multiplication across multiple cycles requires registers to preserve intermediate progress between clock edges.

reg [(2 * WIDTH) - 1:0] MultiplicandRegister;

Stores the current shifted multiplicand contribution used by the shift-and-add datapath.

reg [WIDTH - 1:0] MultiplierRegister;

Stores the working multiplier whose least significant bit determines whether the current multiplicand contribution should be added.

reg [(2 * WIDTH) - 1:0] Accumulator;

Stores the running sum of all partial-product contributions accepted so far.

Product

The registered output containing the multiplication result accumulated by the datapath.

MultiplierBit

Exposes the current least significant bit of MultiplierRegister.

assign MultiplierBit = MultiplierRegister[0];

Continuously exposes the current add-or-skip decision bit from the working multiplier.

MultiplierRegister[0]

The current multiplier bit examined during each shift-and-add iteration.

Because the multiplier is shifted right after every iteration, causing the next original multiplier bit to move into bit position 0.

Why can the sequential multiplier repeatedly inspect MultiplierRegister[0] instead of separately indexing every bit of B?

load

Control signal that initializes the ShiftAddMultiplier for a new multiplication operation.

step

Control signal that commands the ShiftAddMultiplier to perform one multiplication iteration.

posedge clk

The event on which the ShiftAddMultiplier's working state is updated.

Synchronous Reset

The reset behavior used by ShiftAddMultiplier because its reset condition is evaluated inside always @(posedge clk).

MultiplicandRegister <= {(2 * WIDTH){1'b0}};

Resets the working multiplicand register to zero.

MultiplierRegister <= {WIDTH{1'b0}};

Resets the working multiplier register to zero.

Accumulator <= {(2 * WIDTH){1'b0}};

Resets the running multiplication sum to zero.

Product <= {(2 * WIDTH){1'b0}};

Resets the registered multiplication output to zero.

MultiplicandRegister <= {{WIDTH{1'b0}}, A};

Loads A into the lower WIDTH bits of the 2×WIDTH working multiplicand register while zero-extending it.

MultiplierRegister <= B;

Loads operand B into the working multiplier register.

Accumulator <= {(2 * WIDTH){1'b0}};

Clears all accumulated contributions when a new multiplication operation is loaded.

Product <= {(2 * WIDTH){1'b0}};

Clears the visible product when a new multiplication operation is loaded.

Because the shift-and-add process must begin with no previously accumulated partial-product contributions.

Why is Accumulator cleared when load is asserted?

Because the multiplicand will shift left during later iterations and therefore requires enough width to preserve contributions throughout the 2×WIDTH product range.

Why is MultiplicandRegister 2×WIDTH bits wide?

Because only the original WIDTH multiplier bits need to be examined one at a time.

Why is MultiplierRegister only WIDTH bits wide?

if (MultiplierRegister[0])

Determines whether the current shifted multiplicand should be added into the running result during this iteration.

MultiplierRegister[0] = 1

The current multiplicand contribution is included in the accumulated product.

MultiplierRegister[0] = 0

The current multiplicand contribution is skipped.

Accumulator <= Accumulator + MultiplicandRegister;

Adds the current shifted multiplicand contribution into the running multiplication result.

Accumulator <= Accumulator;

Explicitly preserves the existing accumulated result when the current multiplier bit is 0.

Product <= Accumulator + MultiplicandRegister;

Updates Product with the newly calculated accumulated value when the current multiplier bit is 1.

Product <= Accumulator;

Updates Product with the unchanged accumulated value when the current multiplier bit is 0.

Because nonblocking assignments do not immediately change Accumulator during the current clocked evaluation, so Product <= Accumulator would otherwise receive the old accumulator value.

Why does the multiplier use Product <= Accumulator + MultiplicandRegister when MultiplierRegister[0] is 1?

Nonblocking Assignment Semantics

The reason Product must explicitly use the newly calculated sum rather than relying on Accumulator's new value during the same clock edge.

MultiplicandRegister <= MultiplicandRegister << 1;

Shifts the working multiplicand left by one bit after each multiplication step.

MultiplierRegister

Shifts the working multiplier right by one bit after each multiplication step.

Because each successive multiplier bit represents twice the binary weight of the previous multiplier bit.

Why is MultiplicandRegister shifted left after every iteration?

Because shifting left by one position multiplies the current contribution by 2, aligning it with the next multiplier bit's binary weight.

How does shifting MultiplicandRegister left prepare the datapath for the next partial product?

Because the next original multiplier bit must be moved into MultiplierRegister[0], where the datapath performs its add-or-skip test.

Why is MultiplierRegister shifted right after every iteration?

Opposite Shifts

The multiplicand shifts left to increase its positional weight while the multiplier shifts right to bring the next decision bit into the LSB position.

Observe → conditionally add → shift multiplicand left → shift multiplier right

The essential datapath actions of one shift-and-add multiplication iteration.

One Useful Iteration

Processes one original multiplier bit and therefore accounts for one possible partial-product contribution.

WIDTH Useful Iterations

The number of iterations required to process every bit of a WIDTH-bit multiplier when one multiplier bit is handled per step.

Because after WIDTH useful iterations every original bit of B has reached the LSB decision position and its corresponding contribution has either been accumulated or skipped.

Why is shift-and-add multiplication complete after WIDTH useful iterations?

Partial Product in the Sequential Multiplier

The current value of MultiplicandRegister when the current MultiplierRegister[0] is 1.

Accumulator as Algorithmic State

The accumulator preserves the sum of previously accepted partial-product contributions across clock cycles.

MultiplicandRegister as Algorithmic State

Records which shifted version of the multiplicand corresponds to the current iteration.

MultiplierRegister as Algorithmic State

Records which multiplier bits remain to be processed and places the current decision bit at its LSB.

Shifting is part of the multiplication itself.

Is shifting merely bookkeeping around the sequential multiplication algorithm?

Shifting allows one reusable adder to account for successive binary weights without generating every shifted partial product as separate concurrent hardware.

What is the architectural significance of shifting in ShiftAddMultiplier?

if (load) … else if (step)

Gives loading a new multiplication operation priority over performing an iteration on the same clock edge.

Because the datapath must first establish the initial operands and clear the previous accumulated state before any multiplication iteration can be meaningful.

Why does load have priority over step in ShiftAddMultiplier?

Sequential Multiplier Datapath

The part of the multiplier that knows how to perform and preserve the arithmetic transformations of one multiplication step, but does not itself decide when the complete operation should begin or finish.