Advanced Hardware Architectures, Inc.

Kel D Winters

Robert Lyle Wall

Patrick A Owsley

Catherine A French

Peter S Feeley

Robert M Bode

A single clock cycle adaptive data compressor/decompressor with a string reversal mechanism is described which can perform data compression and decompression at the rate of one uncompressed symbol per clock cycle. The LZW data compression algorithm has been improved for use in this data compressor. The compressor builds a string table as the data is received. Each string within the table is made up of the address within the table of the longest previously seen matching string and the one character that makes this string different. This data compressor/decompressor utilizes a content addressable memory to store the string table. This content addressable memory allows the compressor to store the current symbol string in a table while that same string table is simultaneously searched for the current string. During decompression the characters within a symbol string are output in reverse of the order in which they were input. In order for the data to be restored to its original format the characters within a string must be reversed before they are output. Two dual-ported random-access memories are used as circular queues to perform this string reversal. These dual-ported random-access memories have the capability to output the characters within a string from the string reversal mechanism in the order that they were input. The first dual-ported random access memory is used to store the strings of symbols to be reversed and the second dual-ported random access memory is used to store the addresses of the first and last symbol of each string that is stored in the first dual-ported random-access memory.

Single clock cycle data compressor/decompressor with a string reversal

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.

Adaptive data compression system with systolic string matching logic

A content addressable memory cell includes six transistors connected together to perform memory read, memory write, and matching operations. This cell has the ability to perform typical memory write and memory read operations as well as the capability of signalling whether or not its stored data matches data that is being searched for. A cross-coupling scheme is used in the memory cell so that a high potential will always be stored on the gate of a transistor whose source is at ground. This cross-coupling scheme increases the amount of charge stored on the storage transistor and decreases the required frequency of refresh operations. In addition to the transistors configured to store data, an additional transistor configured as a diode is used as a rapid discharge path to maximize the efficiency of the cell during a read operation. During a match operation another transistor is utilized to discharge the Match line quickly in the event the stored data does not match the data that is being searched for.

Growing community of inventors

Moscow, ID, United States of America

Kel D Winters