Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-08-31
2001-10-02
Le, Vu (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240230, C375S240030
Reexamination Certificate
active
06298087
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital data signal decoding, and more particularly to a system, article, and method for variable length decoding and decompression of a digital video signal.
BACKGROUND OF THE INVENTION
Video sequences contain a significant amount of statistical and subjective redundancy within and between frames. One goal of video source coding is bit-rate reduction for storing and transmitting digital video data. One presently practiced method to reduce bit-rate includes compressing video digital data by utilizing the statistical and subjective redundancies within and between video frames, and encoding a “minimum set” of information using entropy coding techniques. This usually results in a compression of the coded video data compared to the original source data.
The International Standards Organization (ISO) has set a standard for video compression for generating a compressed digital data stream that is useful, for example, in the implementation of digital television. This standard is referred to as the ISO MPEG (International Standards Organization—Moving Pictures Experts Group, or “MPEG”) standard. In accordance with the MPEG standard, video data is discrete cosine transformed (DCT), quantised, and Huffman encoded using variable length code packets for transmission.
One version of the MPEG standard, MPEG-2, includes ISO/IEC 13818-1 through ISO/IEC 13818-10 standards. The relevant video standard, ISO/IEC 31818-2 (the Standard), entitled “Information Technology—Generic Coding of Moving Pictures and Associated Audio Components: Video” defines a “lossy” video compression and encoding protocol to enable a target bit-rate for transmission of digital video data signals over communication channels with constrained or low bandwidth capabilities, and for minimizing the digital data storage requirements of the encoded video signals. As a result, MPEG video compression and encoding, and video decoding, include a series of complex steps that are computationally intensive.
In accordance with the Standard, a video picture frame is divided into a series of slices, each slice containing a number of picture areas called “macroblocks” with each macroblock in turn comprising six “blocks,” Comprising four luminance blocks and two chrominance blocks.
Video compression of the pels within the block includes the step of transforming the video data into the frequency domain by using a 2-dimensional discrete cosine transform (DCT) algorithm to convert the video data into an 8×8 matrix of DCT coefficients. In a subsequent quantisation step, the coefficients are quantised thereby limiting the number of allowed values, and resulting in many of the higher frequency DCT coefficients being set to a zero value.
The 8×8 quantised DCT coefficient matrix is then linearized into a stream of quantised frequency coefficients. As most of the higher frequency coefficients are set to zero, linearization produces long runs of zeros. Further compression is achieved by converting the linearized stream of DCT coefficients into a series of run/level pairs. Each pair indicates the number of zero coefficients and the amplitude of the non-zero coefficient that ended the run. The run/level pairs are then coded using a variable length code (VLC), resulting in further compression by replacing shorter codes for more frequently occurring run/level pair values.
Video decoding is performed pursuant to section 7 of the Standard and includes the steps of VLC decoding, inverse scanning to reconstruct the 8×8 2-dimensional quantised DCT coefficient matrix, inverse quantising to recover a truncated set of DCT coefficients, and inverse DCT. In accordance with sections 7.2.2.1 through 7.2.2.4 of the Standard, the VLCs are decoded using tables B.14 and B.15 as provided in Annex B of the Standard. The decoded run/level pairs are then inverse scanned to provide an 8×8 quantised DCT coefficient matrix.
Following inverse scanning, an inverse quantisation step uses Equation 1 below, as specified by Section 7.4.2.3 of the Standard, to produce an inverse-quantised DCT coefficient matrix.
IQC[v][u
]=((2
×QF[v][u]+k
)×
W[w][v][u
]×quantizer_scale/32 Eq. (1)
Where:
IQC [v][u]
is the inverse quantised DCT coefficient
values at row v and column u of the block;
k
= 0 for intra-blocks, and = Sign(QF[v][u])
for non-intra-blocks (i.e., a “−1” for a
negative, and “+1” for positive values of
QF[v][u]), and k = 0 for QF[v][u]
QF[v][u]
are the quantised DCT coefficients in row v,
column u;
W[w][v][u]
is a value selected from one of 4 weighting
matrices as identified in section 7.4.2.1 of
the Standard; and
quantizer_scale
is a scale factor value as defined in section
2.4.2.2 of the Standard.
Equation 1 requires 5 calculations (3 multiplication steps, one addition step and a division step) for each coefficient. For standard definition TV, the number of DCT coefficients may be up to 506,880 requiring approximately 76,032,000 calculations per second. It is evident that the computational complexity increases with increasing picture resolution and frame rates. For example, in one application, the Standard may be used to support compressing and encoding high-definition television (HDTV) video data, wherein the video frames are of higher resolution (as large as 1920×1080 picture elements, or pels, per picture) than those used in present NTSC signals (up to 704×480 pels). Inverse quantisation of the quantised DCT coefficients in this case would require approximately 466,560,000 calculations per second at 30 frames per second.
The demands placed on the decoder can easily consume the entire bandwidth of the decoder processor thereby limiting the decoder's ability to perform other tasks. Such computationally intensive steps require decoder processors that are designed to decode in real time. Processors satisfying the computational demands of the decoding process must be economically priced and readily available in order to render a video decoder practical and to permit economical implementation. Accordingly there is a need to reduce the computational load on a video decoder to thereby permit the use of off-the shelf, readily available processors.
SUMMARY OF THE INVENTION
The system of the present invention includes a digital data decoder, and in particular an MPEG video decoder, having substantially lower computational bandwidth requirements as compared to presently available video decoders. The system of the present invention includes a VLC decoder circuit, an inverse scanning circuit, and an inverse quantiser circuit. The VLC decoder circuit includes at least one data memory, a program memory, and a decoder processor. It is understood by those skilled in the art that the system of the present invention may be embodied as a general purpose processor circuit wherein all functionality is imparted by program code segments stored in memory. It is also understood, that application specific circuits may be defined having minimum program code wherein decoder functionality is executed for the most part in hardware.
In accordance with one feature of the system of the present invention, the VLC decoder circuit includes a memory device having stored therein improved VLC decoding tables. These improved decoding tables include run/level pair combinations wherein the level values been precalculated to include substantially all scalar multiplicands otherwise included as operands in the inverse quantisation calculation. For example, the tables tangibly embodied in the machine readable memories of the present invention have been multiplied by 2 as compared to Tables B.14 and B.15 of Annex B of the Standard. By “pre-multiplying” the values of the levels in the tables of the present invention by the scalar values otherwise include
Luna Amelia Carino
Wang Jason (Naxin)
Williams Richard Lawrence
Card Ronald C.
Fujii Harold T.
Le Vu
Sony Corporation
LandOfFree
System and method for decoding a variable length code... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for decoding a variable length code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for decoding a variable length code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2604097