Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-06-26
2001-09-18
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06292814
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods and apparatus for implementing and using a sign function suitable for use, e.g., in a single instruction multiple data (SIMD) system.
BACKGROUND OF THE INVENTION
The sign(x) function:
sign
(
x
)
=
{
+
1
x
>
0
0
x
=
0
-
1
x
<
0
(
1
)
is encountered in many common applications.
In applications involving the use of single instruction single data (SISD) processors, the sign(x) function is frequently implemented as a series of logical tests implemented as individual processor instructions, e.g., a greater than test followed by an equals test. If the output of any test in the series is true, the next test need not be performed since, in a SISD embodiment, the output of the sign(x) function can be generated from a true outcome of any one of the logical tests (>, =, <) used to implement the function.
Accordingly, using a common SISD processor, the sign(x) function can be determined with relative ease using software and hardware supported logic tests. For this reason, among others, application designers have felt little need to avoid the use of the sign(x) function when designing applications including, for example, video processing operations.
One standard for the coding of motion pictures, commonly referred to as the MPEG-2 standard, described in ISO/IEC 13818-2 (Nov. 9, 1994) Generic Coding of Moving Picture and Associated Audio Information: Video (hereinafter referred to as the “MPEG” reference), relies heavily on the use of discrete cosine transforms, data quantization and motion compensated prediction to code video data. In this patent application, references to MPEG-2 compliant data streams and MPEG-2 compliant inverse quantization operations are intended to refer to data streams and inverse quantization operations that are implemented in accordance with the requirements set forth in the MPEG reference.
The MPEG reference describes in detail the processes involved in decoding a video bitstream that is compliant with the MPEG-2 standard. Many processes are involved in the decoding of a video bitstream. Important to the development of low cost video decoders, are methods for efficient implementation of these processes. One of these process involved in decoding an MPEG-2 image is called inverse quantization.
Quantization is the process that is used in the digital processing of signals, e.g., video encoding, in which an element from a finite set of digital codewords is used to represent approximately, the value of a sampled signal. The digital codewords that are produced by the quantization process for an input sample represent an approximation of the original amplitudes of the signal being processed.
Inverse quantization is the opposite process of quantization. The inverse quantization process takes as its input a digital codeword from a finite set of codewords and produces a so called reconstruction level that is an approximation of the original amplitude of the sample.
The MPEG-2 standard defines methods for the inverse quantization of DCT coefficients. A significant problem encountered when trying to implement the MPEG-2 inverse quantization process is the computation of the sign(x) function required for inverse quantization.
The inverse quantization of one 8×8 block of coefficients, in accordance with the MPEG-2 standard, is described by equations (2)-(6) below.
F
″
[
v
]
[
u
]
=
(
2
×
QF
[
v
]
[
u
]
+
k
)
×
W
[
w
]
[
v
]
[
u
]
×
quantizer
—
scale
32
(
2
)
where:
k
=
{
0
INTRA
sign
(
QF
[
v
]
[
u
]
)
NON
INTRA
and
(
3
)
sign
(
x
)
=
{
+
1
x
>
0
0
x
=
0
-
1
x
<
0
(
4
)
QF[v][u] is a two dimensional array of digital codewords or quantized DCT coefficients, W[w][v][u] is a quantizer matrix, and quantizer_scale is a common scaling factor used for one or more macroblocks. The parameters v and u are used to index each DCT coefficient and the parameter w depends upon the coding type (INTRA or NON-INTRA) and the color component (luminance or chrominance). Following this step, the results undergo a saturation stage to ensure that the reconstructed values lie within the allowed range. This is shown in the equation 5 below.
F
′
[
v
]
[
u
]
=
{
2047
F
″
[
v
]
[
u
]
>
2047
F
″
[
v
]
[
u
]
-
2048
≤
F
″
[
v
]
[
u
]
≤
2047
-
2048
F
″
[
v
]
[
u
]
≤
2048
(
5
)
The final step in the inverse quantization process is to perform the mismatch control as shown below:
sum
=
∑
v
=
0
7
∑
u
=
0
7
F
′
[
v
]
[
u
]
F[v][u]=F′[v][u] ∀u, v except u=v=7
F
[
7
]
[
7
]
=
{
F
′
[
7
]
[
7
]
if
sum
is
odd
{
F
′
[
7
]
[
7
]
-
1
if
F
′
[
7
]
[
7
]
is
odd
F
′
[
7
]
[
7
]
+
1
if
F
′
[
7
]
[
7
]
is
even
if
sum
is
even
(
6
)
The steps that are described by equations (2)-(6) are required for an inverse quantization process that is truly compliant with the MPEG-2 standard. Table I, illustrated in
FIG. 1
, shows the approximate number of discrete operations that are required to perform one particular known MPEG-2 inverse quantization operation on a block of 64 coefficients representing 64 values to be processed. Note that in Table 1, it is assumed that 2 compare operations are used to implement the sign(x) function for each processed coefficient.
Notably, while the mismatch control operation expressed as equation (6) appears to be the most complicated of all the steps in the MPEG-2 inverse quantization processes, it actually requires the least amount of computation, about 10% of the total. While the sign(x) function appears to be much less complicated than the mismatch control, the cost in terms of required computations for that function is about 20% of the total number of computations required.
Accordingly, when attempting to reduce the number of computations required to implement an inverse quantization operation, the sign(x) function presents an area where there is potential for improvement in terms of the number of computations which need to be performed.
To increase computational efficiency and through put, single instruction, multiple data, (SIMD) processor designs and systems are becoming more common. SIMD architectures allow the processing of multiple data elements simultaneously by treating a single n bit word as comprising, e.g., k, multiple distinct sub-words which are to be processed separately. A well-designed SIMD architecture system allows considerable performance advantages of more traditional Single-Instruction Single Data (SISD) architecture systems. An example over a SIMD architecture is the MMX technology that is currently in usage in the microprocessor area.
For purposes of explanation, suppose that there is a system based on a SIMD architecture that operates on four data samples at the same time. In such a system the data samples would have to be presented to the processing unit in the arrangement shown in the diagram of FIG.
2
. Here, one word that is n-bits in length, contains four sub-words, each n/4-bits in length. Accordingly, even though one n-bit word is presented, e.g., to the processor, there are actually four pieces of data that are embedded in that word. When presented to the SIMD processing unit, each of these quarter-words is treated independently of the others. The independent processing of data elements included in a single word is one of primary features of SIMD processing.
As an example of SIMD processing, suppose that it is desired to multiply two sets of numbers, {a, b, c, d} and {e, f
Hitachi America Ltd.
Mai Tan V.
Straub Michael P.
Straub & Pokotylo
LandOfFree
Methods and apparatus for implementing a sign function 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 implementing a sign function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for implementing a sign function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521526