Multiple symbol length lookup table

Details Multiple symbol length lookup table Multiple symbol length lookup table

2000-11-06

2003-02-11

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Coding by table look-up techniques

C341S050000, C341S067000

Reexamination Certificate

active

06518896

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the field of variable length coding and to the field of digital video data processing. More particularly, the present invention relates to the field of lookup tables that return the length of bits that a variable length decoder can decode from a sequence of encoded data bits.
2. Related Art
Variable length coding provides an efficient technique for data compression. Many data processing fields have implemented variable length coding to compress data for numerous data applications. One type of variable length coding is known as Huffman coding. The concept of variable length coding is based on replacing data values that appear most frequently in a stream of unencoded data with shorter variable length codewords or symbols while data values that appear less frequently are replaced with longer variable length codewords or symbols. The idea being that the overall length of-the stream of encoded data is smaller than the overall length of the stream of unencoded data.
Moreover, the code for any one of the variable length symbols cannot be the prefix of the code for any other variable length symbol. For example, if the code “011” is the code for a particular variable length symbol, then no other code for any other variable length symbol can begin with “011”. In this way, when a variable length decoder (which recognizes the variable length symbols including the variable length symbol whose code is “011”) encounters a “011” at the beginning of a stream of encoded data (e.g., 01110010 . . . ), the “011” is decoded by the variable length decoder and then decoding continues with the rest of the stream of encoded data (i.e., “10010 . . . ”)
The field of digital video data processing applies variable length coding in various applications. In particular, digital video data which is formatted as specified in a specification entitled, “The Specification of Consumer Use Digital VCR's using 6.3 mm Magnetic Tape”, (HD Video Conference, December, 1994), is variable length coded as described in the specification to reduce the space required to store the digital video data. This specification is commonly known as the DV standard. The DV standard is a compressed digital video data and digital audio data recording standard. A DV digital video system uses a ¼ inch (6.35 mm) metal evaporate tape to record very high quality digital video data. Alternatively, a DV digital video system can record by transmitting to a memory device (e.g., hard drive, RAM, ROM, etc.) very high quality digital video data and digital audio data for storing therein. Both consumers and professionals use DV digital video systems.
To play the digital video data which is formatted according to the DV standard, the DV digital video system includes a DV decoder for processing the digital video data into a format which can be displayed on an electronic display device. Since the DV decoder processes the digital video data in real-time, speed and performance are crucial characteristics of the DV decoder.
A conventional DV decoder utilizes a lookup table which is similar in function to the single symbol length lookup table
100
illustrated in
FIG. 1
to process a stream of digital video data. The table
200
of variable length symbols illustrated in FIG.
2
. provides the set of variable length symbols
70
A-
70
D used to variable length encode a stream of data bits (e.g., digital video data) specifically for performing a lookup operation with the single symbol length lookup table
100
of
FIG. 1. A
first variable length symbol
70
A has the code “0”. A second variable length symbol
70
B has the code “10”. A third variable length symbol
70
C has the code “110”. A fourth variable length symbol
70
D has the code “111”.
The single symbol length lookup table
100
includes a plurality of lookup entries
10
and a plurality of lookup results
20
, whereas each lookup entry has a corresponding lookup result. For example, the lookup entry
10
D returns the lookup result
20
D. The column
50
shows the variable length symbol whose length is indicated by the lookup result
20
.
In processing the stream of data bits (variable length encoded), the conventional DV decoder submits a number of data bits from the stream of data bits (variable length encoded) to the single symbol length lookup table
100
as a lookup entry
10
A-
10
H. The single symbol length lookup table
100
returns a lookup result
20
A-
20
H that is the length (in bits) of a single variable length symbol in response to a lookup entry
10
A-
10
H having a sequence of input data bits (variable length encoded) forming one or more consecutive variable length symbols. In other words, the single symbol length lookup table
100
returns the length or number of bits (starting from the beginning of the stream of input data bits submitted as a lookup entry) which correspond to a variable length symbol that can be decoded by a variable length decoder. Hence, the conventional DV decoder can find a particular variable length symbol (e.g., a variable length symbol corresponding to an End of Block (EOB)) in the stream of digital video data (variable length encoded) by using the single symbol length lookup table
100
.
For example, if a stream of data bits (variable length encoded) is “00100 . . . ” (encoded using the table
200
of variable length symbols shown in FIG.
2
), the first bit through the third bit are first submitted as the lookup entry value “001”, which corresponds to the lookup entry
10
B. Specifically, the stream “00100 . . . ” has a plurality of consecutive variable length symbols which can be identified once the length of each variable length symbol is determined. In response, the single symbol length lookup table
100
returns the lookup result
20
B which has the value “1”, which indicates that the lookup entry value “001” has a variable length symbol and that its length is “1” bit, (i.e., the code “0”). Therefore, the stream of data bits (variable length encoded) is advanced by one bit.
Thereafter, the second bit through the fourth bit are submitted as the lookup entry value “010”, which corresponds to the lookup entry
10
C. In response, the single symbol length lookup table
100
returns the lookup result
20
C which has the value “1”, which indicates that the lookup entry value “010” has a variable length symbol and that its length is “1” bit, (i.e., the code “0”). Therefore, the stream of data bits (variable length encoded) is advanced again by one bit. Thus, the performance of two lookup operations reveals that the beginning of the stream “00100 . . . ” has a first variable length symbol
70
A and another first variable length symbol
70
A. The processing of the stream of data bits (variable length encoded) continues in a similar manner.
Unfortunately, the single symbol length lookup table
100
slows down the processing of digital video data in a conventional DV decoder because of the great number of lookup operations performed on the stream of digital video data. This slow down caused by the single symbol length lookup table
100
limits the conventional DV decoder's ability to process the digital video data in real-time.
SUMMARY OF THE INVENTION
A multiple symbol length lookup table is described. The multiple symbol length lookup table includes a plurality of lookup entries and a plurality of lookup results, each lookup entry having a corresponding lookup result. Each lookup entry comprises a particular sequence of input data bits. The input data bits are encoded with a variable length coding. Moreover, the input data bits form one or more consecutive variable length symbols. Each lookup result comprises a total length of the consecutive variable length symbols in the input data bits. In an embodiment, the multiple symbol length lookup table is generated by using a single symbol length lookup table.
In practice, the input data bits are submitted to the multiple symbol length lookup table as a lookup entry. In response, the multiple symbol length

Affiliated with

Also associated with

Rating

Multiple symbol length lookup table does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiple symbol length lookup table, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple symbol length lookup table will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3169463