Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-09-09
2003-03-04
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S498000
Reexamination Certificate
active
06529930
ABSTRACT:
FIELD OF INVENTION
The present invention relates to methods and apparatus for performing saturation operations, e.g., signed saturation operations.
BACKGROUND OF THE INVENTION
Signed saturation operations are used to limit values to a pre-selected range of values, e.g., a range of values extending from and including a positive saturation value (PSV) which serves as an upper bound or threshold, and a negative saturation value (NSV) which serves as an lower bound or threshold. Such operations are used in numerous applications including MPEG-2 video decoding to limit the size and/or range of values which need to be stored and/or processed.
FIG. 1
figuratively illustrates a signed saturation operation in terms of three regions identified using the reference numerals
1
,
2
,
3
. As discussed above, the PSV and NSV serve as threshold values in determining an output value Y based on an input value X. In
FIG. 1
, region
1
corresponds to values of X which are greater than the PSV. For each value of X falling within region
1
, an output value PSV is generated. Thus, values of X exceeding the threshold PSV are limited to the PSV.
Region
2
extends between and includes the PSV and NSV. In this region, an input value X is not outside the bounds determined by the PSV and NSV. Accordingly, in region
2
, the output value Y is set equal to X, i.e., each input value is output without being altered. Region
3
corresponds to values less than the NSV. In this region, the output value Y is set equal to the NSV, i.e., for each input value X which falls in this region, an output value Y equal to the NSV is produced.
Most modern digital devices, e.g., computers, digital video decoders, digital communications devices, etc. operate using binary numbers, i.e., numbers represented using 1's and 0's. In such digital systems, 2's compliment representation is frequently used to represent negative numbers. In such a system, the left most bit of a number represents the most negative possible value that can be produced using a fixed number, e.g., k, of bits. Accordingly, a k-bit number expressed using two's compliment representation can take on the values in the range of:
−2
k−1
to +2
k−1
−1.
As discussed above, a signed saturation operation is frequently used to limit an input value to a range of values. In particular, it is often desirable to use a signed saturation operation to limit values to a range which may be represented using a fixed number, e.g., a target saturation width, of k bits. In such cases, the PSV will be +2
k−1
−1 while the NSV will be −2
k−1
. For example, input values in a range requiring N bits, e.g., 16 bits, per value, may be processed using a signed saturation operation to generate a set of values which can be represented using k, e.g., 8, bits per value.
Frequently, signed saturation operations are implemented through the use of software which utilizes multiple standard compare operations to perform the saturation operation. Unfortunately, such compare operations can be costly in terms of processing requirements and time consuming to implement. In the case of MPEG-2 video decoding and other applications which require a large number of signed saturation operations to be performed, the time and processing resources required to perform signed saturation operations using software and multiple compare operations can hinder overall performance.
Given that MPEG-2 video decoding applications and other applications which utilize signed saturation operations are becoming ever more common on computer systems, e.g., personal computers, there is a growing need for improved methods of implementing signed saturation operations.
By incorporating multiple saturation circuits into a single processor, support for single instruction multiple data (SIMD) signed saturation operations is achieved. In such an embodiment, multiple signed saturation operations are performed simultaneously on the data associated with a SIMD saturation instruction.
The saturation circuits of the present invention can be incorporated into a wide range of digital devices, in addition to processors, e.g., they can be incorporated into video decoders.
In particular, there is a need for methods and apparatus for implementing signed saturation operations in computers and other digital electronics devices without having to utilize software involving multiple compare operations. In order to support a wide range of applications, it is desirable that at least some new methods and apparatus be capable of supporting a range of output values determined by a variable target width of k binary bits. It is also desirable that at least some methods and apparatus be capable of supporting single instruction multiple data (SIMD) processor operations.
SUMMARY
Methods and apparatus for performing signed saturation of binary numbers to arbitrary powers of two are described. Given an n-bit signed binary word, the methods and apparatus of the present invention perform a signed saturation to k-bits where the value of k is allowed to vary such that 1<k<n. Through the use of hardware circuits of the present invention the signed saturation operation is implemented in a more efficient manner than software implementations which utilize multiple compare operations.
The signed saturation circuits of the present invention can be incorporated into processors, e.g., CPUs, to provide hardware implementation within the CPU that supports a signed saturation processor instruction. The signed saturation instructions can accept the data value or values upon which the operation is to be performed, and, optionally, a value k indicating the number of bits to which the data value is to be saturated. In response to a signed saturation instruction, in accordance with the present invention, one or more saturation circuits are used to implement the instruction and perform a saturation operation on the data value or values which are received with the instruction. In the case of a SIMD instruction, multiple saturation circuits are used in parallel to implement the instruction.
In MPEG-2 decoding, at the end of the inverse quantization process the quantities being processed undergo signed saturation to 12-bits. In various embodiments, one or more signed saturation circuits of the present invention are incorporated into a fixed function hardware circuit that performs, for example, MPEG-2 video decoding.
Additional features and embodiments of the present invention are discussed in the detailed description which follows.
REFERENCES:
patent: 5448509 (1995-09-01), Lee et al.
patent: 5508951 (1996-04-01), Ishikawa
patent: 5644519 (1997-07-01), Yatim et al.
patent: 5847978 (1998-12-01), Ogura et al.
patent: 5915109 (1999-06-01), Nakakimura et al.
patent: 5959874 (1999-09-01), Lin et al.
patent: 5974540 (1999-10-01), Morikawa et al.
patent: 6202077 (2001-03-01), Smith
patent: 6237084 (2001-05-01), Morikawa et al.
International Standards Organization—Moving Picture Experts Group, Recommendation H.222.0, ISO/IEC 13818-1 titled “Information Technology—Generic coding of Moving Pictures and Associated Audio: Systems”, Nov. 13, 1994, pp. ii-130.
International Standards Organization—Moving Picture Experts Group, Recommendation ITU-T H.262, ISO/IEC 13818-2 titled “Information Technology—Generic Coding of Moving Pictures and Associated Audio Information: Video”, Nov. 9, 1994, pp. i-222.
Plotnick Michael A.
Sazzad Sharif Mohammad
Hitachi America Ltd.
Straub Michael P.
Straub & Pokotylo
LandOfFree
Methods and apparatus for performing a signed saturation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for performing a signed saturation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for performing a signed saturation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3016172