Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-10-13
2003-06-10
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06578062
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to method and apparatus for arithmetic division, and, in particular, to method and apparatus for performing arithmetic division in digital circuits.
BACKGROUND OF THE INVENTION
Division is a time consuming arithmetic function performed by digital computers and digital circuits that require extensive circuitry. A dividend is divided by a divisor to obtain a quotient and a remainder, if any. In a first step, the divisor is subtracted from the initial dividend. Thereafter, in subsequent steps, a current dividend is obtained by shifting each bit of the previous dividend by one toward the next higher order bit of the previous dividend, leaving a vacant lowest order bit. Further, in each step, the divisor is subtracted from the higher order bits of the current dividend to obtain a partial remainder. The partial remainder and the vacant lower order bits of the initial dividend are concatenated. If the result of the subtraction is positive, then a “1” is recorded for that place of the quotient in the lowest order bit position, and a next shift and subtraction occur. If the result of the subtraction is negative, a “0” is recorded for the quotient in the lowest order bit position, and the dividend is restored to its previous condition by adding back the divisor before the next shift and subtraction. However, this process is very time consuming and requires extensive logic components for performing the above steps.
To alleviate such shortcomings, non-restoring techniques have been utilized. An N-bit dividend is divided by an N-bit divisor by performing N repeated subtractions between them by shifting registers. The dividend and the divisor are stored in corresponding registers, and a remainder register is initialized to zero. The divisor is subtracted from a number including the lower (N−1) bits of the remainder and the highest order bit of the dividend register. If the subtraction fails, a zero is stored into the lowest order bit position of the dividend register, and the dividend and the remainder registers are shifted one bit toward their highest order bit positions, such that the highest order bit of the dividend register is shifted out into the lowest order bit of the remainder register. If the subtraction is successful, a “1” is stored into the lowest order bit of the dividend register, and the dividend and the remainder registers are shifted one towards their highest order bits, and the results of the subtraction is written into the remainder register. Repeating the above subtraction by shifting steps N times provides the quotient of the division in the dividend register and the remainder of the division in the remainder register.
Although using the non-restoring method the number of steps for performing division is reduced, a logic circuit for dividing a dividend by a divisor according to such methods requires several hundred logic gates. This is because often a digital logic circuit must be designed to divide one number by another number, and the number of logic gates depends on the number of bits being divided. Such circuits are expensive to design and manufacture, consume precious circuit space, and require excessive power for operating and cooling purposes.
There is, therefore, a need for a method and apparatus which provides for dividing a dividend by a divisor using reduced circuit components and functional steps.
SUMMARY OF THE INVENTION
The present invention satisfies these needs. In one embodiment the present invention provides a method and apparatus for calculating a quotient from a dividend and a divisor. The dividend comprises an X-bit binary number divisible by the divisor without a remainder, wherein the divisor is represented as (2
N
+2
M
) where N is greater than M. According to an embodiment of the method of the present invention, the values of N and M are determined such that the divisor is equal to the value (2
N
+2
M
). Then, the M-th through the (N−1)-th bits of the dividend are selected as lower order bits of the quotient. To obtain the higher order bits of the quotient, the (N−1)-th and the (2N−M−1)-th bits of the dividend are examined. If the (N−1)-th bit of the dividend is “1” and if the (2N−M−1)-th bit of the dividend is “0”, then the value “1” is subtracted from a value represented by the (2N−M)-th through the (X−1)-th bits of the dividend to obtain a value representing the higher order bits of the quotient. Otherwise, the (2N−M)-th through the (X−1)-th bits of the dividend are selected as higher order bits of the quotient. Finally, the higher order bits and the lower order bits are concatenated to obtain the quotient.
In an example of the method of the present invention, the dividend is stored in a dividend register having at least X bits, such that the 0-th through the (X−1)-th bits of the dividend are stored into the 0-th through the (X−1)-th bits of the dividend register, respectively. The M-th through the (N−1)-th bits of the dividend register are stored into the 0-th through the (N−M−1)-th bits of the quotient register, respectively, in parallel or by shifting. If the (N−1)-th bit of the dividend register is “1” and if the (2N−M−1)-th bit of the dividend is “0”, then the value “1” is subtracted from a value represented by the (2N−M)-th through the (X−1)-th bits of the dividend register, and the result of the subtraction is stored in the (N−M)-th through the (2N−2M−3)-th bits of the quotient register, in parallel or by shifting. Otherwise, the (2N−M)-th through the (X−1)-th bits of the dividend register are stored into the (N−M)-th through the (2N−2M−3)-th bits of the quotient register, respectively, in parallel or by shifting. The quotient is represented by the 0-th through the (2N−2M−3)-th bits of the quotient register.
In another aspect, the present invention provides a digital division circuit for performing said division, wherein the dividend is stored in a dividend register. In one embodiment, the digital division circuit comprises: (a) a first circuit connected to the dividend register for providing the M-th through the (N−1)-th bits of the dividend as lower order bits of the quotient; (b) a second circuit connected to the dividend register for providing the (2N−M)-th through the (X−1)-th bits of the dividend as a first higher order bit segment for the quotient; (c) a detector connected to the dividend register for detecting the (N−1)-th and the (2N−M−1)-th bits of the dividend and for generating a control signal if: (1) the (N−1)-th bit of the dividend is “1” and (2) if the (2N−M−1)-th bit of the dividend is “0”; (d) a subtractor connected to the second circuit for subtracting the value “1” from data including the (2N−M)-th through the (X−1)-th bits of the dividend and generating output bits as a second higher order bit segment for the quotient; and (e) a selector connected to the second circuit and to the subtractor, and responsive to the control signal from the detector for selecting between the first and second higher order bit segments to provide higher order bits of the quotient, wherein: (1) in the presence of the control signal the selector provides said second higher order bit segment as the higher order bits of the quotient, otherwise, (2) in the absence of the control signal the selector provides said first higher order bit segment as the higher order bits of the quotient. The higher and lower order bits represent a value of the quotient. The digital division circuit can further comprise a quotient register for storing the quotient therein. The first circuit is connected to the dividend register and to the quotient register for storing the M-th through the (N−1)-th bits of the dividend register into the 0-th through (N−M−1)-th bits of the quotient register, respectively, as the lower order bits of
Gold Cliff
Lee John
Maxtor Corporation
Ngo Chuong Dinh
LandOfFree
Method and circuit for digital division does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and circuit for digital division, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and circuit for digital division will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3090306