US5410671A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression/decompression processor
Assignee: VIA Cyrix Inc
•
Filing: 1993-05-21
•
Granted: 1995-04-25
•
Expires: 2013-05-21
Abstract
Abstract A data compression/decompression processor (a single-chip VLSI data compression/decompression engine) for use in applications including but not limited to data storage and communications. The processor is highly versatile such that it can be used on a host bus or housed in host adapters, so that all devices such as magnetic disks, tape drives, optical drives and the like connected to it can have substantial expanded capacity and/or higher data transfer rate. The processor employs an advanced adaptive data compression algorithm with string-matching and link-list techniques so that it is completely adaptive, and a dictionary is constructed on the fly. No prior knowledge of the statistics of the characters in the data is needed. During decompression, the dictionary is reconstructed at the same time as the decoding occurs. The compression converges very quickly and the compression ratio approaches the theoretical limit. The processor is also insensitive to error propagation.
Inventors
- 👤 Taher A. Elgamal
- 👤 Daniel D. Claxton
- 👤 Robert F. Honea
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:50
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
73 words
A method of accessing files of compressed data on a mass storage device comprising the steps of: allocating one or more logical data blocks to each file using a first allocation table; allocating one or more physical data blocks for storing file data using a second file allocation table; and translating between said first file allocation table and said second file allocation table in response to a request to access the storage device.
Claim 2
Independent Claim
73 words
A method of accessing files of compressed data on a mass storage device comprising the steps of: allocating one or more logical data blocks to each file using a first allocation table; allocating one or more physical data blocks for storing file data using a second file allocation table; and translating between said first file allocation table and said second file allocation table in response to a request to access the storage device.
Claim 3
Dependent Claim
30 words
The method of claim 1 wherein said translating step comprises the step of translating between said first file allocation table and said second file allocation table using a mapping table.
Claim 4
Dependent Claim
25 words
The method of claim 2 wherein said first file allocation table comprises a plurality of entries, each entry associated with a respective logical data block.
Claim 5
Dependent Claim
59 words
The method of claim 3 wherein said step of allocating one or more logical data blocks comprises the step of associating each file with one of said entries corresponding a first logical data block associated with that file and creating a linked list of entries in said first allocation file indicating the logical data blocks associated with the file.
Claim 6
Dependent Claim
35 words
The method of claim 4 wherein each entry of the first allocation table is associated with a respective entry in the mapping table which indicates a physical data block allocated by said second allocation table.
Claim 7
Independent Claim
66 words
A system of storing and retrieving compressed data comprising: a first file allocation table for allocating one or more logical data blocks to each of a plurality of files; a second allocation file for allocating physical data blocks for storing file data; and a mapping table for translating between said first and second file allocation tables in response to a request to access the storage device.
Claim 8
Independent Claim
66 words
A system of storing and retrieving compressed data comprising: a first file allocation table for allocating one or more logical data blocks to each of a plurality of files; a second allocation file for allocating physical data blocks for storing file data; and a mapping table for translating between said first and second file allocation tables in response to a request to access the storage device.
Claim 9
Dependent Claim
38 words
The system of claim 6 and further comprising a processor for compressing the file data in response to a write operation to the storage device and decompressing the data responsive to a read operation from the storage device.
Claim 10
Dependent Claim
25 words
The system of claim 7 wherein said first file allocation table comprises a plurality of entries, each entry associated with a respective logical data block.
Claim 11
Dependent Claim
41 words
The system of claim 8 wherein said mapping table comprises a plurality of entries corresponding to respective of said first file allocation table entries, each entry of said mapping table indicating a physical data block allocated by said second allocation table.
Claim 12
Dependent Claim
21 words
The system of claim 6 wherein said first allocation table maintains a linked list of logical data blocks for each file.
Claim 13
Independent Claim
84 words
A method of accessing files of compressed data on a mass storage device comprising the steps of: maintaining a first file allocation table which indicates one or more logical data blocks; maintaining a second file allocation table which indicates one or more physical data blocks on the mass storage device where the compressed data associated with each file is stored; mapping between the first file allocation table and the second file allocation table in response to a request to access the mass storage device.
Claim 14
Independent Claim
84 words
A method of accessing files of compressed data on a mass storage device comprising the steps of: maintaining a first file allocation table which indicates one or more logical data blocks; maintaining a second file allocation table which indicates one or more physical data blocks on the mass storage device where the compressed data associated with each file is stored; mapping between the first file allocation table and the second file allocation table in response to a request to access the mass storage device.
Claim 15
Dependent Claim
45 words
The method of claim 11 wherein each block of said second file allocation table comprises a plurality of allocation units, and said mapping step comprises the step of associating each block of said first file allocation table with one or more of said allocation units.
Claim 16
Dependent Claim
43 words
The method of claim 11 wherein said mapping step comprises the step of associating each block of said first file allocation table with a block of said second file allocation table and an offset into said block of said second file allocation table.
Claim 17
Dependent Claim
32 words
The method of claim 11 and further comprising the step of allocating a number of logical data blocks in excess of the number of physical data blocks to said first allocation table.
Claim 18
Dependent Claim
26 words
The method of claim 11 wherein said mapping step comprises the step of mapping a plurality of logical data blocks into a single physical data block.
Claim 19
Dependent Claim
29 words
The method of claim 11 wherein said mapping step comprises the step of mapping each logical data block to a physical block and an offset into the physical block.
References Cited (Backward Citations)
US4654777A
Cited
US4667325A
Cited
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4680700A
Cited
US4989137A
Cited
US4701745A
Cited
US4800489A
Cited
US4843389A
Cited
US4876541A
Cited
US4881075A
Cited
US4847619A
Cited
US4870415A
Cited
US5077654A
Cited
US4942541A
Cited
US4906991A
Cited
US4899147A
Cited
US4929946A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-04-24 | 1998-10-24 | 1999-04-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-04-24 | 2002-10-24 | 2003-04-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-04-24 | 2006-10-24 | 2007-04-25 | $7700.00 | Window Closed / Lapsed |