Data compression apparatus with shift register search means
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
60 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25)
-
-
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. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
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. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48, 49)
-
-
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. - View Dependent Claims (51, 52, 53, 54, 55, 56, 57, 58, 59, 60)
-
Specification