Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1993-12-02
1995-01-24
Hoff, Marc S.
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
341106, H03M 742
Patent
active
053845684
ABSTRACT:
Methodology and concomitant circuitry for compacting an incoming data stream into an outgoing compacted data stream utilize a plurality of memories or lists. The incoming data stream is partitioned into a sequence of tokens. A primary memory stores each token, with the most recently appearing token occupying the top rank in the list. A secondary memory stores the location in the primary memory of each of a subset of tokens. The compacted data stream is generated as a coded representation of the token itself, the position of the token in the primary memory, or the position in secondary memory of the location of the token in primary memory. A tertiary list may also be employed to generate a coded representation of the position in the tertiary list of the secondary list. Searching of the lists is effected with a hashing function. Updating of the lists utilizes tree splaying.
REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 4612532 (1986-09-01), Bacon et al.
patent: 4796003 (1989-01-01), Bentley et al.
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5010345 (1991-04-01), Nagy
patent: 5023610 (1991-06-01), Rubow et al.
patent: 5126739 (1992-06-01), Whiting et al.
patent: 5146221 (1992-09-01), Whiting et al.
patent: 5239298 (1993-08-01), Wei
T. A. Welch, "A Technique for High Performance Data Compression," IEEE Computer Magazine, 1984, pp. 8-19.
J. L. Bentley et al., "A Locally Adaptive Data Compression Scheme," Communications of the ACM, Apr. 1986, vol. 29, No. 4, pp. 320-330.
D. D. Sleator et al., "Self-Adjusting Binary Search Trees," Journal of the Association for Computing Machinery, 1985, vol. 32, pp. 652-686.
Grinberg Dennis N.
Rajagopalan Sivaramakrishnan
Venkatesan Ramarathnam
Wei Victor K.-W.
Bell Communications Research Inc.
Hoff Marc S.
Suchyta Leonard Charles
LandOfFree
Data compression 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1470517