Arrangement for compressing data forming a data table

• US 20040139099A1
• Filed: 01/15/2003
• Published: 07/15/2004
• Est. Priority Date: 01/15/2003
• Status: Active Grant

• Current Assignee: Delphi Technologies Ip Limited (BorgWarner Incorporated)
• Original Assignee: Delphi Technologies, Inc. (BorgWarner Incorporated)
• Inventors: Weaver, Richard A.
• Granted Patent: US 7,079,056 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A compressed data table is formed from an uncompressed data table by defining a code description bit structure having a code type and a run length of data items. The code type may be configured to identify byte-length data items, word-length data items and/or one or more user-specified data items. Each run of one or more byte-length, word-length or user-specified data items in the uncompressed data table is represented in the compressed data table with a code description bit structure having an appropriately configured code type and having its run length equal to the number of byte-length, word-length or user-specified data items in the run of one or more byte-length or word-length data items, and in the case of byte-length and word-length data items each code description bit structure is followed in the compressed data table by the one or more byte-length or word-length data items.

Claims

1. A method of forming a compressed data table from an uncompressed data table, the method comprising the steps of:

defining a code description bit structure including a first number of bits defining a code type and a second number of bits defining a run length of data items;

defining a first code descriptor as the code description bit structure having its first number of bits configured to define a bytecode code type identifying byte-length data items;

defining a second code descriptor as the code description bit structure having its first number of bits configured to define a wordcode code type identifying word-length data items;

representing in the compressed data table each run of one or more byte-length data items in the uncompressed data table with the first code descriptor having its run length equal to the number byte-length data items in the run of one or more byte-length data items followed by the one or more byte-length data items; and

representing in the compressed data table each run of one or more word-length data items in the uncompressed data table with the second code descriptor having its run length equal to the number of word-length data items in the run of one or more word-length data items followed by the one or more word-length data items.

2. The method of claim 1 further including the steps of:

defining a third code descriptor as the code description bit structure having its first number of bits configured to define a first shortcode code type identifying a first specified data item; and

representing in the compressed data table each run of one or more of the first specified data items in the uncompressed data table with the third code descriptor having its run length equal to the number of the first specified data items in the run of one or more of the first specified data items.

3. The method of claim 2 further including the steps of:

defining a fourth code descriptor as the code description bit structure having its first number of bits configured to define a second shortcode code type identifying a second specified data item different than the first specified data item; and

representing in the compressed data table each run of one or more of the second specified data items in the uncompressed data table with the fourth code descriptor having its run length equal to the number of the second specified data items in the run of one or more of the second specified data items.

4. The method of claim 1 wherein the code description bit structure is a byte-length code description byte.

5. The method of claim 1 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein the method further includes the step of defining in the compressed data table a header, the header including a first number of bits defining the first number of rows in the uncompressed data table and a second number of bits defining the second number of rows in the uncompressed data table.

6. The method of claim 1 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein the method further includes the step of defining as the first item in the compressed data table a predefined number of bits defining the first number of rows and the second number of columns.

7. The method of claim 1 further including the step of storing the compressed data table in a computer memory.

8. The method of claim 1 wherein the uncompressed data table is a calibration table including data for controlling at least one function associated with a motor vehicle.

9. The method of claim 2 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein the method further includes the step of defining in the compressed data table a header, the header including a first number of bits defining the first number of rows in the uncompressed data table, a second number of bits defining the second number of rows in the uncompressed data table and a third number of bits defining the first specified data item.

10. The method of claim 2 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein the method further includes the step of defining as the first item in the compressed data table a predefined number of bits defining the first number of rows and the second number of columns.

11. The method of claim 1 wherein the uncompressed data table includes a number of rows of uncompressed data;

and further including the step of defining a row description array including a number of row identifiers equal to the number of rows in the uncompressed data table, each of the row identifiers identifying a corresponding one of the first or second code descriptors contained in the compressed data table that defines the first element in the corresponding row of the uncompressed data table.

12. The method of claim 10 further including the step of storing the compressed data table and the row description array in a computer memory.

13. The method of claim 2 wherein the uncompressed data table includes a number of rows of uncompressed data;

