Coded data generation or conversion – Digital code to digital code converters – To or from number of pulses
Reexamination Certificate
2000-10-31
2003-10-21
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from number of pulses
Reexamination Certificate
active
06636167
ABSTRACT:
BACKGROUND
The present disclosure is related to Huffman coding.
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. One issue, however, for this procedure is that the resultant Huffman tree is not unique. One example of an application of such codes is text compression, such as GZIP. GZIP is a text compression utility, developed under the GNU (Gnu's Not Unix) project, a project with a goal of developing a “free” or freely available UNIX-like operation system, for replacing the “compress” text compression utility on a UNIX operation system. See, for example, Gailly, J. L. and Adler, M., GZIP documentation and sources, available as gzip-1.2.4.tar at the website “http://www.gzip.org/”. In GZIP, Huffman tree information is passed from the encoder to the decoder in terms of a set of code lengths along with compressed text. Both the encoder and decoder, therefore, generate a unique Huffman code based upon this code-length information. However, generating length information for the Huffman codes by constructing the corresponding Huffman tree is inefficient. In particular, the resulting Huffman codes from the Huffman tree are typically abandoned because the encoder and the decoder will generate the same Huffman codes from the code length information. It would, therefore, be desirable if another approach for generating the code length information were available.
REFERENCES:
patent: 4813056 (1989-03-01), Fedele
patent: 5875122 (1999-02-01), Acharya
patent: 5995210 (1999-11-01), Acharya
patent: 6009201 (1999-12-01), Acharya
patent: 6009206 (1999-12-01), Acharya
patent: 6047303 (2000-04-01), Acharya
patent: 6075470 (2000-06-01), Little et al.
patent: 6091851 (2000-07-01), Acharya
patent: 6094508 (2000-07-01), Acharya et al.
patent: 6108453 (2000-08-01), Acharya
patent: 6124811 (2000-09-01), Acharya et al.
patent: 6130960 (2000-10-01), Acharya
patent: 6151069 (2000-11-01), Dunton et al.
patent: 6151415 (2000-11-01), Acharya et al.
patent: 6154493 (2000-11-01), Acharya et al.
patent: 6166664 (2000-12-01), Acharya
patent: 6178269 (2001-01-01), Acharya
patent: 6195026 (2001-02-01), Acharya
patent: 6215908 (2001-04-01), Pazmino et al.
patent: 6215916 (2001-04-01), Acharya
patent: 6229578 (2001-05-01), Acharya et al.
patent: 6233358 (2001-05-01), Acharya
patent: 6236433 (2001-05-01), Acharya et al.
patent: 6236765 (2001-05-01), Acharya
patent: 6269181 (2001-07-01), Acharya
patent: 6275206 (2001-08-01), Tsai et al.
patent: 6285796 (2001-09-01), Acharya et al.
patent: 6292114 (2001-09-01), Tsai
patent: 6301392 (2001-10-01), Acharya
patent: 6348929 (2002-02-01), Acharya
patent: 6351555 (2002-02-01), Acharya et al.
patent: 6356276 (2002-03-01), Acharya
patent: 6366692 (2002-04-01), Acharya
patent: 6366694 (2002-04-01), Acharya
patent: 6373481 (2002-04-01), Tan et al.
patent: 6377280 (2002-04-01), Acharya et al.
patent: 6381357 (2002-04-01), Tan et al.
patent: 6392699 (2002-05-01), Acharya
patent: 0 907 288 (1999-04-01), None
Yasushi Ooi, et al., “A 162M/bit/s Variable Length Decoding Circuit Using an Adaptive Tree Search Technique”, ULSI Systems Development Labs, NEC Corp., IEEE 1994, Custom Integrated Circuits Conference, XP 000492966, pp. 651-654.
Cho, et al., “Design Low Power Variable Length Decoder Using Fine Grain Non-Uniform Table Partitioning”, Dept. of EECS, Massachusetts Institute of Technology, 1997 IEEE International Sympasium on Circuits and Systems, Jun. 1997, Hong Kong, pp. 2156-2159.
Chang, et al., “VLSI Designs for High-Speed Huffman Decoder”, Dept. of Electrical Engineering and Computer Science, 1991 IEEE, pp. 500-503.
Mukherjee, et al., “MARVLE: A VLSI Chip for Data Compression Using Tree-Based Codes”, XP 000390613, IEEE Transactions on Very Large Scale Integration (VLSI)Systems, Jun. 1993, No. 2, New York, US, pp. 203-214.
Hirschberg, et al., “Efficient Decoding of Prefix Codes”, XP 000116512, Communications of the ACM 33, Apr. 1990, No. 4, New York, US, 5 Pgs.
Acharya Tinku
Tsai Ping-Sing
Gagne Christopher K.
Intel Corporation
Skaist Howard A.
Young Brian
LandOfFree
Method of generating Huffman code length information 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 Huffman code length information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of generating Huffman code length information will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3128444