Fast Division |
"SRT" division carry propagation free |
To avoid the delay of the carry propagation, the following applet uses a stack of borrow-save "BS" adders/subtractors. The "tail" cell, variant of the "SC" and "AS" cells, is controlled by two bits and executes one of the three following operations:
This operation is selected according to the sign of the partial remainders Rj. To always know precisely
this sign would require the examination of all the remainder's digits. It suffices to check only three (named hereafter). Moreover, the position of the
three digits is known: the least significant one is aligned with the most significant non-zero bits of D.
To nail down this digit position, D is "normalized",
that is the position of its first '1' bit is fixed. Let us call this position 0
and accordingly D's first bit d0. Thus d0= '1'. For an n-bit divider,
2n-2–1 < D < 2n-1 . |
Conditional carry-propagation-free adder/subtractor |
A "conditional adder/subtractor" outputs S from the three following equations:
Each "tail" cell carries out a one-bit addition/subtraction. The carry is not propagated to the "tail" cell at left but fed directly to the "tail" cell below (next row). The delay is independent from the number of digits. |
The "conditional adder/subtractor" function is abstracted by its transfer function called "Robertson's diagram". To converge the division imposes moreover that -2*D £ R £ 2*D. If -D £ R £ 2 then S has two possible values.
|
Check your knowledge of the "tail" cell truth table .
|
Let be = r2* 4 + r1* 2 + r0 and = s2* 4 + s1* 2 + s0 the input and output values of the "head" cell.
In an actual division (without overflow), output s2 will always be 0. The overflow digit s2 is used in the "double division" . |
Necessity of the '0' in the quotient Q |
If R > 0 an addition must not be performed and if R < 0 a subtraction must not be performed, or else the division overflows. When = 0, the sign of R is not known since to know it would potentially require the examination of all R's digits, so neither an addition nor a subtraction can be performed when = 0 and q must be '0' . |
Necessity of the normalization of the divider D |
For the "head" cell, a remainder R is small if = 0 , in other words if -1 < R < 1. In this case R keeps its value that may go outside the " Robertson's diagram" if 1 > D. Consequently 1 £ D. D's maximum value 2 is set only to simplify the head's equations. |
The previous division is simple because the fist bit d0 of the divider D is always '1'. It may be even further simplified if the two first bits d0 and d1 of the divider D are reduced to "1 0" thanks to the operation : |
Head cell of the "SRT" divider with range reduction |
Let = r0 + r1* 0.5 be the "head" cell input value.
Here the difference between the two 0 representations for q : '+ 0' and '- 0' matters. |
The quotient Q is in redundant notation. The conversion into a conventional binary representation is obtained thanks to an adder (in fact a subtractor). Since the digits q are obtained sequentially, most significant digit first, the conversion can be carried out in parallel with the quotient digits selection. Let "ratio" be the "head" cell and "BK" cell delays ratio. The higher the ratio, the more delay available thus the simpler the converter. |
Divider design |
The quotient Q digits are redundant and symmetrical. They are defined by the radix and the maximum digit value. This applet let you choose the quotient digit values then the number of bits from divider D and digit from partial remainder R that must be taken into account for the selection of the quotient digit value. |