Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-08
2002-11-05
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06477557
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a division circuit and more particularly to a division circuit for signed division
2. Description of the Prior Art
According to the prior art, when division on signed dividend and divisor expressed by a complement of 2 is carried out, in order to obtain an accurate quotient and remainder, if the dividend and/or divisor is negative, they are converted to positive values before the division. As a typical division algorithm, two examples of restoring type (pull-back method) and non-restoring type (pull-out method) will be described.
First, the conventional restoring type division algorithm will be explained referring to a structure of a division circuit shown in FIG.
1
.
If a dividend of n bits is a and a divisor of m(n>m) bits is b in
FIG. 1
, a division circuit comprises a remainder register
101
of n bits for storing high order side of a partial remainder during division operation and storing the remainder at the time of division end, a dividend/quotient register
102
of n bits for storing a dividend at the time of division start and successively storing low order side of the partial remainder and a quotient during division operation, a divisor register
103
of n bits for storing the divisor, a subtractor
104
of n bits, a selector
105
in which data obtained by combining a content of the remainder register
101
with that of a dividend/quotient register
102
is shifted by 1 bit so that the highest bit is shifted out, and then, data P# of that high order n bits, namely, data obtained by combining low order n−1 bits of the remainder register
101
with the highest bit of the dividend/quotient register
102
or output of the subtractor
104
is selected and supplied to the remainder register
101
, and a control circuit
106
for determining a quotient by receiving division result of the subtractor
104
and selectively controlling the selector
105
.
Next, the division operation using the division circuit having such a structure will be described according to its operation cycle.
First, if the dividend a and/or divisor b are negative, they/it are/is converted to positive numbers by taking complements thereof. If both are not negative, they are used as they are and these values are treated as a% and b% (first cycle, second cycle, action
1
).
Next, the dividend a% is loaded on the dividend/quotient register
102
and then the divisor b% is loaded on the divisor register
103
. 0 is loaded on all bits of the remainder register
101
(third cycle, action
2
).
Then, the remainder register
101
and dividend register
102
are shifted by 1 bit to the left and high order n bit of data obtained by combining both the registers after the shift is assumed to be P# (fourth cycle, action
3
-
1
). Then, the output data of the divisor register
103
is subtracted from data P# by means of the subtractor
104
(fourth cycle, action
3
-
2
). Then, the content of the dividend/quotient register
102
is shifted by 1 bit to the left. When the output of the subtractor
104
is negative, 0 is written to the least significant bit of the dividend/quotient register
102
as a quotient. If the output of the subtractor
104
is not negative, 1 is written into the least significant bit of the dividend/quotient register
102
as a quotient (fourth cycle, action
3
-
3
). Then, if the output of the subtractor
104
is not negative, the output of the subtractor
104
is stored in the remainder register
101
, and when the output of the subtractor
104
is negative, data P# is stored in the remainder register
101
(pull-back method) (fourth cycle, action
3
-
4
).
The actions (
3
-
1
)-(
3
-
4
) of aforementioned fourth cycle is repeated further (n−1) times (fifth cycle—(n+3) cycle).
Next, if the sign of the dividend is the same as the sign of the divisor, the output of the dividend/quotient register
102
is stored in the dividend/quotient register
102
as a quotient. On the other hand, if the sign of the dividend is different from the sign of the divisor, a complement of the output of the dividend/quotient register
102
is taken and written back to the dividend/quotient register
102
((n+4) cycle, action
5
).
Next, when the dividend is not negative, the output of the remainder register
101
is stored as a remainder. On the other hand, when the dividend is negative, a complement of the output of the remainder register
101
is taken and written to the remainder register
101
((n+5) cycle, action
6
).
Finally, the quotient is stored in the dividend/quotient register
102
and the remainder is stored in the remainder register
101
, and then the signed division is terminated ((n+6) cycle, action
7
).
The division processing is carried out as described above.
FIG. 2
shows an example of division in which dividend a=1001(binary) (means −7 according to decimal notation) and divisor b−0011 (binary) (means 3 according to decimal notation). In
FIG. 2
, the content of the remainder register
101
is expressed by P, the content of the dividend/quotient register
102
is expressed by A and the content of the divisor register
103
is expressed by B.
Then, the conventional non-restoring type division algorithm will be described with reference to a structure of the division circuit shown in FIG.
3
.
In the aforementioned conventional non-restoring type division, if the partial remainder is negative, a temporarily subtracted divisor is pulled back and added, so that the partial remainder is returned to a positive number. However, considering a level lower by a digit, subtraction of the divisor is regarded as (remainder+divisor)×2−divisor. Then, because (remainder+divisor)×2−divisor is remainder×2+divisor, when the partial remainder is negative, it is possible to store the partial remainder as it is and shift it by a bit to the left and then carry out addition instead of subtraction of the partial remainder and divisor. This method can reduce operation time per cycle as compared to the restoring type division. The non-restoring type division algorithm uses such a method.
If a dividend of n bits is a and a divisor of m(n>m) bits is b in
FIG. 3
, a division circuit comprises a remainder register
111
of n bits for storing high order side of a partial remainder during division operation and storing the remainder at the time of division end, a dividend/quotient register
112
of n bits for storing a dividend at the time of division start and successively storing low order side of the partial remainder and a quotient during division operation, a divisor register
113
of n bits for storing the divisor, an adder/subtractor
114
of n bits, and a control circuit
115
for determining a quotient by receiving operation result of the adder/subtractor
114
and instructing the adder/subtractor
114
to carry out addition or subtraction according to operation result of the adder/subtractor
114
.
Next, the division operation using the division circuit having such a structure will be described according to its operation cycle.
First, if the dividend a and/or divisor b are negative, they/it are/is converted to positive numbers by taking complements thereof. If both are not negative, they are used as they are and these values are treated as a% and b% (first cycle, second cycle, action
1
).
Next, the dividend a% is loaded on the dividend/quotient register
112
and then the divisor b% is loaded on the divisor register
113
. 0 is loaded on all bits of the remainder register
111
(third cycle, action
2
).
Then, the remainder register
111
and dividend register
112
are shifted by 1 bit to the left and high order n bit of data obtained by combining both the registers after the shift is assumed to be P% (fourth cycle, action
3
-
1
). Then, the output data of the divisor register
113
is subtracted from data P# by means of the subtractor
114
(fourth cycle, action
3
-
2
). Then, the content of the dividend/quo
Kabushiki Kaisha Toshiba
Malzahn David H.
LandOfFree
Division circuit not requiring taking complements of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Division circuit not requiring taking complements of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Division circuit not requiring taking complements of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2914632