← Back to Patent Explorer
US5003307A Expired / Lapsed US ⏱️ 0.0 years remaining

Data compression apparatus with shift register search means

Assignee: HI/FN Inc
•
Filing: 1989-10-06
•
Granted: 1991-03-26
•
Expires: 2009-10-06
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

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.

Inventors

  • 👤 Douglas L. Whiting
  • 👤 Glen A. George

Bibliographic Details

Application Number —
Jurisdiction US
Data Source google_patents
Last Synchronized 2026-10-27 11:01
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; H03M7/40; H03M7/46

Claims Analysis

Total Claims: 68
Claim 1
Independent Claim 148 words
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.
Claim 2
Independent Claim 148 words
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.
Claim 3
Dependent Claim 21 words
The apparatus of claim 1 further including means for storing said accumulations of results for each entry of said shift means.
Claim 4
Dependent Claim 28 words
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.
Claim 5
Dependent Claim 115 words
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.
Claim 6
Dependent Claim 32 words
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.
Claim 7
Dependent Claim 24 words
The apparatus of claim 4 further including means for limiting said comparison of said shift means to a predefined quantity of input data characters.
Claim 8
Dependent Claim 50 words
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.
Claim 9
Dependent Claim 21 words
The apparatus of claim 7 wherein said means for prioritizing further includes means for choosing the earliest of said longest strings.
Claim 10
Dependent Claim 68 words
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.
Claim 11
Dependent Claim 27 words
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.
Claim 12
Dependent Claim 18 words
The apparatus of claim 9 further including: means for obtaining said first character of said encoded data stream.
Claim 13
Independent Claim 242 words
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.
Claim 14
Independent Claim 242 words
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.
Claim 15
Dependent Claim 42 words
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.
Claim 16
Dependent Claim 30 words
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.
Claim 17
Dependent Claim 59 words
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.
Claim 18
Dependent Claim 70 words
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.
Claim 19
Dependent Claim 45 words
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.
Claim 20
Dependent Claim 38 words
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.
Claim 21
Independent Claim 209 words
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.
Claim 22
Independent Claim 209 words
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.
Claim 23
Dependent Claim 42 words
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.
Claim 24
Dependent Claim 22 words
The apparatus of claim 19 further including: means for discarding input data characters of said input data stream which have been encoded.
Claim 25
Dependent Claim 58 words
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.
Claim 26
Dependent Claim 71 words
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.
Claim 27
Dependent Claim 36 words
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.
Claim 28
Dependent Claim 29 words
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.
Claim 29
Independent Claim 144 words
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.
Claim 30
Independent Claim 144 words
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.
Claim 31
Dependent Claim 22 words
The method of claim 26 further including the step of storing said accumulations of results for each entry of said shift means.
Claim 32
Dependent Claim 29 words
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.
Claim 33
Dependent Claim 156 words
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.
Claim 34
Dependent Claim 33 words
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.
Claim 35
Dependent Claim 25 words
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.
Claim 36
Dependent Claim 49 words
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.
Claim 37
Dependent Claim 22 words
The method of claim 32 wherein said step of prioritizing further includes the step of choosing the earliest of said longest strings.
Claim 38
Dependent Claim 68 words
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.
Claim 39
Dependent Claim 48 words
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.
Claim 40
Dependent Claim 37 words
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.
Claim 41
Independent Claim 209 words
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.
Claim 42
Independent Claim 209 words
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.
Claim 43
Independent Claim 201 words
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.
Claim 44
Independent Claim 201 words
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.
Claim 45
Independent Claim 125 words
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.
Claim 46
Independent Claim 125 words
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.
Claim 47
Dependent Claim 21 words
The apparatus of claim 39 further including means for storing said accumulations of results for each entry of said storage means.
Claim 48
Dependent Claim 28 words
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.
Claim 49
Dependent Claim 115 words
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.
Claim 50
Dependent Claim 32 words
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.
Claim 51
Dependent Claim 24 words
The apparatus of claim 42 further including means for limiting said comparison of said storage means to a predefined quantity of input data characters.
Claim 52
Dependent Claim 50 words
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.
Claim 53
Dependent Claim 21 words
The apparatus of claim 45 wherein said means for prioritizing further includes means for choosing the earliest of said longest strings.
Claim 54
Dependent Claim 68 words
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.
Claim 55
Dependent Claim 27 words
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.
Claim 56
Dependent Claim 18 words
The apparatus of claim 47 further including: means for obtaining said first character of said encoded data stream.
Claim 57
Independent Claim 124 words
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.
Claim 58
Independent Claim 124 words
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.
Claim 59
Dependent Claim 22 words
The method of claim 50 further including the step for storing said accumulations of results for each entry of said storage means.
Claim 60
Dependent Claim 29 words
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.
Claim 61
Dependent Claim 156 words
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.
Claim 62
Dependent Claim 33 words
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.
Claim 63
Dependent Claim 25 words
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.
Claim 64
Dependent Claim 49 words
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.
Claim 65
Dependent Claim 22 words
THe method of claim 56 wherein said step of prioritizing further includes the step of choosing the earliest of said longest strings.
Claim 66
Dependent Claim 68 words
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.
Claim 67
Dependent Claim 48 words
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.
Claim 68
Dependent Claim 37 words
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.

USPTO Annuity & Maintenance Windows

Annuity Stage Window Opens Payment Deadline Surcharge Period Until Estimated Fee Status
3.5 Years (Year 4) 1994-03-25 1994-09-24 1995-03-26 $2000.00 Window Closed / Lapsed
7.5 Years (Year 8) 1998-03-25 1998-09-24 1999-03-26 $3760.00 Window Closed / Lapsed
11.5 Years (Year 12) 2002-03-25 2002-09-24 2003-03-26 $7700.00 Window Closed / Lapsed

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag