Adaptive data compression system with systolic string matching logic
US5532693A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jun 13, 1994 |
| Grant date | Jul 2, 1996 |
| Priority date | — |
| Expiry date | Jun 13, 2014 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M7/3086
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
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 l…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.