Data compression system

• US 4,701,745 A
• Filed: 03/03/1986
• Issued: 10/20/1987
• Est. Priority Date: 03/06/1985
• Status: Expired due to Term

• Current Assignee: Hifn, Inc. (Maxlinear Incorporated)
• Original Assignee: Ferranti Limited
• Inventors: Waterworth, John R.
• Primary Examiner(s): Miller, Charles D.
• Application Number:
  US06/835,793
• Time in Patent Office: 596 Days
• Field of Search: 340/347 DD, 235/310, 358/260, 358/261, 364/900
• US Class Current: 341/63
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A data compression system includes an input store (1) for receiving and storing a plurality of bytes of data from an outside source. Data processing means for processing successive bytes of data from the input store includes circuit means (21-25) operable to check whether a sequence of bytes is identical with a sequence of bytes already processed, output means (27) operable to apply to a transfer medium (12) each byte of data not forming part of such an identical sequence, and an encoder (26) responsive to the identification of such a sequence to apply to the transfer means (12) an identification signal which identifies both the location in the input store of the previous occurrence of the sequence of bytes and the number of bytes in the sequence.

Claims

1. A data compression system comprising an input store for receiving and storing a plurality of bytes of uncompressed data from an outside source, and data processing means for processing successive bytes of data from the input store;

the data processing means including circuit means operable to check whether a sequence of successive bytes to be processed identical with a sequence of bytes already processed, and including hash generating means responsive to the application of a predetermined number of bytes in sequence to derive a hash code appropriate to those bytes, a temporary store in which the hash code may represent the address of a storage location, and a pointer counter operable to store in the temporary store at said address a pointer indicative of the position in the input store of one of the predetermined number of bytes;

output means operable to apply to a transfer medium each byte of data not forming part of such an identical sequence; and

encoding means responsive to the identification of such a sequence to apply to the transfer medium an identification signal which identifies both the location in the input store of the previous occurrence of the sequence of bytes and the number of bytes contained in the sequence.

2. A system as claimed in claim 1 in which the circuit means also includes check means operable to check for identity between each of the said predetermined number of bytes in sequence and each of a similar sequence of bytes contained in the input store at a location defined by a pointer read out from the temporary store at said address and to check whether identity exists between succeeding bytes in each sequence of bytes, and a byte counter operable to count the number of identical bytes in each sequence.

3. A system as claimed in claim 2 in which the encoder is operable when such identity exists to encode the pointer read out from the temporary store and the output of the byte counter.

4. A system as claimed in claim 1 which includes a plurality of input stores each of which contains part only of the data from the outside source.

5. A data compression system as claimed in claim 1 which includes data receiving means operable to receive compressed data from the transfer medium, an output store operable to store any uncompressed byte of data received by the receiving means, and copying means responsive to an identification signal to apply to the output store the sequence of bytes already contained in said output store and identified by the said identification signal, the arrangement being such that the data contained in the output store is an exact reconstruction of that applied at some earlier time to the input store.

6. A system as claimed in claim 5 in which the data receiving means includes decoder means operable to separate uncompressed bytes of data from identification signals.

7. A system as claimed in claim 1 in which the transfer medium comprises a communication channel between two spaced locations.

8. A system as claimed in claim 1 in which the transfer medium comprises a data storage medium.