Sequential Restoring Divider

Hard · Arithmetic · Finite State Machines · Sequential Logic

Implement an unsigned sequential divider that computes one quotient bit per clock cycle using the restoring division algorithm.

Division is far too large to do in one cycle for wide operands, so real CPUs and DSP blocks iterate. Your divider accepts an operation with a start pulse, works for exactly WIDTH cycles, and then pulses done with the result.

Parameters and ports

module seq_divider #(
    parameter int WIDTH = 8
) (
    input  logic             clk,
    input  logic             rst,
    input  logic             start,
    input  logic [WIDTH-1:0] dividend,
    input  logic [WIDTH-1:0] divisor,
    output logic             busy,
    output logic             done,
    output logic [WIDTH-1:0] quotient,
    output logic [WIDTH-1:0] remainder
);

Port	Dir	Width	Meaning
`clk`	input	1	Clock. Everything happens on the rising edge.
`rst`	input	1	Synchronous, active-high reset.
`start`	input	1	Request a division (sampled on the rising edge).
`dividend`	input	`WIDTH`	Unsigned dividend, sampled together with `start`.
`divisor`	input	`WIDTH`	Unsigned divisor, sampled together with `start`.
`busy`	output	1	`1` while a division is in progress.
`done`	output	1	One-cycle pulse: the result is ready.
`quotient`	output	`WIDTH`	`dividend / divisor` (unsigned, rounded toward zero).
`remainder`	output	`WIDTH`	`dividend % divisor`.

WIDTH is any value ≥ 2 (default 8). The judge tests WIDTH = 8.

Reset

rst is synchronous and active high: on a rising edge with rst = 1, the divider aborts any division in progress and afterwards busy = 0, done = 0, quotient = 0, remainder = 0. Reset is checked only at rising clock edges: a rst pulse that rises and falls between two edges has no effect (do not use always_ff @(posedge clk or posedge rst)).

rst has priority over everything else on the same edge:

a start sampled together with rst is ignored, also when the divider is idle (no

division is accepted, busy stays 0);

if rst is high on the edge that would complete a division (E(WIDTH) below), the

division is aborted: done does not pulse, and quotient/remainder become 0.

Timing (exact)

Call the rising edge at which start = 1 is sampled while busy = 0 the accepting edge E0, and the following rising edges E1, E2, ....

At E0 the divider captures dividend and divisor. After E0, busy = 1.
busy stays 1 after E1 … E(WIDTH−1): that is WIDTH cycles of busy.
After E(WIDTH): busy = 0, done = 1, and quotient/remainder hold the result.

So done rises exactly WIDTH clock cycles after the accepting edge.

After E(WIDTH+1): done = 0 again. done is high for exactly one cycle per division.

Other rules:

start while busy = 1 is ignored, and so are changes to dividend/divisor after

E0: the running division uses the captured values and finishes on time.

start in the cycle where done = 1 (when busy is already 0) is accepted: that

edge is the next division's E0. So with start held high continuously, a new division begins every WIDTH + 1 cycles.

Result outputs: whenever busy = 0, quotient and remainder show the result of the

most recent completed division (or 0 if none has completed since reset), and they hold that value until the next division is accepted. While busy = 1 their values are not checked.

Divide by zero: if the captured divisor is 0, the division still takes exactly

WIDTH cycles and pulses done, with quotient = all ones (2**WIDTH − 1) and remainder = the dividend. (This is what the restoring algorithm naturally produces, so you need no special case.)

Timing diagram

WIDTH = 8, computing 100 / 7 = 14 remainder 2:

Examples (WIDTH = 8)

dividend	divisor	quotient	remainder
100	7	14	2
255	1	255	0
7	9	0	7
200	200	1	0
0	5	0	0
42	0	255	42

The restoring algorithm

Keep a partial remainder R (start at 0) and shift the dividend in from its MSB, one bit per cycle. In each of the WIDTH steps:

R = {R, next dividend bit} (shift left by one, bring in the next bit, MSB first).
If R >= divisor: R = R - divisor and the next quotient bit is 1; otherwise the

quotient bit is 0 (the subtraction is "restored", i.e. not applied).

After WIDTH steps the quotient bits (MSB first) form the quotient and R is the remainder. A common trick is to keep the dividend in a shift register and shift quotient bits into its LSB as the dividend bits leave its MSB.

Watch the widths: a plain >= comparison is safest. If you instead compute R - divisor and use its top bit as the "negative" flag, the subtraction must be one bit wider than the operands ({1'b0, R} - {1'b0, divisor}, then test bit WIDTH). The MSB of a WIDTH-bit difference is not a borrow: that version fails for divisors of 2**(WIDTH-1) or more (for example 0 / 129).