Tape controller with data compression and error correction sharing a common buffer

• US 5,159,336 A
• Filed: 08/13/1991
• Issued: 10/27/1992
• Est. Priority Date: 08/13/1991
• Status: Expired due to Fees

• Current Assignee: Ditto TV
• Original Assignee: Iomega Corporation (Dell Technologies Inc.)
• Inventors: Skeggs, Peter L., Rabin, Steve
• Primary Examiner(s): HOFF, MARC S
• Application Number:
  US07/744,319
• Time in Patent Office: 441 Days
• Field of Search: 341/51, 341/65, 341/67, 341/94
• US Class Current: 341/51
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0682 Tape device
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A controller has a data compression unit and error correcting code unit which share a single common random access memory. The controller is connected between a host computer and a peripheral device such as a tape drive. A second order search for strings of data bytes is enabled or disabled to change the compression ratio, data throughput, and memory bandwidth constraints.

Claims

1. A controller for connection between a host computer and a peripheral device for said computer comprising:

an error correcting code unit;

a data compression unit;

a single shared random access memory providing buffer memory for both said error correcting unit and said data compression unit;

a single memory bus between said shared random access memory, said error correcting code unit and said data compression unit; and

an arbiter controlling said ECC unit and said data compression unit to share access to said random access memory across said bus.

2. The controller recited in claim 1 wherein said data compression unit performs a primary search for repeated occurrences of strings in a stream of data bytes passing from said host computer to said peripheral unit;

and

means for controlling the search in said data compression unit to alter the compression ratio and the data throughput of said compression unit.

3. The controller recited in claim 2 wherein said data compression unit includes:

means for performing a more extensive second order search in which the stream of bytes being processed is searched for strings of length greater than the current match length; and

means for enabling and disabling said means for performing a second order search to adjust the compression rate of said compression unit.

4. The system recited in claim 3 wherein said controller is connected between said host computer and said peripheral unit and wherein said controller contains a control bit enabling and disabling said second order search, said control bit being set by said controller in response to data throughput from said host computer to increase the ratio of compressed bytes to bytes not compressed, thereby reducing said compression rate.

5. The controller recited in claim 2 wherein said data compression unit includes:

means for storing strings of data bytes which match other strings in a stream of data bytes passing from said host computer to said peripheral unit;

means for searching for natural extensions of the current match length as each subsequent byte is processed;

means for performing a second order search in which the stream of bytes is searched for strings of length greater than the current match length; and

means for enabling and disabling said means for performing said second order search to adjust the compression rate of said compression unit.

6. The system recited in claim 5 wherein said shared random access memory includes:

a history buffer for storing groups of bytes processed by said compression unit;

a buffer pointing to the head of a linked list for each byte value appearing in said history buffer; and

means for updating said history buffer each time a byte is processed by said compression unit and wherein said second order search is performed if the current match length is not extended, said second order search being performed on all previously processed bytes for strings greater than the current match length.

7. The system recited in claim 6 wherein said random access memory includes:

a pointer buffer containing a linked list of all occurrences of each byte value appearing in said history buffer, and wherein said pointer buffer is updated as each byte is processed.

8. The system recited in claim 6 further comprising:

an input buffer containing input bytes for which no compressed representation has been produced.

9. The system recited in claim 1 wherein said peripheral is a tape drive.

10. The system recited in claim 1 wherein said error correcting code unit, said data compression unit, said shared random access memory and said arbiter are integrated into a single VLSI integrated circuit.

11. A data compression unit for connection between a host computer and a peripheral device for said computer comprising:

means for performing a primary search for repeated occurrences of strings in a stream of data bytes passing from said host computer to said peripheral unit;

means for controlling the search in said data compression unit to alter the compression ratio and the data throughout of said compression unit;

means for performing a more extensive second order search in which the stream of bytes being processed is searched for strings of length greater than the current match length; and

means for enabling and disabling said means for performing a second order search to adjust the compression ratio of said compression unit.

12. The data compression unit recited in claim 11 further comprising:

means for storing strings of data bytes which match other strings in a stream of data bytes passing from said host computer to said peripheral unit;

means for searching for natural extensions of the current match length as each subsequent byte is processed;

means for performing a second order search in which the stream of bytes is searched for strings of length greater than the current match length; and

means for enabling and disabling said means for performing said second order search to adjust the compression rate of said compression unit.

13. The system recited in claim 11 wherein said random access memory includes:

a history buffer for storing groups of bytes processed by said compression unit;

a buffer pointing to the head of a linked list for each byte value appearing in said history buffer; and

means for updating said history buffer each time a byte is processed by said compression unit and wherein said second order search is performed if the current match length is not extended, said second order search being performed on all previously processed bytes for strings greater than the current match length.

14. The system recited in claim 13 wherein said random access memory further includes:

a pointer buffer containing a linked list of all occurrences of each byte value appearing in said history buffer, and wherein said pointer buffer is updated as each byte is processed.

15. The system recited in claim 13 further comprising:

an input buffer containing input bytes for which no compressed representation has been produced.

16. The system recited in claim 11 wherein said data compression unit is in a controller connected between said host computer and said peripheral unit, and wherein said controller contains a control bit enabling and disabling said second order search, said control bit being set by said controller in response to data throughput from said host computer to increase the ratio of compressed bytes to bytes not compressed, thereby reducing said compression rate.

17. The system recited in claim 11 wherein said peripheral is a tape drive.