and further including the step of defining a row description array including a number of row identifiers equal to the number of rows in the uncompressed data table, each of the low identifiers identifying a corresponding one of the first, second or third code descriptors contained in the compressed data table that defines the first element in the corresponding row of the uncompressed data table.

14. A computer readable storage medium having stored therein a compressed data table formed from an uncompressed data table, the storage medium comprising:

a number of code description bit structures each including a first number of bits defining a code type and a second number of bits defining a run length of data items, wherein some of the number of code description bit structures define first code descriptors each corresponding to the code description bit structure having its first number of bits configured to define a bytecode code type identifying byte-length data items, and others of the number of code description bit structures define second code descriptors each corresponding to the code description bit structure having its first number of bits configured to define a wordcode code type identifying word-length data items;

wherein each run of one or more byte-length data items in the uncompressed data table is stored in the compressed data table as a combination of the first code descriptor having its run length equal to the number of byte-length data items in the run of one or more byte-length data items followed by the one or more byte-length data items;

and wherein each run of one or more word-length data items in the uncompressed data table is stored in the compressed data table as a combination of the second code descriptor having its run length equal to the number of word-length data items in the run of one or more word-length data items followed by the one or more word-length data items.

15. The computer readable storage medium of claim 14 wherein still others of the number of code description bit structures define third code descriptors each corresponding to the code description bit structure having its first number of bits configured to define a first shortcode code type identifying a first specified data item;

and wherein each run of one or more of the first specified data items in the uncompressed data table is stored in the compressed data table as the third code descriptor having its run length equal to the number of the first specified data items in the run of one or more of the first specified data items.

16. The computer readable storage medium of claim 15 wherein yet others of the number of code description bit structures define fourth code descriptors each corresponding to the code description bit structure having its first number of bits configured to define a second shortcode code type identifying a second specified data item different than the first specified data item;

and wherein each run of one or more of the second specified data items in the uncompressed data table is stored in the compressed data table as the fourth code descriptor having its run length equal to the number of the second specified data items in the run of one or more of the second specified data items.

17. The computer readable storage medium of claim 14 wherein each of the number of code description bit structures is a byte-length code description byte,

18. The computer readable storage medium of claim 14 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein the compressed data table includes a header stored therein, the header including a first number of bits defining the first number of rows in the uncompressed data table and a second number of bits defining the second number of rows in the uncompressed data table.

19. The computer readable storage medium of claim 14 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein a first item in the compressed data table comprises a predefined number of bits defining the first number of rows and the second number of columns.

20. The computer readable medium of claim 14 wherein the compressed data table stored therein is a calibration table including data for controlling at least one function associated with a motor vehicle.

21. The computer readable medium of claim 15 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein the compressed data table includes a header stored therein, the header including a first number of bits defining the first number of rows in the uncompressed data table, a second number of bits defining the second number of rows in the uncompressed data table and a third number of bits defining the first specified data item.

22. The computer readable storage medium of claim 15 wherein the uncompressed data table includes a first number of rows and a second number of columns of uncompressed data;

and wherein a first item in the compressed data table comprises a predefined number of bits defining the first number of rows and the second number of columns.

23. The computer readable medium of claim 14 wherein the uncompressed data table includes a number of rows of uncompressed data;

and wherein the computer readable medium further includes a row description array stored therein and including a number of row identifiers equal to the number of rows in the uncompressed data table, each of the row identifiers identifying a corresponding one of the first or second code descriptors contained in the compressed data table that defines the first element in the corresponding row of the uncompressed data table.

24. The computer readable medium of claim 15 wherein the uncompressed data table includes a number of rows of uncompressed data;

and wherein the computer readable medium further includes a row description array stored therein and including a number of row identifiers equal to the number of rows in the uncompressed data table, each of the row identifiers identifying a corresponding one of the first, second or third code descriptors contained in the compressed data table that defines the first element in the corresponding row of the uncompressed data table.

25. The computer readable storage medium of claim 14 further having stored therein a search algorithm configured to retrieve data items from the compressed data table corresponding to data items in specified rows and columns of the uncompressed data table by first locating appropriate ones of the first, second or third code descriptors in the compressed data table identified by row identifiers corresponding to the specified rows, and then processing at least the appropriate ones of the first, second or third code descriptors to locate the data items in the compressed data table that correspond to those in the specified columns of the uncompressed data table.