GB2313511A

GB2313511A - Decoding variable length codewords such as MPEG2 DCT coefficients

Info

Publication number: GB2313511A
Application number: GB9611039A
Authority: GB
Inventors: Patrick Clement; Fathy Fouad Yassa
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 1996-05-25
Filing date: 1996-05-25
Publication date: 1997-11-26
Anticipated expiration: 2016-05-25
Also published as: HK1004970A1; GB9611039D0; GB2313511B

Abstract

A decoder circuit comprises a shift register 30 and a decoder 40, 50. The shift register 30 is coupled to receive a data bit stream 20. The decoder 40, 50 contains a set of unique codes, and is coupled to the shift register 30 for identifying when a pattern within the shift register 30 matches one of the set of unique codes within the decoder 40, 50 , and for providing a decoded output in dependence upon the matched one of the set of unique codes. The shift register 30 is initially set with a predetermined bit pattern which is arranged such that when a last bit of a valid variable length word enters the shift register 30 , the combination of the valid word and a residual portion of the predetermined bit pattern defines a pattern equal to one of the set of unique codes.

Description

DECODER CiRcun' AND METHOD Field of the Invention This invention relates to decoder circuits and particularly but not exclusively to decoder circuits for decoding variable length binary words.

Background of the Invention Several techniques are known for decoding variable length codewords in a serial bit-stream of data. Once such technique is based upon a tree- searching algorithm, which operated on data in a sequential mode, either bit-by-bit as disclosed in US Pat. No. 4,899,149, or several bits at a time as disclosed in US Pat. No. 5,398,027. Both of these methods are slow because several operators are cascaded along the critical path in addition to a shift register and a lookup table.

Other methods perform decoding in a parallel manner by comparing entire codewords with the content of a look-up table. These methods require extensive hardware, since in addition to providing fixed length data corresponding to the variable length codewords, the look-up table also has to indicate the length of the codewords, which is then fed back to align codewords in the input buffer.

This invention seeks to provide a decoder circuit and method which mitigates the above mentioned disadvantages.

Summarv of the Invention According to a first aspect of the present invention there is provided a decoder circuit for decoding a known set of variable length words comprising: a shift register coupled to receive a data bit stream, and initially set with a predetermined bit pattern; and, a decoder containing a set of codes, coupled to the shift register, wherein a variable length word and a residual portion of the predetermined bit pattern define one of the set of codes, and the decoder is arranged for providing a decoded output signal when a last bit of a valid word enters the shift register and the pattern therein matches one of the sets of codes.

Preferably the bit stream is loaded into the shift register in one bit steps, and between each step the value of the shift register is compared with the set of unique codes stored in the decoder, which correspond to the variable length words.

The decoder circuit preferably further comprising a flag register for storing information about the incoming bit stream. Preferably the decoder comprises a look-up table and an output buffer means. The look-up table preferably comprises a plurality of subsets of codes, one of the subsets being selected for decoding the shift register.

According to a second aspect of the present invention there is provided a method of decoding a known set of variable length words in a shift register coupled to receive a data bit stream, comprising the steps of: setting the shift register with an initial predetermined bit pattern; loading the shift register with portions of the data bit stream; comparing the contents of the shift register with a set of codes; wherein a valid word and a residual portion of the predetermined bit pattern define one of the set of codes, providing a decoded output signal when a last bit of a valid word enters the shift register and the pattern therein matches one of the sets of codes.

Preferably the portions of the data bit stream are one bit portions.

In this way a decoder and method is provided which does not require extensive hardware, and is fast enough to allow bit-by-bit comparison of the shift register contents with the known set of variable length codewords.

Brief Description of the Drawmg(s) An exemplary embodiment of the invention will now be described with reference to the drawing in which: FIG. 1 shows a preferred embodiment of a decoder circuit in accordance with the invention.

FIG.2 shows part of the decoder circuit of FIG.1 FIGs. 3,4 and 5 show various states of the part of the decoder circuit shown in FIG.2 Detalled DescnDton of a Preferred Embodiment Referring to FIGs.1 and 2 there is shown a decoder circuit 10 for decoding a serial bitstream of variable length codewords, such as MPEG2 DCT (Discrete cosine transform) coefficients. An input terminal 20 is coupled to receive the bitstream, which may be the transform coefficients of a compressed video signal, or any other variable length code.

A shift register 30, having 19 bit cells QO-Q18, has an input coupled to receive the bitstream from the input terminal 20 into register cell QO. The shift register 30 is also coupled to receive a number of 19 bit reset patterns 35 and a code detection signal, both to be further described below.

A look-up table (LUT) 40 is coupled to the shift register 30, and is arranged for comparing the contents of the shift register 30 with a set of unique 19 bit codes, and for providing an output signal if the contents of the 19 bits in the shift register 30 are matched with one of the sets of 19 bit unique codes. The LUT 40 has a plurality of tables.

Output buffers 50 are coupled to receive output signals from the LUT 40, for providing buffered decoded outputs and for providing the code detection signal.

A flag register 60 is also coupled to the LUT 40 and to flag signal 65 inputs.

The flag register 60 is further coupled to receive the code detection signal.

The flag register 60 is arranged to store information pertaining to the type of variable length code being received, and to determine which table of the plurality of tables within the LUT 40 is to be used for the decoding.

