Restoring Division

Restoring Division

A division algorithm in which subtraction is used as a trial; a successful trial is kept, while an unsuccessful trial causes the previous valid remainder state to be preserved or restored.

Trial Subtraction

A tentative subtraction of the divisor from the shifted partial remainder used to determine whether the divisor fits.

TrialRemainder

The tentative result obtained by subtracting DivisorRegister from ShiftedRemainder.

TrialRemainder = ShiftedRemainder - DivisorRegister

The arithmetic question evaluated during each restoring-division step.

Successful Trial

The condition in which the shifted partial remainder is large enough to subtract the divisor.

Failed Trial

The condition in which the shifted partial remainder is too small to subtract the divisor.

Successful trial → keep TrialRemainder + quotient bit 1

What state decision follows when the divisor fits?

Failed trial → keep ShiftedRemainder + quotient bit 0

What state decision follows when the divisor does not fit?

Because subtraction determines whether the divisor fits at the current quotient position.

Why is subtraction both an arithmetic operation and a decision mechanism in restoring division?

Restoration

The act of rejecting an unsuccessful trial subtraction and retaining the valid remainder that existed before that subtraction was accepted.

Because an unsuccessful tentative subtraction must not become the next stored partial remainder.

Why does restoring division need the concept of restoration?

UnsignedRestoringDivider

The project's unsigned iterative division datapath that retains divisor, quotient/dividend, and partial-remainder state and performs one restoring-division step when step is asserted.

QuotientRegister

A WIDTH-bit working register that initially stores Dividend and progressively becomes the constructed Quotient.

RemainderRegister

A WIDTH+1-bit working register that stores the evolving partial remainder.

DivisorRegister

A WIDTH-bit register that preserves the Divisor throughout the iterative division operation.

Why is Dividend initially loaded into QuotientRegister?

Because the register initially supplies dividend bits to the division process and is progressively transformed into the final quotient.

QuotientRegister <= Dividend

The load operation that initializes the quotient/dividend working register.

RemainderRegister <= 0

The load operation that initializes the partial remainder before division iterations begin.

DivisorRegister <= Divisor

The load operation that preserves the divisor for use throughout the division sequence.

load

Control signal that initializes the divider's working state for a new division.

step

Control signal that permits one restoring-division iteration.

Why must DivisorRegister preserve the divisor?

Because the same divisor must be available for every compare/subtract decision while the other working values evolve.

Why is RemainderRegister cleared during load?

Because the iterative division process begins with no partial remainder accumulated yet.

reg [WIDTH:0] RemainderRegister

Declares a partial-remainder register containing WIDTH+1 bits.

WIDTH + 1

The number of bits available in RemainderRegister, ShiftedRemainder, and TrialRemainder.

Why is the remainder working path WIDTH+1 bits wide?

It provides an additional high-order bit for the shifted partial-remainder arithmetic and divisor trial path.

