Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2000-03-01
2002-09-03
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S065000
Reexamination Certificate
active
06445314
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to systems and methods for encoding and decoding variable length codes. In particular, the present invention relates to a system and a method for decoding bitstreams of variable length codes.
2. Description of the Related Art
Variable length coding (VLC) is well known in the areas of compression and transmission of digital data and is used to reduce the number of binary bits required to represent information. The basic idea behind variable length coding is very simple: in a binary representation of symbols in a given sequence of symbols, the more frequently used symbols should be represented by shorter binary codes, giving rise to the concept that different symbols ought to be represented by binary codes of different lengths, thus variable length codes. To illustrate the concept, assuming that a message consists of the following sequence of symbols: {a, b, a, c, b, c, a, a, a, c, c, a, b, a, c, b, c, a, a, b }. In this sequence, the message is represented by an alphabet of three letters. The relative frequency of the three symbols is:
frequency_a=9/20=0.45
frequency_b=1/4=0.25
frequency_c=3/10=0.3
Variable length coding replaces each letter by a binary sequence. Using the concept of VLC described above, letter ‘a’ should be represented by the shortest binary sequence: say, ‘0’, letter ‘c’ should be the next shortest binary sequence ‘01’, letter ‘b’ should be the longest, say, ‘010’. Such a scheme attempts to minimize the number of bits used to represent the symbol taking into consideration their frequency of presence in the sequence. The binary sequence used to represent the symbols is called a codeword. With this representation, the sequence is represented as the bit string {001000101001000010100100010100100010}. One problem with this representation is that in order to recover the original message from the above, without knowing what the original message is, we may have reconstructed (decoded): {a, c, a, a, c, c, a. c . . . }. This is clearly different from the original. The reason is that the letter ‘b’ can also be interpreted as letter ‘c’ followed by ‘a’. In other words, the binary representation of letter ‘c’ is a prefix of letter ‘b’. To avoid this problem, all variable length codes must be of the so called prefix code, namely, no variable length code can be the prefix of another variable length code. In the above example, we can use the following representation:
‘a’→‘0’, ‘b’→‘100’, ‘c’→‘11’.
With this set of variable length codes, the message's binary representation becomes: {010001110011000111101000111001100100}. One can easily see from that the above binary sequence can be reverted uniquely back to the original message.
Another problem with variable length codes is the efficiency of the representation. Using the same example, we see that if we use:
‘a’→‘0’, ‘c’→‘10’, ‘b’→‘11’ (EQ 1)
that is another prefix code, the message can be represented by fewer number of bits: {0110101110000101001101011100011}. There are many way store present symbols using VLC. In addition, mathematically it is possible to create VLCs that are most efficient (i.e., no other VLC can be more efficient in terms of the number of bits used). In general, VLCs used in compression are aimed at the most optimal VLC representation based on the observed relative frequency.
The processing of representing symbols in a given message by variable length codes (VLCs) is called VLC Encoding, or simply VLE. The reverse process is called VLC Decoding, or VLD. The VLE and VLD are used together to create a more efficient binary representation of a given message at the source and reconstruct the message at the destination. The mapping between the message symbols and the binary sequences must be known by both source and destination beforehand. The mapping is called VLC table. Each VLC table has a number of entries; each entry in the table corresponds to the mapping between the message symbol and the corresponding binary sequence. In the example above, the mapping given in (EQ 1) can be shown in Table 1.
TABLE 1
An example VLC table
Symbol
Binary representation
A
0
B
11
C
10
The present invention is described below in the context of methods for VLD. In addition, the following description is limited to VLCs that are of prefix-code type (i.e., no variable length codeword is the partial prefix of another codeword).
A VLD algorithm is the reverse process that maps variable length code back to the original symbols. In compressed video signals such as MPEG-2, for example, many types of information in the elementary stream layer are represented as variable length codes to reduce the number of bits needed to represent the information. In the MPEG-2 decoder, such information must be recovered from the VLC codewords. For the ease of discussion, let's assume that a codeword, denoted by C, has N number of bits, where N vanes from codeword to codeword. Therefore, a sequence of M codewords can be denoted by {C
1
, C
2
, C
3
, . . . , C
M
}, where the codeword C
M
has N
M
bits. The total number of bits of this sequence is given by:
∑
l
≤
m
≤
M
N
m
.
In addition, assuming that the codewords are received in the following order: C
1
then C
2
and so on. Corresponding to these codewords are the original symbols, denoted by &agr;
1
, &agr;
2
, &agr;
3
, . . . , &agr;
M
, respectively. This can be illustrated as shown in FIG.
5
.
Prior art methods decode VLCs by inspecting the codewords one bit at a time as the binary sequence is introduced into the decoder. As the bits are read, the decoder determines which VLC table entries have the matching bit patterns. There may be multiple entries that have partially matching bit patterns. But as more and more bits are read, the number of matching entries reduces, eventually down to a single entry as all bits of the codeword are read. When this last bit is read depends on the length of the codeword. For example, if the codeword has 10 bits, it will take up to 10 binary decisions to reach the final entry that matches the given codeword. To show the above decoding process graphically, the above-described algorithm corresponds to a tree traversing process. An example is shown in FIG.
2
. In this example, the VLC table consists of 6 entries, representing 6 symbols, a, b, c, d, e, f. The VLC table is shown in Table 2. (Note that the VLC is of prefix-code type).
TABLE 2
Symbol
codeword
A
000
B
001
C
010
D
011
E
10
F
11
In the example shown in
FIG. 2
, an input codeword has 3 bits: ‘011’, therefore, as the decoder accepts each bit, it makes a binary decision along the code tree: to traverse left or right. With the first bit being ‘0’, it traverses left, possible decoded symbols are a, b, c, d. With the second bit being ‘1’, it traverses right, possible decoded symbols are reduced to c, d. With the third and last bit being ‘1’, it traverse right, leaving symbol d as the only symbol left. Therefore, after three such decisions, processing steps and memory accesses, it reaches the node d, which is the desired symbol. This is typical with the prior art, thus making VLD generally computationally intensive. Thus, there is a need to simplify or reduce the number of computations need for decoding and thereby reduce the time required for decoding.
Therefore, there is a need for a new system and a new method for performing decoding that is computationally inexpensive.
SUMMARY OF THE INVENTION
The present invention overcomes the deficiencies and limitations of the prior art with a system and a method for decoding variable length codes. A preferred embodiment of the system of the present invention comprises a window buffer, a unique variable length code look-up table and a decoder. The window buffer is coupled to receive a bit stream and provides a window output having the same number or more of bits in the longest variable
Wu Fang
Zhang Ji
Beyer Weaver & Thomas,LLP
Cisco Technology Inc.
Jean-Pierre Peguy
Lauture Joseph
LandOfFree
System and method for the decoding of variable length codes 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 the decoding of variable length codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for the decoding of variable length codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858166