Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2007-01-09
2007-01-09
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S107000
Reexamination Certificate
active
11015894
ABSTRACT:
An enumerator employs “indexing volumes” as the add-on values used to compute indexes for n-item ordered sets such as symbol sequences. Each indexing volume is associated with a different class into which the allowed ordered sets are partitioned. The indexing volumes all equal or exceed the number of ordered sets that belong to their respective classes. Additionally, the indexing volume Viassociated with a given class of i-item equals or exceeds the sum of the indexing volumes associated with the classes that contain the (i−1)-item prefixes of the ordered sets that belong to the given class. The indexing volumes are quantized such that each volume V=wrs, where r is an integer greater than unity, s is a non-negative integer, w is a positive integer less than rm, m is some positive integer less than h, and, for some allowed ordered set whose size is less than n, h is the number of radix-r digits in the smallest quotient that results from evenly dividing by a positive-integer power of r the set count of the class to which that allowed ordered set belongs. As a result, the addition operations used to compute the indexes can be performed with limited precision, and storage requirements for the add-on values can be relatively modest.
REFERENCES:
patent: 4122440 (1978-10-01), Langdon, Jr. et al.
patent: 4286256 (1981-08-01), Langdon, Jr. et al.
patent: 4295125 (1981-10-01), Langdon, Jr.
patent: 4463342 (1984-07-01), Langdon, Jr. et al.
patent: 4467317 (1984-08-01), Langdon, Jr. et al.
patent: 4633490 (1986-12-01), Goertzel et al.
patent: 4652856 (1987-03-01), Mohiuddin et al.
patent: 4792954 (1988-12-01), Arps et al.
patent: 4891643 (1990-01-01), Mitchell et al.
patent: 4901363 (1990-02-01), Toyokawa
patent: 4905297 (1990-02-01), Langdon, Jr. et al.
patent: 4933883 (1990-06-01), Pennebaker et al.
patent: 4935882 (1990-06-01), Pennebaker et al.
patent: 4973961 (1990-11-01), Chamzas et al.
patent: 4989000 (1991-01-01), Chevion et al.
patent: 5023611 (1991-06-01), Chamzas et al.
patent: 5025258 (1991-06-01), Duttweiler
patent: 5045852 (1991-09-01), Mitchell et al.
patent: 5099440 (1992-03-01), Pennebaker et al.
patent: 5142283 (1992-08-01), Chevion et al.
patent: 5210536 (1993-05-01), Furlan
patent: 5272478 (1993-12-01), Allen
patent: 5307062 (1994-04-01), Ono et al.
patent: 5309381 (1994-05-01), Fukui
patent: 5311177 (1994-05-01), Kimura et al.
patent: 5363099 (1994-11-01), Allen
patent: 5404140 (1995-04-01), Ono et al.
patent: 5406282 (1995-04-01), Nomizu
patent: 5414423 (1995-05-01), Pennebaker
patent: 5418532 (1995-05-01), Lei
patent: 5546080 (1996-08-01), Langdon, Jr. et al.
patent: 6298160 (2001-10-01), Goertzen
patent: 6441755 (2002-08-01), Dietz et al.
patent: 6621428 (2003-09-01), Crane
patent: 6633242 (2003-10-01), Brown
patent: 6894628 (2005-05-01), Marpe et al.
Pearlman, William A. “High Performance, Low-Complexity Image Compression.” Electrical, Computer and Systems Engineering Dept., Rensselaer Polytechnic Institute, Troy, New York, Jul. 1997, pp. 1-13.
Tsai et al. “Stack-Run Coding for Low Bit Rate Image Communication.” Electrical Engineering Department, University of California, Los Angeles, California, 1996 IEEE, pp. 681-684.
Moffat et al. “Arithmetic Coding Revisited.” ACM Transactions on Information Systems, vol. 16, No. 3, Jul. 1998, pp. 256-294.
Bookstein, et al. “Is Huffman Coding Dead?” Computing, Springer-Verlag, Austria, vol. 50, 1993, pp. 279-296, no month given.
Lynch, Thomas J. “Sequence Time Coding for Data Compression.” Proceedings Letters, Proceedings of the IEEE, Oct. 1966, pp. 1490-1491.
Davisson, L.D. “Comments on ‘Sequence Time Coding for Data Compression.’” Proceedings Letters, Proceedings of the IEEE, Dec. 1966, p. 2010.
Öktem et al. “Hierarchical Enumerative Coding of Locally Stationery Binary Data.” Electronics Letters, 19thAug. 1999, vol. 35, No. 17, pp. 1428-1429.
Dai et al. “Binary Combinatorial Coding.” Proceedings of the Data Compression Conference (DCC'03), 2003 IEEE, one page, no month given.
Myrvold et al. “Ranking and Unranking Permutations in Linear Time.” Information Processing Letters, vol. 79, 2001, pp. 281-284.
Immink, Kees A. Schouhamer. “A Practical Method for Approaching the Channel Capacity of Constrained Channels.” IEEE Transactions on Information Theory, vol. 43, No. 5, Sep. 1997, pp. 1389-1399.
Cover, Thomas M. “Enumerative Source Encoding.” IEEE Transactions on Information Theory, vol. 1T-19, No. 1, Jan. 1973, pp. 73-77.
Lawrence, John C. “A New Universal Coding Scheme for the Binary Memoryless Source.” IEEE Transactions on Information Theory, vol. 1T-23, No. 4, Jul. 1977, pp. 466-472.
Web search results on “Enumerative Coding”, CiteSeer, http://citeseer.ist.psu.edu, Aug. 31, 2004, page one of one.
Tjalkens, Tjalling J. “A Universal Variable-to-Fixed Length Source Code Based on Lawrence's Algorithm.” IEEE Transactions on Information Theory, vol. 38, No. 2, Mar. 1992, pp. 247-253.
Immink et al. “Effects of Floating Point Arithmetic in Enumerative Coding.” Philips Research Laboratories, Prof. Holstlaan 6, 5656 AA Eindhoven, The Netherlands, Apr. 1997, pp. 1-6.
Schalkwijk, J. Pieter M. “An Algorithm for Source Coding.” IEEE Transactions on Information Theory, vol. 1T-18, No. 3, May 1972, pp. 395-399.
Rissanen, J.J. “Generalized Kraft Inequality and Arithmetic Coding.” IBM J. Res. Develop., May 1976, pp. 198-203.
Printz, Harry. “Tutorial on Arithmetic Coding.” Feb. 23, 1994.
Bird et al. “Arithmetic Coding with Folds and Unfolds.” Advanced Functional Programming 4, Lecture Notes in Computer Science, Johan Jeuring and Simon Payton Jones, editors, 2003, pp. 1-26.
Öktem, Levent. “Hierarchical Enumerative Coding and Its Applications in Image Compression.” Thesis, Signal Processing Laboratory of Tampere University of Technology, 1999, pp. i-123.
1st Works Corporation
Foley & Hoag LLP
Young Brian
LandOfFree
Fast, practically optimal entropy coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast, practically optimal entropy coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast, practically optimal entropy coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3809346