Decoder of variable length codes

• US 6,272,257 B1
• Filed: 02/18/1998
• Issued: 08/07/2001
• Est. Priority Date: 04/30/1997
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Prokop, Tomasz Thomas
• Primary Examiner(s): Grant, II, Jerome
• Application Number:
  US09/025,613
• Time in Patent Office: 1,266 Days
• Field of Search: 358/427, 382/246, 382/244, 382/233, 341/65, 341/67
• US Class Current: 382/246
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3897 with adaptable data path
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G11C 7/1075 for multiport memories each having random access ports and serial ports, e.g. video RAM
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

The present invention relates to a method and an apparatus (1158, 1171-1173, 1180-1184, 1188) for decoding blocks of data encoded using a plurality of variable-length code words. Preferably, the encoding used is Huffman coding. The blocks also comprise fixed-length, not-encoded fields and variable-length, not-encoded bit fields. The code words are interleaved with the variable-length, not-encoded bit fields. The apparatus (1158, 1171-1173, 1180-1184, 1188) includes a preprocessing logic unit for removing the fixed-length, not-encoded fields. The preprocessing logic unit outputs the variable-length code words interleaved with the variable-length, not-encoded bit fields, as well as signals indicating positions of the fixed-length, not-encoded fields in the data blocks. The apparatus (1158, 1171-1173, 1180-1184, 1188) also includes a circuit that synchronously passes the position-indicating signals to an output of the apparatus with the data being decoded. Thus, if there is a multiplicity of variable-length coded data between the fixed-length, not-encoded fields on the input of the apparatus (1158, 1171-1173, 1180-1184, 1188), a multiplicity of corresponding decoded data appears on the output of the apparatus (1158, 1171-1173, 1180-1184, 1188) between any two position-indicating signals corresponding to the fixed-length not-encoded words on the input.

Claims

1. An apparatus for decoding encoded blocks of data, the encoded blocks of data each comprising a plurality of variable-length code words, a plurality of not-encoded bit fields of variable length, and a plurality of not-encoded bit fields of fixed length, wherein the variable-length code words are interleaved with the not-encoded bit fields of variable length and the not-encoded bit fields of fixed length, said apparatus comprising:

a preprocessing logic unit for removing the plurality of not-encoded bit fields of fixed length from the encoded blocks of data and outputting the variable-length code words interleaved with the not-encoded bit fields of variable length as blocks of data, and for outputting signals indicating positions of the removed non-encoded bit fields of fixed length in the outputted blocks of data; and

a circuit adapted for passing the signals indicating the positions to an output of said apparatus in a synchronous and parallel manner, with the outputted blocks of data being decoded, such that, if there is multiplicity of the variable-length code words between the not-encoded bit fields of fixed length at an input of said apparatus, then a multiplicity of corresponding decoded data appears at the output of said apparatus between two signals indicating positions corresponding to the not-encoded words bit fields of fixed length at the input.

2. The apparatus according to claim 1, further comprising:

a first processing unit comprising a first set of barrel shifters and a first register, wherein said first processing unit processes the outputted plurality of variable-length code words interleaved with the not-encoded bit fields of variable length; and

a second processing unit comprising a second set of barrel shifters and a second register, said second processing unit for processing the outputted signals indicating positions of the removed not-encoded bit fields of fixed length in the outputted blocks of data,

wherein said first and second processing units are identical, and an output of the respective barrel shifters and said first and second processing units receive identical control signals.

3. The apparatus according to claim 2, wherein the output of said second processing unit for processing signals indicating positions of the removed not-encoded bit fields of fixed length is used to determine a size of a not-encoded variable length field to be removed from data stored in a data register for decoding purposes.

4. The apparatus according to claim 1, wherein said preprocessing logic unit for removing the not-encoded bit fields of fixed length outputs a plurality of variable-length code words interleaved with the not-encoded bit fields of variable length as words of fixed length composed of bit fields of fixed lengths such that a outputted single bit field has a corresponding tag indicating whether the outputted field is passed or removed by said preprocessing unit, or passed by said preprocessing unit and following or preceding a marker that is a not-encoded bit field of fixed length.

5. The apparatus according to claim 1, wherein the blocks of data are encoded using Hoffman coding.

