Sequential Multiplier in Verilog: Shift-and-Add FSM Design

A combinational array multiplier computes a full product in one step, but it costs a large amount of logic and has a long critical path. When area matters more than single-cycle latency, engineers reach for a sequential multiplier verilog code built around the classic shift-and-add algorithm — the same longhand method you learned in school, executed one bit per clock by a small finite state machine (FSM).

This page delivers two complete, synthesizable designs. The first is a fixed-latency unsigned multiplier that always runs W steps; the second is an early-terminating variant that stops once the remaining multiplier bits are all zero. Both ship with self-checking testbenches that verify 13×11, 255×255 and more against the golden a*b result.

Shift-and-add FSM multiplier

The datapath holds an accumulator, a left-shifting zero-extended multiplicand, and a right-shifting multiplier. On start the operands load; each RUN cycle conditionally adds the multiplicand when the multiplier LSB is 1, then shifts. After W steps the FIN state latches the product and raises done.

// Unsigned shift-and-add sequential multiplier (FSM)
module seq_mult #(parameter W = 8) (
    input                 clk,
    input                 rst_n,
    input                 start,
    input      [W-1:0]    a,       // multiplicand
    input      [W-1:0]    b,       // multiplier
    output reg [2*W-1:0]  product,
    output reg            done
);
    // FSM states
    localparam IDLE = 2'd0;
    localparam RUN  = 2'd1;
    localparam FIN  = 2'd2;

    reg [1:0]       state;
    reg [2*W-1:0]   accum;        // accumulator (holds partial product)
    reg [2*W-1:0]   mcand;        // shifted multiplicand
    reg [W-1:0]     mplier;       // shifting multiplier
    integer         count;        // step counter

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            state   <= IDLE;
            accum   <= {(2*W){1'b0}};
            mcand   <= {(2*W){1'b0}};
            mplier  <= {W{1'b0}};
            product <= {(2*W){1'b0}};
            done    <= 1'b0;
            count   <= 0;
        end else begin
            case (state)
                IDLE: begin
                    done <= 1'b0;
                    if (start) begin
                        accum  <= {(2*W){1'b0}};
                        mcand  <= {{W{1'b0}}, a};   // zero-extend multiplicand
                        mplier <= b;
                        count  <= 0;
                        state  <= RUN;
                    end
                end
                RUN: begin
                    // if current LSB of multiplier is 1, add multiplicand
                    if (mplier[0])
                        accum <= accum + mcand;
                    // shift multiplicand left, multiplier right
                    mcand  <= mcand  << 1;
                    mplier <= mplier >> 1;
                    count  <= count + 1;
                    if (count == W-1)
                        state <= FIN;
                end
                FIN: begin
                    product <= accum;   // accum already holds a*b
                    done    <= 1'b1;
                    state   <= IDLE;
                end
                default: state <= IDLE;
            endcase
        end
    end
endmodule

module tb;
    localparam W = 8;
    reg              clk, rst_n, start;
    reg  [W-1:0]     a, b;
    wire [2*W-1:0]   product;
    wire             done;
    integer          errors;

    seq_mult #(.W(W)) dut (
        .clk(clk), .rst_n(rst_n), .start(start),
        .a(a), .b(b), .product(product), .done(done)
    );

    // clock generation
    initial clk = 1'b0;
    always #5 clk = ~clk;

    // task: run one multiply and self-check
    task run_mult;
        input [W-1:0] ta, tb;
        reg   [2*W-1:0] expected;
        begin
            @(negedge clk);
            a = ta; b = tb; start = 1'b1;
            @(negedge clk);
            start = 1'b0;
            // wait for completion
            wait (done == 1'b1);
            @(negedge clk);
            expected = ta * tb;
            if (product === expected) begin
                $display("PASS: %0d * %0d = %0d", ta, tb, product);
            end else begin
                $display("FAIL: %0d * %0d = %0d (expected %0d)", ta, tb, product, expected);
                errors = errors + 1;
            end
        end
    endtask

    initial begin
        errors = 0;
        start  = 1'b0;
        a = 0; b = 0;
        rst_n = 1'b0;
        repeat (2) @(negedge clk);
        rst_n = 1'b1;

        run_mult(8'd13,  8'd11);   // 143
        run_mult(8'd255, 8'd255);  // 65025
        run_mult(8'd0,   8'd200);  // 0
        run_mult(8'd1,   8'd1);    // 1
        run_mult(8'd100, 8'd3);    // 300

        if (errors == 0)
            $display("ALL TESTS PASS");
        else
            $display("TESTS FAILED: %0d", errors);
        $finish;
    end
endmodule

PASS: 13 * 11 = 143
PASS: 255 * 255 = 65025
PASS: 0 * 200 = 0
PASS: 1 * 1 = 1
PASS: 100 * 3 = 300
ALL TESTS PASS
Every case — including the 255×255 = 65025 worst case — matches a*b, and the run ends with ALL TESTS PASS.

Early-termination variant
Instead of a fixed step counter, this version watches the multiplier register. The moment it becomes all-zero, no further partial products can change the result, so the FSM asserts done immediately. Small operands finish in far fewer cycles.
// Early-termination sequential multiplier: stops as soon as the
// remaining multiplier bits are all zero, so small operands finish sooner.
module seq_mult_fast #(parameter W = 8) (
    input                 clk,
    input                 rst_n,
    input                 start,
    input      [W-1:0]    a,
    input      [W-1:0]    b,
    output reg [2*W-1:0]  product,
    output reg            done
);
    localparam IDLE = 1'b0;
    localparam RUN  = 1'b1;

    reg             state;
    reg [2*W-1:0]   accum;
    reg [2*W-1:0]   mcand;
    reg [W-1:0]     mplier;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            state   <= IDLE;
            accum   <= {(2*W){1'b0}};
            mcand   <= {(2*W){1'b0}};
            mplier  <= {W{1'b0}};
            product <= {(2*W){1'b0}};
            done    <= 1'b0;
        end else begin
            case (state)
                IDLE: begin
                    done <= 1'b0;
                    if (start) begin
                        accum  <= {(2*W){1'b0}};
                        mcand  <= {{W{1'b0}}, a};
                        mplier <= b;
                        state  <= RUN;
                    end
                end
                RUN: begin
                    if (mplier == {W{1'b0}}) begin
                        // no 1-bits left: result is final
                        product <= accum;
                        done    <= 1'b1;
                        state   <= IDLE;
                    end else begin
                        if (mplier[0])
                            accum <= accum + mcand;
                        mcand  <= mcand  << 1;
                        mplier <= mplier >> 1;
                    end
                end
            endcase
        end
    end
endmodule

module tb;
    localparam W = 8;
    reg              clk, rst_n, start;
    reg  [W-1:0]     a, b;
    wire [2*W-1:0]   product;
    wire             done;
    integer          errors, cycles;

    seq_mult_fast #(.W(W)) dut (
        .clk(clk), .rst_n(rst_n), .start(start),
        .a(a), .b(b), .product(product), .done(done)
    );

    initial clk = 1'b0;
    always #5 clk = ~clk;

    task run_mult;
        input [W-1:0] ta, tb;
        reg   [2*W-1:0] expected;
        begin
            @(negedge clk);
            a = ta; b = tb; start = 1'b1;
            @(negedge clk);
            start = 1'b0;
            cycles = 0;
            while (done !== 1'b1) begin
                @(negedge clk);
                cycles = cycles + 1;
            end
            expected = ta * tb;
            if (product === expected)
                $display("PASS: %0d * %0d = %0d  (%0d run cycles)", ta, tb, product, cycles);
            else begin
                $display("FAIL: %0d * %0d = %0d (expected %0d)", ta, tb, product, expected);
                errors = errors + 1;
            end
        end
    endtask

    initial begin
        errors = 0; start = 1'b0; a = 0; b = 0;
        rst_n = 1'b0;
        repeat (2) @(negedge clk);
        rst_n = 1'b1;

        run_mult(8'd13,  8'd11);   // b=11 -> 4 effective bits
        run_mult(8'd255, 8'd255);  // worst case, all 8 bits
        run_mult(8'd200, 8'd1);    // b=1 -> finishes almost immediately
        run_mult(8'd7,   8'd8);    // 56

        if (errors == 0) $display("ALL TESTS PASS");
        else             $display("TESTS FAILED: %0d", errors);
        $finish;
    end
endmodule
PASS: 13 * 11 = 143  (5 run cycles)

PASS: 255 * 255 = 65025  (9 run cycles)

PASS: 200 * 1 = 200  (2 run cycles)

PASS: 7 * 8 = 56  (5 run cycles)

ALL TESTS PASS
Notice the per-case cycle count: 200×1 finishes in 2 run cycles while 255×255 still needs the full 9. Average throughput improves for data with few set bits.
How the shift-and-add algorithm works
Multiplication is repeated conditional addition. For each bit of the multiplier b, starting from the LSB, you test whether that bit is 1. If it is, you add the multiplicand a — shifted left by the bit position — into a running accumulator. After W iterations the accumulator holds the full 2W-bit product. The hardware mirrors this exactly: rather than shifting the accumulator, we zero-extend a into a 2W-bit mcand register and shift it left by one each cycle, while shifting mplier right so its current LSB is always mplier[0].
The three-state FSM
The control is a tiny Moore machine. IDLE waits for start and clears done; the load happens on the same edge that moves to RUN. RUN performs the conditional add and the two shifts, incrementing a counter until it reaches W-1. FIN copies the accumulator into product, raises done for exactly one cycle, and returns to IDLE. Keeping load, compute and output in separate states makes the timing contract unambiguous: the consumer samples product only when done is high.
Synthesis notes
This design uses one 2W-bit adder, three shift/accumulate registers and a 2-bit state register — dramatically less area than a W×W array multiplier, at the cost of W clocks per result. Because mcand is 2W bits wide and shifted left, no product bit is ever lost. The reset is asynchronous active-low (negedge rst_n), the common convention in ASIC flows. Everything is strict Verilog-2005: reg/wire, an integer loop/count variable, and width-parameterized vectors via parameter W.
Common pitfalls
The classic bug is making mcand only W bits wide — the high half of the product then vanishes. A second trap is reading product before done; in the fixed version the accumulator is not copied out until FIN, so always gate on the flag. Watch the done pulse width too: it is a single-cycle strobe, not a level, so a slow consumer must latch it. Finally, if you re-pulse start while a multiply is in flight it is ignored, because start is only sampled in IDLE.
Interview angle
Interviewers use this problem to probe your grasp of the area-versus-latency trade-off and your FSM discipline. Be ready to explain why the multiplicand is zero-extended to 2W bits, how many cycles a W-bit multiply takes, and how you would extend the design to signed operands (Booth recoding, or sign-extend and correct). The early-termination variant is a natural follow-up: it shows you can reason about data-dependent latency and when it is — or is not — acceptable in a synchronous pipeline.
Have questions about this topic?
Share your question in comments or talk to our mentor team for batch guidance.
▶ Try it in the ChipXpert LabOpen this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Run it in the Lab
← PreviousCarry-Save Adder in Verilog: 3:2 Compressor and a 4-Operand CSA TreeNext →Restoring Divider in Verilog: FSM-Based Unsigned Division Code
Learn Verilog with mentors, labs and placement support
This free series is maintained by the ChipXpert training team in Hyderabad & Bengaluru. Go deeper with instructor-led courses on real EDA tools.
Explore VLSI Courses
Explore more:VerilogSystemVerilogUVMVerificationDigital FundamentalsOnline LabVLSI Courses