Lossless data compression circuit and method

• US 5,150,430 A
• Filed: 03/15/1991
• Issued: 09/22/1992
• Est. Priority Date: 03/15/1991
• Status: Expired due to Fees

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Chu, Ke-Chiang
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): KLOCINSKI, STEVEN
• Application Number:
  US07/670,281
• Time in Patent Office: 557 Days
• Field of Search: 382/56, 341/51, 341/67, 341/95, 341/106, 358/261.1, 358/261.4, 358/261.2
• US Class Current: 382/246
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A lossless data compression circuit compares a new data string with a set of comparison data, and produces a sequence of codewords representing a sequence of successive, non-overlapping substrings of the new data string. A shift register stores and shifts the comparison data until all of the characters in the comparison data have been compared with the new data string. A composite reproduction length circuit finds the maximum length string within the set of comparison characters matching substrings of characters in the new data string beginning at each position in the new data string. The composite reproduction length circuit produces a multiplicity of data pairs, one for each position of the new data string. Each data pair comprises a maximum length value, corresponding to the maximum length matching comparison string found for the new data substring starting at the corresponding position, and a pointer value denoting where the maximum length matching comparison string is located in the comparison data. A codeword generator then generates a sequence of codewords representing the new data string, each codeword including one of these data pairs and representing a substring of the new data string. By using N such data compression units in parallel, with each storing an identical new data string, and each unit'"'"'s shift register storing and shifting a different subset of a specified comparison string, processing time for generating codewords is reduced by a factor of approximately (N-1)/N.

Claims

1. A lossless data compression circuit, comprising:

new data register means for storing a new data string to be compressed, said new data string containing an ordered sequence of characters stored at corresponding positions in said new data register means;

shift register means for storing and shifting a set of comparison characters to be compared with said characters stored in said new data register means;

said shift register shifting positions of said comparison characters until all of said comparison characters have been shifted through said shift register means;

comparison means, coupled to said new data register means and said shift register means, for simultaneously comparing all of said characters stored in said new data register means with corresponding ones of said comparison characters stored in said shift register means each time that said comparison characters are shifted in said shift register means;

composite reproduction length means, coupled to said comparison means, for determining simultaneously, for all positions in at least a contiguous subset of positions in said new data register means, maximum length strings within said set of comparison characters matching substrings of said characters stored in said new data register means beginning at corresponding positions in said new data register means, said composite reproduction length means producing in parallel a multiplicity of data pairs, each data pair corresponding to a different position in said new data register means, each data pair comprising a length value, corresponding to said maximum length string found for a substring beginning at a corresponding position in said new data register means, and a pointer value denoting where said maximum length string is located in said set of comparison characters; and

codeword generating means, coupled to said composite reproduction length means, for generating a sequence of codewords representing said new data string to be compressed, each said codeword including data corresponding to one of said data pairs and representing a substring of said new data string.

2. A lossless data compression circuit as in claim 1, said composite reproduction length means including:

reproduction length register means for storing a multiplicity of said length values, each said length value corresponding to a different position in said new data register means;

pointer means for storing a multiplicity of said pointer values, each said pointer value corresponding to one of said length values in said reproduction length register means;

counter means for generating a current pointer value denoting which comparison characters are currently stored in said shift register means;

tallying means for simultaneously generating tally values for all positions in said at least a contiguous subset of positions in said new data register means, each said tally value representing how many consecutive comparison characters stored in said shift register means, up to a predefined maximum value, match said characters stored in said new data register means beginning at a corresponding position in said new data register means; and

decoder means for simultaneously comparing all of said tally values with corresponding ones of said length values stored in said reproduction length register means, and when any of said tally values exceeds said corresponding stored length value, replacing said stored corresponding length value with said tally value and replacing said corresponding pointer value stored in said pointer means with said current pointer value generated by said counter means.

3. A lossless data compression circuit as in claim 1,

said sequence of codewords representing a sequence of successive, non-overlapping substrings of said new data string, said codeword generating means including means for repeatedly selecting a position in said new data register means following a substring represented by a previous codeword generated by said codeword generating means and generating a codeword corresponding to the data pair for said selected position in said new data register means.

4. A lossless data compression circuit, comprising:

(1) a plurality of lossless data compression units, each lossless data compression unit including;

(a) new data register means for storing a new data string to be compressed, said new data string containing an ordered sequence of characters stored at corresponding positions in said new data register;

(b) shift register means for storing and shifting a set of comparison characters to be compared with said characters stored in said new data register means;

said shift register shifting positions of said comparison characters until all of said comparison characters have been shifted through said shift register means;

(c) comparison means, coupled to said new data register means and said shift register means, for comparing said characters stored in said new data register means with corresponding ones of said comparison characters stored in said shift register means each time that said comparison characters are shifted in said shift register; and

