Method of generating a length-constrained huffman code

Details Method of generating a length-constrained huffman code Method of generating a length-constrained huffman code

2000-11-03

2004-02-10

Jeanglaude, Jean Bruner (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from number of pulses

C341S067000

Reexamination Certificate

active

06690306

ABSTRACT:

BACKGROUND
The present disclosure is related to the generation of Huffman codes.
As is well-known, in Huffman coding, greater or longer code lengths are assigned to the less-frequently occurring symbols. Likewise, the two least frequently occurring symbols will have the same code length. See, for example, D. A. Huffman, “A Method for the Construction of Minimum—Redundancy Codes,” Proceedings of the IRE, Volume 40 No. 9, pages 1098 to 1101, 1952. As is well-known, Huffman codes of a set of symbols are generated based at least in part on the probability of occurrence of source symbols. A binary tree, commonly referred to as a “Huffman Tree” is generated to extract the binary code and the code length. See, for example, D. A. Huffman, “A Method for the Construction of Minimum—Redundancy Codes,” Proceedings of the IRE, Volume 40 No. 9, pages 1098 to 1101, 1952. D. A. Huffman, in the aforementioned paper, describes the process this way:
List all possible symbols with their probabilities;
Find the two symbols with the smallest probabilities;
Replace these by a single set containing both symbols, whose probability is the sum of the individual probabilities;
Repeat until the list contains only one member.
This procedure produces a recursively structured set of sets, each of which contains exactly two members. It, therefore, may be represented as a binary tree (“Huffman Tree”) with the symbols as the “leaves.” Then to form the code (“Huffman Code”) for any particular symbol: traverse the binary tree from the root to that symbol, recording “0” for a left branch and “1” for a right branch. In some circumstances, it may be desirable to constrain or limit the maximum length code for the set of symbols, although state of the art Huffman Tree and/or Huffman Code processes do not generally provide for this.


REFERENCES:
patent: 5548338 (1996-08-01), Ellis et al.
patent: 6188338 (2001-02-01), Yokose
patent: 6208274 (2001-03-01), Taori et al.

Affiliated with

Also associated with

Rating

Method of generating a length-constrained huffman code 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 generating a length-constrained huffman code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of generating a length-constrained huffman code will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3310048