Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
1998-12-16
2001-04-10
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S065000
Reexamination Certificate
active
06215424
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a decoder for decoding successive variable length codewords encoding run length encoded coefficients. In particular, the present invention relates to a variable length decoder (VLD) which may be used for decoding variable length codewords in a high definition television (HDTV) video data signal which has been encoded according to the Motion Pictures Expert Group (MPEG) international standard.
BACKGROUND OF THE INVENTION
In the United States, a standard has been proposed for digitally encoding high definition television signals. This standard is essentially the same as the MPEG2 standard, pro posed by the Moving Picture Experts Group (MPEG) of the Inter national Standards Organization (ISO). This standard is referred to herein as the MPEG standard and signal conforming to this standard are referred to as MPEG or MPEG encoded signals. This standard is described in a draft internal standard (DIS) publication entitled “Information Technology—Generic Coding of Moving Pictures and Associated Audio, Recommendation H.262 ISO/IEC 13818.2; 1995 (E) available from the ISO and incorporated by reference.
The MPEG2 video signal encoding standard specifies encoding video data representing an image into binary (digital) data consisting mostly of blocks of discrete cosine transfer (DCT) coefficients. These coefficients are run length encoded into fixed size run length codewords. Each run length encoded codeword is then Huffman encoded into variable length code words. In an MPEG encoded HDTV signal, blocks of DCT coefficients must be decoded at a predetermined rate in order to properly decode and display the image being transmitted. The instantaneous rate can vary depending upon the detail and motion in the image. However, there is a maximum rate at which run length encoded codewords, and thus variable length code words, occur for a ‘worst case’ image. This rate exceeds 100 million code words per second. Various methods have been proposed to decode codewords at this rate.
Variable length decoders (VLDs) have been proposed in which have the capability of decoding multiple variable length codewords simultaneously in a single clock cycle, under the proper conditions. In prior art VLDs, a number of bits of the received encoded signal are supplied in parallel to the decoding section of the VLD via a barrel shifter. Such a VLD is termed a parallel decoder. The number of bits is selected to be at least the number of bits in the maximum sized variable length codeword. These bits are supplied to a lookup table (LUT), preconfigured with entries for each allowed variable length codeword. Each entry in the LUT contains the value of the run length codeword represented by the variable length codeword, and the length (i.e. the number of bits) of the variable length codeword. As a codeword is decoded, the number of parallel bits in the newly decoded variable length codeword are shifted out of the barrel shifter, and the remaining bits in the barrel shifter are shifted into their place. If necessary, the next bits in the digital bit stream are inserted into the barrel shifter. Then the remaining bits in the barrel shifter are processed to decode the next codeword. Such a VLD can decode a single variable length codeword in a single clock cycle.
However, as described above, for MPEG encoded HDTV signals, the maximum rate at which variable length codewords must be decoded is over 100 million per second. This requires a clock frequency of over 100 MHz. Operating at this frequency is currently beyond the capability of the integrated circuitry which is practical for consumer electronics. Thus, a VLD has been proposed which can decode more than one codeword per clock cycle. This would allow a VLD to be implemented which can operate with a clock signal rate below the 100 MHz rate which would be required in the circuitry described above.
In U.S. Pat. No. 5,225,832, entitled “High Speed Variable Length Decoder”, issued Jul. 6, 1993 to Wang et al., a parallel VLD is disclosed. In Wang et al., it is recognized that because the variable length codewords vary in length, it is possible that more than a single variable length codeword may fit within the number of bits in the maximum sized variable length codeword. The decoding LUT includes further entries for combined short codewords. Thus, should two shorter codewords be present simultaneously at the output of the barrel shifter, the two codewords will be recognized by the LUT and decoded simultaneously. This allows the VLD to decode at a rate higher than one codeword per clock cycle. The increase over the single-codeword-per-clock-cycle is further increased because shorter codewords are statistically more likely to occur than longer ones. This increase of decoding rate comes at the expense of increased complexity of the decoding LUTs.
It has also been suggested that the width of the output from the barrel shifter be increased to produce two maximum sized variable length codewords simultaneously. This doubled width barrel shifter output is supplied to an LUT which will recognize two codewords simultaneously. A first portion of the LUT recognizes the first variable length codeword, and a second portion recognizes the second variable length codeword. The LUT produces three output values: a first value represents the first variable length codeword, a second value represents the second variable length codeword, and a third value represents the length of the combined two codewords. Such an arrangement would enable the VLD to operate at a clock rate of around 50 MHz, which is well within the practical range. However, the LUT in such an arrangement is very large, compared to that in the single variable length codeword per clock cycle arrangement. For each codeword entry in the first portion of the LUT, the LUT must include circuitry for looking up the complete set of codewords for the second portion. If there are n allowable codewords, there must be n squared entries. This makes the LUT large and slow in operation.
In an article, “Pair-Match Huffman Transcoding to Achieve a Highly Parallel Variable Length Decoder with Two-Word Bit Stream Segmentation” by Bakhmutsky, published in the SPIE Proceedings, Volume 3021, pages 247-265, an enhancement to the parallel VLD of the type disclosed in Wang et al. is disclosed. The VLD of Bakhmutsky can decode at least two DCT coefficients per clock cycle. Bakhmutsky recognizes that the output of the VLD is a series of fixed length run length encoded codewords, each corresponding to a received variable length codeword. Each run length codeword represents one or more DCT coefficients, and includes a run portion and a value portion. The run portion represents the number of zero valued DCT coefficients before the coefficient represented by the current code word. The value portion represents the value of the non-zero DCT coefficient following the run of zero valued coefficients.
Bakhmutsky recognized that a zero run run-length codeword, represented by a single variable length codeword, represents only a single coefficient value (i.e. zero zero-valued coefficients), and that a one run run-length codeword, represented by a single variable length codeword, represents two coefficients: one zero-valued coefficient, and one non-zero valued coefficient. Should two variable length codewords representing two respective zero run run-length codewords, each representing a single coefficient, occur sequentially, they must be decoded simultaneously in a single clock cycle in order to maintain the two coefficient per clock cycle decoding rate. Furthermore, a variable length codeword representing a zero run run-length code (i.e. one coefficient) followed by a variable length codeword representing a one run run-length codeword (i.e. two coefficients) must also be decoded simultaneously in a single clock cycle in order to maintain the two coefficient per clock cycle decoding rate. If this were not done, that is, if each were separately decoded in one clock cycle, then three coefficients would be decoded in two clo
Burke Alexander J.
Jean-Pierre Peguy
Kurdyla Ronald H.
Thomson Licensing S.A.
Tokar Michael
LandOfFree
System for variable length codeword processing suitable for... 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 for variable length codeword processing suitable for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for variable length codeword processing suitable for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2472276