Divider and method with high radix

Details Divider and method with high radix Divider and method with high radix

2000-06-01

2003-09-23

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S655000, C708S656000

Reexamination Certificate

active

06625633

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a divider using restoring division for division using a dividend and divisor given by binary numbers, more particularly relates to a high radix divider for radix 2
k
division of a dividend to find a quotient for k number of bits at a time and a method for the same.
2. Description of the Related Art
Restoring division is known as a system of a subtractor (for example, see reference John L. Hennessy, David A. Paterson, translated by Mitsuaki Narita,
Configuration and Design of Computer,
1st volume, pp. 191 to 199, Nikkei BP Co., April 1996).
Radix 2 restoring division obtains a quotient one bit at a time from the upper bit.
In this case, when a dividend is N bits, a minimum of N number of computations becomes required. For example, when the dividend is 32 bits, a minimum of 32 computations have to be performed.
When finding a quotient one bit at a time in this way, the number of computations becomes just too large, so there is the method of increasing the number of bits of the quotient found by one computation to 2 bits or more to decrease the number of computations. This is called high radix division.
When obtaining k number of bits at a time, the operation is called radix 2
k
division. For example, when performing radix 4 division of a 32-bit dividend, the quotient is found 2 bits at a time per computation and the minimum number of computations falls to 16. Similarly, with a radix 8, the number of computations becomes 11.
Below, radix 2 and radix 4 restoring division will be explained in detail.
Radix 2 Restoring Division
Here, the dividend is made A and the divisor is, made B. A and B are made N-bit signed binary numbers (two's complements).
Note that the MSB appearing in the following explanation expresses to the most significant bit in the binary number and indicates the (M−1)th bit in the case of an M-digit binary number.
The registers include a sign register (one digit) for storing the sign of a quotient, a B register (N digits) for storing the divisor B, an R register (N digits) for storing the remainder, and a Q register (N digits) for storing the quotient.
All registers are initialized to zero.
The routine for division explained below is divided into the three first, second, and third stages STG
1
to STG
3
.
The first stage STG
1
is a preparatory stage, the third stage STG
3
is a final stage for correction of the sign of the obtained quotient, and the second stage STG
2
is the central stage of the division.
Each of the stages STG
1
, STG
2
, and STG
3
end upon entry into the registers. The series of operations in a stage is performed in one cycle.
[Routine]
First Stage STG
1
(1) The sign bit (MSB) of the dividend A and divisor B are referred to and the sign of the quotient is found in advance and stored in the sign register. Here, when negative, the sign=1.
(2) An absolute value of the dividend A is found and entered in the Q register.
(3) An absolute value of the divisor B is found and entered in the B register.
Second Stage STG
2
-
1
(1) R−B=diff(N digits) is calculated.
(2) When diff is not negative (MSB of diff is “0”), the divisor can be subtracted from the remainder.
At this time, the quotient judgement data Judge=1 and the new remainder is diff=R−B=Re (N digits).
On the other hand, when diff is negative, the divisor cannot be subtracted from the remainder.
At this time, the quotient judgement data Judge=0 and the new remainder is R=Re (N digits).
(3) By combining the Re, Q, and Judge and shifting by one bit to the left, the value NEXT_R of the R register and the value NEXT_Q of the next Q register are found.
Namely,
NEXT_R={(N−2)th to 0th digits of Re, (N−1)th digit of Q}
NEXT_Q={(N−2)th to 0th digits of Q, Judge}
(4) The NEXT_R and NEXT_Q are respectively entered into the R, Q registers.
Second Stage STG
2
-
2
The above operations of (1) to (4) are carried out in one cycle.
This is repeated for N number of times.
Third Stage STG
3
(1) R−B=diff (N digits) is calculated.
(2) When diff is not negative (MSB of diff is “0”), the divisor can be subtracted from the remainder.
At this time, the quotient judgement data is made Judge=1 and the new remainder is made diff=R−B=Re (N digits).
On the other hand, when diff is negative, the divisor cannot be subtracted from the remainder.
At this time, the quotient judgement data is made Judge=0 and the new remainder is made R=Re (N digits).
(3) By combining Re and Q and shifting by one bit to the left, the value of the R register NEXT_R and value of the next Q register NEXT_Q are found.
Namely,
NEXT_R={(N−2)th to 0th digits of Re, (N−1)th digit of Q}
NEXT_Q={(N−2)th to 0th digits of Q, Judge}
The explanation up to here is the same as the second stage STG
2
.
(4) The sign of the quotient is corrected by referring to the sign register and the final quotient LAST_Q is found.
Namely,
Sign=1 (when negative):LAST_=~NEXT_Q+1 (two's complement is taken).
Note that “~” indicates inversion.
Sign=0 (when not negative):LAST_Q=NEXT_Q
On the other hand. the final remainder is Re.
(5) The LAST_Q is entered into the Q register and Re is entered into the R register.
Here, the Q register shows the quotient and the remainder shows the R register.
The above completes the division by radix 2 restoring division.
FIG. 1
is a circuit diagram of an example of the general configuration of a restoring division subtractor.
The restoring division subtractor comprises, as shown in
FIG. 1
, an exclusive OR gate
110
for obtaining the sign of the quotient in the first stage STG
1
, absolute value generators
111
and
112
for obtaining absolute values of the dividend A and the divisor B in the first stage STG
1
, a quotient/remainder Judgement unit
113
for the processing of the second stage STG
2
, a sign inversion unit
114
for the processing of the third stage STG
3
, a selector
115
, stage selecting selectors
116
to
119
operated by a control signal CTL, a sign register
120
, a B register
121
, an R register
122
, and a Q register
123
.
The quotient/remainder judgement unit
113
is for realizing the second stage STG
2
-
1
in the above explained routine. An example of the configuration is shown in FIG.
2
.
As shown in
FIG. 2
, the quotient/remainder judgement unit
113
is comprised by a subtractor
131
for subtraction of (R−B) in the processing of the above second stage STG
2
-
1
(
1
), a selector
132
for obtaining a new remainder Re based on the quotient judgement in the processing of the second stage
2
-
1
(
2
), and bit matchers
133
and
134
for the processing of the second stage STG
2
-
1
(
3
).
In a restoring division subtractor configured in this way, by properly giving a control signal CTL, the operations of the above first stage STG
1
, second stage STG
2
, and third stage STG
3
are switched.
FIG. 3
is a view of the process of the operation of the subtractor.
In this example, 77654321h/00000007h was calculated.
When looking at the column “Judge” in
FIG. 3
, the process by which the quotient is found bit by bit from the upper bit can be understood.
Radix 4 Restoring Division
The case of a radix 4 differs from the case of a radix 2 in the point that the quotient is obtained 2 bits at a time. Also, only the part of the second stage STG
2
-
1
differs in the routine of the above restoring division.
[Routine]
Second Stage
2
-
1
(1) 2B(N+1 digits) is found by bit shifting. 3B(N+2 digits) is found from 2B+B.
Then,
R−
3
B
=diff
3
(
N+
2 digits)
R−
2
B
=diff
2
(
N+
1 digits)
R−B
diff
1
(
N
digits)
are calculated in parallel.
(2) If diff
3
is not negative ((N+1)th bit is “0”), the new remainder is made diff
3
=R−3B=Re (N digits, upper 2 bits truncated) and the qu

Affiliated with

Also associated with

Rating

Divider and method with high radix does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3017389