{1'b0, DivisorRegister}

Extends the WIDTH-bit unsigned divisor to the WIDTH+1-bit width of the remainder arithmetic path.

Why is 1'b0 concatenated above DivisorRegister?

Because the unsigned divisor must be represented at the same WIDTH+1-bit width as ShiftedRemainder before comparison and subtraction.

reg [WIDTH:0] ShiftedRemainder

A WIDTH+1-bit combinational temporary representing the partial remainder after the next dividend/quotient bit has been shifted into it.

reg [WIDTH - 1:0] ShiftedQuotient

A WIDTH-bit combinational temporary representing QuotientRegister shifted left by one position.

reg [WIDTH:0] TrialRemainder

A WIDTH+1-bit combinational temporary containing the result of the trial subtraction.

always @(*)

The combinational block that continuously calculates ShiftedRemainder, ShiftedQuotient, and TrialRemainder from the current divider state.

ShiftedRemainder = {RemainderRegister[WIDTH - 1:0], QuotientRegister[WIDTH - 1]}

Forms the next shifted partial remainder by shifting the retained remainder information and bringing in the current most-significant bit of QuotientRegister.

QuotientRegister[WIDTH - 1]

The next dividend-information bit transferred into the partial remainder during a restoring-division step.

RemainderRegister[WIDTH - 1:0]

The lower WIDTH bits of the current partial remainder that are shifted upward when ShiftedRemainder is constructed.

Why is QuotientRegister[WIDTH - 1] inserted into ShiftedRemainder?

It implements the division operation of bringing the next dividend bit into the working partial remainder.

ShiftedQuotient = QuotientRegister << 1

Produces the shifted working quotient value and opens bit 0 for the new quotient decision.

Why is QuotientRegister shifted left during every division step?

The working register must advance to the next dividend/quotient position while creating space for the newly determined quotient bit.

ShiftedQuotient[0] = 0 after the logical left shift

The default quotient decision represented by ShiftedQuotient before a successful trial explicitly changes bit 0 to 1.

TrialRemainder = ShiftedRemainder - {1'b0, DivisorRegister}

Computes the tentative partial remainder that would result if the divisor were accepted at the current step.

ShiftedRemainder >= {1'b0, DivisorRegister}

The RTL condition used to determine whether the unsigned divisor fits into the current shifted partial remainder.

Why does this RTL compare before accepting TrialRemainder?

The comparison determines whether the subtraction is valid for the unsigned restoring algorithm before the tentative result is stored.

Divisor fits

The condition ShiftedRemainder >= {1'b0, DivisorRegister}.

Divisor does not fit

The condition ShiftedRemainder < {1'b0, DivisorRegister}.

RemainderRegister <= TrialRemainder

The next-state update used when the divisor fits.

RemainderRegister <= ShiftedRemainder

The next-state update used when the divisor does not fit.

Why is ShiftedRemainder stored when the divisor does not fit?

The shift itself is still part of the iteration, but the unsuccessful subtraction must not alter that valid shifted remainder.

QuotientRegister <= ShiftedQuotient

The basic quotient-register update performed after shifting.

QuotientRegister[0] <= 1'b1

The additional update used on a successful trial to record a quotient decision of 1.

Successful quotient-bit insertion

Shift QuotientRegister left and then make its new least-significant bit 1.

Failed quotient-bit insertion

Shift QuotientRegister left and leave its new least-significant bit at 0.

Why is the new quotient bit inserted at bit 0?

The left shift creates the new quotient position at the least-significant end of the working register.

One step with successful subtraction

Shift remainder information, subtract divisor, store TrialRemainder, shift QuotientRegister, and insert 1 into quotient bit 0.

One step with unsuccessful subtraction

Shift remainder information, preserve ShiftedRemainder, shift QuotientRegister, and leave quotient bit 0 as 0.

ShiftedRemainder is not stored state.

Is ShiftedRemainder a register that remembers information between clock cycles?

Why is ShiftedRemainder combinational working logic rather than persistent algorithmic state?

It describes a candidate value derived from the current stored state; RemainderRegister captures the accepted next state on a clock edge.

TrialRemainder is not automatically accepted.

Does computing TrialRemainder mean that the subtraction necessarily becomes part of the divider's state?

Why is TrialRemainder called a trial?

The datapath computes it before knowing whether that subtraction should become the next stored RemainderRegister value.

Candidate State

A combinationally calculated possible next value that is stored only if the algorithmic decision selects it.

Accepted Next State

The candidate or preserved value actually captured into the working register on the clock edge.

Current state → candidate calculations → decision → accepted next state

The architectural pattern demonstrated by the restoring-divider datapath.

Why does restoring division need next-state selection?

The arithmetic trial creates more than one possible remainder outcome, and the comparison determines which outcome becomes persistent state.

always @(posedge clk)

The sequential block that stores the divider's accepted working state.

reset

The highest-priority condition that clears QuotientRegister, RemainderRegister, and DivisorRegister.

load has priority over step.

What happens if the datapath's load and step controls are simultaneously asserted?

Why does load override step in UnsignedRestoringDivider?

The datapath must initialize the new division state rather than perform an iteration using the previous operation's working values.

step = 0 with no reset/load

The divider's working registers retain their current values.

step = 1 with no reset/load

One restoring-division state transformation is accepted on the rising clock edge.

Combinational Candidate Logic + Clocked Working Registers

The two structural portions of UnsignedRestoringDivider.

Candidate Logic

Calculates ShiftedRemainder, ShiftedQuotient, and TrialRemainder from the current stored state.

Working Registers

QuotientRegister, RemainderRegister, and DivisorRegister preserve algorithmic progress between iterations.

The combinational block asks what the next state could be; the clocked block decides and remembers what the next state becomes.

How do the two always blocks divide responsibility in UnsignedRestoringDivider?

assign Quotient = QuotientRegister

Exposes the progressively constructed quotient working register as the divider's Quotient output.

assign Remainder = RemainderRegister[WIDTH - 1:0]

Exposes the lower WIDTH bits of the working partial remainder as the Remainder output.

Why is the output Remainder WIDTH bits even though RemainderRegister is WIDTH+1 bits?

The extra bit belongs to the internal working arithmetic path, while the module interface returns a WIDTH-bit remainder.

Restoring Divider Datapath

State registers plus shift, compare/subtract, next-remainder selection, and quotient-bit insertion logic.

Retain divisor → shift working state → test subtraction → choose remainder → insert quotient bit → store next state

The architectural flow of one UnsignedRestoringDivider iteration.

Why is the algorithm called restoring division even though this RTL does not literally subtract first and then add the divisor back?

The RTL computes the subtraction as TrialRemainder but stores ShiftedRemainder when the trial is rejected, achieving the same architectural effect by selecting the pre-subtraction value.

Explicit Restore vs. Next-State Selection

A literal implementation may undo a failed subtraction, while this RTL can obtain the same result by never committing the failed TrialRemainder and instead selecting ShiftedRemainder.

Why is next-state selection an efficient way to express restoration?

The tentative subtraction remains combinational, so an unsuccessful result can simply be discarded rather than stored and subsequently reversed.

The algorithm's name describes what must happen to hardware state.

What deeper architectural meaning does the word restoring carry?