US5612693A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Sliding window data compression using a toroidal bit shift register
Assignee: International Business Machines Corp
•
Filing: 1994-12-14
•
Granted: 1997-03-18
•
Expires: 2014-12-14
Abstract
Abstract Systems and methods for compressing data. Lempel-Ziv data compression is applied in the context of an exhaustive sliding window implementation using a large character history bit pattern memory. Shifted updating of the character history bit pattern memory is accomplished through a pointer system. Linear patterns of bits, derived by COPY function from the character history bit pattern memory or by bit wise AND logic combination of selected bit patterns, are circularly shifted in synchronism with new data characters using a toroidal bit shift register. The relatively long bit strings subject to shifting are converted to a matrix format, shifted with fewer affected bits and returned to a linear format. The systems and methods materially improve the speed of exhaustive sliding window data compression as accomplished by general purpose processors.
Inventors
- 👤 David J. Craft
- 👤 Oscar C. Strohacker
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 19:13
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
101 words
A data compression system, comprising: means for receiving successive data characters; means for marking a memory to indicate the receipt of a first data character and its order of occurrence; means for marking the memory to indicate the receipt of a second data character and its order of occurrence; means for detecting a string match between the order of successive new data characters and the first and second data characters by copying, shifting with a toroidal bit shift register, and comparing marked positions from the memory; and means for encoding new data responsive to the means for detecting a string match.
Claim 2
Dependent Claim
101 words
A data compression system, comprising: means for receiving successive data characters; means for marking a memory to indicate the receipt of a first data character and its order of occurrence; means for marking the memory to indicate the receipt of a second data character and its order of occurrence; means for detecting a string match between the order of successive new data characters and the first and second data characters by copying, shifting with a toroidal bit shift register, and comparing marked positions from the memory; and means for encoding new data responsive to the means for detecting a string match.
Claim 3
Dependent Claim
25 words
The apparatus recited in claim 1, wherein the means for marking a memory comprises a pointer which increments a memory address for successive data characters.
Claim 4
Dependent Claim
21 words
The apparatus recited in claim 2, wherein the means for marking uses a memory address specified by a data character comparator.
Claim 5
Dependent Claim
29 words
The apparatus recited in claim 3, wherein the combination of memory addresses specified by the pointer and by the data character comparator uniquely identify a position in the memory.
Claim 6
Dependent Claim
29 words
The apparatus recited in claim 3, wherein the combination of memory addresses specified by the pointer and by the data character comparator uniquely identify a position in the memory.
Claim 7
Dependent Claim
17 words
The apparatus recited in claim 1, further comprising a means for decoding encoded string matched data characters.
Claim 8
Dependent Claim
121 words
A data processing system, comprising: a memory; a processor connected to the memory; means for receiving successive data characters by the processor; means for the processor to mark the memory to indicate the receipt of a first data character and its order of occurrence; means for the processor to mark the memory to indicate the receipt of a second data character and its order of occurrence; means for detecting a string match between the order of successive new data characters and the first and second data characters by copying, shifting with a toroidal bit shift register, and comparing marked positions from the memory; and means for the processor to encode new data responsive to the means for detecting a string match.
Claim 9
Dependent Claim
121 words
A data processing system, comprising: a memory; a processor connected to the memory; means for receiving successive data characters by the processor; means for the processor to mark the memory to indicate the receipt of a first data character and its order of occurrence; means for the processor to mark the memory to indicate the receipt of a second data character and its order of occurrence; means for detecting a string match between the order of successive new data characters and the first and second data characters by copying, shifting with a toroidal bit shift register, and comparing marked positions from the memory; and means for the processor to encode new data responsive to the means for detecting a string match.
Claim 10
Dependent Claim
28 words
The apparatus recited in claim 7, wherein the means for the processor to mark the memory comprises a pointer which increments a memory address for successive data characters.
Claim 11
Dependent Claim
27 words
The apparatus recited in claim 8, wherein the means for the processor to mark the memory system uses a memory address specified by a data character comparator.
Claim 12
Dependent Claim
29 words
The apparatus recited in claim 7, wherein the combination of memory addresses specified by the pointer and by the data character comparator uniquely identify a position in the memory.
Claim 13
Independent Claim
95 words
A method of compressing data, comprising the steps of: receiving successive data characters; marking a memory to indicate the receipt of a first data character and its order of occurrence; marking the memory to indicate the receipt of a second data character and its order of occurrence; detecting a string match between the order of successive new data characters and the first and second data characters by copying, shifting with a toroidal bit shift register, and comparing marked positions from the memory; and encoding new data responsive to the means for detecting a string match.
Claim 14
Independent Claim
95 words
A method of compressing data, comprising the steps of: receiving successive data characters; marking a memory to indicate the receipt of a first data character and its order of occurrence; marking the memory to indicate the receipt of a second data character and its order of occurrence; detecting a string match between the order of successive new data characters and the first and second data characters by copying, shifting with a toroidal bit shift register, and comparing marked positions from the memory; and encoding new data responsive to the means for detecting a string match.
Claim 15
Dependent Claim
27 words
The method recited in claim 11, wherein the step of marking a memory is performed with a pointer which increments a memory address for successive data characters.
Claim 16
Dependent Claim
23 words
The method recited in claim 12, wherein the step of marking the memory uses a memory address specified by a data character comparator.
Claim 17
Dependent Claim
29 words
The method recited in claim 11, wherein the combination of memory addresses specified by the pointer and by the data character comparator uniquely identify a position in the memory.
References Cited (Backward Citations)
US5369605A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-17 | 2000-09-16 | 2001-03-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-17 | 2004-09-16 | 2005-03-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-17 | 2008-09-16 | 2009-03-18 | $7700.00 | Window Closed / Lapsed |