Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-05-04
2001-06-05
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S402000
Reexamination Certificate
active
06243730
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to media processors, and in particular, is directed to methods and systems for performing the faster two-dimensional inverse discrete cosine transforms (IDCT) in media processors.
A “media processor” is a type of computer which capable of processing video and audio signals. The market demand for fast media processors has increased with the demand for popular entertainment and consumer electronic goods. Typically, multimedia applications handle video and audio signs in real time and are often slow to execute. Media processors, therefore, are often specially designed for a particular application. Conventional media processors, for example, may have such features as a partitioned Single Instruction, Multiple Data (SIMD) architecture, custom instruction set, and wide registers to efficiently perform signal processing of image data. Another technique for improving media processors is to specially design the media processor to perform frequently required, time-intensive operations more efficiently.
Discrete cosine transforms (DCT) and inverse discrete cosine transform (IDCT) are widely used operations in the signal processing of image data. Both are used, for example, in the international standards for moving picture video compression put forth by the Motion Picture Experts Group (MPEG). DCT has certain properties that produce simplified and efficient coding models. When applied to a matrix of pixel data, the DCT is a method of decomposing a block of data into a weighted sum of spatial frequencies, or DCT coefficients. Conversely, the IDCT is used to transform a matrix of DCT coefficients back to pixel data.
FIG. 1
is a basic flow diagram showing the encoding and decoding processes of a prior art digital video (DV) codec. DV codecs are one example of a device using a DCT-based data compression method. In the blocking stage, the image frame is divided into N by N blocks of pixel information including, for example, brightness and color data for each pixel (stage
100
). A common block size is eight pixels horizontally by eight pixels vertically. The pixel blocks are then “shuffled” so that several blocks from different portions of the image are grouped together (stage
110
). Shuffling enhances the uniformity of image quality.
Different fields are recorded at different time incidents. For each block of pixel data, a motion detector looks for the difference between two fields of a frame (stage
115
). The motion information is sent to the next processing stage (stage
120
). In stage
120
, pixel information is transformed using a DCT. An 8—8 DCT, for example, takes eight inputs and returns eight outputs in both vertical and horizontal directions. The resulting DCT coefficients are then weighted by multiplying each block of DCT coefficients by weighting constants (stage
125
).
The weighted DCT coefficients are quantized in the next stage (stage 140). Quantization rounds off each DCT coefficient within a certain range of values to be the same number (stage
140
). Quantizing tends to set the higher frequency components of the frequency matrix to zero, resulting in much less data to be stored. Since the human eye is most sensitive to lower frequencies, however, very little perceptible image quality is lost by this stage.
Quantization stage
140
includes converting the two-dimensional matrix of quantized coefficients to a one-dimensional linear stream of data by reading the matrix values in a zigzag pattern and dividing the one-dimensional linear stream of quantized coefficients into segments, where each segment consists of a string of zero coefficients followed by a non-zero quantized coefficient. Variable length coding (VLC) then is performed by transforming each segment, consisting of the number of zero coefficients and the amplitude of the non-zero coefficient in the segment, into a variable length codeword (stage
145
). Finally, a framing process packs every 30 blocks of variable-length coded quantized coefficients into five fixed-length synchronization blocks (stage
150
).
The lower portion of
FIG. 1
shows a basic flow diagram of a prior art DV codec decoding process. Decoding is essentially the reverse of the encoding process described above. The digital stream is first deframed (stage
155
). Variable length decoding (VLD) then unpacks the data so that it may be restored to the individual coefficients (stage
160
).
After inverse quantizing the coefficients (stage
165
), inverse weighting (stage
170
) and an inverse discrete cosine transform (IDCT) (stage
175
) are applied to the result. The inverse weights are the multiplicative inverses of the weights that were applied in the encoding process. The output of the inverse weighting function is then processed by the IDCT. The IDCT operation may be described mathematically using the following formula:
f
uv
=
2
N
∑
m
=
0
N
-
1
∑
n
=
0
N
-
1
c
(
u
)
c
(
v
)
F
mn
cos
(
(
2
u
+
1
)
m
π
2
N
)
cos
(
(
2
v
+
1
)
n
π
2
N
)
where F
N×N
is an input matrix of DCT coefficients of size N by N, ƒ
N×N
is a output matrix of pixel information of size N by N, and c(u) and c(v) are matrices of constants as defined below.
(
k
)
=
1
2
if
(
k
=
0
1
if
(
k
≠
0
The result is then deshuffled (stage
180
) and deblocked (stage
185
) to form the full image frame.
Because the DCT and IDCT are widely used, much attention has been devoted to developing fast algorithms for implementing them. Furthermore, there exist many different, but mathematically equivalent, hardware and software implementations for computing the DCT and IDCT. For example, the IDCT equation above can also be written matrix notation as:
[ƒ
N×N
]=[A
N×N
]
T
[F
N×N
][A
N×N
] (Equation 1)
where [A
N×N
] is a N×N constant matrix. By applying simple rules of matrix multiplication, two mathematically equivalent matrix notation equations may be derived from Equation 1 as shown below.
[ƒ
N×N
]=[A
N×N
]
T
([
A
N×N
]
T
[F
N×N
]
T
)
T
(Equation 2)
[ƒ
N×N
]=M
([
A
N×N
]
T
{circle around (×)}[
A
N×N
]
T
L
([
F
N×N
]
T
)) (Equation 3)
where L is an operation that converts an N×N matrix to a vector according to the equation L([X
22
])=[x
00
x
01
x
10
x
11
], M is an operation that converts a vector into a matrix according to the equation [X
22
]=M([x
00
x
01
x
10
x
11
]), and the symbol {circle around (×)} indicates a tensor product. The tensor product of [X
22
]{circle around (×)}[Y
22
] is defined as,
[
X
22
]
⊗
[
Y
22
]
=
[
X
00
Y
00
X
00
Y
01
X
01
Y
00
X
01
Y
01
X
00
Y
10
X
00
Y
11
X
01
Y
10
X
01
Y
11
X
10
Y
00
X
10
Y
01
X
11
Y
00
X
11
Y
01
X
10
Y
10
X
10
Y
11
X
11
Y
10
X
11
Y
11
]
Equation 2 demonstrates that a two-dimensional IDCT may be computed by multiplying the input data matrix (F) by the constant matrix (A), transposing the result, and then multiplying the transposed matrix by the constant matrix (A). Algorithms that compute two-dimensional IDCTs in this manner are called “type I” algorithms. Type I algorithms are easy to implement on a parallel machine, that is, a computer formed of a plurality of processors operating simultaneously in parallel. For example, when using N parallel processors to perform a matrix multiplication on N×N matrices, N column multiplies can be simultaneously performed. Additionally, a parallel machine can be designed so as to contain special hardware or software instructions for performing fast matrix transposition.
One di
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Mai Tan V.
Sony Electronics Inc.
LandOfFree
Methods and systems for performing short integer chen IDCT... 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 systems for performing short integer chen IDCT..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for performing short integer chen IDCT... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447254