Method of encoding and storing in a machine control computer a compressed data lookup table

• US 7,079,056 B2
• Filed: 01/15/2003
• Issued: 07/18/2006
• 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
• Primary Examiner(s): Wamsley, Patrick
• Application Number:
  US10/342,493
• Publication Number:
  US 20040139099A1
• Time in Patent Office: 1,280 Days
• Field of Search: 341/87, 341/51, 341/59, 341/106, 707/101, 708/203, 235/494, 251/129.04, 358/1.13, 477/110, 477/160, 701/33, 701/114, 710/68
• US Class Current: 341/106
• 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 compressing digital data from an uncompressed data lookup table into an encoded, addressable, compressed data lookup table and storing the compressed data lookup table in a memory of a machine control computer, the uncompressed data lookup table comprising a plurality of uncompressed numerical data items having a single predetermined uncompressed data bit length in a row/column structure and the machine control computer being programmed to perform data lookup procedures with specification of a row and column of the uncompressed data lookup table, the method comprising the steps:

scanning the uncompressed data lookup table for compressible and uncompressible data items,

defining a plurality of code descriptors for compressible data items, each of the code descriptors having a first predetermined number of bits describing a code type and a second predetermined number of bits for defining a run length of data items, each of the code types specifying a different compressed data item bit length less than the single predetermined uncompressed data bit length;

for each unique uncompressible data, storing the unique uncompressible data item in the compressed data lookup table and defining a code descriptor for the unique uncompressible data item having a first predetermined number of bits identifying the memory location of the stored unique uncompressible data item and a second predetermined number of bits for defining a run length of the unique uncompressible data item

encoding and storing in the compressed data lookup table data specifying the number of rows and the number of columns of the uncompressed data lookup table;

generating and storing in the compressed data lookup table an encoded code/data string by encoding and storing each row of uncompressed data items in the uncompressed data lookup table that is not identical to a previously encoded and stored row according to the following steps, beginning at the first column of the row;

(a) beginning with the next uncompressed data item in the row that has not been encoded, determining a run of consecutive uncompressed data items within the row for which a single one of the code descriptors is most appropriate and storing the most appropriate code descriptor encoded with the run length of the determined run,

(b) if and only if the stored most appropriate code descriptor is a code descriptor for compressible items, storing compressed data items for the run following the code descriptor in column order, each of the compressed data items having a bit length equal to the bit length indicated by the code type thereof and including all significant bits of the corresponding uncompressed data item; and

(c) repeating steps (a) and (b) to the end of the row; and

assembling and storing in the compressed data lookup table a row descriptor array comprising the locations in the compressed code data string of the code descriptors associated with the first uncompressed data item of each row, with the entry in the array for any row of the uncompressed data lookup table that is omitted being the same as that of the previous encoded and stored row to which it is identical, whereby the row descriptor array provides indexing of the initial column of each row of the compressed data lookup table for a table lookup operation with a specified row and column; and

storing the compressed data lookup table in the memory of a machine control computer.

2. The method of claim 1 wherein, for code types used in encoding a compressible data item, the most appropriate code type is that which specifies the smallest of the compressed data item bit lengths able to contain all the significant numerical bits of the uncompressed data item.

3. The method of claim 1 further comprising the step of storing in the memory of a machine control computer program modifications enabling location of a compressed data item by specification of its row and column in the uncompressed data lookup table using the code descriptors and the row descriptor array.

4. The method of claim 1 wherein the single predetermined uncompressed data bit length for all data items is greater than two bytes and the plurality of code descriptors comprises at least one having a bit length of one byte and another having a bit length of two bytes.