Data compression system with expansion protection

• US 4,870,415 A
• Filed: 10/19/1987
• Issued: 09/26/1989
• Est. Priority Date: 10/19/1987
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Van Maren, David J., Kato, Jeff J.
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): Young, Brian K.
• Application Number:
  US07/109,969
• Time in Patent Office: 708 Days
• Field of Search: 340/347 DD, 358/260, 358/261, 358/257, 358/263, 358/280, 382/56, 235/310, 364/926.1, 364/926.2, 364/926.3, 364/926.6, 341/51, 341/55, 341/63, 341/71, 341/87, 341/94, 341/95
• US Class Current: 341/94
• CPC Class Codes: G06F 40/12 Use of codes for handling textual entities
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present

Abstract

A data compression system implementing expansion protection employs one or more pairs of FIFOs to compare the lengths of raw and processed versions of a block of received data. The shorter version is transmitted so that the data transmitted by the data compression system is at most negligibly expanded relative to the system input. A code is inserted in the output stream to indicate the beginning of the transmission of a raw data block so that a receiving or retrieving system can determine whether the data following needs to be decompressed or not. Further codes can be injected to indicate a switch from raw data to processed data in the output of the compression system.

Claims

1. A system comprising:

system input means for receiving raw data;

system output means for transmitting data;

a data compressor for providing processed data, said compressor including a compressor input for receiving raw data and a compressor output for transmitting processed data, said compression input of said data compressor being coupled to said system input means;

processed data buffer means for storing processed data from said data compressor, said processed data buffer means having a processed data buffer input coupled to said compressor output and a processed data buffer output coupled to said system output, said processed data buffer including process data buffer full indicator means for providing a process data buffer full indication when a predetermined amount of processed data is stored therein;

raw data buffer means for storing raw data, said raw data buffer means having a raw data buffer input coupled to said system input means and a raw data buffer output coupled to said system output means, said raw data buffer means including raw data full indicator means for providing a raw data buffer full indication when a predetermined amount of data is stored therein; and

controller means for controlling the flow of raw and processed data between said system input means and said system output means, said controller means including means for receiving full indications from said buffers and means for enabling the outputs of both said buffer means so that the contents of said processed data buffer means can be transmitted via said system output means in response to a full indication from said raw data buffer means and so that the contents of said raw data buffer means can be transmitted via said system output means in response to a full indication from said processed data buffer.

2. The system of claim 1 further comprising:

code injection means for outputting a predetermined code sequence via said system output means, said code injection means having an injection output coupled to said system output means, said controller means including means for activating said code injection means so as to transmit a code identifying data transmitted from said raw data buffer means as raw data.

3. The system of claim 1 wherein:

said processed data buffer means includes a first-in-first-out memory device; and

said raw data buffer means includes a first-in-first-out memory device.

4. The system of claim 1 wherein:

said processed data buffer means includes first and second first-in-first-out memory devices and means for filling said first and second memory devices in alternation, and

said raw data buffer means includes third and fourth first-in-first-out memory devices and means for filling said third and fourth memory devices in alternation.

5. A method comprising:

receiving raw data;

concurrently storing said raw data in a first memory device and processing said raw data according to a predetermined compression strategy and storing the resulting processed data in a second memory device;

determining which of said memory devices is the first to fill; and

transmitting the contents of the other memory device.

6. A method comprising:

receiving raw data;

concurrently storing said raw data in a first memory device and processing said raw data according to a predetermined compression strategy and storing the resulting processed data in a second memory device;

determining which of said memory devices is the first to fill;

transmitting the contents of the other memory device; and

transmitting a code to mark the transmitted contents as raw data when said second memory device is the first to fill.