Lossless data compression circuit and method

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.

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.