6. A method of decoding encoded blocks of data, the encoded blocks of data each comprising a plurality of variable-length code words, a plurality of not-encoded bit fields of variable length, and a plurality of not-encoded fields of fixed length, wherein the variable-length code words are interleaved with the not-encoded bit fields of variable length and the not-encoded fields of fixed length, said method comprising the steps:

removing the not-encoded bit fields of fixed length from the encoded blocks of data and outputting the variable-length code words interleaved with the not-encoded bit fields of variable length as blocks of data, and outputting signals indicating positions of the removed not-encoded bit fields of fixed length in the outputted blocks of data; and

passing the signals indicating the positions to an output of a decoder apparatus in a synchronous and parallel manner, with the outputted blocks of data being decoded, such that, if there is a multiplicity of the variable-length code words between the non-encoded bit fields of fixed length being input, then a multiplicity of corresponding decoded data appears at the output between two signals indicating positions corresponding to the not-encoded bit fields of fixed length at the input.

7. The method according to claim 6, further comprising the steps of:

processing the outputted plurality of variable-length code words interleaved with the not-encoded bit fields of variable length using a first processing unit comprising a first set of barrel shifters and a first register; and

processing the outputted signals indicating the positions of the removed not-encoded bit fields of fixed length in the outputted blocks of data using a second processing unit comprising a second set of barrel shifters and a second register,

wherein the first and second processing units are identical, and an output of the respective barrel shifters and the first and second processing units receive identical control signals.

8. The method according to claim 7, further comprising the step of determining a size of a not-encoded variable length field to be removed from data stored in a data register for decoding purposes dependent upon an output of the second processing unit for processing signals indicating the positions of the not-encoded bit fields of fixed length.

9. The method to claim 6, further comprising the step of:

outputting, by a preprocessing logic unit for removing the not-encoded bit fields of fixed length, a plurality of variable-length code words interleaved with the not-encoded bit fields of variable length as words of fixed length composed of bit fields of fixed lengths such that an outputted single bit field has a corresponding tag indicating whether the outputted field is passed or removed by the preprocessing unit, or passed by the preprocessing unit and following or preceding a marker that is a not-encoded bit field of fixed length.

10. The method according to claim 6, wherein the blocks of data are encoded using Huffman coding.

11. A method of decoding encoded blocks of data, the encoded blocks of data each comprising a plurality of variable-length code words, a plurality of not-encoded bit fields of variable length, and a plurality of not-encoded fields of fixed length, wherein the variable-length code words are interleaved with the not-encoded bit fields of variable length and the not-encoded fields of fixed length, said method comprising the steps:

removing bytes from the not-encoded bit fields of fixed length from the encoded blocks of data and replacing the removed bytes with dummy bytes so as to provide modified encoded blocks of data, and outputting tags, wherein each byte of the modified encoded blocks of data has a corresponding tag indicating whether the byte has been removed and replaced; and

passing the tags to an output of a decoding apparatus in a synchronous and parallel manner, with the modified encoded blocks of data be ing decoded, such that, if there is a multiplicity of the variable-length code words between the not-encoded bit fields of fixed length at an input of the apparatus, then a multiplicity of corresponding decoded data appears at the output of the apparatus between tags corresponding to the not-encoded bit fields of fixed length at the input.

12. An apparatus for decoding encoded blocks of data, the encoded blocks of data each comprising a plurality of variable-length code words, a plurality of not-encoded bit fields of variable length, and a plurality of not-encoded fields of fixed length, wherein the variable-length code words are interleaved with the not-encoded bit fields of variable length and the not-encoded fields of fixed length, said apparatus comprising:

a preprocessing logic unit for removing bytes from the not-encoded bit fields of fixed length from the encoded blocks of data and replacing the removed bytes with dummy bytes so as to provide modified encoded blocks of data, and for outputting tags, wherein each byte of the modified encoded blocks of data has a corresponding tag indicating whether the byte has been removed and replaced by said preprocessing unit; and

a circuit adapted for passing the tags to an output of said apparatus in a synchronous and parallel manner, with the modified encoded blocks of data being decoded, such that, if there is a multiplicity of the variable-length code words between the not-encoded bit fields of fixed length at an input of said apparatus, then a multiplicity of corresponding decoded data appears at the output of said apparatus between tags corresponding to the not-encoded bit fields of fixed length at the input.