Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-22
2001-11-13
Mai, Tan V. (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06317771
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of digital division. More particularly, the present invention provides for faster and more efficient digital division in integrated circuits.
2. Description of the Related Art
Digital, or binary, division is a process whereby a binary number, referred to as a dividend is divided by a second binary number referred to as a divider. Digital division is increasingly required for many applications such as high quality graphics rendering. Unfortunately, division circuits are usually much larger than multiplier circuits for an equivalent data word length. One conventional method of performing digital division known as restoring and non-restoring division typically involves subtracting the divider from a reference number referred to as a current number. These methods of performing digital division generally require that the divider be added back to the current number after each computation stage. In the restoring method, the decision whether to add back the divider to the current number depends on the result of a subtraction stage. In the non-restoring method, a selection between addition and subtraction is made in the next computation stage following the subtraction stage. In either case, substantial amounts of logic and related logic circuitry are required to implement restoring and non-restoring division. Such additional logic typically can include at least an exclusive-OR (XOR) gate for every bit, which is the equivalent of five (5) NAND gates for every bit.
Hence, conventional techniques for implementing digital division require substantial amounts of logic resources and related logic circuitry. When the integrated circuit is a programmable logic device (PLD), large amounts of valuable programming resources are required to implement digital division, thereby limiting the size or precision of the data words that can be accommodated. Additionally, the serpentine data paths required to connect the related logic circuitry within a particular integrated circuit result in slow performance and can, in some cases, cause the integrated circuit to be non-functional.
In view of the foregoing, it would be advantageous and therefore desirable to provide an efficient method of performing digital division that can be implemented in an integrated circuit using fewer logical resources. By using fewer logical resources, the precision and the speed of the digital division as performed by the integrated circuit are able to be increased. Additionally, the probability of successfully implementing the digital division in an integrated circuit, such as PLD, is commensurably increased.
SUMMARY OF THE INVENTION
The present invention relates to an efficient method of performing digital, or binary, division in an integrated circuit. The invention provides for faster and more efficient digital division in integrated circuits. Efficient digital division is particularly advantageous for applications that require large amounts of division computations (e.g., graphics rendering). While the integrated circuit can be of many types, the present invention is well suited for a complex programmable logic device (CPLD) having various functional blocks included therein. Any number of functional blocks within the CPLD can be suitably coupled and programmed to perform the inventive digital division.
In one embodiment of the invention, a method for performing digital division is disclosed. A quotient data word is generated from a divider data word and a dividend data word. The divider data word and the dividend data word each include P bits where P is a precision index indicative of a desired precision of the digital division. The method can be performed by the following operations. Selected divider data word bits and selected current data word bits from a current number data word are operated on to form a subtraction result data word and an associated remainder result data word. A logical OR result data word based upon at least said associated remainder result data word is then generated. A quotient data word bit of the quotient data word is set to a predefined value based upon the logical OR result data word. A new current number data word is then generated based upon the logical OR result data word, the subtraction result data word, the current number data word, and the dividend data word. In a preferred embodiment, the operation that forms subtraction result data word and the associated remainder result data word is subtraction.
In another embodiment of the invention, a digital division circuit for generating a quotient data word from a divider data word and a dividend data word is disclosed. The divider data word and the dividend data word each include P bits where P is a precision index indicative of a desired precision of the digital division. The digital division circuit includes a first means for performing the function of operating on selected divider data word bits and selected current number data word bits from a current number data word to form a subtraction result data word and a associated remainder result data word. The digital division circuit also includes a second means connected to the first means for performing the function of generating a logical OR result data word based upon at least the associated remainder result data word. The digital division circuit further includes a third means connected to the second means for performing the function of setting a quotient data word bit of the quotient data word to a predefined value based upon the logical OR result. The digital division circuit also includes a fourth means connected to the third means for performing the function of generating a new current number data word based upon the logical OR result data word, the subtraction result data word, and the current number data word.
In a preferred embodiment, the digital division circuit is included in an integrated circuit that includes a programmable logic device.
In still another embodiment of the invention, a division circuit for generating a quotient data word from a divider data word and a dividend data word, the divider data word and the dividend data word each include P bits where P is a precision index indicative of a desired precision of the digital division is described. The division circuit includes a plurality of input/output lines arranged to receive the dividend data word and the divider data word and a subtractor connected to the input/output lines for subtracting selected divider data word bits from selected current number data word bits to form a subtraction result data word and an associated remainder result data word. The division circuit also includes a logical ORing unit connected to the subtractor for generating a logical OR result data word based upon at least the associated remainder result data word. The division circuit also includes a bit setter connected to the logical ORing unit for setting a quotient data word bit of the quotient data word to a pre-defined value based upon the logical OR result. The division circuit further includes a selector connected to the logical ORing unit and the input/output lines used to create a new current number data word based upon the subtraction result data word, the current number data word and selected dividend data bits.
Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.
REFERENCES:
patent: 5027309 (1991-06-01), Koumoto et al.
patent: 5493523 (1996-02-01), Huffman
Altera Corporation
Beyer Weaver & Thomas LLP
Mai Tan V.
LandOfFree
Method and apparatus for performing 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 apparatus for performing digital division, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing digital division will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572440