US5379036A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for data compression
Assignee: Individual
•
Filing: 1992-04-01
•
Granted: 1995-01-03
•
Expires: 2012-04-01
Abstract
Abstract A data compression system utilizes multiple encoding/decoding processing units arranged in a massively parallel systolic pipe array for compressing a stream of input characters received at an input end of the pipe. The systolic pipe executes data compression by textual substitution, converting the uncompressed stream of input characters into a compressed set of pointers representative of the input. The processors store a dictionary of strings of previously-read input characters in association with corresponding pointers. The processors match portions of the input stream with the stored strings, and transmit the corresponding pointers in place of the strings. In order to execute decoding or decompression of the stream of pointers, the processors maintain a dictionary identical to that generated during encoding. The processors match received pointers with stored strings of data and transmit the corresponding data strings in place of the pointers. Novel methods for matching, update, and deletion in a massively parallel systolic pipe structure enhance processing speed.
Inventors
- 👤 James A. Storer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 15:33
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
415 words
A real-time digital processing apparatus for dynamically compressing an input data stream of characters into a compressed stream of digital codes, and for dynamically decompressing a compressed stream of digital codes into an uncompressed stream of characters, the apparatus comprising: a plurality of digital data storage and processing cells connected in a systolic pipe array, each digital data storage and processing cell including digital data storage means for storing digital data, the digital data storage means in each digital data storage and processing cell being in communication with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, the systolic pipe including: input means for receiving the input data stream of characters at an input end of the systolic pipe array, dictionary means for storing an indexed dictionary of strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparator means for comparing successive portions of the input stream with the strings stored in the digital data storage elements, to detect a portion of the input stream that matches a corresponding one of the stored strings, the comparator means including match means for detecting the longest possible portion of the input stream that will match a corresponding one of the stored strings, the match means including means for constructing successively longer matched portions of the input stream for pairs of smaller, previously matched portions of the input stream, means for transmitting, in place of the detected portion of the input stream that matches a corresponding stored string, the pointer representative of the corresponding stored string, thereby to convert the input stream in a compressed set of pointers representative of the input stream, decompression means for receiving a stream of pointers representative of strings of characters, the decompression means comprising means for comparing each received pointer with strings stored in the dictionary to locate a string corresponding to each received pointer, and means for transmitting, in place of each received pointer corresponding to a stored string, the stored string corresponding to the pointer, thereby to decompress the stream of pointers into an uncompressed stream of characters, means for ensuring that the encoder and decoder have a consistent method for leaning pairs of pointers by employing a modified learning rule and/or retiming of the input-output stream.
Claim 2
Dependent Claim
415 words
A real-time digital processing apparatus for dynamically compressing an input data stream of characters into a compressed stream of digital codes, and for dynamically decompressing a compressed stream of digital codes into an uncompressed stream of characters, the apparatus comprising: a plurality of digital data storage and processing cells connected in a systolic pipe array, each digital data storage and processing cell including digital data storage means for storing digital data, the digital data storage means in each digital data storage and processing cell being in communication with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, the systolic pipe including: input means for receiving the input data stream of characters at an input end of the systolic pipe array, dictionary means for storing an indexed dictionary of strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparator means for comparing successive portions of the input stream with the strings stored in the digital data storage elements, to detect a portion of the input stream that matches a corresponding one of the stored strings, the comparator means including match means for detecting the longest possible portion of the input stream that will match a corresponding one of the stored strings, the match means including means for constructing successively longer matched portions of the input stream for pairs of smaller, previously matched portions of the input stream, means for transmitting, in place of the detected portion of the input stream that matches a corresponding stored string, the pointer representative of the corresponding stored string, thereby to convert the input stream in a compressed set of pointers representative of the input stream, decompression means for receiving a stream of pointers representative of strings of characters, the decompression means comprising means for comparing each received pointer with strings stored in the dictionary to locate a string corresponding to each received pointer, and means for transmitting, in place of each received pointer corresponding to a stored string, the stored string corresponding to the pointer, thereby to decompress the stream of pointers into an uncompressed stream of characters, means for ensuring that the encoder and decoder have a consistent method for leaning pairs of pointers by employing a modified learning rule and/or retiming of the input-output stream.
Claim 3
Dependent Claim
24 words
Apparatus according to claim 1, wherein the digital data storage means comprises first and second register means for storing portions of the input stream.
Claim 4
Dependent Claim
65 words
Apparatus according to claim 1, wherein the decompression means comprises means for generating a STOP bit upon detection of a match between a received pointer and a string stored in the dictionary means, and means for transmitting the STOP bit to the preceding digital storage and processing cell in the systolic pipeline array, thereby to control the volume of data generated by the decompression means.
Claim 5
Dependent Claim
59 words
Apparatus according to claim 3, wherein the decompression means comprises means, responsive to detection of the STOP bit at the input end of the systolic pipeline array, for generating an XON/XOFF signal representative of a request to temporarily suspend transmission of pointers by an external data source, and means for transmitting to the external data source the XON/XOFF signal.
Claim 6
Dependent Claim
57 words
Apparatus according to claim 1, further comprising FLUSH means for generating a FLUSH signal representative of a request to expel data stored in the systolic pipeline array through successive cells of the systolic pipeline array, thereby to enable any of reception of a new data stream, generation of a new dictionary, or switch from compression to decompression.
Claim 7
Dependent Claim
54 words
Apparatus according to claim 5, further comprising compression monitoring means, in communication with the FLUSH means, for dynamically monitoring the compression ratio provided by the systolic pipeline array, and for generating the FLUSH signal when the compression ratio falls below a selected threshold, thereby to enable generation of a new dictionary and unique decorability.
Claim 8
Dependent Claim
18 words
Apparatus according to claim 6 wherein the FLUSH signal is generated without suspending reception of the input stream.
Claim 9
Dependent Claim
39 words
Apparatus according to claim 1, further comprising means for generating a leader bit and for propagating the leader bit through successive cells of the systolic pipeline array, thereby to designate a leader processor that is enabled to execute matching.
Claim 10
Dependent Claim
17 words
Apparatus according to claim 8, further comprising update means for updating the dictionary means with matched strings.
Claim 11
Dependent Claim
26 words
Apparatus according to claim 9, wherein the update means includes means for generating a mark bit associated with a pointer matched by a designated leader processor.
Claim 12
Dependent Claim
27 words
Apparatus according to claim 1, further comprising deletion means for deleting selected strings from the dictionary means when utilization of the dictionary means exceeds a selected threshold.
Claim 13
Dependent Claim
66 words
Apparatus according to claim 1, wherein the dictionary means comprises first and second dictionary elements, and the systolic pipe array means comprises SWAP controller means, in communication with the first and second dictionary elements, for detecting utilization levels in the first and second dictionary elements, and for causing a dictionary to be generated in the second dictionary element when the first dictionary element fills to capacity.
Claim 14
Dependent Claim
14 words
Apparatus according to claim 1, further comprising means for providing an implicit leader bit.
Claim 15
Dependent Claim
31 words
Apparatus according to claim 1, further comprising means for flexible processor ordering and usage that allows any ordering or processors and any combination of indices to be reserved for other uses.
Claim 16
Dependent Claim
11 words
Apparatus according to claim 1, further comprising means for static indexing.
Claim 17
Dependent Claim
12 words
Apparatus according to claim 1, further comprising means for providing dummy processors.
Claim 18
Dependent Claim
33 words
Apparatus according to claim 1, further comprising means providing for fault-tolerant capability that circumvents cells that are determined to be defective by compression of test data at start-up with increasing numbers of processors.
Claim 19
Dependent Claim
12 words
Apparatus according to claim 1, further comprising means for providing pad buffering.
Claim 20
Dependent Claim
14 words
Apparatus according to claim 1, further comprising means for providing multiple entries per cell.
Claim 21
Dependent Claim
20 words
Apparatus according to claim 1, further comprising means for employing other learning strategies that are determined by two other entries.
Claim 22
Dependent Claim
19 words
Apparatus according to claim 1, further comprising means performing for lossy compression by storing vector quantization (VQ) codebook entries.
Claim 23
Dependent Claim
334 words
A real time method for dynamically compressing an input data stream of characters into a compressed stream of digital pointers, the method comprising the steps of electrically connecting a plurality of digital data storage and processing cells into a systolic pipe array such that a digital data storage element in each digital data storage and processing cell can communicate with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, receiving the input data stream of characters at an input end of the systolic pipe array, storing, in the connected digital data storage elements of the digital data storage and processing cells of the systolic pipeline array, an indexed dictionary or strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparing, in digital processing elements in the connected digital data storage and processing cells, successive portions of the input stream with the strings stored in the digital data storage elements, to detect a portion of the input stream that matches a corresponding one of the storm strings, and transmitting, in place of the detected portion of the input stream that matches a corresponding stored string, the pointer representative of the corresponding stored string, thereby converting the input stream into a compressed set of pointers representative of the input stream, wherein the comparing step includes the step of detecting a portion that will match a corresponding one of the stored strings, the step of detecting a portion including the step of constructing successively longer matched portions of the input stream from pairs of smaller, previously matched portions of the input stream, said method ensuring that the encoder learns pairs of pointers in a way such that consistent decoding is possible by employing a modified learning rule and or retiming of the input/output stream.
Claim 24
Dependent Claim
334 words
A real time method for dynamically compressing an input data stream of characters into a compressed stream of digital pointers, the method comprising the steps of electrically connecting a plurality of digital data storage and processing cells into a systolic pipe array such that a digital data storage element in each digital data storage and processing cell can communicate with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, receiving the input data stream of characters at an input end of the systolic pipe array, storing, in the connected digital data storage elements of the digital data storage and processing cells of the systolic pipeline array, an indexed dictionary or strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparing, in digital processing elements in the connected digital data storage and processing cells, successive portions of the input stream with the strings stored in the digital data storage elements, to detect a portion of the input stream that matches a corresponding one of the storm strings, and transmitting, in place of the detected portion of the input stream that matches a corresponding stored string, the pointer representative of the corresponding stored string, thereby converting the input stream into a compressed set of pointers representative of the input stream, wherein the comparing step includes the step of detecting a portion that will match a corresponding one of the stored strings, the step of detecting a portion including the step of constructing successively longer matched portions of the input stream from pairs of smaller, previously matched portions of the input stream, said method ensuring that the encoder learns pairs of pointers in a way such that consistent decoding is possible by employing a modified learning rule and or retiming of the input/output stream.
Claim 25
Dependent Claim
250 words
A real time method for dynamically decompressing a compressed stream of digital pointers into an uncompressed stream of characters, the method comprising the steps of electrically connecting a plurality of digital data storage and processing cells into a systolic pipe array such that a digital data storage element in each digital data storage and processing cell can communicate with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, receiving an input stream of pointers representative of strings of characters at an input end of the systolic pipe array, storing, in the connected digital data storage elements of the digital data storage and processing cells of the systolic pipeline array, an indexed dictionary or strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparing each received pointer with the strings stored in the dictionary to locate a string corresponding to each received pointer, and transmitting, in place of each pointer corresponding to a stored string, the stored string corresponding to the received pointer, thereby to decompress the stream of pointers into an uncompressed stream of characters said method ensuring that the decoder learns pairs of pointers in a way that is consistent with an encoding by employing a modified learning rule and or retiming of the input/output stream.
Claim 26
Dependent Claim
250 words
A real time method for dynamically decompressing a compressed stream of digital pointers into an uncompressed stream of characters, the method comprising the steps of electrically connecting a plurality of digital data storage and processing cells into a systolic pipe array such that a digital data storage element in each digital data storage and processing cell can communicate with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, receiving an input stream of pointers representative of strings of characters at an input end of the systolic pipe array, storing, in the connected digital data storage elements of the digital data storage and processing cells of the systolic pipeline array, an indexed dictionary or strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparing each received pointer with the strings stored in the dictionary to locate a string corresponding to each received pointer, and transmitting, in place of each pointer corresponding to a stored string, the stored string corresponding to the received pointer, thereby to decompress the stream of pointers into an uncompressed stream of characters said method ensuring that the decoder learns pairs of pointers in a way that is consistent with an encoding by employing a modified learning rule and or retiming of the input/output stream.
References Cited (Backward Citations)
US4814746A
Cited
US4558302A
Cited
US4558302B1
Cited
US4876541A
Cited
US4881075A
Cited
US4847619A
Cited
US5175543A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-01-02 | 1998-07-04 | 1999-01-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-01-02 | 2002-07-04 | 2003-01-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-01-02 | 2006-07-04 | 2007-01-03 | $7700.00 | Window Closed / Lapsed |