Efficient ziv-lempel lzi data compression system using variable code

Abstract

A system for compressing digital data at one byte-per-cycle throughput by removing redundancy before storage or transmission. The system includes an improved Ziv-Lempel LZ1 process that uses a history buffer to save the most recent source string symbols for use in encoding the source symbols as 'match-length' and 'match-offset' tokens. The match-length code symbols are selected from two groups of buckets that are assigned variable-length prefixes for the shorter, more probable match-lengths and a fixed-length prefix code for the longer, less probable match-lengths. This exploits a transition from Laplacian match-length probability distribution to Uniform match-length probability distribution for longer match-lengths. The offset code field length is reduced during start-up to improve start-up compression efficiency during filling of the history buffer. The match-length code book is limited to a maximum value T<256 to limit latency and simplify the process. Several unused match-length code slots are reassigned to 'control codes' that can be inserted into the compressed data stream on the fly without slowing or interrupting the encoding process. Compressed data is verified on the fly by simultaneous decode and CRC comparison with source data, permitting insertion of error-correction 'control codes' as necessary without interruption or slowing of the compression flow.