Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-11-03
2002-06-04
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S497000
Reexamination Certificate
active
06401107
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to processing arithmetic operations with microprocessors and, in particular, to reducing computational error in such processors having no rounding support.
BACKGROUND OF THE INVENTION
Many arithmetic operations performed by microprocessors require extra numeric precision to represent the result of the operation. For example, when multiplying two 16-bit integers, the product may contain 31 valid bits. Microprocessors optimized for signal processing functions typically have hardware support to deal with the precision expansion. For example, some processors store operation results in an accumulator that has a wider word length than the operands, and have special instructions to round the results automatically. Other processors, especially general purpose processors used in personal computers or hand-held devices, usually are not equipped with such special hardware. Conventionally, the method to deal with precision expansion is to compute the results for at least one bit more precision than is required, then perform rounding in software.
To compute a result of an arithmetic operation with excess precision, one can either implement multiple precision arithmetic in software or limit the numerical range of the operands. In the former, multiple registers are banked together to store the result, and in the latter, by not utilizing the entire word length of the register for the operands, extra bits are made available to implement the extra precision. With at least one bit of excess precision, rounding of the result of the arithmetic operation can be performed in software by modifying the result based on the “add-one” principle, i.e., adding 0.5 to the result and setting the bits to the right of the decimal point to zero. (Here, it is assumed that the placement of the decimal point is such that the bits to the right of the decimal point can be ignored for the target precision). It is common knowledge that the quantization noise or rounding error introduced by the above procedure has an average value of zero, i.e., no bias is introduced, under the assumption that the quantization noise is uniformly distributed.
FIG. 1
illustrates the conventional method for dealing with the extra numerical precision required for the result of an arithmetic operation in processors with no rounding support. The process
101
consists of multiple stages of operations, each using operands having a first number of valid bits (e.g., 16). The result of the operation is computed and represented using a second number of bits (e.g., 32), greater than the first number of bits. After each operation, rounding is performed in software by adding 0.5 to the result of the operation and truncating and/or shifting the result such that the result is represented using the first number of valid bits (e.g. 16). In other words, consider the placement of decimal point such that the result of operation is represented as X.Y, where X is the target precision portion of the result and Y is the excess precision portion. Software rounding produces floor(X.Y+0.5). More particularly, software rounding produces a number that is the largest integer not exceeding (X.Y+0.5). It can be shown that for Y uniformly distributed between 0 and 1, the expectation or average of X.Y-floor(X.Y+0.5) is zero, (i.e., no bias).
When multiple stages of operations are involved, the effect of bias will be amplified if the biases are allowed to accumulate. This may result in unacceptable computational error. While no bias is introduced in the quantization noise of the conventional method described above, extra processing is needed to implement the multiple precision arithmetic and software rounding. If the excess precision is provided by limiting the dynamic range of the operands (as opposed to multiple precision arithmetic), there will a loss of dynamic range and the extra processing associated with software rounding is still needed. When multiple stage operation is involved, the extra processing may become a significant burden to the microprocessor implementing these operations. Therefore a need exists for a method and apparatus for reducing computational error in a processor having no rounding support that does not require the extra processing needed with current techniques.
REFERENCES:
patent: 3891837 (1975-06-01), Sunstein
patent: 4727506 (1988-02-01), Fling
patent: 4750146 (1988-06-01), Dalqvist
patent: 5894428 (1999-04-01), Harada
Conger Keith
Yang Jian
Malzahn David H.
Motorola Inc.
LandOfFree
Method and processor for reducing computational error in a... 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 processor for reducing computational error in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and processor for reducing computational error in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2951666