Coded data generation or conversion – Digital code to digital code converters
Patent
1995-02-28
1997-03-04
Gaffin, Jeffrey A.
Coded data generation or conversion
Digital code to digital code converters
341 87, 341 95, 341 51, 341 59, 341 63, 341106, H03M 738
Patent
active
056083963
ABSTRACT:
A system for compressing digital data at one byte-per-cycle throughput by removing redundancy before storage or transmission. The system includes an improved Ziv-Lempel LZ1 process that uses a history buffer to save the most recent source string symbols for use in encoding the source symbols as "match-length" and "match-offset" tokens. The match-length code symbols are selected from two groups of buckets that are assigned variable-length prefixes for the shorter, more probable match-lengths and a fixed-length prefix code for the longer, less probable match-lengths. This exploits a transition from Laplacian match-length probability distribution to Uniform match-length probability distribution for longer match-lengths. The offset code field length is reduced during start-up to improve start-up compression efficiency during filling of the history buffer. The match-length code book is limited to a maximum value T<256 to limit latency and simplify the process. Several unused match-length code slots are reassigned to "control codes" that can be inserted into the compressed data stream on the fly without slowing or interrupting the encoding process. Compressed data is verified on the fly by simultaneous decode and CRC comparison with source data, permitting insertion of error-correction "control codes" as necessary without interruption or slowing of the compression flow.
REFERENCES:
patent: 4054951 (1977-10-01), Jackson et al.
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4814746 (1989-03-01), Miller et al.
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5087913 (1992-01-01), Eastman
patent: 5126739 (1992-06-01), Whiting et al.
patent: 5150119 (1992-09-01), Yoshida et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5153591 (1992-10-01), Clark
patent: 5406279 (1995-04-01), Anderson et al.
patent: 5414425 (1995-05-01), Whiting et al.
Kent Anderson, "Methods of Data Compression after the Manner of Lempel and Ziv", Optical Information Systems, Jan.-Feb. 1990, pp. 40-43.
J. Ziv and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding", IEEE Transactions on Information Theory, vol. IT-24, No. 5, Sep. 1978, pp. 530-536.
V. S. Miller et al., "Variations on a Theme by Ziv and Lempel", IBM Research Report RC10630, Jul. 1984, pp. 1-11.
J. Ziv. and A. Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, vol. IT-23, No. 3, May 1977, pp. 337-343.
D. Whiting, "A Comparison of Stac and Hewlett-Packard Data Compression Methods", Stac Electronics, Nov. 1989, pp. 1-10.
R. Lutz, "9703/9704 Design Guide", Stac Electronics Application Note APP-0006, Stac Electronics, Jul. 1990, pp. 720-726.
D. R. Helman, "General Purpose Data Compression ICs", IEEE, 1991, pp. 344-348.
"Data Compression Format for 1/4-inch Data Cartridge Tape Drives", Development Standard QIC-122, rev. B, Feb. 6, 1991, Quarter-inch Cartridge Drive Standards, pp. 1-4.
T. Welch, "A Technique for High-Performance Data Compression", IEEE Computer, Jun. 1984, pp. 8-19.
G. Langdon, Jr., "A Note on the Ziv-Lempel Model for Compressing Individual Sequences", IEEE Transactions on Information Theory, vol. IT-29, No. 2, Mar. 1983.
Cheng Joe-Ming
Craft David J.
Garibay Larry J.
Karnin Ehud D.
Gaffin Jeffrey A.
International Business Machines - Corporation
Vick Jason H.
LandOfFree
Efficient Ziv-Lempel LZI data compression system using variable does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient Ziv-Lempel LZI data compression system using variable , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Ziv-Lempel LZI data compression system using variable will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2149011