Patent US5384567A successfully refreshed from Google Patents.
US5384567A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Combination parallel/serial execution of sequential algorithm for data compression/decompression
Assignee: International Business Machines Corp
•
Filing: 1993-07-08
•
Granted: 1995-01-24
•
Expires: 2013-07-08
Abstract
Abstract An apparatus and method for executing a sequential data compression algorithm that is especially suitable for use where data compression is required in a device (as distinguished from host) controller. A history buffer compresses an array of i identical horizontal slice units. Each slice unit stores j symbols to define j separate blocks in which the symbols in each slice unit are separated by exactly i symbols. Symbols in a string of i incoming symbols are compared by i comparators in parallel with symbols previously stored in the slice units to identify matching sequences of symbols. A control unit controls execution of the sequential algorithm to condition the comparators to scan symbols in parallel but in each of the blocks sequentially and cause matching sequences and nonmatching sequences of symbols to be stored in the array. The parameters i and j are selected to limit the number of comparators required to achieve a desired degree of efficiency in executing the algorithm based upon a trade-off of algorithm execution speed versus hardware cost. A priority encoder calculates from signals output by the slice units each j,i address in which a matching sequence is identified, but it outputs the address of only one (such as the smallest) of these addresses.
Inventors
- 👤 Martin A. Hassner
- 👤 Ehud D. Karnin
- 👤 Uwe Schwiegelshohn
- 👤 Tetsuya Tamura
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-10 01:37
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3002; H03M7/3084; H03M7/3086; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
129 words
An apparatus for executing a sequential data compression algorithm, comprising: an array of i identical horizontal slice units, each of which stores j symbols to define j separate blocks in which the symbols in each slice unit are separated by exactly i symbols, i and j being positive integers larger than 1; i comparators to compare symbols in a string of i incoming symbols in parallel with i noncontiguous symbols, one from each block, previously stored in said slice units to identify matching sequences of symbols; and means, including controller means, for (i) executing the sequential algorithm to condition the comparators to scan symbols in parallel but in each of said blocks sequentially, and (ii) cause matching sequences and nonmatching sequences of symbols to be stored in said array.
Claim 2
Independent Claim
129 words
An apparatus for executing a sequential data compression algorithm, comprising: an array of i identical horizontal slice units, each of which stores j symbols to define j separate blocks in which the symbols in each slice unit are separated by exactly i symbols, i and j being positive integers larger than 1; i comparators to compare symbols in a string of i incoming symbols in parallel with i noncontiguous symbols, one from each block, previously stored in said slice units to identify matching sequences of symbols; and means, including controller means, for (i) executing the sequential algorithm to condition the comparators to scan symbols in parallel but in each of said blocks sequentially, and (ii) cause matching sequences and nonmatching sequences of symbols to be stored in said array.
Claim 3
Dependent Claim
52 words
The apparatus of claim 1, wherein the location address of each stored symbol is uniquely specified by an indexing rule, such that k equals m times i, where k varies from 1 to j and m varies from 1 to N/i, and N, the size of the array, is i times j.
Claim 4
Independent Claim
167 words
An apparatus for executing a sequential data compression algorithm, comprising: an array of i identical horizontal slice units, each of which stores j symbols to define j separate blocks in which the symbols in each slice unit are separated by exactly i symbols, i and j being positive integers larger than 1; i comparators to compare symbols in a string of i incoming symbols in parallel with symbols previously stored in said slice units to identify matching sequences of symbols; each slice unit providing an output signal which is of one state if a matching sequence is identified; a priority encoder for calculating from said output signals each j,i address in which a matching sequence is identified, but outputting only one of said addresses; and means, including controller means, for (i) executing the sequential algorithm to condition the comparators to scan symbols in parallel but in each of said blocks sequentially, and (11) cause matching sequences and nonmatching sequences of symbols to be stored in said array.
Claim 5
Independent Claim
167 words
An apparatus for executing a sequential data compression algorithm, comprising: an array of i identical horizontal slice units, each of which stores j symbols to define j separate blocks in which the symbols in each slice unit are separated by exactly i symbols, i and j being positive integers larger than 1; i comparators to compare symbols in a string of i incoming symbols in parallel with symbols previously stored in said slice units to identify matching sequences of symbols; each slice unit providing an output signal which is of one state if a matching sequence is identified; a priority encoder for calculating from said output signals each j,i address in which a matching sequence is identified, but outputting only one of said addresses; and means, including controller means, for (i) executing the sequential algorithm to condition the comparators to scan symbols in parallel but in each of said blocks sequentially, and (11) cause matching sequences and nonmatching sequences of symbols to be stored in said array.
Claim 6
Dependent Claim
37 words
The apparatus of claim 3, wherein each output signal when in said one state identifies the thus far last byte of a previously stored sequence that matches the most recent sequence in the string of incoming symbols.
Claim 7
Dependent Claim
21 words
The apparatus of claim 3, including: means for inhibiting application of the algorithm to any blocks which do not contain symbols.
Claim 8
Dependent Claim
53 words
The apparatus of claim 3, including: a single latch in each respective one of the slice units, which latches are serially connected and in combination constitute a shift register; and means for resetting said latches and hence said shift register each time before symbols are stored in a different location in said array.
Claim 9
Independent Claim
129 words
A method of executing a sequential data compression algorithm, comprising the steps of: providing an array of i identical horizontal slice units, each for storing j symbols to define j separate blocks in which the symbols in each slice unit are separated by exactly i symbols, i and j being positive integers larger than 1; using i comparators, comparing symbols in a string of i incoming symbols in parallel with symbols previously stored in said slice units to identify matching sequences of symbols; executing the sequential algorithm by (i) scanning symbols in parallel but in each of said blocks sequentially, and (ii) storing matching sequences and nonmatching sequences of symbols in an input/output device; and inhibiting application of the algorithm to any blocks which do not contain valid symbols.
Claim 10
Independent Claim
129 words
A method of executing a sequential data compression algorithm, comprising the steps of: providing an array of i identical horizontal slice units, each for storing j symbols to define j separate blocks in which the symbols in each slice unit are separated by exactly i symbols, i and j being positive integers larger than 1; using i comparators, comparing symbols in a string of i incoming symbols in parallel with symbols previously stored in said slice units to identify matching sequences of symbols; executing the sequential algorithm by (i) scanning symbols in parallel but in each of said blocks sequentially, and (ii) storing matching sequences and nonmatching sequences of symbols in an input/output device; and inhibiting application of the algorithm to any blocks which do not contain valid symbols.
Claim 11
Dependent Claim
32 words
The method of claim 7, including the steps of: calculating each j,i address in which a matching sequence is identified; and outputting the address of only the smallest one of said addresses.
Claim 12
Dependent Claim
32 words
The method of claim 7, including the step of: identifying the thus far last byte of a previously stored sequence that matches the most recent sequence in the string of incoming symbols.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-01-23 | 1998-07-25 | 1999-01-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-01-23 | 2002-07-25 | 2003-01-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-01-23 | 2006-07-25 | 2007-01-24 | $7700.00 | Window Closed / Lapsed |