Divider


Weighting a bread loaf with restoration and without restoration

We want to computer Q = A ÷ D. By a stoke of luck, we have available a scale, a white bread whose weight is actually just A and a set of brass weights with values D, 2D, 4D, 8D, .... 2i*D respectively marked with 1, 2, 4, 8, ... 2i.
In fact D is a binary number, and 2i*D is simply obtained by a shift of D. The scale compares the sum of the weights on each of the two plates ( £ or > ).

Digit recurrence division

Division is not frequent. Nevertheless since its execution delay is far larger than the addition or multiplication's one, its impact in the total execution time is substantial, thus it is advisable to design dividers carefully.
Let say that we want Q = A ÷ D. This is equivalent to Q × D = A. Therefore if Q and D are both written onto n bits, A is written onto 2n  bits.
Let us build a series Qn, Qn-1, ... Q2, Q1, Q0 and a series Rn, Rn-1, ... R2, R1, R0 such that the invariant A = Qj × D + Rj holds for all j.
The recurrence is :

  • Qj-1 = Qj + qj-1 * 2j-1                     ( this is merely a concatenation )
  • Rj-1 = Rj – qj-1 * D * 2j-1                ( this is a conditional subtraction )

with initial conditions :

  • Qn = 0
  • Rn = A.

When the recurrence terminates, we have Q = Q0 = Si qi * 2i. R = R0 is the division remainder.

Conditional subtractor

A "conditional subtractor" gives the following result S:
if R < D then S = R else S = R – D ; // S = R modulo D
Each "SC" cell computes both the result and the carry (borrow) of the subtraction R – D. If the output carry (leftmost) equals '1' then S is assigned the result of the subtraction else S is assigned the value of R. This last case, that seems to "restore" R to its previous value is sometimes called "restoration", from which the divider's name derives.
 

The "conditional subtractor" function: if R < D then S = R else S = R – D, is abstracted by its transfer function called "Robertson's diagram". To converge the division imposes moreover that 0 £ R £ 2*D. The "Robertson's diagram" also visualizes the overflow .The overflow detection logic is not included in the following divisors.

"SC" cell of the conditional subtractor

Check whether you are acquainted with the logic of the "SC" cell :
if q = '0' then { co = majority ( r, d, ci ) ; s = r } // identity
else { co = majority ( r, d, ci ) ; s = r Å d Å ci } // subtraction

Restoring divider

A "restoring" divider consists in a series of shifts and tried subtractions. It is made of a regular array of conditional subtraction "SC" cell (subtraction or identity according to a carry out qj ).

Inverse of the division

If the restoring divider is turned upside-down and the conditional subtractors "SC" are substituted by conditional adders "AC" ( identity or addition according to qj ) the operators delivers the inverse of the division i.e. the multiplication with "remainder" : A = D * Q + R.

Conditional adder cell "AC"

Check whether you are acquainted with the logic of the "AC" cell :
2 * co + s = (q*d) + r + ci , in other words :
co = majority ((q*d), r, ci ) ;
s = (q*d) Å r Å ci ;

Non-restoring divider

A "non-restoring" divider is a sequence of shifts and additions or subtractions. Is made of a regular structure of "AS" cells (addition or subtraction according to q), q is given by the signs of R and D.

  • if R < 0 and D < 0 then {S = R – D ; q = '1'}
  • if R < 0 and D ³ 0 then {S = R + D ; q = '-1'}
  • if R ³ 0 and D < 0 then {S = R + D ; q = '-1'}
  • if R ³ 0 and D ³ 0 then {S = R – D ; q = '1'}

 

The function of a row of "AS" cells is plotted by the "Robertson's Diagram"
if R < 0 then S = R + D else S = R – D.

Cell of the adder/subtractor "AS"

Check your knowledge of the logic equations of the "AS" cell:
if q = '-1' then 2*co + s = r + d + ci // addition
if q = '1' then 2*co + s = r + 1 – d + ci // subtraction

Advantages and disadvantages of the non-restoring divider

The main advantage is the compatibility with 2's complement notation for dividend A and divisor D. Nevertheless the quotient Q is noted with digits '-1' and '1', it must be converted to 2's complement, which is very simple.

Reseting the least significant bit of Q (odd) yields Q – 1 (even) .
For the division, it is agreed that if the final remainder R is not zero then it must have the same sign as the dividend A. An "XOR" gate detects the A and R signs difference.

  • if A ³ 0 and R < 0 and D ³ 0 then { Q = Q – 1 ; R = R + D }
  • if A ³ 0 and R < 0 and D < 0 then { Q = Q + 1 ; R = R – D }
  • if A < 0 and R > 0 and D ³ 0 then { Q = Q + 1 ; R = R – D }
  • if A < 0 and R > 0 and D < 0 then { Q = Q – 1 ; R = R + D }

One pathological case remains R = - | D | that must be detected to force R = 0 .

Fast dividers

Three approaches are combined to realize fast dividers:

  • Utilization of carry-propagation-free addition/subtraction.
  • Preconditioning of the dividend and the divisor in order to simplify the division.
  • Use of higher radixes to reduce the number of steps.

Robertson Diagram

For a square Robertson's diagram, the successive partial remainders are normalized: ( Rj * b-j ) where b is the numeration radix.
The black sloops represent the transfer function Rj Þ Rj-1, the red line is the identity function that passes to the next step. Pulling the mouse out of the pictures suspends the animation. Clicking into the white square sets the starting point, clicking outside stops or restarts the animation from the same point.

Radix 10 is familiar to us, it is given here just for illustration because it would not be very efficient in binary. "SRT" is named after D. Sweeney, J. Robertson and K. Tocher, who published simultaneously carry-propagation-free dividers.