US4929946A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive data compression apparatus including run length encoding for a tape drive system
Assignee: Storage Technology Corp
•
Filing: 1989-02-09
•
Granted: 1990-05-29
•
Expires: 2009-02-09
Abstract
Abstract The adaptive data compression apparatus is located within a tape drive control unit which is interposed between one or more host computers and one or more tape transports. The adaptive data compression apparatus functions to efficiently compress a user data file received from a host computer into a bit oriented compressed format for storage on the magnetic tape that is loaded in the tape transport. The data compression apparatus divides each block of an incoming user data file into predetermined sized segments, each of which is compressed independently without reference to any other segment in the user data file. The data compression apparatus concurrently uses a plurality of data compression algorithms to adapt the data compression operation to the particular data stored in the user data file. A cyclic redundancy check circuit is used to compute a predetermined length CRC code from all of the incoming user data bytes before they are compressed. The computed CRC code is appended to the end of the compressed data block. The data compression apparatus operates by converting bytes and strings of bytes into shorter bit string codes called reference values. The reference values replace the bytes and strings of bytes when recorded on the magnetic tape. The byte strings have two forms, a run length form for characters that are repeated three or more times, and a string form that recognizes character patterns of two or more characters.
Inventors
- 👤 John T. O'Brien
- 👤 Neil L. Thomas
- 👤 Tracy D. Dyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 18:33
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/09; H03M13/091; G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; H03M7/00; H03M7/30; H03M7/46; H03M7/48
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
233 words
A data compression apparatus for efficiently compressing a user block data into a bit compressed data block for storage on a data storage medium comprising: means for dividing said user data block into a plurality of equal sized segments of data; means for compressing each of said segments of data independent of all other segments of data in said user data block comprising: means responsive to a received user data byte in one of said segments of data for determining whether said received user data byte is identical to the n previous data bytes, the last byte of a string or a single user data byte in said one segment of data; means responsive to said determining means for assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; means responsive to said determining means for assigning one of a plurality of byte compression reference values to a user data byte; means responsive to said determining means for assigning one of a plurality of string compression reference values to a user data byte that comprises the last byte of a data string; and means for writing each of said reference values successively received from said compressing means on to a data storage medium to form said bit compressed data block.
Claim 2
Dependent Claim
233 words
A data compression apparatus for efficiently compressing a user block data into a bit compressed data block for storage on a data storage medium comprising: means for dividing said user data block into a plurality of equal sized segments of data; means for compressing each of said segments of data independent of all other segments of data in said user data block comprising: means responsive to a received user data byte in one of said segments of data for determining whether said received user data byte is identical to the n previous data bytes, the last byte of a string or a single user data byte in said one segment of data; means responsive to said determining means for assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; means responsive to said determining means for assigning one of a plurality of byte compression reference values to a user data byte; means responsive to said determining means for assigning one of a plurality of string compression reference values to a user data byte that comprises the last byte of a data string; and means for writing each of said reference values successively received from said compressing means on to a data storage medium to form said bit compressed data block.
Claim 3
Dependent Claim
46 words
The apparatus of claim 1 further including: means responsive to the last user data byte of said user data block for appending a CRC value representative of the CRC of said user data block to said bit compressed data block written on said data storage medium.
Claim 4
Dependent Claim
103 words
The apparatus of claim 1 further including: means for storing each received data byte; means responsive to said storing means storing the last byte of said one segment of data for calculating the byte length of said reference values written on to said data storage medium representative of said one segment of data; and means responsive to said byte length exceeding the byte length of said one segment of data for writing said one segment of data on to said data storage medium in place of said reference values written on to said data storage medium representative of said one segment of data.
Claim 5
Dependent Claim
81 words
The apparatus of claim 1 further including: means responsive to said compressing means assigning a reference value to the last data byte of said one segment of data for decompressing said reference values successively assigned to the data bytes of said one segment of data; and means responsive to said decompressing means for comparing said decompressed bit compressed segment of said data block with said one segment of data to identify errors in said bit compressed segment of said data block.
Claim 6
Dependent Claim
27 words
The apparatus of claim 1 further comprising: means for selectively bypassing said compressing means to write said segments of data directly on to said data storage medium.
Claim 7
Dependent Claim
77 words
The apparatus of claim 1 wherein said string reference value assignment means includes: means for comparing a received string of data bytes with a table containing entries representative of previously received strings of data bytes in said one segment of data that have been assigned a string reference value; and means responsive to said received string of data bytes failing to match said table entries for assigning a previously unassigned string reference value to said received string.
Claim 8
Dependent Claim
35 words
The apparatus of claim 1 further including: means for determining the length of each compressed segment of data; and means for appending a value, indicative of said determined length, to said compressed segment of data.
Claim 9
Dependent Claim
56 words
The apparatus of claim 7 further including: means, responsive to said compressed data block read from said data storage medium in backwards order, for reading said appended value; means for dividing a segment, the length of which is indicated by said appended value, from said read compressed data block; and means for decompressing said divided segment.
Claim 10
Dependent Claim
308 words
A data compression apparatus for efficiently compressing a user data block into a bit compressed data block for storage on a data storage medium comprising: means for dividing said user data block into a plurality of equal sized segments of data; means for compressing each of said segments of data independent of all other segments of data in said user data file comprising: means responsive to a received user data byte in one of said segments of data for determining whether said received user data byte is identical to the n previous data bytes, the last byte of a string or a single user data byte in said one segment of data; means responsive to said determining means for assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; means responsive to said determining means for assigning one of a plurality of byte compression reference values to a user data byte; means responsive to said determining means for assigning one of a plurality of string compression reference values to a suer data byte that comprises the last byte of a data string; means for writing each of said reference values successively received from said compressing means on to a data storage medium; means for storing each received data byte; means responsive to said storing means storing the last byte of said one segment of data for calculating the byte length of said reference values written on to said data storage medium representative of said one segment of data; and means responsive to said byte length exceeding the byte length of said one segment of data for writing said one segment of data in place of said reference values written on to said data storage medium.
Claim 11
Dependent Claim
308 words
A data compression apparatus for efficiently compressing a user data block into a bit compressed data block for storage on a data storage medium comprising: means for dividing said user data block into a plurality of equal sized segments of data; means for compressing each of said segments of data independent of all other segments of data in said user data file comprising: means responsive to a received user data byte in one of said segments of data for determining whether said received user data byte is identical to the n previous data bytes, the last byte of a string or a single user data byte in said one segment of data; means responsive to said determining means for assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; means responsive to said determining means for assigning one of a plurality of byte compression reference values to a user data byte; means responsive to said determining means for assigning one of a plurality of string compression reference values to a suer data byte that comprises the last byte of a data string; means for writing each of said reference values successively received from said compressing means on to a data storage medium; means for storing each received data byte; means responsive to said storing means storing the last byte of said one segment of data for calculating the byte length of said reference values written on to said data storage medium representative of said one segment of data; and means responsive to said byte length exceeding the byte length of said one segment of data for writing said one segment of data in place of said reference values written on to said data storage medium.
Claim 12
Independent Claim
191 words
A method of efficiently compressing a user data block into a bit compressed data block for storage on a data storage medium comprising the steps of: dividing said user data block into a plurality of equal sized segments of data; compressing each of said segments of data independent of all other segments of data in said user data block comprising: determining whether said received user data byte in one of said segments of data is identical to the n previous data bytes, the last byte of a string or a single user data byte in said one segment of data; assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; assigning one of a plurality of byte compression reference values to a user data byte; assigning one of a plurality of string compression reference values to a user data byte that comprises the last byte of a data string; and writing each of said reference values successively received from said compressing means on to a data storage medium.
Claim 13
Independent Claim
191 words
A method of efficiently compressing a user data block into a bit compressed data block for storage on a data storage medium comprising the steps of: dividing said user data block into a plurality of equal sized segments of data; compressing each of said segments of data independent of all other segments of data in said user data block comprising: determining whether said received user data byte in one of said segments of data is identical to the n previous data bytes, the last byte of a string or a single user data byte in said one segment of data; assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; assigning one of a plurality of byte compression reference values to a user data byte; assigning one of a plurality of string compression reference values to a user data byte that comprises the last byte of a data string; and writing each of said reference values successively received from said compressing means on to a data storage medium.
Claim 14
Dependent Claim
49 words
The method of claim 10 further including the step of: appending, in response to the last user data byte of said user block data, a CRC value representative of the CRC of said user data block to said bit compressed data block written on to said data storage medium.
Claim 15
Dependent Claim
79 words
The method of claim 10 further including the steps of: storing each received data byte; calculating the byte length of said reference values written on to said data storage medium representative of said one segment of data; and writing, in response to said byte length exceeding the byte length of said one segment of data, said one segment of data on to said data storage medium in place of said reference values written on to said data storage medium.
Claim 16
Dependent Claim
76 words
The method of claim 10 further including the steps of: decompressing, in response to said compressing means assigning a reference value to the last data byte of said one segment of data, said reference values successively assigned to the data bytes of said one segment of data; and comparing said decompressed bit compressed segment of said data block with said one segment of data to identify errors in said bit compressed segment of said data block.
Claim 17
Dependent Claim
70 words
The method of claim 10 wherein the step of assigning a string reference value includes: comparing a received string of data bytes with a table containing entries representative of previously received strings of data bytes that have been assigned a string reference value; and assigning, in response to said received string of data bytes failing to match said table entries, a previously unassigned string reference value to said received string.
Claim 18
Dependent Claim
34 words
The method of claim 10 further including the steps of: determining the length of each compressed segment of data; and appending a value, indicative of said determined length, to said compressed segment of data.
Claim 19
Dependent Claim
57 words
The method of claim 15 further including the steps of: reading said appended value from said compressed data block when said compressed data block is read from said data storage medium in backwards order; dividing a segment, the length of which is indicated by said appended value, from said compressed data block; and decompressing said divided segment.
Claim 20
Independent Claim
277 words
A method of efficiently compressing a user data block into a bit compressed data block for storage on a data storage medium comprising the steps of: dividing said user data block into a plurality of equal sized segments of data; compressing each of said segments of data independent of all other segments of data in said user data block comprising: determining in response to a received user data byte in one of said segments of data whether said received user data byte is identical to the n previous data bytes; the last byte of a string or a single user data byte in said one segment of data; assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; assigning one of a plurality of byte compression reference values to a user data byte; assigning one of a plurality of string compression reference values to a user data byte that comprises the last byte of a data string; writing each of said reference values successively received from said compressing means on to a data storage medium; storing each received data byte; calculating, in response to said storing means storing the last byte of said one segment of data, the byte length of said reference values written on to said data storage medium representative of said one segment of data; and writing, in response to said byte length exceeding the byte length of said one segment of data, said one segment of data in place of said reference values written on to said data storage medium.
Claim 21
Independent Claim
277 words
A method of efficiently compressing a user data block into a bit compressed data block for storage on a data storage medium comprising the steps of: dividing said user data block into a plurality of equal sized segments of data; compressing each of said segments of data independent of all other segments of data in said user data block comprising: determining in response to a received user data byte in one of said segments of data whether said received user data byte is identical to the n previous data bytes; the last byte of a string or a single user data byte in said one segment of data; assigning one of a plurality of run length reference values to a user data byte that is identical to at least the n previous user data bytes, where n is an integer >2; assigning one of a plurality of byte compression reference values to a user data byte; assigning one of a plurality of string compression reference values to a user data byte that comprises the last byte of a data string; writing each of said reference values successively received from said compressing means on to a data storage medium; storing each received data byte; calculating, in response to said storing means storing the last byte of said one segment of data, the byte length of said reference values written on to said data storage medium representative of said one segment of data; and writing, in response to said byte length exceeding the byte length of said one segment of data, said one segment of data in place of said reference values written on to said data storage medium.
References Cited (Backward Citations)
US4021782A
Cited
US4494150A
Cited
US4558302A
Cited
US4558302B1
Cited
US4586027A
Cited
US4568983A
Cited
US4626824A
Cited
US4626829A
Cited
US4729020A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-05-28 | 1993-11-27 | 1994-05-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-05-28 | 1997-11-27 | 1998-05-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-05-28 | 2001-11-27 | 2002-05-29 | $7700.00 | Window Closed / Lapsed |