Sequential Multiplier with Early Exit

High-performance arithmetic units rely on data-dependent latency to optimize system throughput. A standard sequential shift-and-add multiplier takes N cycles for an N-bit operation, regardless of the operands. By detecting when the remaining multiplier bits are all zero, the control logic can terminate the operation early, bypassing unnecessary clock cycles and saving significant power.

This module is a sequential multiplier that computes the 32-bit product of two 16-bit unsigned integers, a (multiplicand) and b (multiplier). When start is asserted, the module loads the operands and begins computation. For each subsequent clock cycle, it performs a standard shift-and-add step.

The critical feature is the early exit: at the end of any cycle where the remaining unshifted bits of the multiplier evaluate to zero, the module must immediately stop computing, transition to its completion state, and assert done for exactly one clock cycle. The product p must hold the correct result while done is high and remain stable until a new operation begins.

| Signal | Direction | Width | Description | |---|---|---|---| | clk | input | 1 | Positive-edge triggered clock | | rst_n | input | 1 | Asynchronous active-low reset; done and p reset to 0 | | start | input | 1 | High for one cycle to begin multiplication | | a | input | 16 | Multiplicand | | b | input | 16 | Multiplier | | done | output | 1 | Asserted for exactly one cycle when multiplication completes | | p | output | 32 | Product of a and b; valid when done is 1 |

Constraints

• The module must use an asynchronous active-low reset.
• The done signal must assert for exactly one clock cycle per operation.
• The product p must be 0 on reset and hold its final value after done is asserted until a new operation overwrites it.
• The operation must complete in exactly N + 2 clock cycles measured from the start assertion, where N is the index of the highest set bit in b (e.g., if b is 4, N=2, total cycles=4).
• If b is 0, the operation must complete in exactly 1 clock cycle after start.
• If start is asserted while the module is already computing a product, the new start pulse must be ignored until the current operation completes.

Topics

Related problems

• Binary to Gray Code DatapathEasy
• Fixed Point Multiplication with SaturationHard
• Absolute Value with Bit GrowthMedium
• 8 bit Basic ALU with FlagsEasy
• 8-bit Combinational PopcountMedium
• 8-bit Logical Barrel ShifterMedium
• 16-bit Arithmetic Barrel ShifterHard
• Parameterized ALU with Safe DefaultsMedium