System and method for compressing data using adaptive field encoding

• US 6,225,922 B1
• Filed: 03/16/1998
• Issued: 05/01/2001
• Est. Priority Date: 03/16/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Norton, Kirkpatrick W.
• Primary Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US09/039,929
• Time in Patent Office: 1,142 Days
• Field of Search: 341/50, 341/51, 341/87
• US Class Current: 341/87
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

A data compression system and method for compressing data of an input data stream having field widths for holding data values of a data set. Each field width is represented by a field value. The data compression system includes an adaptive processor having an encode module for encoding the input signal and dynamically changing the field widths at various positions in the data stream. This minimizes a storage space required to represent the entire data set. A decode module can be included for decoding the compressed format and producing an output signal having a lossless representation of the input signal.

Claims

1. A data compression system for compressing data of an input data stream, the input data stream having field widths for holding data values of a data set, each field width being represented by a field value, the data compression system comprising an adaptive processor for encoding the input data stream by dynamically changing the field widths at various positions in the data stream, the adaptive processor including an encode module that dynamically indicates changes from longer to shorter and from shorter to longer field widths at the various positions using a width flag and one width information field.

2. The data compression system of claim 1, wherein each data value is represented by a width information field and each new width flag indicates field width changes and that a following field contains a width information field.

3. The data compression system of claim 2, wherein each new width flag is dynamically located to produce an optimal representation of the data set.

4. The data compression system of claim 1, wherein the adaptive processor further comprises an optimizer module for tracking the field widths and the data values of the input data stream, for evaluating potential new field widths at which each data value can be represented at, and for determining a minimum number of field values required to represent all of the data values of the data set.

5. The data compression system of claim 1, further comprising a prefilter for preconditioning low frequency data of the input data stream.

6. The data compression system of claim 1, wherein the adaptive processor further comprises a decode module for decoding the encoded input data stream and producing output data.

7. The data compression system of claim 6, wherein the output data is a lossless representation of the input data.

8. A data compression method for compressing data of an input data stream, the input data stream having field widths for holding data values of a data set, each field width being represented by a field value, the data compression method comprising encoding the input data stream by dynamically changing the field widths at various positions in the data stream, wherein encoding includes dynamically indicating changes from longer to shorter and from shorter to longer field widths at the various positions by using a width flag and at least one width information field.

9. The data compression method of claim 8, further comprising representing each data value by a width information field and indicating field width changes with each new width flag and that a following field contains a width information field.

10. The data compression method of claim 9, further comprising dynamically locating each new width flag to produce an optimal representation of the data set.

11. The data compression method of claim 8, further comprising tracking the field widths and the data values of the input data stream, evaluating potential new field widths at which each data value can be represented at, and determining a minimum number of field values required to represent all of the data values of the data set.

12. The data compression method of claim 8, further comprising preconditioning low frequency data of the input data stream.

13. The data compression method of claim 8, further comprising decoding the encoded input data stream to produce output data.

14. The data compression method of claim 13, wherein the output data is a lossless representation of the input data.

15. A computer-readable medium having computer-executable components for causing a computer to function as a data compression system for producing encoded data from input data stream, the input data stream having field widths for holding data values of a data set, each field width being represented by a field value, the data compression system comprising:

a computer-readable storage medium; and

a computer data compression system stored on said medium, said computer data compression system having an adaptive processor for dynamically changing the field widths at various positions in the data stream, the adaptive processor including an encode module that dynamically indicates changes from longer to shorter and from shorter to longer field widths at the various positions by using a width flag and at least one width information field.

16. The data compression system of claim 15, wherein each data value is represented by a width information field and each new width flag indicates field width changes and that a following field contains a width information field.

17. The data compression system of claim 16, wherein each new width flag is dynamically located to produce an optimal representation of the data set.

18. The data compression system of claim 15, wherein the adaptive processor further comprises an optimizer module for tracking the field widths and the data values of the input data stream, for evaluating potential new field widths at which each data value can be represented at, and for determining a minimum number of field values required to represent all of the data values of the data set.

19. The data compression system of claim 15, further comprising a prefilter for preconditioning low frequency data of the input data stream.

20. The data compression system of claim 15, wherein the adaptive processor further comprises a decode module for decoding the encoded input data stream and producing output data.

21. A computer-readable medium having computer-executable instructions for performing a method for compressing data of an input data stream having field widths for holding data values of a data set, each field width being represented by a field value, the method comprising:

receiving the input data stream;

sequentially reading and associating the data values;

sequentially tracking the field widths and the data values;

determining potential new field widths at which each sequentially received data value can be represented at;

selecting a new field width sequence that optimally represents the data set by dynamically changing the field widths at various positions in the data stream by using a width flag and at least one width information field, the changes in width fields being from longer to shorter and from shorter to longer width fields; and

representing the data with a new field width sequence as encoded data.

22. The method for compressing data of claim 21, further comprising preconditioning low frequency data of the input data stream.

23. The method of claim 21, further comprising decoding the encoded input data to produce output data as a lossless representation of the input data.

24. The method for compressing data of claim 21, wherein sequentially reading and associating the data values is performed by a linked list component and sequentially tracking the field widths and the data values and determining potential new field widths at which each sequentially received data value can be represented at is performed by a decision tree component.

25. A computer-readable memory device encoded with a data structure for compressing data of an input data stream having field widths for holding data values of a data set, each field width being represented by a field value, the data structure having entries each entry containing:

a first parameter value corresponding to an input module for receiving the input data stream and sequentially reading and associating the data values;

a second parameter value corresponding to a tracking module for sequentially tracking the field widths and the data values and an evaluation module for determining potential new field widths at which each sequentially received data value can be represented at and selecting a new field width sequence by dynamically changing the field widths at various positions in the data stream by using a width flag and at least one width information field, the changes in field widths being from longer to shorter and from shorter to longer field widths; and

wherein the new field width sequence is in a compressed format that is an optimal representation of the data set.

26. The computer-readable memory device of claim 25, wherein the third parameter value further corresponding to noting each field width change.

27. The computer-readable memory device of claim 25, further comprising a fourth parameter value corresponding to a filter for preconditioning low frequency data of the input data stream.

28. The computer-readable memory device of claim 25, wherein the input module is a linked list component and the tracking and evaluation modules are a decision tree component.

29. The computer-readable memory device of claim 25, further comprising a decode module for receiving the compressed format to produce output data as a lossless representation of the input data.

30. The computer-readable memory device of claim 29, wherein the decode module reads the compressed format at prescribed field widths and writes information to the output data at maximum field widths until all data has been read and written.

31. A method of compressing data comprising:

receiving an input data, the input data including a plurality of data sets, each data set having a field width; and

compressing the input data by reducing the width field of each data set, wherein compressing includes;

selecting a minimum field width for each data set;

indicating a change in field width of a previous data set and a field width of a subsequent data set using a field width flag, the change in field width including a change from a longer to a shorter and from a shorter to a longer filed width; and

placing a field width information code after the flag to indicate the width field of the subsequent data set.