US5260693A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for lossless and adaptive data compression and decompression
Assignee: SPACELABS Inc A CORP OF
•
Filing: 1991-10-11
•
Granted: 1993-11-09
•
Expires: 2011-10-11
Abstract
Abstract A method and system for compression and decompression. The system compresses data by calculating the differences between adjacent data values, identifying a plurality of frequently occurring differences, tracking the frequency of occurrence of the identified differences, generating a first encoding for the identified differences wherein the length of the encoding is based on the frequency of occurrence, generating a second encoding for the differences other than the identified differences, and for each calculated difference, encoding the calculated difference is identified difference and encoding the calculated difference using the second encoding when the calculated difference is not an identified difference to effect the compression of the data.
Inventors
- 👤 Erik R. Horsley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 02:03
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/50; H04N19/593; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
158 words
A method in a computer system of compressing a plurality of packets of data values, the method comprising the steps of: defining a frequency table indicating frequencies of differences of data values; and for each of the plurality of packets, identifying a set of differences in the frequency table; generating a frequency-based encoding for each difference in the identified set based on the frequencies in the frequency table; calculating differences of adjacent data values in the packet; for each calculated difference, when the calculated difference is in the identified set, outputting the generated frequency-based encoding for the calculated difference, and when the calculated difference is not in the identified set, outputting the calculated difference in a format that is not frequency-based encoded, wherein output generated encodings and output calculated differences form a compressed packet of data values; and updating the frequency table based on calculated differences wherein subsequently generated frequency-based encodings are based on the updated frequency table.
Claim 2
Independent Claim
158 words
A method in a computer system of compressing a plurality of packets of data values, the method comprising the steps of: defining a frequency table indicating frequencies of differences of data values; and for each of the plurality of packets, identifying a set of differences in the frequency table; generating a frequency-based encoding for each difference in the identified set based on the frequencies in the frequency table; calculating differences of adjacent data values in the packet; for each calculated difference, when the calculated difference is in the identified set, outputting the generated frequency-based encoding for the calculated difference, and when the calculated difference is not in the identified set, outputting the calculated difference in a format that is not frequency-based encoded, wherein output generated encodings and output calculated differences form a compressed packet of data values; and updating the frequency table based on calculated differences wherein subsequently generated frequency-based encodings are based on the updated frequency table.
Claim 3
Dependent Claim
42 words
The method of claim 1 including the step of when successive calculated differences are equal, outputting a run length encoding of the calculated differences, the run length encoding including an indicator of the number of equal calculated differences and the calculated difference.
Claim 4
Dependent Claim
59 words
The method of claim 2 including the step of when the identified set of differences includes a difference that is equal to the indicator of the number of equal calculated differences in the run length encoding, outputting the generated frequency-based encoding for the difference as the indicator of the number of equal calculated differences in the run length encoding.
Claim 5
Dependent Claim
49 words
The method of claim 3 including the step of when the identified set of differences does not include a difference that is equal to the indicator of the number of equal calculated difference in the run length encoding, outputting the indicator in a format that is not frequency-based encoded.
Claim 6
Dependent Claim
39 words
The method of claim 2 including the step of when the equal calculated difference of the run length encoding is in the identified set, outputting the generated frequency-based encoding for the equal calculated difference in the run length encoding.
Claim 7
Independent Claim
143 words
A method of compressing a packet of data values, the method comprising the steps of: specifying a frequency distribution of data values; generating a frequency-based encoding for each data value based on the frequencies in the frequency table; when a set of successive data values are equal, outputting a run length encoding of the data values, the run length encoding including a run length indicator and the data value, the run length indicator being output as a generated frequency-based encoding for data value equal to the run length indicator; when successive data values are not equal, outputting the generated frequency-based encoding for the data values; and after generating the frequency based encoding, updating the frequency distribution of data values based on the frequency of data values in the packet wherein the updated frequency distribution is used when encoding another packet of data values.
Claim 8
Independent Claim
143 words
A method of compressing a packet of data values, the method comprising the steps of: specifying a frequency distribution of data values; generating a frequency-based encoding for each data value based on the frequencies in the frequency table; when a set of successive data values are equal, outputting a run length encoding of the data values, the run length encoding including a run length indicator and the data value, the run length indicator being output as a generated frequency-based encoding for data value equal to the run length indicator; when successive data values are not equal, outputting the generated frequency-based encoding for the data values; and after generating the frequency based encoding, updating the frequency distribution of data values based on the frequency of data values in the packet wherein the updated frequency distribution is used when encoding another packet of data values.
Claim 9
Dependent Claim
26 words
The method of claim 6 including wherein the data value of the run length encoding is output as the generated frequency-based encoding for the data value.
Claim 10
Independent Claim
156 words
A method in a computer system of compressing a plurality of packets of data values, the method comprising the steps of: defining a frequency table indicating frequencies of data values; and for each of the plurality of packets, identifying a set of data values in the frequency table; generating a frequency-based encoding for each data value in the identified set based on the frequencies in the frequency table; for each data value in the packet, when the data value is in the identified set, outputting the generated frequency-based encoding for the data value, and when the data value is not in the identified set, outputting the data value in a format that is not frequency-based encoded, wherein output generated encodings and output data values form a compressed packet of data values; and updating the frequency table based on frequency of data values in the packet wherein subsequently-generated frequency-based encodings are based on the updated frequency table.
Claim 11
Independent Claim
156 words
A method in a computer system of compressing a plurality of packets of data values, the method comprising the steps of: defining a frequency table indicating frequencies of data values; and for each of the plurality of packets, identifying a set of data values in the frequency table; generating a frequency-based encoding for each data value in the identified set based on the frequencies in the frequency table; for each data value in the packet, when the data value is in the identified set, outputting the generated frequency-based encoding for the data value, and when the data value is not in the identified set, outputting the data value in a format that is not frequency-based encoded, wherein output generated encodings and output data values form a compressed packet of data values; and updating the frequency table based on frequency of data values in the packet wherein subsequently-generated frequency-based encodings are based on the updated frequency table.
Claim 12
Dependent Claim
43 words
The method of claim 8 including the step of when successive data values are equal, outputting a run length encoding of the equal data values, the run length encoding including an indicator of the number of equal data values and the data value.
Claim 13
Dependent Claim
53 words
The method of claim 9 including the step of when the identified set of data values includes a data value that is equal to the indicator of the number of equal data values in the run length encoding, outputting the generated frequency-based encoding as the equal data value in the run length encoding.
Claim 14
Dependent Claim
51 words
The method of claim 10 including the step of when the identified set of data values does not include a data value that is equal to the indicator of the number of equal data values in the run length encoding, outputting the indicator in a format that is not frequency-based encoded.
Claim 15
Dependent Claim
37 words
The method of claim 9 including the step of when the data value of the run length encoding is in the identified set, outputting the generated frequency-based encoding for the data value in the run length encoding.
Claim 16
Independent Claim
261 words
A method in a computer system of compressing a plurality of packets of uncompressed data values into packets of compressed data values and decompressing the packets of compressed, data values, the method comprising the steps of: defining a compression frequency table and a decompression frequency table indicating frequencies of data values; for each of the plurality of packets of uncompressed data values, identifying a set of data values in the compression frequency table; generating a frequency-based encoding for each data value in the identified set based on the frequencies in the compressed frequency table; for each uncompressed data value in the packet, when the uncompressed data value is in the identified set, outputting the generated frequency-based encoding for the uncompressed data value; and when the uncompressed data value is not in the identified set, outputting the uncompressed data value in a format that is not frequency-based encoded, wherein output generated encodings and output data values form a packet of compressed data values; and updating the compression frequency table based on frequency of uncompressed data values in the packet; and for each packet of compressed data values, retrieving each generated encoding and each data value that is not in a frequency-based encoded format from the packet of compressed data values; decoding the retrieved generated encoding using the decompression frequency table to generate an uncompressed data value, wherein the generated data values and the retrieved data values form a packet of decompressed data value; and updating the decompression frequency table based on frequency of data values in the packet of decompressed data values.
Claim 17
Independent Claim
261 words
A method in a computer system of compressing a plurality of packets of uncompressed data values into packets of compressed data values and decompressing the packets of compressed, data values, the method comprising the steps of: defining a compression frequency table and a decompression frequency table indicating frequencies of data values; for each of the plurality of packets of uncompressed data values, identifying a set of data values in the compression frequency table; generating a frequency-based encoding for each data value in the identified set based on the frequencies in the compressed frequency table; for each uncompressed data value in the packet, when the uncompressed data value is in the identified set, outputting the generated frequency-based encoding for the uncompressed data value; and when the uncompressed data value is not in the identified set, outputting the uncompressed data value in a format that is not frequency-based encoded, wherein output generated encodings and output data values form a packet of compressed data values; and updating the compression frequency table based on frequency of uncompressed data values in the packet; and for each packet of compressed data values, retrieving each generated encoding and each data value that is not in a frequency-based encoded format from the packet of compressed data values; decoding the retrieved generated encoding using the decompression frequency table to generate an uncompressed data value, wherein the generated data values and the retrieved data values form a packet of decompressed data value; and updating the decompression frequency table based on frequency of data values in the packet of decompressed data values.
Claim 18
Dependent Claim
149 words
A computer system for compressing a plurality of packets of data values comprising: a frequency table indicating frequencies of data values; means for identifying a set of values in the frequency table; means for generating a frequency-based encoding for each data value in the identified set based on the frequencies in the frequency table; means for retrieving a data value from a packet; means for outputting the generated frequency-based encoding for the retrieved data value when a retrieved data value is in the identified set, means for outputting the retrieved data value in a format that is not frequency-based encoded when the retrieved data value is not in the identified set; means for storing the output generated encodings and output data values as a packet of compressed data values; and means for updating the frequency table based on frequency of data values in one of the plurality of packets.
Claim 19
Dependent Claim
149 words
A computer system for compressing a plurality of packets of data values comprising: a frequency table indicating frequencies of data values; means for identifying a set of values in the frequency table; means for generating a frequency-based encoding for each data value in the identified set based on the frequencies in the frequency table; means for retrieving a data value from a packet; means for outputting the generated frequency-based encoding for the retrieved data value when a retrieved data value is in the identified set, means for outputting the retrieved data value in a format that is not frequency-based encoded when the retrieved data value is not in the identified set; means for storing the output generated encodings and output data values as a packet of compressed data values; and means for updating the frequency table based on frequency of data values in one of the plurality of packets.
Claim 20
Dependent Claim
43 words
The computer system of claim 14 including means for outputting a run length encoding of retrieved data values when successive retrieved data values are equal, the run encoding including an indicator of the number of equal data values and the equal data value.
Claim 21
Dependent Claim
47 words
The computer system of claim 15 including means for outputting a generated frequency-based encoding in the run length encoding when the identified set of data values includes a data value that is equal to the indicator of the number of data values in the run length encoding.
Claim 22
Dependent Claim
50 words
The computer system of claim 16 including means for outputting the indicator in a format that is not frequency-based encoded when the identified set of data values does not include a data value that is equal to the indicator of the number of data values in the run length encoding.
Claim 23
Dependent Claim
39 words
The computer system of claim 15 including means for outputting the generated frequency-based encoding for the equal data value in the run length encoding when the equal data value of the run length encoding is in the identified set.
References Cited (Backward Citations)
US4578704A
Cited
US4546342A
Cited
US4839649A
Cited
US4781096A
Cited
US4626829A
Cited
US4734768A
Cited
US4813056A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-08 | 1997-05-10 | 1997-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-08 | 2001-05-10 | 2001-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-08 | 2005-05-10 | 2005-11-09 | $7700.00 | Window Closed / Lapsed |