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.
with initial conditions :
When the recurrence terminates, we have Q = Q0 = Si qi * 2i. R = R0 is the division remainder. |
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 ant 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.
|
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 |
A "restoring" divider consists in a series of shifts and attempted subtractions. It is made of a regular net of conditional subtraction "SC" cell (subtraction or identity according to a carry out bit). |
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 qi ) the operators delivers the inverse of the division i.e. the multiplication with "remainder" : A = D * Q + R. |
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.
|
The function of a row of "AS" cells is plotted by the "Robertson's Diagram" |
Fast dividers |
Three approaches are combined to realize fast dividers:
|
For a square Robertson's diagram, the successive partial remainders are normalized: ( Rj * b-j
) where b is the numeration radix. |