Method of performing Huffman decoding

Details Method of performing Huffman decoding Method of performing Huffman decoding

2000-10-31

2003-05-13

Williams, Howard L. (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from number of pulses

C341S067000

Reexamination Certificate

active

06563439

ABSTRACT:

BACKGROUND
The present invention is related to Huffman decoding.
As is well-known, Huffman coding is a popular variable length statistical encoding scheme. As is also well-known, Huffman code generation relies on statistical probabilities for each individual symbol. See, for example, D. A. Huffman, “A Method for the Reconstruction of Minimum-Redundancy Codes” Proceedings of the IRE, Volume 40, No. 9, pages 1098-1101, 1952. A traditional table lookup based encoding scheme is widely used for Huffman encoding due, at least in part, to its efficiency and relative ease of implementation. However, table searching based decoding is typically inefficient in both software and hardware implementations. This is especially the case when the number of entries in a table is reasonably high, as is typical for practical applications. Another approach employed for Huffman decoding is the creation of a Huffman tree which employs a “tree traversing technique.” However, this decoding technique also has disadvantages. This particular technique is bit sequential, and introduces extra “overhead” both in terms of memory allocation and the execution of computations for the Huffman tree generation process and for the decoding process.


REFERENCES:
patent: 4813056 (1989-03-01), Fedele
patent: 4899149 (1990-02-01), Kahan
patent: 5467088 (1995-11-01), Kinouchi et al.
patent: 5973627 (1999-10-01), Bakhmutsky
patent: 6040790 (2000-03-01), Law
patent: 6075470 (2000-06-01), Little et al.
patent: 0907288 (1999-04-01), None
Mukherjee, et al., “Marvle: A VLSI Chip for Data Compression Using Tree-Based Codes”, 8432 IEEE Transactions on very large scale integration (VLSI) systems, Jun. 1, 1993, No. 2, New York, US, XP 000390613, 6 Pgs.
Hirschberg, et al., “Efficient Decoding of Prefix Codes”, 8070 Communications of the ACM 33 (1990) Apr. No. 4, New York, US, XP 000116512, 5 Pgs.
Chang, et al., “VLSI Designs for High-Speed Huffman Decoder”, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA, 1991 IEEE, pp. 500-503.
Cho, et al., “Design of Low Power Variable Length Decoder Using Fine Non-Uniform Table Partitioning”, Department of EECS, Massachusetts Institute of Technology, Cambridge, MA, 1997 IEEE, pp. 2156-2159.
Ooi, et al., “A 162Mbit/s Variable Length Decoding Circuit Using an Adaptive Tree Search Technique”, IEEE 1994 Custom Integrated circuits conference, XP 000492866, 2 Pgs.

Affiliated with

Also associated with

Rating

Method of performing Huffman decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of performing Huffman decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of performing Huffman decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3021657