Data compression apparatus with shift register search means

• US 5,003,307 A
• Filed: 10/06/1989
• Issued: 03/26/1991
• Est. Priority Date: 01/13/1989
• Status: Expired due to Fees

• Current Assignee: Hifn, Inc. (Maxlinear Incorporated)
• Original Assignee: Stac, Inc. (Titan Corporation)
• Inventors: Whiting, Douglas L., George, Glen A.
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): Logan, Sharon D.
• Application Number:
  US07/418,034
• Time in Patent Office: 536 Days
• Field of Search: 341/51, 341/67, 341/63, 341/76, 341/106, 341/95, 375/27, 358/261.1, 364/200, 364/900
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

An apparatus and method are disclosed for converting an input data character stream into a variable length encoded data stream in a data compression system. The data compression system includes a shift register means. The shift register means has a plurality of entries and each entry of the shift register means is for storing a data character of the input data stream. The method for converting the input data character stream includes the following steps. Performing a search in the shift register means for a data string which matches the input data string. The step for performing the search includes the steps of broadcasting each input data character of the input data stream to each entry of the shift register means and comparing each input data character simultaneously with the previously stored contents of each entry of said shift register means. If the matching data string is found within the shift register means, the next step includes encoding the longest matching data string by appending to the encoded data stream a tag indicating the matching data string and a string substitution code. If the matching data string is not found within the shift register means, the next step includes encoding the first character of the input data string by appending to the encoded data stream a raw data tag and the first character of the input data string.

Claims

1. An apparatus for comparing an input data character with a data stream, said data stream including a plurality of data characters, said apparatus comprising:

shift means for storing said data characters of said data stream, said shift means having a plurality of entries and each entry of said shift means for storing one of said data characters of said data stream;

means for broadcasting said input data character to each entry of said shift means;

means for transferring each said stored data character of each entry of said shift means to another entry of said shift means;

for each entry of said shift means, means for comparing said stored data character of said entry with said input data character to determine whether said stored data character matches said input data character; and

means for separately accumulating the results of said comparison for each entry of said shift means.

2. The apparatus of claim 1 further including means for storing said accumulations of results for each entry of said shift means.

3. The apparatus of claim 2 further including means for comparing said stored result of said comparison with the result of a comparison for a later input data character.

4. The apparatus of claim 1 further including means for converting a string of one or more of said input data characters into a variable length encoded data stream, said means comprising:

means for encoding matching input data characters by assigning a tag indicating said matching input data characters were found and a substitution code including a variable length indicator of said length of said matching input data characters and a pointer indicating said entry of said shift means having at least one character of said matching input data characters;

means for encoding the first character of said input data characters by assigning a "raw" data tag and said first character of said input data characters.

5. The apparatus of claim 4 further including means for evaluating said accumulations of comparison results to determine which of said accumulations corresponds to a longest string of said matching input data characters.

6. The apparatus of claim 4 further including means for limiting said comparison of said shift means to a predefined quantity of input data characters.

7. The apparatus of claim 6 further including means for evaluating said accumulations of comparison results to determine which of said accumulations corresponds to the longest strings of said matching input data characters, and means for prioritizing said longest strings when more than one of said longest strings have equal length.

8. The apparatus of claim 7 wherein said means for prioritizing further includes means for choosing the earliest of said longest strings.

9. The apparatus of claim 4 further including means for decoding said variable length encoded data stream, said means including:

means for parsing said encoded data stream into separate portions, each said separate portion starting with one of said tags;

means for evaluating said tag of said separate portion for determining whether said tag indicates said raw data tag or said tag indicates said encoded matching input data characters.

10. The apparatus of claim 9 further including:

means for interpreting said length indicator and said pointer of said substitution code for generating said matching input data characters.

11. The apparatus of claim 9 further including:

means for obtaining said first character of said encoded data stream.

12. A method for converting an input data character stream into a variable length encoded data stream in a data compression system, said data compression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said input data stream, said method comprising the steps of:

performing a search in said shift means for a longest matching data string which matches said input data stream, said step of performing said search including the steps of broadcasting each of said input data character of said input data stream to each entry of said shift means, comparing each input data character simultaneously with each entry of said shift means, and inputting each input data character into said shift means,

