Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-04-23
2001-10-02
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S550000
Reexamination Certificate
active
06298368
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer arithmetic. More particularly, this invention relates to a circuit and method for calculating an approximation of the square of a binary number.
BACKGROUND OF THE INVENTION
The square of a number is desired by many applications in computers, signal processing, computer graphics, and computer arithmetic. In many of these applications, calculating an approximation of the square of a number meets the needs of the application. For example, take a number sampled by a 16-bit analog to digital converter that represents a value between zero and one. This could be represented as a 16-bit number with the radix point to the left of the most significant bit. Also, since this number has only sixteen bits of precision, then there are at most sixteen significant binary digits. When this number is squared, the result would be thirty-two bits long with the radix point still to the left of the most significant bit. However, because the result of the computation can be no more accurate than the least-accurate number in the data, at most sixteen of these bits are significant. The lower order sixteen bits should be rounded off. Because the lower order sixteen bits should be removed to round off the result to an appropriate number of significant binary digits, an approximation of the square of this number that produces the correct sixteen higher order bits can be a sufficient result.
Accordingly, a method and apparatus that produces an approximate square of a number in less time, and takes less area on an integrated circuit than calculating an exact square has broad need and application in the art.
SUMMARY OF THE INVENTION
A preferred embodiment of the invention can provide an approximate square of a number using about one-half the area on an integrated circuit, about one-half the power, and only taking about one half-the time compared to calculating an exact square using a full multiplier. The invention is scalable to accommodate inputs with different numbers of bits and can be implemented using existing circuits and techniques.
An embodiment of the invention may be implemented as a partial Booth-encoded multiplier. This partial Booth-encoded multiplier has M+1 fewer rows of Booth encoding and shifter-adder rows than a full Booth-encoded multiplier. The missing rows correspond to the M+1 least significant bits. A multiplier is generated by truncating the number to be squared by removing these M+1 least significant bits. This multiplier is applied to the rows of the partial Booth-encoded multiplier. In addition, the least significant bit of the multiplier (the Mth numbered bit of the original number when counting starts with the 0
th
bit) is applied to the −1 bit input of the first Booth encoder. A multiplicand is generated by removing the Mth numbered bit of the original number, shifting the least significant M bits up by one bit, and placing a zero in the least significant bit position. This multiplicand is applied to the columns of the partial-Booth encoded multiplier to be shifted, added, and subtracted according to Booth's algorithm. The output of the partial Booth-encoded multiplier array is an approximate square of the number.
Other aspects and advantages of the present 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: 5629885 (1997-05-01), Pirson et al.
patent: 5957999 (1999-09-01), Davis
Agilent Technologie,s Inc.
Mai Tan V.
Neudeck Alexander J.
LandOfFree
Method and apparatus for efficient calculation of an... 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 efficient calculation of an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient calculation of an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2589083