Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2003-07-31
2004-10-26
Jeanglaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S106000
Reexamination Certificate
active
06809665
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application claims priority to Korean Patent Application No. 2002-45975, filed on Aug. 3, 2002, which is herein incorporated by reference in its entirety.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a decoding apparatus, and more particularly, to an apparatus and method for decoding variable length coded data.
2. Description of the Related Art
The Moving Picture Experts Group (MPEG)2 standard, published in April of 1994, is an international standard for the compression and decompression of video.
Methods of compressing and decompressing video have been increasingly used in various applications such as for the transmission of digital image data and for digital storage devices. Image compression algorithms typically perform lossless compression of image data using a variable length encoder.
The variable length encoder assigns shorter bits to data symbols having a relatively high probability of occurrence and longer bits to data symbols having a relatively low probability of occurrence. Accordingly, when encoding a given data bitstream, the variable length encoder generates a shorter data bitstream than a fixed length encoder.
The variable length decoder detaches a variable length code corresponding to a single symbol from an input variable length coded data bitstream and obtains a fixed length code from the detached variable length code using a symbol table. If a variable length coding table used in the variable length encoder can be set by a user, the variable length decoder detaches variable length codes while reading fixed-length bits from an input data bitstream based on the variable length coding table used in the variable length encoder.
A method of detaching bits from an input data bitstream one by one and performing a tree search algorithm on each bit is a fundamental variable length decoding method. In the case of an MPEG bitstream, a typical maximum code length is 16 bits. For a code length of 16 bits, 16 tree searches need to be performed to obtain a code value. In another method, bits are detached in groups of two from an input data bitstream and a tree search algorithm is performed on each group of two bits. In this method, 8 tree searches need to be performed to obtain a code value given a code length of 16 bits.
As the number of bits detached from a data bitstream increases, decoding speed increases, but the structure of a decoder becomes increasingly complicated. Accordingly, an appropriate trade-off between decoding speed and the complexity of a decoder is needed.
Therefore, a need exists for a variable length decoder capable of handling a plurality of codes simultaneously.
SUMMARY OF THE INVENTION
The present invention provides an apparatus for decoding a variable length code, wherein L bits are detached from an input data bitstream and decoded. Pre-decoding methods are selectively used according to a characteristic of a code value of the input data bitstream.
The present invention provides a method of decoding a variable length code, wherein L bits are detached from an input data bitstream and decoded. Pre-decoding methods are selectively used according to a characteristic of a code value of the input data bitstream.
According to an embodiment of the present invention, there is provided an apparatus for decoding a variable length code comprising a pre-decoding unit, a shifter, first through M-th look-up table address registers, a selector, a memory controller, a memory, and a memory searcher. The pre-decoding unit receives a data bitstream and generates a first selection signal or a second selection signal for selecting a look-up table address register from a set of first through M-th look-up table address registers according to a code value of the data bitstream, where M is a natural number. The shifter shifts the data bitstream by a predetermined number of bits in response to one of the first selection signal and the second selection signal and a predetermined continuous node signal. Each of the first through M-th look-up table address registers includes a LOC (Local Codes) address designating a K-bit LOC table value stored in a memory, where K is a natural number. The selector selects an output of the first through M-th look-up table address registers and outputs the selected output in response to one of the first selection signal and the second selection signal. The memory controller receives the output of the selector, generates a third selection signal for selecting a LOC table value and a terminal value corresponding to the LOC table value in response to the predetermined continuous node signal, or generates a fourth selection signal for selecting a predetermined fixed length code stored in the memory in response to a predetermined symbol address signal, where the LOC table value and the terminal value are stored in the memory, and the terminal value is used to obtain a predetermined symbol address. The memory stores LOC table values, terminal values, and fixed length codes, outputs a LOC table value and a terminal value in response to the third selection signal, and outputs a fixed length code in response to the fourth selection code. The memory searcher receives the LOC table value and the terminal value that are output from the memory and L bits of the data bitstream, determines whether the L bits of the data bitstream designate a terminal node or a continuous node using a LOC information table stored therein, generates a continuous node signal or a symbol address signal based on the result of the determination, receives the fixed length code output from the memory, and outputs the fixed length code, where L is a natural number.
The pre-decoding unit includes a first pre-decoder and a second pre-decoder. The first pre-decoder receives the data bitstream and when sequential 0s or 1s exist in a set of most significant bits (MSBs) of the data bitstream, generates the first selection signal for selecting the look-up table address register from the set of first through M-th look-up table address registers according to the number of sequential 0s or 1s. The second pre-decoder receives the data bitstream and generates the second selection signal for selecting the look-up table address register from the set of first through M-th look-up table address registers using N bits in the MSBs of the data bitstream, where N is a natural number.
The shifter shifts the data bitstream by 3 bits in response to the continuous node signal.
The memory controller includes an offset register, an adder, a LOC address register, and a symbol address register. The offset register receives the output of the selector and stores it until a next output is received from the selector. The adder generates the third selection signal for selecting values from a LOC table stored in the memory by adding the output of the offset register and a predetermined next LOC address. The LOC address register generates the predetermined next LOC address in response to the continuous node signal. The symbol address register generates the fourth selection signal for selecting the fixed length code in response to the symbol address signal.
The next LOC address is a sum of a current LOC address and a number of non-terminal nodes in a current LOC up to a current node.
The symbol address is a sum of a terminal value corresponding to a current LOC table value and a number of terminal nodes in a current LOC before a current node.
The LOC information table stored in the memory searcher includes node types indicating whether a node designated by the variable length code is a terminal node, a continuous node, or an invalid node, each node type comprising N*2
L
LOC information bits, and LOC information bits for each node type are expressed using four formats A, B, C, and D. Each format comprises N bits.
In the LOC information table stored in the memory searcher, a node type designated by the variable length code is a terminal node when the variable length code is 0, 1, 00, 01, 10, or 11, and a node type designated by the var
Kim Tae-sun
Park Tae-hwan
F. Chau & Associates LLC
Jeanglaude Jean Bruner
LandOfFree
Apparatus and method for decoding variable length code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for decoding variable length code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for decoding variable length code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3331028