Huffman decoder with reduced memory size

Details Huffman decoder with reduced memory size Huffman decoder with reduced memory size

2001-01-16

2002-06-25

Tokar, Michael (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from number of pulses

C341S067000

Reexamination Certificate

active

06411226

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to decoders and more particularly to a Huffman decoder having a reduced memory size and a method of decoding a Huffman encoded bitstream.
Audio and video files, before being compressed, typically consist of 16 bit samples recorded at a sampling rate more than twice the actual audio bandwidth (e.g., 44.1 kHz for Compact Disks), which yields more than 1.4 Mbit to represent just one second of stereo music in CD quality. Since such vast amounts of data are unwieldy, data compression is required.
MPEG (Motion Picture Experts Group) provides standards for compressing digital audio and video signals. MP3 (MPEG Layer 3) is the MPEG layer 3 audio standard. Using MPEG audio coding, the original sound data can be reduced by a factor of 12, without sacrificing sound quality. Recently MP3 audio files have become very popular and as a result, MP3 has become the de facto standard for storing audio files, with many MP3 files available on the Internet and many programs that support the MP3 standard.
FIG. 1
is a schematic block diagram of a conventional MP3 decoder
10
. The decoder
10
receives an encoded MP3 bit stream and converts it to an analog audio output signal that is a single PCM coded signal that sounds identical to the original audio signal. More specifically, the MP3 bit stream is a sequence of many frames, each containing a header, error checking bits, miscellaneous information, and encoded data.
At block
12
, the MP3 bit stream is received and upon detection of a sync-word indicating the start of a frame, the decoder
10
identifies the header and side information. Next, at block
14
, the decoder
10
obtains scale factors. Then, the decoder
10
must decode the samples, which are coded using Huffman codes, at block
16
. Huffman coding uses different length bit patterns to encode different pieces of data. The patterns that occur most often are given the shortest bit patterns, while the patterns that occur less frequently are given longer bit patterns. For example, encoding 8-bit bytes with Huffman coding provides many Huffman codes that are less than 8 bits in length, and probably some that are more than 8 bits. Huffman coding can pack audio data very efficiently. Further, Huffman coding is lossless because no noise is added to the audio signal.
Referring to
FIG. 2
, one method of Huffman decoding is to compare the Huffman coded word with entries in a lookup table until a matching bit pattern is detected. Each Huffman table can contain as many as 256 entries.
FIG. 2
shows a table for illustrating the Huffman decode process. The x and y columns represent a bit pattern, the column labeled “Huff code” shows the corresponding Huffman code, and the length column indicates the length of the corresponding Huffman code. This method of Huffman decoding produces a wide variation in decoding time. For example, in a best case, if the codeword matches the first entry, only one search is required. However, if the codeword matches the last entry, if the table has 256 entries, 256 compares are performed.
Another known method of performing Huffman decoding is through the use of a finite state machine, which reduces the code word search time. Initially, the state machine is in a ready/start state. In this state, the index is zero (0). According to the state machine, each time a bit is read, the machine changes state according to the bit read.
FIG. 3
shows two one-dimensional arrays, storing “0-way” and “1-way” data for illustrating such a Huffman decode process. The 0-way stores an index adjustment or relative state when the Huffman bit is zero (0). The 1-way stores the index adjustment when the Huffman bit is one (1). The state changes if bit ‘0’ or bit ‘1’ is input. The new 0-way value is checked immediately after a state change. If the 0-way value is ‘0’, the value in the 1-way is the result. The value in 1-way is returned and the state machine returns to the ready state. If the 0-way value is non-zero, the state machine waits for the next input bit and then changes state accordingly.
For example, looking at the row encircled and indicated at 30, if the 0-way entry is ‘0’, the corresponding value in 1-way is the final decoded value, which in this case is the decoded 8-bit value represented by ‘01’, where the upper 4-bits (X) are ‘0’ and the lower 4-bits (Y) are ‘0001’. The ready/start state is returned to after a code word is successfully decoded.
Referring to FIG.
3
and
FIG. 4
, an example of when the Huffman codeword is ‘001’ will be discussed.
FIG. 4
is a graphical view of the arrays of
FIG. 3
being processed by the state machine. At the initial state
40
, the first code word bit read is ‘0’, so the state machine proceeds to state
42
, as indicated by arrow A. At state
42
, the next code word bit is ‘0’, so the state machine proceeds to state
44
, as indicated by arrow B. The next code word bit is ‘1’, so the state machine proceeds to state
46
, as shown by arrow C. At state
46
, since the 0-way value is ‘0’, the actual coded value is determined to be ‘01’ and this value is output by the state machine. Upon completion, the state machine returns to the initial state
40
.
The state machine implementation reduces the average search and also the large variation between searches. The number of state changes is equal to the length of the Huffman code. Thus, for a Huffman code that is no more than 16 bits, the best case is one state change and the worst case is sixteen state changes. Therefore, the search time is close to optimal. Further, the memory size for a table, usually maintained in ROM, is only 5546 bytes.
Referring again to
FIG. 1
, after a bit pattern is decoded, it is dequantized at block
18
using a non-linear dequantization equation, and at block
20
, reorder, anti-alias and stereo processing are performed on the samples. Next, at block
22
, an Inverse Modified Discrete Cosine Transform (IMDCT) is performed on the frequency domain samples. Finally, at block
24
, sub-band synthesis is performed to transform the sub-band samples to the PCM audio signal.
As previously discussed, the Huffman codes are predefined in large tables or in state machine implementations, with a 5 k byte table. While large tables are readily formed without concern for the amount of memory used by MP3 players implemented on personal computers, with the increase in the popularity of MP3 files for storing music, there has been a corresponding increase in the demand for stand-alone MP3 devices and other, smaller portable devices, such as mobile telephones and personal digital assistants (PDAs) capable of playing MP3 encoded music. It would be beneficial if this memory requirement could be reduced for portable devices.
SUMMARY OF THE INVENTION
In order to provide more efficient processing operation, the present invention provides a data structure for storing Huffman codes. The data structure has a first field for storing a 0-way code and a second field for storing a 1-way code. A first flag is associated with the first field and indicates whether the first field stores an index adjustment or a Huffman code result. A second flag is associated with the second field and indicates whether the second field stores an index adjustment or a Huffman code result.
The present invention further provides a method of decoding a Huffman encoded bitstream including the steps of selecting one of a first flag and a second flag based on a value of a first bit of said bitstream and then analyzing a value of the selected flag. If the selected flag has a first value, then a code stored in a node corresponding to the selected flag represents an index adjustment and if the selected flag has a second value, then the code stored in the node corresponding to the selected flag represents a resultant Huffman code value. These steps are repeated on the bits of the bitstream until a flag having the second value is obtained.
The present invention also provides a variable length data structure for a Huffman decoder. The variable length data structure includes a fir

Affiliated with

Also associated with

Rating

Huffman decoder with reduced memory size does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Huffman decoder with reduced memory size, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Huffman decoder with reduced memory size will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2895781