Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1994-06-13
1996-07-02
Young, Brian K.
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
H03M 730
Patent
active
055326935
ABSTRACT:
An adaptive lossless data compression system with systolic string matching logic performs compression and decompression at the maximum rate of one symbol per clock cycle. The adaptive data compression system uses an improvement of the LZ1 algorithm. A content addressable memory (CAM) is used to store the last n input symbols. The CAM is stationary, stored data is not shifted throughout the CAM, but rather the CAM is used as a circular queue controlled by a Write Address Pointer Counter (WREN). During a compression operation, a new input symbol may be written to the CAM on each clock cycle, while simultaneously the rest of the CAM is searched for the input symbol. Associated with each word of the CAM array is a String Match State Machine (SMSM) and, an address logic module (ALM). These modules detect the occurrence of strings stored in the CAM array that match the current input string and report the address of the longest matching string nearest to the Write Address Pointer. The SMSM modules constitute a systolic logic array, where state information is shifted synchronously in the direction of the Write Address Pointer. The strings are represented by a string code which includes a length value, representing the length of the string, and a position value, representing the position in the CAM of the beginning of the string. During a decompression operation, the single symbols and string codes are input to the system. The symbols are stored in the CAM and the control logic outputs the decompressed data symbols using the stored data and the string codes.
REFERENCES:
patent: 4021782 (1977-05-01), Hoerning
patent: 4056809 (1977-11-01), Hoerning et al.
patent: 4558302 (1985-12-01), Welch
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5373290 (1994-12-01), Lempel et al.
T. Bell, "A Unifying Theory and Improvements for Existing Approaches to Text Compression," Dept. of Computer Science, Univ. of Canterbury, Christchurch, New Zealand, 1986.
T. Bell, J. Cleary and I. Witten, "Text Compression", Prentice-Hall, Englewood Cliffs NJ, 1990.
J. Ziv. and A. Lempel, "Compression of Individual Sequences via Variable Rate Coding", IEEE Transactions on Information Theory, vol. 24, No. 5, pp. 530-536, Sep. 1978.
Terry Welch, "A Technique for High Performance Data Compression", IEEE Computer, vol. 17, No. 6, pp. 8-19, Jun. 1984.
J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory vol. 23, No. 3, pp. 337-343, May 1977.
J. Storer and T. Szymanski, "Data Compression via Textual Substitution," Journal of the ACM, vol. 29, No. 4, pp. 928-951, Oct. 1982.
J. Storer, "Data Compression: Methods and Theory, Computer Science Press", Rockville MD, pp. 64-69, 146-163, 1988.
Bode Robert M.
Feeley Peter S.
French Catherine A.
Owsley Patrick A.
Winters Kel D.
Advanced Hardware Architectures
Young Brian K.
LandOfFree
Adaptive data compression system with systolic string matching l does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive data compression system with systolic string matching l, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive data compression system with systolic string matching l will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1510040