Split remainder divider

Details Split remainder divider Split remainder divider

1999-01-19

2001-11-13

Malzahn, David H. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S656000

Reexamination Certificate

active

06317772

ABSTRACT:

BACKGROUND OF THE INVENTION
Generally mathematical division in a computer involves division of a dividend by a divisor to produce a quotient. Such division is slow because it requires iteratively generating a series of partial remainders and quotient digits. Therefore, the speed of the division operation is dependent on the amount of time it takes to complete one iteration and the total number of iterations required. The total number of iterations is dependent on the number of quotient digits required to provide an accurate quotient. For example, in floating point division twenty-five quotient digits are required for single precision and fifty-four quotient digits are required for double-precision, therefore the time required to generate each of the required quotient digits is critical to the speed of the division.
One well known method of performing division is restorative division. A computer procedure or routine for performing binary restorative division is shown in Table 1.
If(
R
i
>=Divisor) then
R
i+1
=2*(
R
i
−Divisor)
Q
i
=1
Else
R
i+1
=2*(
R
i
)
Q
i
=0
where R
i
=partial remainder; Q
i
=quotient digit
Table 1
In binary restorative division, quotient digits are selected from the set of two possible quotient digits {0, 1}. In each iteration, a partial remainder is compared to a divisor. If the partial remainder is greater than or equal to the divisor, the quotient digit is set to ‘1’. The partial remainder for the next iteration is set equal to a left shift, by one bit, of the result of the divisor subtracted from the current partial remainder. If the current partial remainder is less than the divisor, the quotient digit is set to ‘0’. In the next iteration, the partial remainder is set equal to a left shift by one bit of the current partial remainder.
For example, to divide dividend=1.01 by divisor=1.1 using the restoring division routine in Table 1 results in quotient=0.1101. The division operation requires the generation of five partial remainders and five quotient digits as shown in Table 2.
TABLE 2
Partial
Partial
Division Stage
Remainder(in)
Remainder(out)
Quotient Digit
1
1.01
10.10
0
2
10.10
10.00
1
3
10.00
1.00
1
4
1.00
10.00
0
5
10.00
1.00
1
6
1.00
To generate the quotient digits, the partial remainder must be calculated precisely in each iteration. Therefore, the subtraction of the divisor from the partial remainder requires propagating a carry bit from the least significant bit (“LSB”) to the most significant bit (“MSB”) of the partial remainder, through the use of a Carry Propagate Adder (“CPA”). Due to the requirement to propagate the carry bit, the subtraction is relatively slow.
For example, to subtract divisor=1.1 from partial remainder=10.1 in division Stage 2 as shown in Table 2, requires propagating the carry bit from the LSB(bit #
0
) to MSB(bit#
3
) of the CPA.
Another well known method for performing division is non-restoring division in which a quotient is provided in redundant form. For example, in a binary non-restoring divider, quotient digits are selected from redundant binary sets of quotient digits such as, the set of redundant binary digits {−1, 0, 1} or the set of redundant binary digits {−2, −1, 0, 1, 2}. A routine for selecting a quotient digit in a binary non-restoring divider from the set of redundant binary digits {−1, 0, 1} is shown in Table 3.
If(
R
i
>=0.5Divisor);
Q
i
=1
If(0
<R
i
<0.5Divisor);
Q
i
=1, 0
If(−0.5Divisor<
R
i
<0);
Q
i
=−1, 0
If(−0.5Divisor<=
R
i
);
Q
i
=−1
R
i+1
=2*(
R
i
−Q
i
Divisor)
where R
i
=partial remainder; Q
i
=quotient digit
Table 3
Non-restoring division generates a quotient digit by real-time comparison of the divisor to a small number of the partial remainder MSBs. The quotient digit generation does not require a precise subtraction of the divisor from the input partial remainder therefore Carry Save Adders (“CSAs”) can be used. The CSAs save the carry bits and do not require propagating a carry bit from the LSB to the MSB of the partial remainder. As a result, subtraction using CSAs is much faster than subtraction using a CPA.
For example, dividing dividend=1.01 by divisor=1.1 using non-restoring division results in redundant binary quotient digits=1,0,−1,1,−1. The division requires the generation of five partial remainders and quotient digits as shown in Table 4.
TABLE 4
Partial
Partial
Division Stage
Remainder(in)
Remainder(out)
Quotient Digit
1
1.01
−0.1
1
2
−0.10
−1.0
0
3
−1.00
1.0
−1
4
1.00
−1.0
1
5
−1.00
1.0
−1
The quotient=0.1101 is generated from the redundant binary quotient digits as shown in Table 5. A normalized scaled quotient digit is generated from each redundant binary quotient digit, by shifting the redundant binary quotient digit, and multiplying the result by −1. After the normalized scaled quotient digits have been generated, they are added to generate the quotient.
TABLE 5
Redundant Binary Quotient Digit
Normalized Scaled
Division Stage
(from Table 4)
Quotient Digit
1
−1
1.0
2
0
0.0
3
1
−0.01
4
−1
0.001
5
1
−0.0001
Quotient =
0.1101
In sum, the comparison of the divisor to the partial remainder is relatively fast in restoring division, but the subtraction to provide the precise partial remainder is relatively slow because it requires the use of a CPA. The comparison of the divisor to the partial remainder is relatively slow in non-restoring division, but the subtraction using CSAs is relatively fast.
Therefore, non-restoring division has slow comparison and fast CSAs, and restoring division has a slow CPA and fast comparison. The tradeoff between comparison speed and subtraction speed (CPA and CSAs) is a long standing issue faced by computer divider designers.
SUMMARY OF THE INVENTION
In a computer system, a mathematical division operation is performed by a state machine coupled to an array of CSAs for dividing a dividend by a divisor. The most significant bits of the dividend and the divisor are input to the state machine. The least significant bits of the dividend and the divisor are input to the array of carry save adders.
In the array of carry save adders there is a different carry save adder for each least significant bit of the dividend. For a given least significant bit of the dividend, the least significant bit of the dividend and a respective least significant bit of the divisor are summed in the respective carry save adder.
The state machine is coupled in parallel to the array of carry save adders. The state machine includes at least one state machine stage which is fully encoded for all possible combinations of the most significant bits of the dividend and the divisor. The state machine stage provides a quotient digit and the most significant bits of a partial remainder dependent on the most significant bits of the dividend and the divisor.
The most significant bits of the partial remainder provided by the state machine stage are also dependent on the addition of spillover signals generated by the carry save adder. The spillover signals are added in the state machine by selecting the encoded partial remainder set equal to the result of the mathematical addition.
To generate more quotient digits the most significant bits of the partial remainder are fed back to the input of the state machine, as the next stage dividend. The state machine may be fully encoded for quotient digits from the redundant binary set {−1, 0, 1} or from the redundant binary set {−2, −1, 0, 1, 2}. A fully encoded state machine for quotient digits from the redundant binary set {−1, 0, 1} sets the quotient digit to −1 if the partial remainder is greater than half the divisor. If the partial remainder is less than or equal to ha

Affiliated with

Also associated with

Rating

Split remainder divider does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Split remainder divider, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split remainder divider will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2586369