(d) reproduction length means, coupled to said comparison means, for determining a maximum length string within said set of comparison characters matching said characters stored in said new data register means, and for generating a data pair comprising a length value, corresponding to said maximum length string, and a pointer value denoting where said maximum length string is located in said set of comparison characters; and

(2) codeword generating means, coupled to said reproduction length means in all of said plurality of lossless data compression units, including means for determining which of said length values generated by said plurality of reproduction length means is largest, and for generating a codeword representing a portion of said new data string, said codeword including data corresponding to the one of said data pairs with said largest of said length values;

wherein each said new data register means stores an identical new data string, and each said shift register stores and shifts a different subset of a specified comparison string, whereby when N of said lossless data compression units are used, processing time for generating said codewords is reduced by a factor of approximately (N-1)/N.

5. A lossless data compression circuit as in claim 4,

each said reproduction length means in each of said plurality of lossless data compression units comprising a composite reproduction length means, coupled to said comparison means, for determining simultaneously, for all positions in at least a contiguous subset of the positions in said new data register means, maximum length strings within said set of comparison characters matching substrings of said characters stored in said new data register means beginning at corresponding positions in said new data register means, said composite reproduction length means producing in parallel a multiplicity of said data pairs, each said data pair corresponding to a different position in said new data register means;

and

said codeword generating means including means for generating a sequence of codewords representing said new data string to be compressed, said sequence of codewords representing a sequence of successive, non-overlapping substrings of said new data string, said codeword generating means including means for repeatedly selecting a position in said new data string following a substring represented by a previous codeword generated by said codeword generating means, determining a largest length value for the plurality of data pairs corresponding to said selected position in said new data string, and generating a codeword corresponding to the one of said plurality of data pairs with said largest length value.

6. A lossless data compression circuit as in claim 5, said composite reproduction length means in each lossless data compression unit including:

reproduction length register means for storing a multiplicity of said length values, each said length value corresponding to a different position in said new data register means;

pointer means for storing a multiplicity of said pointer values, each said pointer value corresponding to one of said length values in said reproduction length register means;

counter means for generating a current pointer value denoting which comparison characters are currently stored in said shift register means;

tallying means for simultaneously generating tally values for all positions in said at least a contiguous subset of the positions in said new data register means, each said tally value representing how many consecutive comparison characters stored in said shift register means, up to a predefined maximum value, match said characters stored in said new data register means beginning at a corresponding position in said new data register means; and

decoder means for simultaneously comparing all of said tally values with corresponding ones of said length values stored in said reproduction length register means, and when any of said tally values exceeds said corresponding stored length value, replacing said stored corresponding length value with said tally value and replacing said corresponding pointer value stored in said pointer means with said current pointer value generated by said counter means.

7. A lossless data compression method, the steps of the method comprising:

storing in a data register a new data string to be compressed, said new data string containing an ordered sequence of characters stored at corresponding positions in said data register;

storing in a shift register a set of comparison characters to be compared with said characters stored in said data register;

successively shifting positions of said comparison characters stored in said shift register until all of said comparison characters have been shifted through said shift register;

simultaneously comparing all of said characters stored in said data register with corresponding ones of said comparison characters stored in said shift register each time that said comparison characters are shifted in said shift register;

determining, simultaneously for all positions in at least a contiguous subset of the positions in said data register, maximum length strings within said set of comparison characters matching substrings of said characters stored in said data register beginning at corresponding positions in said data register, and producing in parallel a multiplicity of data pairs, each data pair corresponding to a different position in said data register, each data pair comprising a length value, corresponding to said maximum length string found for a substring beginning at a corresponding position in said data register, and a pointer value denoting where said maximum length string is located in said set of comparison characters; and

generating a sequence of codewords representing said new data string to be compressed, each said codeword including data corresponding to one of said data pairs and representing a substring of said new data string.

8. The lossless data compression method of claim 7, said determining step including the steps of:

storing a multiplicity of said length values, each length value corresponding to a different position in said data register;

storing a multiplicity of said pointer values, each pointer value corresponding to one of said stored length values;

generating a current pointer value denoting which comparison characters are currently stored in said shift register;

each time said comparison characters are shifted in said shift register, generating simultaneously current tally values for all positions in said at least a contiguous subset of the positions in said data register, each said current tally value representing how many consecutive comparison characters stored in said shift register, up to a predefined maximum value, match said characters stored in said data register beginning at a corresponding position in said data register; and

each time said comparison characters are shifted in said shift register, simultaneously comparing all of said current tally values with corresponding ones of said stored length values, and when any of said current tally values exceeds said corresponding stored length value, replacing said corresponding stored length value with said current tally value and replacing the corresponding stored pointer value with a value corresponding to said current pointer value.

9. The lossless data compression method of claim 7,

said sequence of codewords representing a sequence of successive, non-overlapping substrings of said new data string;

and

said codeword generating step including repeatedly selecting a position in said data register following a substring represented by a previous codeword generated by said codeword generating step and generating a codeword corresponding to the data pair for said selected position in said data register.