operative when said longest matching data string is found within said shift means, encoding said matching data string by assigning a tag indicating said matching data string and a string substitution code including a variable length indicator of said length of said matching data string and a pointer indicating said entry of said shift means having said matching data string,

operative when said matching input data string is not found within said shift means, encoding a first character of said input data stream by assigning a "raw" data tag and said first character of said input data stream,

whereby said input data stream is converted into a variable length encoded data stream.

13. The method of claim 12 wherein said of performing said search in said shift means for said longest matching data string further includes the step of limiting said search to a predefined quantity of input data characters of said input data stream.

14. The method of claim 12 further including the steps of:

discarding input data characters of said input data stream which have been encoded and further encoding said input data stream.

15. The method of claim 12 wherein said step of assigning said pointer and said length indicator further includes the step of representing said pointer and said length indicator by an encoding scheme which ensures that a matching string of two characters of said input data stream is compressed to less than said two characters of said input data stream.

16. The method of claim 12 further including the step of decoding said variable length encoded data stream, said step including the steps of:

parsing said variable length encoded data stream into separate portions, each said separate portion starting with one of said tags,

evaluating tags of said separate portions for determining whether any of said tags is said raw data tag or said tag indicating said encoded matching data string.

17. The method of claim 16 further including the step:

operative when said tag indicates said encoded matching string, interpreting said length indicator and said pointer of said substitution code for generating said matching data string, thereby reconstructing a portion of the original input data stream.

18. The method of claim 16 further including the step:

operative when said tag indicates said raw data tag, obtaining said first character of said encoded input data stream, thereby reconstructing a portion of the original input data stream.

19. An apparatus for converting an input data character stream into a variable length encoded data stream in a data compression system, said data compression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said input data stream, said apparatus comprising:

means for performing a search in said shift means for a longest matching data string which matches said input data stream, said means for performing said search including means for broadcasting each said data character of said input data stream to each said entry of said shift means, and means for comparing each said input data stream simultaneously with each entry of said shift means,

means for encoding said matching data string by assigning a tag indicating said matching data string and a string substitution code including a variable length indicator of the length of said matching data string and a pointer indicating the entry of said shift of said matching data string,

means for encoding a first character of said input data stream by assigning a "raw" data tag and said first character of said input data stream,

whereby said input data stream is converted into a variable length encoded data stream.

20. The apparatus of claim 19 wherein said means for performing said search in said shift means for said longest matching data string further includes means for limiting said search to a predefined quantity of input data characters of said input data stream.

21. The apparatus of claim 19 further including:

means for discarding input data characters of said input data stream which have been encoded.

22. The apparatus of claim 19 wherein said means for assigning said pointer and said length indicator further includes means for representing said pointer and said length indicator by an encoding scheme which ensures that a matching string of two characters of said input data stream is compressed to less than said two characters of said input data stream.

23. The apparatus of claim 19 further including means for decoding said variable length encoded data stream, said means including:

means for parsing said variable length encoded data stream into separate portions, each said separate portion starting with one of said tags,

means for evaluating each said tag of said separate portions for determining whether each said tag is said raw data tag or said tag indicating said encoded matching data string.

24. The apparatus of claim 23 further including:

means for interpreting said length indicator and said pointer of said substitution code for generating said matching data string, thereby reconstructing a portion of the original input data stream.

25. The apparatus of claim 23 further including:

means for obtaining said first character of said encoded input data stream, thereby reconstructing a portion of the original input data stream.

26. A method for comparing an input data character with a data stream, said data stream including a plurality of data characters, said method comprising the steps of:

storing said data characters of said data stream in a shift means, said shift means having a plurality of entries and each entry of said shift means for storing one of said data characters of said data stream;

broadcasting said input data character to each entry of said shift means;

transferring each said stored data character of each entry of said shift means to another entry of said shift means;

for each entry of said shift means, comparing said stored data character of said entry with said input data character to determine whether said stored data character matches said input data character; and

separately accumulating the results of said comparison for each entry of said shift means.

27. The method of claim 26 further including the step of storing said accumulations of results for each entry of said shift means.

