Coded data generation or conversion – Digital code to digital code converters – Coding by table look-up techniques
Patent
1990-11-27
1992-06-30
Deboer, Todd E.
Coded data generation or conversion
Digital code to digital code converters
Coding by table look-up techniques
341 67, 341 51, 395375, H03M 742, G06F 934
Patent
active
051267390
ABSTRACT:
An apparatus and method as disclosed for converting an input data character stream into a variable length encoded data stream in a data compression system. The data compression system includes a history array means. The history array means has a plurality of entries and each entry of the history array means is for storing a portion of the input data stream. The method for converting the input data character stream includes the following steps. Performing a search in a history array means for the longest data string which matches the input data string. If the matching data string is found within the history buffer means, the next step includes encoding the longest matching data string found by appending to the encoded data stream a tag indicating the longest matching data string was found and a string substitution code. If the matching data string is not found within the history array means, the next step includes encoding the first character of the input data string by appending to the encoded data stream a raw data tag indicating that no matching data string was found and the first character of the input data string.
REFERENCES:
patent: 3976844 (1976-08-01), Betz
patent: 4021782 (1977-05-01), Hoerning
patent: 4054951 (1977-10-01), Jackson et al.
patent: 4370711 (1983-01-01), Smith
patent: 4412306 (1983-10-01), Moll
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4491934 (1985-01-01), Heinz
patent: 4558302 (1985-12-01), Welch
patent: 4612532 (1986-09-01), Bacon et al.
patent: 4701745 (1987-10-01), Waterworth
patent: 4730348 (1988-03-01), MacCrisken
patent: 4814746 (1989-03-01), Miller et al.
patent: 4876541 (1989-10-01), Storer
patent: 4942520 (1990-07-01), Langendorf
patent: 5001478 (1991-03-01), Nagy
Aho, Hopcroft and Ullman, The Design and Analysis of Computer Algorithms, pp. 111-113, 145-147 (1974).
Augenstein and Tenenbaum, Data Structures and PL/I Programmingpp. 534-542 (1979).
A. Lempel and J. Ziv. "On the Complexity of Finite Sequences," IEEE Transactions on Information Theory, vol. IT-22, No. 1, Jan., 1976, pp. 75-81.
V. S. Miller and M. N. Wegman, "Variations on a Theme by Lempel and Ziv," Combinatorial Algorithms on Words, pp. 131-140 (1985).
J. H. Reif and J. A. Storer, "Real-Time Dynamic Compression of Video on a Grid-Connected Parallel Computer," Third International Conference on Supercomputing, May 15-20, 1988, pp. 453-462.
J. A. Storer, "Parallel Algorithms For On-Line Dynamic Data Compression," IEEE International Conference On Communications 1988, pp. 385-389.
J. A. Storer, "Textual Substitution Techniques for Data Compression," Combinatorial Algorithms on Words, pp. 111-129 (1985).
M. E. Gonzalez Smith and J. A. Storer, "Parallel Algorithms for Data Compression," Journal of the Association for Computing Machinery, vol. 32, No. 2, Apr., 1985, pp. 344-373.
George Glen A.
Ivey Glen E.
Whiting Douglas L.
Deboer Todd E.
Logan Sharon D.
STAC Electronics
LandOfFree
Data compression apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1867172