×

Method and apparatus for the compression and decompression of data using Lempel-Ziv based techniques

  • US 5,179,378 A
  • Filed: 07/30/1991
  • Issued: 01/12/1993
  • Est. Priority Date: 07/30/1991
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for parsing and coding a string of a variable number of uncoded data symbols to provide a fixed length codeword, comprising the steps of:

  • providing a symbol storage device having predetermined storage locations, said storage locations arranged into a first half and a second half,initializing the storage locations in the first half of said symbol storage device with predetermined data symbols,inserting an uncoded string of data symbols into the storage locations in the second half of said symbol storage device,comparing the data symbols in the storage locations in the second half of said symbol storage device with the predetermined symbols in the storage locations in the first half of said storage device using a plurality of processors, said processors being connected in a systolic array, and each processor in said systolic array of processors comparing selected pairs of data symbols and selectively passing the data symbols to an adjacent processor,providing fixed length outputs from the systolic array of processors indicating;

    i) the length of the longest string of data symbols in the first half of the storage device that matches a string of data symbols from the second half of said symbol storage, and ii) the storage location in the first half of said symbol storage device of the starting point for said string,shifting the data symbols of said longest matched string and the data symbol immediately following said longest string from the storage locations in the second half of said symbol storage device into the storage locations in the first half of said symbol storage device in a predetermined sequence and shifting subsequent uncoded data symbols into the storage locations in the second half of said symbol storage device,providing a fixed length output from said symbol storage device indicating the data symbol that immediately follows said longest string,arranging the fixed length outputs from the systolic array of processors and the fixed length output from said symbol storage device in a codeword storage device to provide a codeword having a fixed length.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×