Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-07-12
2001-06-05
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S551000
Reexamination Certificate
active
06243728
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of hardware used for implementing arithmetic operations such as processor instructions. More specifically, the present invention relates to a binary shift right circuit for signed and non-signed binary values.
2. Related Art
Binary right shift circuits input multi-bit binary values and shift the bits to the right by a predetermined number of bits. By right shifting, the binary value is typically divided. For instance, a right shift by one bit position divides the original number by two. A right shift by three bit positions divides the original number by eight, etc. Generally, a right shift by n bit positions will divide the original number by 2
n
. Right shift circuits of the prior art ignore the bits that are shifted out of the original binary value (e.g., truncates the result) and zeros are typically shifted into the right side, which is also called the most significant bit (MSB) position. Many arithmetic functions utilize the right shift operation and, in practice, arithmetic logic units (ALUs) of hardware processors always contain one or more right shift hardware units. One such arithmetic operation that utilizes the right shift operation is used in conjunction with processing Motion Picture Expert Group (MPEG) digital data.
The basic steps in MPEG compression and decompression processes are based around computationally demanding functions such as the Inverse Discrete Cosine Transform (IDCT) function, the Discrete Cosine Transform (DCT), Quantization and Motion Compensation functions. All of these functions require operations that shift, average, and/or divide multiple operands. For instance, a software MPEG decoder performs the IDCT function and Motion Compensation processes. More specifically, the IDCT function transforms the MPEG encoded coefficients back to their pixel values. In some decoders, an integer processor is preferred for performing IDCT and Motion Compensation functions because it is faster than a floating point processor.
However, the use of integer processors in the MPEG decoder requires conversion of the floating point values into binary integer values. Specifically, in one operation, a 12-bit range coefficient is input (integer) but the pixel values generated by the decoder are in the 9-bit range. Computations are performed using 16-bit operations to avoid any overflow problems. In this particular MPEG decoding process, a prescaling step is performed where the input value is left shifted by 3 bits to preserve precision in the 16-bit operations that follow the prescaling step. In the end, the result is then right shifted to accommodate the 9-bit output and to compensate for the prescaling operation.
Unfortunately, the right shift circuits of the prior art truncate their results, e.g., discarding the bits that are shifted out of the LSB (least significant bit) positions. This is disadvantageous because one of the main objectives of MPEG processing is to retain a high image quality. Another attribute of MPEG processing is that fast computations need to be performed because the MPEG data is typically large and transmitted isochronously. Therefore, computational latencies can produce unwanted artifacts (e.g., image jitter, etc.) in the audio/visual playback. In order to maintain high data precision and image quality, it would be advantageous to provide a right shift circuit that does not discard these truncated bits, yet does not require additional latencies in the computation. The present invention provides these advantages.
SUMMARY OF THE INVENTION
Accordingly, the present invention provides a right shift circuit that performs both right shifting and a rounding function, within a single instruction, thereby providing additional accuracy for the right shifted result. The rounding functionality is performed within the right shift instruction and therefore the present invention does not require execution of additional rounding instructions by the processor in order to achieve the same accuracy. The present invention preserves high image quality without sacrificing the speed of operation and is particularly advantageous for MPEG decoding although the circuit of the present invention can be applied to any number of uses.
A partitioned shift right circuit is described herein that is programmable and contains selective rounding support. The circuit of the present invention accepts a 32-bit input binary value and a binary shift amount vector and then performs a right shift operation on the 32-bits and automatically rounds the result(s). Signed or unsigned values can be accepted with or without sign extension. The right shift circuit is partitioned so that the 32-bit value can represent: (1) a single 32-bit number; or (2) two 16-bit values. A two bit selection input indicates the particular partition format. In a preferred embodiment, only two partition modes are available, a full 32-bit mode and a second mode supporting two 16-bit input values. In this configuration one signal, f
0
, selects the appropriate mode.
In operation, if the input value is not negative, then one (“1”) is added at the guard bit position and a right shift with truncate is performed. However, if the input is negative and the guard bit is zero, then no addition is done and a right shift with truncate is performed. If the input is negative and the guard bit is one and the sticky bit is zero, then no addition is done and a right shift with truncate is performed. Lastly, if the input is negative and the guard bit is one and the sticky bit is one, then one is added at the guard bit position and a right shift with truncate is performed. The right shift circuitry used by the present invention is fully partitioned to accept word or half-word input and contains multiple cascaded multiplexer stages for performing partitioned right shifting and supports signed shifting with or without extension. Each multiplexer stage can be programmed to perform a selected right shift amount (including
0
shift). The right shift circuit of the present invention can be used in multi-media applications and can also be used for general purpose and VLIW (very long instruction word) processor without performance degradation.
More specifically, an embodiment of the present invention includes a circuit having a decoder receiving a shift value, indicating a number of bits to right shift an input binary value, and producing a decoded result indicating a guard bit position; a plurality of rounding control circuits together producing a multi-bit mask, each circuit receiving a respective bit of the decoded result and also receiving a respective predetermined number of bits of the input binary value, each of the rounding control circuits separately computing a respective sticky bit corresponding to its bit position and also computing a mask bit based on the respective sticky bit, a sign bit and the respective bit of the decoded result; an adder circuit adding the multi-bit mask to the input binary value to produce a sum value; and a right shift circuit producing a binary shifted result by right shifting the sum value a number of bits corresponding to the shift value.
Embodiments of the present invention include the above and wherein the right shift circuit comprises a plurality of cascaded multiplexer stages wherein each multiplexer stage is programmable to select a right shift amount from a predetermined range of values. Embodiments of the present invention include the above and wherein, for an ith rounding control circuit, the predetermined number of bits of the input binary value are the (i-1)th, (i-2)th, (i-3)th and (i-4)th bits of the input binary value and wherein the ith rounding control circuit comprises: OR logic producing a logical OR result of the (i-1)th, (i-2)th, (i-3)th and (i-4)th bits; output circuitry producing logical one in the mask provided the sign bit indicates a non-signed input binary value and its respective bit of the decoded result is a logical one; and wherein the output circuitry also produces a logical on
Chehrazi Farzad
Farooqui Aamir Alam
Li Wei-Jen
Oklobdzija Vojin G.
Yu Andy W.
Malzahn David H.
Sony Corporation of Japan
Wagner , Murabito & Hao LLP
LandOfFree
Partitioned shift right logic circuit having rounding support does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partitioned shift right logic circuit having rounding support, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioned shift right logic circuit having rounding support will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2540901