28. The method of claim 27 further including the step of comparing said stored result of said comparison with the result of a comparison for a later input data character.

29. The method of claim 26 further including the step of converting a string of one or more of said input data characters into a variable length encoded data stream, said converting step comprising the steps of:

operative when matching input data characters are found within said shift means, encoding said matching input data characters by assigning a tag indicating said matching input data characters were found and a substitution code including a variable length indicator of said length of said matching input data characters and a pointer indicating said entry of said shift means having at least one character of said matching input data characters;

operative when said matching input data characters are not found within said shift means, encoding the first character of said input data characters by assigning a "raw" data tag and said first character of said input data characters;

whereby said data stream is converted into said variable length encoded data stream.

30. The method of claim 29 further including the step of evaluating said accumulations of comparison results to determine which of said accumulations corresponds to a longest string of said matching input data characters.

31. The method of claim 29 further including the step of limiting said comparison of said shift means to a predefined quantity of input data characters.

32. The method of claim 31 further including the steps of evaluating said accumulations of comparison results to determine which of said accumulations corresponds to the longest strings of said matching input data characters, and prioritizing said longest strings when more than one of said longest strings have equal length.

33. The method of claim 32 wherein said step of prioritizing further includes the step of choosing the earliest of said longest strings.

34. The method of claim 29 further including the step of decoding said variable length encoded data stream, said step including the steps of:

parsing said encoded data stream into separate portions, each said separate portion starting with one of said tags;

evaluating said tag of said separate portion for determining whether said tag indicates said raw data tag or said tag indicates said encoded matching input data characters.

35. The method of claim 34 further comprising the steps of:

operative when said tag indicates said encoded matching input data characters, interpreting said length indicator and said pointer of said substitution code for generating said matching input data characters,

thereby reconstructing a portion of the original data stream.

36. The method of claim 34 further including the step of:

operative when said tag indicates said raw data tag, obtaining said first character of said encoded data stream, thereby reconstructing a portion of the original data stream.

37. A method for converting a variable length encoded data stream into an output data character stream in a data decompression system, said data decompression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said output data character stream, said method comprising the steps of:

parsing said variable length encoded input data stream into separate portions, each said separate portion starting with a tag,

evaluating said tag of each said separate portion for determining whether said tag is a raw data tag or a tag indicating an encoded matching data string,

operative when said tag is said raw data tag, parsing a raw data byte from said separate portion, outputting said raw data byte, placing said raw data byte in said shift means, and

operative when said tag is said tag indicating an encoded matching data string, parsing a variable length indicator of the length of said matching data string and an offset indicating an entry within said shift means containing the first character of said matching data string, outputting said matching data string at said entry within said shift means for said length, and placing said matching data string in said shift means.

38. An apparatus for converting a variable length encoded data stream into an output data character stream in a data decompression system, said data decompression system comprising a shift means, said shift means having a plurality of entries, each entry of said shift means for storing a data character of said output data character stream, said apparatus comprising:

means for parsing said variable length encoded input data stream into separate portions, each said separate portion starting with a tag,

means for evaluating said tag of each said separate rate portion for determining whether said tag is a raw data tag or a tag indicating an encoded matching data string,

means for parsing a raw data byte from said separate portion, means for outputting said raw data byte, means for placing said raw data byte in said shift means, and

means for parsing a variable length indicator of the length of said matching data string and an offset indicating an entry within said shift means containing the first character of said matching data string, means for outputting said matching data string at said entry within said shift means for said length, and means for placing said matching data string in said shift means.

39. An apparatus for comparing an input data character with a data stream, said data stream including a plurality of data characters, said apparatus comprising:

means for storing said data characters of said data stream, said storage means having a plurality of entries and each entry of said storage means for storing one of said data characters of said data stream;

means for broadcasting said input data character to each entry of said storage means;

for each entry of said storage means, means for comparing said stored data character of said entry with said input data character to determine whether said stored data character matches said input data character; and

means for separately accumulating the results of said comparison for each entry of said storage means.

40. The apparatus of claim 39 further including means for storing said accumulations of results for each entry of said storage means.

