Adaptive data compression system with systolic string matching logic

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.

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.