Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-09
2001-10-09
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06301598
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Not applicable.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a method for estimating a square of a number and more particularly to estimating the square of negative and positive integers. More particularly still, the invention relates to a flexible technique for estimating a square of an integer in accordance with a desired level of accuracy.
2. Background of the Invention
Many functions performed by digital processing systems such as personal computers and video systems require advanced mathematical calculations. For example, many video systems require the calculation of a “square” of a number. Squaring a number is the mathematical operation by which the number is multiplied by itself. The square of the number 10, for example, is represented as 10
2
which equals 10×10 or 100.
Squaring a number is required or recommended for many applications such as for motion estimation in a video processing system. Motion estimation involves determining whether an object has moved from one video frame to the next. One technique for estimating motion involves calculating the sum of square differences between the object at its current location versus its location in a previous frame. That is, the differences between the values of the corresponding “pixels” comprising the image between frames is calculated and then squared. Finally, the squared values are added together and compared to a predetermined threshold value to determine if the object has moved.
Implementing a digital logic circuit to compute accurately a square typically requires a relatively large circuit. The size of a circuit can be measured in terms of “logic gates” or “cell units.” A logic gate usually refers to a NAND gate logic unit which is a basic logic unit comprising many digital circuits. A NAND gate comprises one or more switching transistors. By combining NAND gates, and/or other types of logic gates, advanced digital circuits can be created for performing a variety of functions. A cell unit refers to a unit of surface area on an integrated circuit. A single logic gate generally requires approximately 3 cell units. The size of a digital circuit thus can be measured in terms of gates or cell units. This disclosure uses the cell unit to characterize the size of the circuits described herein.
Various techniques have been suggested for determining the square of a number. Some digital systems include a multiplier circuit which actually calculates the square of an input number. Multipliers, however, are undesirably large and expensive and consume a great deal of electrical power. A multiplier that can multiply two 9-bit integers, for example, requires 2,281 cell units for its implementation.
Alternatively, a table look-up method can be implemented for determining the square of a number. In this method, a table stored in memory includes the squares of a plurality of predefined numbers. The squares of the numbers, therefore, are predetermined and loaded into the table Thus, rather than actually calculating the square of a number, the square can be obtained directly from the table. If the square of a number is not stored in the table, the squares of the closest numbers can be used to estimate or calculate the desired result. Table look-up techniques generally require larger circuits for their implementation than multipliers. A table look-up implementation that includes look-ups for 512 squares requires approximately 4300 cell units.
Thus, a technique is needed for determining a square of a number that can be implemented with a smaller circuit and consume less power than previously possible. Despite the advantages offered by such a system, to date no such system is known to exist.
BRIEF SUMMARY OF THE INVENTION
The problems noted above are solved in large part by a square estimator that includes a square estimate term generator for producing at least one estimate term representative of an estimate of the input number and summing logic coupled to the square estimate term generator for adding together the estimate term from the square estimate term generator. Negative correction logic can also be provided to permit the square estimator to estimate the square of a negative number. If included, the negative correction logic is coupled to the square estimate term generator and the summing logic. The square estimate term generator produces an output estimate term that is added to a negative correction term generated by the negative correction logic. The resulting value from the summing logic represents an estimate of the square of the input number to the square estimator.
The level of accuracy in the estimate produced by the square estimator can be varied by varying the number of estimate terms produced by the square estimate term generator. Accordingly, the square estimate term generator can be configured to include one or more term generators. If a less accuracy is acceptable the square estimate term generator can be configured with only a single term generator. This single term generator produces an output estimate term that is based on input number to the square estimator. This term is then added by the summing logic to the negative correction term from the negative correction logic to produce the estimate of the square of the input number. If greater accuracy is desired, the square estimate term generator can be configured to include a second term generator which produces an estimate term that, when added to the first estimate term and the negative correction term, produces an estimate of the input number that is generally more accurate than the estimate generated without the second term generator. If further accuracy is desired, additional term generators can be included in the square estimate term generator.
Alternatively, the square estimate term generator can be constructed with enough term generators to achieve 100 percent accuracy over a desired range of input values. Each term generator included in the square estimate term generator can also be configured to accept a select signal that enables or disables the associated term generator. Thus, the square estimate term generator can be programmed by turning on and off various term generators to produce square estimates with varying degrees of accuracy.
The square estimator described herein permits an estimate of the square of an input number to be generated with any desired level of accuracy. Further, the estimate of the square of an input number can be performed generally using fewer logic gates then required for many other techniques for calculating the square of a number. These and other advantages will become apparent once the following disclosure and accompanying drawings are read.
REFERENCES:
patent: 3610906 (1971-10-01), Stampler
patent: 5337267 (1994-08-01), Colavin
patent: 5394350 (1995-02-01), Gong et al.
patent: 5629885 (1997-05-01), Pirson et al.
patent: 6018758 (2000-01-01), Griesbach et al.
patent: 6032169 (2000-02-01), Malzahn et al.
Dierke Gregg
Neuman Darren D.
LSI Logic Corporation
Mai Tan V.
LandOfFree
Method and apparatus for estimating a square of a number 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 estimating a square of a number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for estimating a square of a number will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556252