Lossless data compression circuit and method
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
9 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. - View Dependent Claims (2, 3)
-
-
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. - View Dependent Claims (5, 6)
-
-
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. - View Dependent Claims (8, 9)
-
Specification