Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
1999-06-10
2001-09-18
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S065000, C341S106000
Reexamination Certificate
active
06292114
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to data compression. More specifically, the invention relates to data compression for image processing and other such applications.
2. Description of the Related Art
Image compression techniques can be classified as either “lossy” or “lossless”. With lossless compression, the original image prior to compression can be exactly recovered when the compressed image is decompressed. Consequently, lossless techniques, whose compression ratios depend upon the entropy of an image, do not achieve high compression ratios and, since they preserve a high percentage of original image information, are computationally expensive. By contrast, lossy compression schemes provide only an approximation of the original image. Thus, with lossy compression, greater compression ratios can be achieved but with loss in image quality compared to lossless techniques. One such lossy technique referred to as “predictive coding” (also called Digital Pulse Code Modulation (DPCM) which is well-known in the art) predicts the value of a successive pixel (pixels are color components related by spatial row, column position) by linearly combining the properties of already processed neighboring pixels. An error pixel is defined as the difference between the original image pixel and the corresponding predicted pixel. The error pixel is first quantized and then binary encoded. Traditionally, the binary encoding involves either using a fixed-length code or variable-length code which encodes the quantized error pixel (value). Variable-length coding is used in image/motion compression techniques such as JPEG (Joint Photographic Experts Group), MPEG (Motion Pictures Experts Group) and H.261. In the variable-length encoding situation, quantized error values will have different lengths based upon the number of bits needed to represent the value in binary. Thus, often, both a run-length (i.e., the length of the code to follow or the number of consecutive zeroes or ones) and the code itself must be encoded. Strictly variable-length code is difficult to decode and inefficient to implement in a parallel processing architectures since there are no predefined boundaries between codewords. Variable-length encoding is inherently serial in nature, where decoding is usually done one bit at a time, since there is a wide possible variation in the lengths of the quantized error codes.
The implementation of such computationally intensive techniques demands more VLSI circuitry than is suitable for digital cameras and portable, small devices desiring image compression. One method developed for the decoding of variable length codes is the construction of a “decoding tree.” Thus, in popular variable length coding schemes such as Huffman coding, after a Huffman encoding list (which specifies how and with what lengths data is to be coded) is developed, a corresponding decoding tree is also constructed and then somehow stored in memory. Starting from the root, the tree may be traversed through its branches until a leaf (terminal node) is encountered. The terminal node indicates that the codeword is fully decoded, such that the corresponding symbol may be read out. This process restarts at the root for each such potential codeword.
The construction of such decoding trees is resource intensive and can cost valuable time. Further, a key problem in the implementation of such methods is how to most efficiently store the decoding tree from which codewords may be decoded. Thus, there is a need for simpler technique to implement bit-serial decoding while reducing the complexity and resource use of that in traditional decoding tree techniques.
SUMMARY OF THE INVENTION
A method comprising constructing a bit-serial decoding table for a list of variable length codewords without the use of a binary decoding tree, and then decoding using that decoding table, in a bit serial fashion, a bitstream encoded using the variable length codewords.
REFERENCES:
patent: 5696507 (1997-12-01), Nam
patent: 5990812 (1999-11-01), Bakhmutsky
patent: 6188797 (2001-02-01), Moledina et al.
Acharya Tinku
Tsai Ping-Sing
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Tokar Michael
Tran Anh Q.
LandOfFree
Efficient memory mapping of a huffman coded list suitable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient memory mapping of a huffman coded list suitable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient memory mapping of a huffman coded list suitable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2494882