In operation, a chosen 19 bit reset pattern of the reset patterns 35 is loaded into the shift register 30. A new bit is clocked into cell QO of the shift register 30, and each bit within the shift register 30 is shifted to the right by one cell (Qx+1=Qx for the range 17 to 0). The bit stored in Q18 is overwritten.

The bits Q0-Q18 of the shift register 30 are compared with the set of unique 19 bit codes stored in the LUT 40. If no match is detected, the next bit of the bitstream is loaded into the shift register 30, with corresponding shifts in each cell of the shift register 30 as described above, the contents are again compared with the unique codes, and so on.

At each iteration, a portion of the reset pattern is resident in the rightmost cells of the shift register 30, and bits from the bitstream occupy the leftmost cells of the shift register 30. As each new bit is clocked into QO, one less bit (the bit in Q18 immediately preceding the shift) of the reset pattern remains in the shift register 30.

The reset pattern is predetermined such that the residual portion of the reset pattern in combination with a valid variable length codeword defines a unique 19 bit value in the shift register 30, which matches one of the unique 19 bit codes of the LUT 40. No two combinations of codeword (or partially loaded codeword) and residual reset pattern define the same 19 bit value.

If a match occurs, an output signal is sent to the output buffers 50. Decoded outputs are provided at the outputs of the output buffers 50, and a code detection signal is sent to the shift register 30 and to the flag register 60.

The code detection signal is a feedback signal which informs the shift register 30 and the flag register 60 that a match has been detected within the LUT 40. In other words, a complete valid codeword is resident in the shift register 30, without any bits of the next codeword being present. The contents of the shift register are then overwritten with a new reset pattern 35, and the next new bit is clocked into the shift register 30.

The contents of the flag register 60 are similarly overwritten with new flag signals 65. The flag signals define. certain parameters of the codewords, such as whether they are DCT codewords and which table of the LUT 40 will be used for the decoding.

Since the LUT 40 is not required to decode the length of the codewords, only to recognise a 19 bit match, it is able to operate at a speed which allows the code detection signal to be fedback to the shift register 30 and the flag register 60 before the arrival of the next bit of the bitstream.

Furthermore, since the shift register 30 is informed by the code detection signal that it contains an entire codeword (but no more than an entire codeword) the shift register can be purged without there being any danger of inadvertently losing a loaded bit or bits belonging to the next codeword.

Referring now also to FIG.3 there is shown an exemplary 19bit reset pattern, initially loaded into the shift register 30. In this particular pattern cell Q9 is set with the value 0, and all other cells are set with the value 1.

Therefore the codes stored in the LUT 40 must reflect this by having all residual bit pattern cells set to 1, with the exception of cell Q(9+y) where y is the length of each variable length word.

Referring now also to FIGs. 4 and 5 there are shown two exemplary codewords and their associated residual portions of the reset pattern of FIG.3.

Thus in order to decode the variable length word '100', the associated code stored in the LUT 40 must have Q12=0 (Q9+3), with all other residual cells equal to 1 (Q3-Q11 and Q13-Q18), and the valid word in Q2, Q1, QO in that order, as shown in FIG.4 In order to decode the variable length word '1111 11100', the associated code stored in the LUT 40 must have Q18=0 (Q9+9), with all other residual cells equal to 1 (Q9-Q17), and the valid word in Q8-QO in that order, as shown in FIG.5.

It will be appreciated that alternative embodiments to the one described above are possible. For example, the bit patterns and variable length words described above are exemplary only. The LUT 40 could contain a number of tables, one of which is chosen in dependence upon a value stored in the flag register 60.

The number of cells of the shift register 30 in the embodiment above is suitable for MPEG2 DCT coefficients. However, the number of shift register cells could be any suitable number, chosen in dependence upon the length of the longest variable length words to be decoded.

Claims

1. A decoder circuit for decoding a known set of variable length words comprising: a shift register coupled to receive a data bit stream, and initially set with a predetermined bit pattern; and, a decoder containing a set of codes, coupled to the shift register, wherein a variable length word and a residual portion of the predetermined bit pattern define one of the set of codes, and the decoder is arranged for providing a decoded output signal when a last bit of a valid word enters the shift register and the pattern therein matches one of the sets of codes.

2. The decoder circuit of claim 1 wherein the bit stream is loaded into the shift register in one bit steps, and between each step the value of the shift register is compared with the set of unique codes stored in the decoder, which correspond to the variable length words.

3. The decoder circuit of claim 1 or claim 2 further comprising a flag register for storing information about the incoming bit stream.

4. The decoder circuit of any preceding claim wherein the decoder comprises a look-up table and an output buffer means.

5. The decoder circuit of claim 4 wherein the look-up table comprises a plurality of subsets of codes, one of the subsets being selected for decoding the shift register.

6. A method of decoding a known set of variable length words in a shift register coupled to receive a data bit stream, comprising the steps of: setting the shift register with an initial predetermined bit pattern; loading the shift register with portions of the data bit stream; comparing the contents of the shift register with a set of codes; wherein a valid word and a residual portion of the predetermined bit pattern define one of the set of codes, providing a decoded output signal when a last bit of a valid word enters the shift register and the pattern therein matches one of the sets of codes.

7. The method of claim 6 wherein the portions of the data bit stream are one bit portions.

8. A decoder circuit substantially as hereinbefore described and with reference to the drawings.

9. A method of decoding a known set of variable length words substantially as hereinbefore described and with reference to the drawings.