Method and system for variable length decoding

Details Method and system for variable length decoding Method and system for variable length decoding

1999-12-15

2003-05-06

Kelley, Chris (Department: 2613)

Pulse or digital communications

Bandwidth reduction or expansion

Television or motion video signal

C341S065000

Reexamination Certificate

active

06560288

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
This invention relates generally to the field of data compression, and more particularly to a method and system for variable length decoding.
BACKGROUND OF THE INVENTION
To reduce bandwidth required to transmit a video stream or memory space required to store a video file, motion video is compressed for transmission and storage. MPEG coding was developed in response to a need for a generic coding method for motion video and associated audio for various applications such as digital storage media, television broadcasting, and communication. The use of MPEG allows motion video to be manipulated as a form of computer data and to be stored on various storage media, transmitted and received over existing networks, and distributed on existing broadcasting channels.
MPEG and other encoding methods compress motion video by transforming video data into a series of variable length codes. Often used types of video data are represented by shorter codes while less frequently used types of video data are represented by longer codes. In this way, compression is further increased.
Traditional solutions for decoding MPEG and other variable length codes use redundantly-coded tables in order to determine the value and the length of the codes. Using this methodology, decoding of a next code in the compressed stream cannot begin until the current code is fully decoded. This is because the length of the current code is not known, and thus the beginning of the next code is not determinable. As architectures increase in speed, the latency of memory access relative to the speed of computation increases. As a result, variable length decoding has become bottlenecked in the table lookup stage. In addition, depending on the specific variable length code being decoded, three or four table-lookups in a hierarchical arrangement of tables may be needed to finally decode a given symbol.
Traditionally, hardware solutions have been used to reduce bottlenecks in the table-lookup stage. Such hardware solutions, however, are expensive to implement and add design complexity to the system. Further, hardware solutions are not amicable to emerging variable length decoding standards, such as the 3-D scheme contained in MPEG-4. Thus, many existing hardware implementations are locked into supporting a small set of existing standards.
SUMMARY OF THE INVENTION
The present invention provides a method and system for variable length decoding that substantially eliminate or reduce disadvantages and problems associated with previously developed systems and methods. In particular, the present invention determines the length of variable length codes in a compressed data stream using information in the compressed data stream.
In accordance with one embodiment of the present invention, variable length codes are identified in a compressed data stream by determining a leading position of a specified value in the compressed data stream. A length of a leading code in the compressed data stream is determined based on the leading position of the specified value.
More particularly, in accordance with a particular embodiment of the present invention, a table of decode entries is provided that is organized and accessed by code length. In this embodiment, the leading code is decoded by matching at least part of the leading code to a decode entry in the table for the length of the leading code. In addition, the leading code may be extracted from the compressed data stream prior to decoding to allow processing of a next leading code while decoding the leading code.
Technical advantages of the present invention include providing an improved method and system for variable length decoding. In particular, code lengths in a compressed data stream are determined based on information in the compressed data stream. As a result, code length may be determined prior to decoding, and processing of a next code begun while decoding the previous code. Thus, adjacent codes are processed in parallel rather than serially, which reduce bottlenecks at the decode stage.
Another technical advantage of the present invention includes providing reduced decode table size for variable length decoding. In particular, because code length is determined based on information in a compressed data stream, length storage is no longer necessary in decode tables and multiple lookups per code are eliminated. In addition, processor utilization is increased because code length is available sooner and the decode rate is constant.
Other technical advantages of the present invention will be readily apparent to one skilled in the art from the following figures, description, and claims.


REFERENCES:
patent: 6219457 (2001-04-01), Potu
patent: 6246347 (2001-06-01), Bakhmutsky
patent: 6298087 (2001-10-01), Luna
patent: 6324306 (2001-11-01), Natsume
patent: 6385341 (2002-05-01), Lisitsa
MPEG Document,ISO/IEC 13818-2:1995(E), 1995, 219 pages.
Eckart, Stefan; /*getblk.c, DCT block decoding(mpeg2decode), 13 pages, Jul. 13, 1994.
/*getvic.h, variable length code tables,MPEG Software Simulation Group, 9 pages, 1994.

Affiliated with

Also associated with

Rating

Method and system for variable length decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for variable length decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for variable length decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3006875