8x8 Sequential Shift-and-Add Multiplier

Hard

Problem Statement

Implement an 8-bit by 8-bit unsigned multiplier using the classic shift-and-add algorithm, controlled by a simple start/busy/done handshake. This is a standard multi-cycle datapath design question: the result cannot be produced combinationally in one cycle, so the circuit must coordinate a small control FSM with an arithmetic datapath across several clock cycles. Ports: - `clk` — input, 1 bit, clock - `rst` — input, 1 bit, synchronous active-high reset - `start` — input, 1 bit, pulsed high for one cycle to begin a multiplication - `a` — input, 8 bits (`a[7:0]`), the multiplicand - `b` — input, 8 bits (`b[7:0]`), the multiplier - `product` — output, 16 bits (`product[15:0]`), registered, holds the final unsigned product `a * b` once computed - `busy` — output, 1 bit, high while a multiplication is in progress - `done` — output, 1 bit, pulses high for exactly one clock cycle on the cycle the result in `product` first becomes valid, then returns to 0 Algorithm (shift-and-add), conceptually: 1. On reset: `busy = 0`, `done = 0`, `product` holds 0. 2. While idle (`busy = 0`), if `start` is asserted, the circuit latches `a` and `b` internally, clears its internal accumulator, and begins multiplying — `busy` becomes 1 starting the next cycle. `start` is ignored whenever `busy` is already 1 (an in-progress multiplication is never interrupted or restarted). 3. Internally, over 8 iterations (one per clock cycle while `busy` is 1), the circuit examines the current least-significant bit of the (shifting) multiplier: if it is 1, the current (shifting) multiplicand is added into the accumulator. After each iteration, the multiplicand shifts left by one bit position and the multiplier shifts right by one bit position, in standard shift-and-add fashion. 4. After the 8th iteration completes, `busy` returns to 0 and `done` pulses high for exactly that one cycle, with `product` holding the complete, correct 16-bit unsigned result of `a * b`. On the next cycle, `done` returns to 0, and the circuit is ready to accept a new `start`. The numeric result in `product` must always be the exact unsigned product `a * b` (no overflow is possible since 8 bits × 8 bits always fits in 16 bits). The specific internal cycle-by-cycle mechanics described above are the intended implementation, but what is graded is the externally observable contract: `busy` correctly reflects "an operation is in progress," `done` pulses exactly once per completed operation when the correct result is ready, and `start` is correctly ignored while `busy` is high.

Verilog