Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1992-09-02
1995-04-11
Young, Brian K.
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
341 65, H03M 730
Patent
active
054062799
ABSTRACT:
A general-purpose, single-pass, adaptive, and lossless data compression invention implements an LZ1-like method using a hash-based architecture. It is suitable for use in data storage and data communications applications. Implementation efficiency, in terms of required memory and logic gates relative to the typical compression ratio achieved, is highly optimized. An easy-to-implement and quick-to-verify hash function is used. Differential copy lengths may be used to reduce the number of bits required to encode the copy-length field within copy tokens. That is, if multiple matches to a sequence of input bytes are found in the current window, then the length of the copy may be encoded as the difference between the lengths of the longest and the second-longest match, which results in a smaller copy length which likely has a shorter encoded representation. To further increase the compression achieved, literals are not used, but rather input bytes without window matches are mapped into alphabet tokens of variable length using a unary-length code. Other unary-length codes are used to represent the copy-length field and the displacement field within copy tokens.
REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4531200 (1985-07-01), Whitley
patent: 4558302 (1985-12-01), Welch
patent: 4562577 (1985-12-01), Glover et al.
patent: 4564941 (1986-01-01), Woolley et al.
patent: 4564945 (1986-01-01), Glover et al.
patent: 4695949 (1987-09-01), Thatte et al.
patent: 4701745 (1987-10-01), Waterworth
patent: 4730348 (1988-03-01), MacCrisken
patent: 4763332 (1988-08-01), Glover
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5051745 (1991-09-01), Katz
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5140321 (1992-08-01), Jung
Dictionary Techniques, Bell, Timothy C., Cleary, John G., and Witten, Ian H., Text Compression, pp. 214-226, pub. by Prentice Hall, Englewood Cliffs, N.J. (1990).
"New Asymptotic Bounds and Improvements on the Lempel-Ziv Data Compression Algorithm" IEEE Tractions on Information Theory vol. 27, No. 3, pp. 721-729 by Paul E. Beneder, et al., May 1981.
"Data Compression via Textual Substitution" Journal of the Association for Computing Machinery vol. 29, No. 4, pp. 928-951 by Storer et al. Oct. 1982.
"A Universal Algorithm for Sequential Data Compression" IEEE Transactions on Information Theory, vol. IT-23, No. 3, pp. 337-343 by Ziv et al., Jul. 1986.
"A Technique for High-Performance Data Compression" IEEE, pp. 8-19, by Welch et al., 1984.
A Method for the Construction of Minimum-Redundancy Codes, by David A. Huffman, Proceedings of the IRE, vol. 40, Sep. 1952, pp. 1098-1101.
An Introduction to Arithmetic Coding, Langdon, Jr., Glen G., IBM Journal of Resarch and Development, vol. 28, No. 2, pp. 135-349, Mar. 1984.
Better OPM/L Text Compression, Bell, Timothy C., IEEE Transactions on Communications, vol. COM-34, No. 12, Dec. 1986, pp. 1176-1182.
Linear Algorithm for Data Compression via String Matching, Rodeh, Michael, Pratt, Vaughan R., and Even, Shimon, Journal of the Association for Computing Machinery, vol. 28, No. 1, Jan. 1981, pp. 16-24.
Anderson Kent D.
Glover Neal
Alford William E.
Blakely, Jr. Roger W.
Cirrus Logic Inc.
Goates Gary B.
Young Brian K.
LandOfFree
General purpose, hash-based technique for single-pass lossless d does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with General purpose, hash-based technique for single-pass lossless d, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General purpose, hash-based technique for single-pass lossless d will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1541686