Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2001-07-25
2003-07-01
Wamsley, Patrick (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C382S246000
Reexamination Certificate
active
06587057
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates in general to digital decoding and more specifically to a decoding system especially suited for MPEG-type decoding.
The Moving Pictures Experts Group (MPEG) standards of compression have gained wide popularity. The MPEG standards are used extensively in digital audio and image compression, encoding, transfer and decoding and decompression. Copies of the standards are available from many sources. On such source is the MPEG home page at http://www.cselt.it/mpeg/.
Implementing the MPEG standard in a computer, server, consumer electronic device, or other digital system can be daunting because of the enormous bandwidth and throughput requirements of today's MPEG content. Devices that play back MPEG content must be very fast. Often such devices are restricted to very limited resources. Thus, any improvements in efficiency in implementing various aspects of the MPEG standard are welcome and valuable.
One MPEG standard function that can greatly benefit from improvement is MPEG decoding. MPEG decoding occurs at the time of playback of MPEG content. This often means that the decoder is executing in a consumer electronic device with very limited resources. For example, such consumer electronics devices often have simple, slower processors that are also used for other tasks in the device. The amount of memory, or other storage, is limited and is needed by other tasks or features in the device.
A significant portion of MPEG decoding involves decoding bitstreams that represent audio or image content (or both). A bitstream includes variable length coding (VLC) code words. Each code word is a variable number of bits. One use of VLC code words is to decode discrete cosine transform coefficients. In this case, each code word indicates (1) the number of zeros before the next coefficient (the “run”), (2) the value of the next coefficient (the “level”) and (3) how to obtain the next code word in the bitstream (i.e., the “length” of the present code word).
Table I, below, shows selected VLC code words used to decode DCT coefficients. A complete set of VLC code words can be found in the MPEG standards. In Table I, “run” indicates the number of zeros until the next non-zero coefficient and “level” is the value of the coefficient. There are 114 code words for this particular example.
TABLE I
Variable length code
[a]
run
level
10
[b]
end of block
1s
[c]
0
1
11s
[d]
0
1
011s
1
1
0100 s
0
2
0101 s
2
1
0010 1s
0
3
0011 1s
3
1
0011 0s
4
1
. . .
0000 0000 0001 1110
s
28
1
0000 0000 0001 1101
s
29
1
0000 0000 0001 1100
s
30
1
0000 0000 0001 1011
s
31
1
Notes:
[a] The last bit ‘s’ denotes the sign of the level, ‘0’ for positive and ‘1’ for negative.
[b] “End of Block” shall not be the only code of the block.
[c] This code shall be used for the first (DC) coefficient in the block.
[d] This code shall be used for all other coefficients.
Run-level pairs that occur more frequently are assigned short code words while those occurring less frequently are assigned long code words, effectively compressing the data since the more frequent shorter code words dominate. Only the codes with high probability of occurrence are coded with a VLC. Less probable events are coded with an escape symbol followed by fixed length codes.
The basic idea of VLC decoding is to match bit patterns of an incoming bitstream against a codebook containing all of the allowed bit patterns. A simple decoding algorithm would check the bitstream one bit at a time until a matching pattern was found. For most applications, such an approach is far too slow to be practical; and, commonly, decoding speed is increased by matching multiple bits at a time using lookup tables.
Programmable processors are frequently employed for VLC decoding, but they are relatively inefficient because of their fixed word sizes as well as their modest shifting and bit testing capabilities.
Many approaches exist for decoding VLC encoded coefficients. See, e.g., “MPEG-2 Video Decoding on the TMS320C6X DSP Architecture,” Sundararajan Sriram, and Ching-Yu Hung.
SUMMARY OF THE INVENTION
The present invention provides a fast, memory efficient, lookup table-based system for VLC decoding. Code words are grouped by prefix and recoded to reduce the number of bits that must be matched, reducing the memory requirements. General-purpose processor and finite state machine (FSM) decoder implementations are described.
REFERENCES:
patent: 4899149 (1990-02-01), Kahan
patent: 5623423 (1997-04-01), Lipovski
patent: 5748688 (1998-05-01), Kim et al.
patent: 5748790 (1998-05-01), Golin
patent: 5781135 (1998-07-01), Kim et al.
patent: 5808570 (1998-09-01), Bakhmutsky
patent: 5821886 (1998-10-01), Son
patent: 5949356 (1999-09-01), Kim et al.
patent: 5969650 (1999-10-01), Wilson
patent: WO 93/13603 (1993-07-01), None
patent: WO 96/33558 (1996-10-01), None
Aggarwal, Manoj, “Efficient Human Decoding,” IEEE, 2000, pp. 936-939.
Schneider, Claus, “A Parallel/Serial Trade-Off Methodology for Look-Up Table Based Decoders,” DAC 1997, Anaheim, CA, pp. 498-503.
Sriram, Sundararajan, et al., “MPEG-2 Video Decoding on the TMS320C6X DSP Architecture,” IEEE, 1998, pp. 1735-1739.
Ishii, Daiji, et al., Parallel Variable Length Decoding with Inverse Quantization for Software MPEG-2 Decoders, IEEE 1997, pp. 500-509.
MPEG-2 Video Decoding on the TMS320C6X DSP Architecture, Sundararajan Sriram and Ching-Yu Hung, DSPS R&D Center, Texas Instruments, Dallas TX 75265, 5 pages.
Kulas Charles J.
QuickSilver Technology, Inc.
Townsend and Townsend / and Crew LLP
Wamsley Patrick
LandOfFree
High performance memory efficient variable-length coding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High performance memory efficient variable-length coding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High performance memory efficient variable-length coding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108779