Restoring Divider in Verilog: FSM-Based Unsigned Division Code

// Unsigned restoring division FSM
module restoring_divider #(parameter W=8)(
  input clk, rst_n, start,
  input [W-1:0] dividend, divisor,
  output reg [W-1:0] quotient, remainder,
  output reg done
);
  // State encoding (Verilog-2005 parameters, no enum)
  parameter S_IDLE = 2'd0, S_CALC = 2'd1, S_DONE = 2'd2;
  reg [1:0] state;

  reg [W-1:0] q;              // quotient being built
  reg [W:0]   rem_acc;        // remainder accumulator (W+1 bits for sign check)
  reg [W-1:0] div_reg;        // latched divisor
  reg [W-1:0] dvd_reg;        // shifting dividend
  integer     count;          // iteration counter

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      state <= S_IDLE; done <= 1'b0;
      quotient <= 0; remainder <= 0;
    end else begin
      case (state)
        S_IDLE: begin
          done <= 1'b0;
          if (start) begin
            rem_acc <= 0;
            div_reg <= divisor;
            dvd_reg <= dividend;
            q       <= 0;
            count   <= 0;
            state   <= S_CALC;
          end
        end
        S_CALC: begin
          // shift remainder left, bring in MSB of dividend, then trial-subtract
          begin : step
            reg [W:0]  rshift;
            reg [W:0]  trial;
            rshift = {rem_acc[W-1:0], dvd_reg[W-1]}; // shift in top dividend bit
            trial  = rshift - {1'b0, div_reg};
            if (trial[W]) begin
              // negative -> restore, quotient bit 0
              rem_acc <= rshift;
              q       <= {q[W-2:0], 1'b0};
            end else begin
              rem_acc <= trial;
              q       <= {q[W-2:0], 1'b1};
            end
            dvd_reg <= {dvd_reg[W-2:0], 1'b0};
          end
          count <= count + 1;
          if (count == W-1) state <= S_DONE;
        end
        S_DONE: begin
          quotient  <= q;
          remainder <= rem_acc[W-1:0];
          done      <= 1'b1;
          state     <= S_IDLE;
        end
      endcase
    end
  end
endmodule

module tb;
  localparam W = 8;
  reg clk, rst_n, start;
  reg [W-1:0] dividend, divisor;
  wire [W-1:0] quotient, remainder;
  wire done;
  integer errors = 0;

  restoring_divider #(.W(W)) dut(
    .clk(clk), .rst_n(rst_n), .start(start),
    .dividend(dividend), .divisor(divisor),
    .quotient(quotient), .remainder(remainder), .done(done));

  always #5 clk = ~clk;

  task run_case;
    input [W-1:0] a, b;
    input [W-1:0] exp_q, exp_r;
    begin
      if (b == 0) begin
        $display("SKIP: divisor is zero, undefined");
      end else begin
        @(negedge clk); dividend = a; divisor = b; start = 1;
        @(negedge clk); start = 0;
        wait (done == 1'b1);
        @(negedge clk);
        if (quotient === exp_q && remainder === exp_r &&
            (a == quotient*divisor + remainder)) begin
          $display("PASS: %0d / %0d -> q=%0d r=%0d  (check %0d*%0d+%0d=%0d)",
                   a, b, quotient, remainder, quotient, b, remainder,
                   quotient*b+remainder);
        end else begin
          errors = errors + 1;
          $display("FAIL: %0d / %0d -> q=%0d r=%0d (exp q=%0d r=%0d)",
                   a, b, quotient, remainder, exp_q, exp_r);
        end
      end
    end
  endtask

  initial begin
    clk = 0; rst_n = 0; start = 0; dividend = 0; divisor = 1;
    #12 rst_n = 1;
    run_case(8'd100, 8'd7,  8'd14, 8'd2);
    run_case(8'd255, 8'd16, 8'd15, 8'd15);
    run_case(8'd42,  8'd6,  8'd7,  8'd0);
    if (errors == 0) $display("PASS: all restoring-division cases correct");
    else             $display("FAIL: %0d case(s) wrong", errors);
    $finish;
  end
endmodule

PASS: 100 / 7 -> q=14 r=2  (check 14*7+2=100)
PASS: 255 / 16 -> q=15 r=15  (check 15*16+15=255)
PASS: 42 / 6 -> q=7 r=0  (check 7*6+0=42)
PASS: all restoring-division cases correct
The wait (done) in the TB rides out the fixed W-cycle latency, so the same stimulus works for any parameter W. Each case prints the identity check so you can see the result reconstruct the dividend exactly.

Combinational variant (fully unrolled)
The same algorithm collapsed into one always @(*) block with a for loop over the bit positions. There is no clock and no state — synthesis unrolls the loop into W cascaded subtract-and-select stages. Handy for understanding the datapath the FSM time-multiplexes.
div_comb.vSimulation log
// Combinational unsigned restoring divider (unrolled loop, no clock)
module restoring_div_comb #(parameter W=8)(
  input  [W-1:0] dividend, divisor,
  output [W-1:0] quotient, remainder
);
  reg [W-1:0] q;
  reg [W:0]   rem;        // W+1 bits to hold sign of trial subtraction
  reg [W:0]   trial;
  integer i;
  always @(*) begin
    rem = 0;
    q   = 0;
    for (i = W-1; i >= 0; i = i - 1) begin
      rem   = {rem[W-1:0], dividend[i]};   // shift in next dividend bit
      trial = rem - {1'b0, divisor};       // trial subtract
      if (trial[W]) begin                  // negative: restore, q bit = 0
        q[i] = 1'b0;
      end else begin                       // keep subtraction, q bit = 1
        q[i] = 1'b1;
        rem  = trial;
      end
    end
  end
  assign quotient  = q;
  assign remainder = rem[W-1:0];
endmodule

module tb;
  localparam W = 8;
  reg  [W-1:0] a, b;
  wire [W-1:0] q, r;
  integer errors = 0;

  restoring_div_comb #(.W(W)) dut(.dividend(a), .divisor(b),
                                  .quotient(q), .remainder(r));

  task chk;
    input [W-1:0] da, db, eq, er;
    begin
      if (db == 0) begin
        $display("SKIP: divisor zero");
      end else begin
        a = da; b = db; #1;
        if (q === eq && r === er && (da == q*db + r))
          $display("PASS: %0d / %0d -> q=%0d r=%0d", da, db, q, r);
        else begin
          errors = errors + 1;
          $display("FAIL: %0d / %0d -> q=%0d r=%0d (exp q=%0d r=%0d)",
                   da, db, q, r, eq, er);
        end
      end
    end
  endtask

  initial begin
    chk(8'd100, 8'd7,  8'd14, 8'd2);
    chk(8'd255, 8'd16, 8'd15, 8'd15);
    chk(8'd42,  8'd6,  8'd7,  8'd0);
    chk(8'd200, 8'd13, 8'd15, 8'd5);
    if (errors == 0) $display("PASS: all combinational cases correct");
    else             $display("FAIL: %0d wrong", errors);
    $finish;
  end
endmodule
PASS: 100 / 7 -> q=14 r=2

PASS: 255 / 16 -> q=15 r=15

PASS: 42 / 6 -> q=7 r=0

PASS: 200 / 13 -> q=15 r=5

PASS: all combinational cases correct
Because everything is combinational, the #1 settle delay before each check is all the TB needs. The loop index i is an integer — the Verilog-2005 way to walk bit positions without SystemVerilog loop-local declarations.
How the restoring algorithm works
Binary long division processes the dividend one bit at a time, from the most significant down. The accumulator rem holds the partial remainder; at each step it is shifted left and the next dividend bit enters the LSB. The divisor is then trial-subtracted. If the result is non-negative, the divisor "fit," so the quotient bit is 1 and the subtraction is kept. If the result is negative, the divisor did not fit, so the quotient bit is 0 and the old remainder is restored (that restore step is what names the algorithm). After W iterations the quotient is complete and whatever remains in the accumulator is the remainder.
Why the accumulator is W+1 bits wide
The trial subtraction rem - divisor can go negative, and the only way to detect that in unsigned hardware is to keep one extra guard bit at the top. We compute trial = {1'b0,rem} - {1'b0,divisor} and read trial[W]: a 1 there means a borrow occurred, i.e. the result was negative, so we restore. This one-bit sign test is the heart of the design — get the width wrong and every borrow is silently lost.
FSM vs combinational: the real engineering trade-off
The two designs implement identical math but sit at opposite ends of the area-versus-throughput curve. The FSM reuses a single subtractor across W clock cycles: small area, fixed W-cycle latency, one result per W cycles. The combinational version unrolls into W chained subtract-select stages: large area and a long carry-rippling critical path, but a new result every evaluation. Real dividers usually pick a middle ground — radix-4 (two bits/cycle), pipelined arrays, or SRT division — but restoring division is the canonical teaching baseline because its control is trivial.
Common pitfalls
Three bugs catch almost everyone. First, forgetting the guard bit so the negative trial result wraps around and the restore never triggers. Second, an off-by-one iteration count — you need exactly W shifts, and the FSM here checks count == W-1 before the increment latches, so the Wth result lands in DONE. Third, division by zero: the hardware has no defined behavior, so the testbench guards divisor != 0 and skips it rather than asserting a bogus expected value. In production you would flag a divide-by-zero with a status output.
Interview angle
Expect to be asked to draw the restoring-division datapath and name the registers: remainder accumulator, divisor register, and a shifting quotient/dividend register. A sharp follow-up is "what does the extra sign bit do?" — answer with the borrow-detect logic above. Another favorite: "how many cycles for an N-bit divide?" (N for simple restoring, N/2 for radix-4). Being able to contrast restoring with non-restoring division — which skips the explicit restore by adding the divisor back in the next step instead — signals you understand the algorithm family, not just one block.
Have questions about this topic?
Share your question in comments or talk to our mentor team for batch guidance.
▶ Try it in the ChipXpert Lab
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Run it in the Lab
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