Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2001-03-23
2002-12-31
Wamsley, Patrick (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S106000
Reexamination Certificate
active
06501398
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a variable-length code (VLC) decoder.
In order to reduce the bandwidth of a communication means or the capacity of a storage medium in transmitting or recording a moving picture, the picture is compressed and encoded. International standards for moving picture encoding include H.261, MPEG (moving picture experts group) 1, MPEG2, and so on.
These encoding methods are combinations of motion vector estimation and motion compensation, DCT (discrete cosine transform), quantization, zigzag scanning, variable-length coding, etc. Variable-length coding is an encoding method for reducing the average number of bits by converting quantized fixed-length codewords into a bit stream of variable-length codewords according to their statistics. To decode such a bit stream and present moving pictures, it is necessary to perform variable-length code (VLC) decoding for converting the variable-length codewords into the original fixed-length data. In VLC decoding, the codewords have non-constant lengths, and it is not possible to identify the first bit position of each variable-length codeword in the bit stream. Therefore, the codewords need to be decoded according to the order of bits included in the bit stream.
Various VLC decoders have been proposed in the art to realize a high-speed VLC decoding operation. A known VLC decoder is disclosed in U.S. Pat. No. 5,245,338.
FIG. 11
is a block diagram illustrating a VLC decoder of this type. The VLC decoder shown in
FIG. 11
decodes variable-length codewords with a maximum code length of 16 bits.
A buffer
901
stores an input bit stream. If a read signal RD is “1”, the buffer
901
outputs the stored bit stream to a first barrel shifter
911
and a first input register
912
on a 16-bit basis in the next cycle. The buffer
901
holds the output for one cycle.
The first and second input registers
912
and
913
have a 16-bit configuration, and latch the input data in the next cycle if an update signal is “1”.
The first barrel shifter
911
combines the outputs of the second and first input registers
913
and
912
and the output of the buffer
901
with each other as the upper, middle and lower 16-bit sub-sequences, respectively, to obtain a 48-bit data sequence. Then, using a sum SM (from 0 through 31), i.e., the output of an adder
914
, as a shift length (from 1 through 32), the first barrel shifter
911
selects 16 bits from the 48-bit combined data sequence and then writes the 16-bit data sequence on a first barrel shifter register
922
. The 16 bits selected are the (shift length+1)
th
through (shift length+16 bits of the 48-bit data sequence as counted from the most significant bit (MSB) thereof. It should be noted that the “first bit” herein means the MSB of the 48-bit combined data sequence.
A second barrel shifter
921
combines the outputs of second and first barrel shifter registers
923
and
922
with each other as the upper and lower 16-bit sub-sequences, respectively, to obtain a 32-bit data sequence. Then, using the output of a shift length register
925
as a shift length (from 1 through 16), the second barrel shifter
921
selects 16 bits from the 32-bit combined data sequence and then writes the 16-bit data sequence on the second barrel shifter register
923
. The 16 bits selected are the (shift length+1)
th
through (shift length+16)
th
bits of the 32-bit data sequence as counted from the MSB thereof.
A lookup table (LUT)
924
performs variable-length code decoding on the output of the second barrel shifter
921
to obtain a decoded symbol DC and a code length CL (from 1 through 16), and then writes the code length CL on the shift length register
925
. The LUT
924
is a table so compiled as to output a decoded symbol and a code length for each codeword with any of various lengths. The LUT
924
receives each codeword with the first bit thereof regarded as the MSB thereof.
The adder
914
adds together the output of the shift length register
925
(from 1 through 16) and the output of an accumulation register
915
(from 0 through 15) to output the sum SM. The adder
914
writes a carry signal CR, which is “1” if the sum SM is 16 to 31, on a hold register
916
and writes a remainder RM (from 0 through 15) of the sum SM modulo 16 on the accumulation register
915
. Thus, the MSB of the 5-bit sum SM, obtained by adding together the 5-bit output of the shift length register
925
and the 4-bit output of the accumulation register
915
, is the carry signal CR, while the remaining 4 bits thereof is the remainder RM of the sum SM modulo 16. The carry signal CR is used as an update signal for the first and second input registers
912
and
913
, and the read signal RD, i.e., the output of the hold register
916
, is used as a read signal for the buffer
901
.
FIG. 12
illustrates exemplary cycle-by-cycle data flows in the VLC decoder shown in FIG.
11
. For example, “a1-a8” denotes an 8-bit data sequence consisting of a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
and a
8
. For example, “a1-a8b1-b6c1-c2” for the buffer output in cycle
0
denotes a 16-bit data sequence consisting of a
1
through a
8
, b
1
through b
6
and c
1
through c
2
.
In
FIG. 12
, as for cycle
0
to cycle
2
, the update and read signals and shift lengths for the first and second barrel shifters are “1”, “1”, “16” and “16”, respectively, to set initial-state data for the respective registers. From cycle
3
on, the same processing is repeatedly performed based on the respective values of the carry and read signals, the accumulation register and the shift length register.
In this manner, a decoded symbol is obtained every cycle. At the beginning of the decoding operation, the first decoded output is obtained in cycle
2
, i.e., two cycles later than cycle
0
at which the input buffer
901
outputs data for the first time.
However, the known VLC decoder as illustrated in
FIG. 11
needs two input registers and a 48-bit-input, 16-bit-output circuit as the first barrel shifter. Thus, the decoder must be implemented at a large circuit size, and occupies an excessively broad chip area when realized as an LSI.
In addition, when the conventional VLC decoder illustrated in
FIG. 11
starts its decoding operation, it is not until two cycles have passed after the input buffer has supplied its first output that a first decoded codeword is obtained. If multiple streams of variable-length codewords are included in a single bit stream, information other than the variable-length code, such as headers, is included between the variable-length codeword streams. In such a case, the variable-length codeword streams are not contiguous with each other, and the VLC decoding cannot be performed continuously. Thus, if the VLC decoding cannot be performed consecutively, the 2-cycle delay occurs every time a variable-length codeword stream starts to be decoded. As a result, it takes a huge number of cycles to decode the entire bit stream.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to implement a variable-length code decoder at a reduced circuit size so that the decoder occupies a smaller chip area and supplies its decoded output at a much smaller delay.
Specifically, an inventive variable-length code decoder sequentially decodes a series of variable-length codewords included in a bit stream and outputs decoded symbols corresponding to the codewords. The decoder includes an interface section and a decoding section. The interface section accumutates various code lengths of the decoded codewords to obtain a sum. In accordance with the sum, the interface section selects a contiguous data sequence having a length of N bits (where N is a maximum code length of the variable-length codewords) from another contiguous data sequence, which has a length of 2N or 2N−1 bits and included in the bit stream, and outputs the N-bit contiguous data sequence. The decoding section receives the output of the interface section and decodes a codeword, included in a combination of the output a
LandOfFree
Variable-length code decoder using barrel shifters and a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Variable-length code decoder using barrel shifters and a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable-length code decoder using barrel shifters and a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980799