US5532693A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive data compression system with systolic string matching logic
Assignee: Comtech Telecommunications Corp
•
Filing: 1994-06-13
•
Granted: 1996-07-02
•
Expires: 2014-06-13
Abstract
Abstract An adaptive lossless data compression system with systolic string matching logic performs compression and decompression at the maximum rate of one symbol per clock cycle. The adaptive data compression system uses an improvement of the LZ1 algorithm. A content addressable memory (CAM) is used to store the last n input symbols. The CAM is stationary, stored data is not shifted throughout the CAM, but rather the CAM is used as a circular queue controlled by a Write Address Pointer Counter (WREN). During a compression operation, a new input symbol may be written to the CAM on each clock cycle, while simultaneously the rest of the CAM is searched for the input symbol. Associated with each word of the CAM array is a String Match State Machine (SMSM) and, an address logic module (ALM). These modules detect the occurrence of strings stored in the CAM array that match the current input string and report the address of the longest matching string nearest to the Write Address Pointer. The SMSM modules constitute a systolic logic array, where state information is shifted synchronously in the direction of the Write Address Pointer. The strings are represented by a string code which includes a length value, representing the length of the string, and a position value, representing the position in the CAM of the beginning of the string. During a decompression operation, the single symbols and string codes are input to the system. The symbols are stored in the CAM and the control logic outputs the decompressed data symbols using the stored data and the string codes.
Inventors
- 👤 Kel D. Winters
- 👤 Patrick A. Owsley
- 👤 Catherine A. French
- 👤 Robert M. Bode
- 👤 Peter S. Feeley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:52
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/02; G06T; G06T9/00; G06T9/005; H; H03; H03K; H03K3/00; H03K3/02; H03K3/027; H03K3/037; H03K3/353; H03K3/356; H03K3/356104; H03K3/356113; H03K3/356147; H03K3/356156; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
85 words
A data compression system comprising: means for sequentially receiving a plurality of data symbols from an input source; and b. means for simultaneously storing a present one of the symbols into one of a plurality of content addressable memory cells and comparing the present symbol to a plurality of previously received symbols to determine if the present symbol matches a previously received symbol wherein state information indicative of a match is transferred between the memory cells and symbols are not transferred between the memory cells.
Claim 2
Dependent Claim
85 words
A data compression system comprising: means for sequentially receiving a plurality of data symbols from an input source; and b. means for simultaneously storing a present one of the symbols into one of a plurality of content addressable memory cells and comparing the present symbol to a plurality of previously received symbols to determine if the present symbol matches a previously received symbol wherein state information indicative of a match is transferred between the memory cells and symbols are not transferred between the memory cells.
Claim 3
Dependent Claim
17 words
The data compression system as claimed in claim 1 wherein each byte represents eight bits of information.
Claim 4
Dependent Claim
21 words
The data compression system as claimed in claim 1 wherein the content addressable memory has means for writing, searching, and reading.
Claim 5
Dependent Claim
98 words
The data compression system as claimed in claim 1 further comprising: a. means for grouping symbols into uncoded bytes and strings, where each string comprises a longest matching string stored in the content addressable memory from the previously received signals; and b. means for generating a string code representative of each string or a previously written byte if no matching string occurs; wherein the string code comprises a length value representative of a number of symbols in the string and a position value representative of a position of the longest matching string stored in the content addressable memory.
Claim 6
Dependent Claim
53 words
The data compression system as claimed in claim 4 further comprising means for determining which longest matching string stored in the content addressable memory is nearest in location to a last byte stored in the content addressable memory, if there is more than one longest matching string stored in the content addressable memory.
Claim 7
Dependent Claim
36 words
The data compression system as claimed in claim 1 further comprising a plurality of string match state machines, each of the string match state machines cooperatively coupled to a stored symbol in the content addressable memory.
Claim 8
Dependent Claim
80 words
The data compression system as claimed in claim 6 wherein each of the string match state machines comprise three states: a. a first state signalling that the stored symbol does not match a current input string; b. a second state signalling that the stored symbol matches only a last symbol of the current input string; and c. a third state signalling that a string including the stored symbol matches at least a last two symbols of the current input string.
Claim 9
Dependent Claim
41 words
The data compression system as claimed in claim 7 wherein each of the string match state machines comprise a fourth state for initialization, wherein upon a reset signal all of the string match state machines are forced into the fourth state.
Claim 10
Dependent Claim
46 words
The data compression system as claimed in claim 1 wherein the means for simultaneously storing and comparing further comprises an array of a plurality of string match modules, each string match module comprising a CAM word, a string match state machine and an address logic module.
Claim 11
Dependent Claim
26 words
The data compression system as claimed in claim 9 wherein the array of a plurality of string match modules are arranged in a one-dimensional circular queue.
Claim 12
Dependent Claim
26 words
The data compression system as claimed in claim 9 wherein the array of a plurality of string match modules are arranged in both columns and rows.
Claim 13
Dependent Claim
17 words
The data compression system as claimed in claim 1 further comprising means for decompressing previously compressed data.
Claim 14
Dependent Claim
55 words
The data compression system as claimed in claim 1 wherein the means for sequentially receiving a plurality of data symbols receives the plurality of data symbols at a rate of one symbol per clock cycle and the means for simultaneously storing and comparing processes the data at a rate of one symbol per clock cycle.
Claim 15
Dependent Claim
184 words
A data compression system comprising: a. means for receiving data from an input source a byte at a time, each byte representing eight bits of information; b. means for simultaneously storing a present data byte into one of a plurality of content addressable memory cells and comparing the present data byte to a plurality of previously received data bytes to determine if the present data byte matches the previously received data bytes wherein state information indicative of a match is transferred between the memory cells and data bytes are not transferred between the memory cells; c. means for grouping data bytes into uncoded bytes and strings, where each string consists of a longest matching string stored in the content addressable memory from the previously received data; d. means for determining which longest matching string stored in the content addressable memory is nearest to a last byte received, if there is more than one longest matching string stored in the content addressable memory; and e. means for outputting a string code representative of each string or a previously written byte if no matching string occurs.
Claim 16
Dependent Claim
184 words
A data compression system comprising: a. means for receiving data from an input source a byte at a time, each byte representing eight bits of information; b. means for simultaneously storing a present data byte into one of a plurality of content addressable memory cells and comparing the present data byte to a plurality of previously received data bytes to determine if the present data byte matches the previously received data bytes wherein state information indicative of a match is transferred between the memory cells and data bytes are not transferred between the memory cells; c. means for grouping data bytes into uncoded bytes and strings, where each string consists of a longest matching string stored in the content addressable memory from the previously received data; d. means for determining which longest matching string stored in the content addressable memory is nearest to a last byte received, if there is more than one longest matching string stored in the content addressable memory; and e. means for outputting a string code representative of each string or a previously written byte if no matching string occurs.
Claim 17
Dependent Claim
21 words
The data compression system as claimed in claim 14 wherein the content addressable memory has means for writing, searching, and reading.
Claim 18
Dependent Claim
45 words
The data compression system as claimed in claim 14 wherein the string code comprises a length value representative of a number of bytes in the string and a position value representative of a position of the longest matching string stored in the content addressable memory.
Claim 19
Dependent Claim
36 words
The data compression system as claimed in claim 14 further comprising a plurality of string match state machines, each of the string match state machines cooperatively coupled to a stored byte in the content addressable memory.
Claim 20
Dependent Claim
86 words
The data compression system as claimed in claim 17 wherein each of the string match state machines comprises three states: a. a first state signalling that the stored byte of data does not match a current input string; b. a second state signalling that the stored byte of data matches only a last byte of the current input string; and c. a third state signalling that a string including the stored byte of data matches at least a last two characters of the current input string.
Claim 21
Dependent Claim
42 words
The data compression system as claimed in claim 18 wherein each of the string match state machines further comprise a fourth state for initialization, wherein upon a reset signal all of the string match state machines are forced into the fourth state.
Claim 22
Dependent Claim
46 words
The data compression system as claimed in claim 14 wherein the means for simultaneously storing and comparing further comprises an array of a plurality of string match modules, each string match module comprising a CAM word, a string match state machine and an address logic module.
Claim 23
Dependent Claim
26 words
The data compression system as claimed in claim 20 wherein the array of a plurality of string match modules are arranged in a one-dimensional circular queue.
Claim 24
Dependent Claim
26 words
The data compression system as claimed in claim 20 wherein the array of a plurality of string match modules are arranged in both columns and rows.
Claim 25
Dependent Claim
17 words
The data compression system as claimed in claim 14 further comprising means for decompressing previously compressed data.
Claim 26
Dependent Claim
29 words
The data compression system as claimed in claim 14 wherein the means for simultaneously storing and comparing processes the data at a rate of one byte per clock cycle.
Claim 27
Dependent Claim
225 words
A data compression system, for receiving data and compressing it at a rate of one byte per clock cycle, the compression system comprising: a. means for receiving data from an input source a byte at a time, each byte representing eight bits of information; b. an array of string match modules coupled to the means for receiving data comprising: i. a content addressable memory comprising a first plurality of CAM words, each CAM word capable of storing an input byte and simultaneously comparing subsequently received input bytes to stored data to determine if the subsequently received input bytes match stored data; and ii. a third plurality of string match state machines where state information is passed in a same direction as a direction followed by an active write pointer; c. means for grouping the received input bytes into uncoded bytes and strings, each string comprising a fourth plurality of input bytes; d. means for determining which longest matching string stored in the content addressable memory is nearest to a last byte received, if there is more than one longest matching string stored in the content addressable memory; and e. means for outputting a string code or a previously written byte if no matching string occurs, representative of each string, each string correspondingly matching a stored string of input bytes stored in the content addressable memory.
Claim 28
Dependent Claim
225 words
A data compression system, for receiving data and compressing it at a rate of one byte per clock cycle, the compression system comprising: a. means for receiving data from an input source a byte at a time, each byte representing eight bits of information; b. an array of string match modules coupled to the means for receiving data comprising: i. a content addressable memory comprising a first plurality of CAM words, each CAM word capable of storing an input byte and simultaneously comparing subsequently received input bytes to stored data to determine if the subsequently received input bytes match stored data; and ii. a third plurality of string match state machines where state information is passed in a same direction as a direction followed by an active write pointer; c. means for grouping the received input bytes into uncoded bytes and strings, each string comprising a fourth plurality of input bytes; d. means for determining which longest matching string stored in the content addressable memory is nearest to a last byte received, if there is more than one longest matching string stored in the content addressable memory; and e. means for outputting a string code or a previously written byte if no matching string occurs, representative of each string, each string correspondingly matching a stored string of input bytes stored in the content addressable memory.
Claim 29
Dependent Claim
45 words
The data compression system as claimed in claim 25 wherein the string code comprises a length value representative of the number of characters in the string and a position value representative of the position of the longest matching string stored in the content addressable memory.
Claim 30
Dependent Claim
47 words
The data compression system as claimed in claim 26 further comprising means for determining which longest matching string stored in the content addressable memory is nearest to the last input byte received, if there is more than one longest matching string stored in the content addressable memory.
Claim 31
Dependent Claim
36 words
The data compression system as claimed in claim 25 further comprising a plurality of string match state machines, each of the string match state machines cooperatively coupled to a stored byte in the content addressable memory.
Claim 32
Dependent Claim
80 words
The data compression system as claimed in claim 28 wherein each of the string match state machines comprises three states: a. a first state signalling that the stored byte does not match a current input string; b. a second state signalling that the stored byte matches only a last byte of the current input string; and c. a third state signalling that a string including the stored byte matches at least a last two characters of the current input string.
Claim 33
Dependent Claim
41 words
The data compression system as claimed in claim 29 wherein each of the string match state machines comprise a fourth state for initialization, wherein upon a reset signal all of the string match state machines are forced into the fourth state.
Claim 34
Dependent Claim
39 words
The data compression system as claimed in claim 30 wherein the means for receiving data receives a byte of data every clock cycle and the content addressable memory can store and compare a byte of data every clock cycle.
References Cited (Backward Citations)
US4021782A
Cited
US4056809A
Cited
US4558302A
Cited
US4558302B1
Cited
US5003307A
Cited
US5016009A
Cited
US5373290A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-02 | 2000-01-01 | 2000-07-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-02 | 2004-01-01 | 2004-07-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-02 | 2008-01-01 | 2008-07-02 | $7700.00 | Window Closed / Lapsed |