41. The apparatus of claim 40 further including means for comparing said stored result of said comparison with the result of a comparison for a later input data character.

42. The apparatus of claim 39 further including means for converting a string of one or more of said input data characters into a variable length encoded data stream, said means comprising:

means for encoding matching input data characters by assigning a tag indicating said matching input data characters were found and a substitution code including a variable length indicator of said length of said matching input data characters and a pointer indicating said entry of said storage means having at least one character of said matching input data characters;

means for encoding the first character of said input data characters by assigning a "raw" data tag and said first character of said input data characters.

43. The apparatus of claim 42 further including means for evaluating said accumulations of comparison results to determine which of said accumulations corresponds to a longest string of said matching input data characters.

44. The apparatus of claim 42 further including means for limiting said comparison of said storage means to a predefined quantity of input data characters.

45. The apparatus of claim 44 further including means for evaluating said accumulations of comparison results to determine which of said accumulations corresponds to the longest strings of said matching input data characters, and means for prioritizing said longest strings when more than one of said longest strings have equal length.

46. The apparatus of claim 45 wherein said means for prioritizing further includes means for choosing the earliest of said longest strings.

47. The apparatus of claim 42 further including means for decoding said variable length encoded data stream, said means including:

means for parsing said encoded data stream into separate portions, each said separate portion starting with one of said tags;

means for evaluating said tag of said separate portion for determining whether said tag indicates said raw data tag or said tag indicates said encoded matching input data characters.

48. The apparatus of claim 42 further including:

means for interpreting said length indicator and said pointer of said substitution code for generating said matching input data characters.

49. The apparatus of claim 47 further including:

means for obtaining said first character of said encoded data stream.

50. A method for comparing an input data character with a data stream, said data stream including a plurality of data characters, said method comprising the steps of:

storing said data characters of said data stream in a storage means, said storage means having a plurality of entries and each entry of said storage means for storing one of said data characters of said data stream;

broadcasting said input data character to each entry of said storage means;

for each entry of said storage means, comparing said stored data character of said entry with said input data character to determine whether said stored data character matches said input data character; and

separately accumulating the results of said comparison for each entry of said storage means.

51. The method of claim 50 further including the step for storing said accumulations of results for each entry of said storage means.

52. The method of claim 51 further including the step of comparing said stored result of said comparison with the result of a comparison for a later input data character.

53. The method of claim 50 further including the step of converting a string of one or more of said input data characters into a variable length encoded data stream, said converting step comprising the steps of:

operative when matching input data characters are found within said storage means, encoding said matching input data characters by assigning a tag indicating said matching input data characters were found and a substitution code including a variable length indicator of said length of said matching input data characters and a pointer indicating said entry of said storage means having at least one character of said matching input data characters;

operative when said matching input data characters are not found within said storage means, encoding the first character of said input data characters by assigning a "raw" data tag and said first character of said input data characters;

whereby said data stream is converted into said variable length encoded data stream.

54. The method of claim 53 further including the step of evaluating said accumulations of comparison results to determine which of said accumulations corresponds to a longest string of said matching input data characters.

55. The method of claim 53 further including the step of limiting said comparison of said storage means to a predefined quantity of input data characters.

56. The method of claim 55 further including the steps of evaluating said accumulations of comparison results to determine which of said accumulations corresponds to the longest strings of said matching input data characters, and prioritizing said longest strings when more than one of said longest strings have equal length.

57. THe method of claim 56 wherein said step of prioritizing further includes the step of choosing the earliest of said longest strings.

58. The method of claim 53 further including the step of decoding said variable length encoded data stream, said step including the steps of:

parsing said encoded data stream into separate portions, each said separate portion starting with one of said tags;

evaluating said tag of said separate portion for determining whether said tag indicates said raw data tag or said tag indicates said encoded matching input data characters.

59. The method of claim 58 further comprising the steps of:

operative when said tag indicates said encoded matching input data characters, interpreting said length indicator and said pointer of said substitution code for generating said matching input data characters,

thereby reconstructing a portion of the original data stream.

60. The method of claim 58 further including the step of:

operative when said tag includes said raw data tag, obtaining said first character of said encoded data stream, thereby reconstructing a portion of the original data stream.