Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1998-02-18
2001-08-07
Grant, II, Jerome (Department: 2724)
Image analysis
Image compression or coding
Lossless compression
Reexamination Certificate
active
06272257
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to decoders for decoding codes of variable length that are interleaved with variable-length bit fields not being encoded, some of which are passed unchanged through the decoder. The length of the not-encoded bit fields are equal to or greater than zero.
BACKGROUND OF THE INVENTION
Generally, large amounts of data being compressed and decompressed for numerous reasons, including transmission, storage, retrieval, and processing use at some stage means of variable-length coding, such as Huffman coding. Huffman coding was originally disclosed by D. A. Huffman in an article “A Method for the Construction of Minimum Redundancy Codes”
Proc. IRE
, 40: 1098, 1952. In many cases, variable-length codes in an encoded bit stream are not contiguous, but are interleaved with other not-encoded bit fields. The bit fields may represent control and/or formatting information, and/or provide additional specification for encoded data including marker headers, marker codes, stuff bytes, padding bits and additional bits in, for example, JPEG encoded data.
Variable length encoding allocates codes of different lengths to different input data according to the probability of occurrence of the input data, so that statistically more frequent input codes are allocated shorter codes than the less frequent codes. The less frequent input codes are allocated longer codes. The allocation of codes may be done either statically or adaptively. For the static case, the same output code is provided for a given input datum, no matter what block of data is being processed. For the adaptive case, output codes are assigned to input data based on a statistical analysis of a particular input block or set of blocks of data, and possibly changes from block to block (or from a set of blocks to a set of blocks).
Significant problems arise when high speed decoding of variable length codes is required. Problems particularly arise when the encoded stream contains variable-length bit fields that are not encoded are interleaved with encoded data as in, for example, the JPEG standard. Greater difficulty in fast decoding of such variable-length encoded data occurs when the length of a particular not-encoded bit field can be determined only after the preceding (encoded) datum is fully decoded, as in JPEG standard. This generally excludes direct pipelining from being incorporated into a decoder, because the position of the beginning of the next encoded datum is known only after the preceding one is fully decoded.
Existing solutions either require several steps (clock cycles) to decode a single input datum, which renders them too slow for many applications, or use iterative units to decode more than one symbol quasi-simultaneously, i.e. in one stage (clock cycle). However, additional decoding blocks often make such decoders economically unjustifiable, and further are not necessarily fast enough. This is because multiple decoding units do not work fully in parallel, since the beginning of processing in the next unit still depends on the result of processing in the previous one which determines the beginning of the input data for the next one. Thus, even if decoding of several symbols takes place in one stage (clock cycle), that stage (clock period) is relatively long and the whole decoder is too slow for many applications.
Therefore, a need clearly exists for a decoder that can decode variable-length codes interleaved with variable-length bit fields that are not encoded overcoming one or more of the disadvantages of conventional decoders.
SUMMARY OF THE INVENTION
In accordance with a first aspect of the invention, there is provided an apparatus for decoding blocks of data encoded using a plurality of variable-length code words, the blocks of data also comprising not-encoded fields of fixed length, the code words being interleaved with not-encoded bit fields of variable length, the apparatus comprising:
a preprocessing logic unit for removing a plurality of not-encoded fields of fixed length and outputting the plurality of variable-length code words interleaved with the not-encoded bit fields of variable length, and outputting signals indicating positions of the plurality of not-encoded fields of fixed length in the blocks of data;
means for passing the signals indicating positions to an output of the apparatus in a way synchronous with the data being decoded, such that if there is a multiplicity of variable-length coded data between the not-encoded fields of fixed length on the input of the apparatus, a multiplicity of corresponding decoded data appears on the output of the apparatus between any two signals indicating positions corresponding to the not-encoded words of fixed length on the input.
Preferably, the apparatus further comprises: a first processing unit comprising a first set of barrel shifters and a first register, wherein the 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, the second processing unit for processing the outputted signals indicating positions of the not-encoded words of fixed length in the blocks of data; wherein the first and second processing units are identical, and the output of the respective barrel shifters and the units receive identical control signals. Further, the output of the second processing unit for processing signals indicating positions of the not-encoded words of fixed length may be used to determine the size of a not-encoded variable length field to be removed from the data stored in a data register for decoding purposes.
Preferably, the preprocessing logic unit for removing the not-encoded 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 length such that a single bit field has a corresponding tag indicating if the outputted field is passed or removed by the preprocessing unit, or passed by the preprocessing unit and following or preceding a marker being a not-encoded field of fixed length.
Preferably, the blocks of data are encoded using Huffman coding.
In accordance with a second aspect of the invention, there is provided a method of decoding blocks of data which have been encoded using a plurality of variable-length code words, the blocks of data comprising not-encoded fields of fixed length, the code words being interleaved with not-encoded bit fields of variable length, the method comprising the steps:
removing the not-encoded fields of fixed length, and outputting the plurality of variable-length code words interleaved with the not-encoded bit fields of variable length, and outputting signals indicating positions of the not-encoded words of fixed length in the blocks of data;
passing the signals indicating positions to an output in a way synchronous with the data being decoded, such that if there is a multiplicity of variable-length coded data between the not-encoded fields of fixed length being input, a multiplicity of corresponding decoded data appears at the output between any two signals indicating positions corresponding to the not-encoded words of fixed length at the input.
Preferably, the method further comprises 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 positions of the not-encoded words of fixed length in the 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 the output of the respective barrel shifters and the units receive identical control signals. Further, the method may comprise the step of determining the size of a not-enco
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Grant II Jerome
LandOfFree
Decoder of variable length codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoder of variable length codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoder of variable length codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2540449