Data Compression by Multi-Order Differencing

• US 20100161568A1
• Filed: 03/05/2010
• Published: 06/24/2010
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Xiao, Jing
• Granted Patent: US 8,031,089 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: G01S 19/258 relating to the satellite constellation, e.g. almanac, ephemeris data, lists of satellites in view

Abstract

Embodiments of the present invention enable compression and decompression of data. Applications of the present invention are its use in embodiments of systems for compression and decompression of GPS long-term Ephemeris (LTE) data, although the present invention is not limited to such applications. In embodiments, the LTE data may be grouped into a set of data values associated with a parameter. In embodiments, a data set may be compressed by using a multi-order differencing scheme. In such a scheme, a set of the differences between values may be compressed because the differences have smaller magnitudes than the values. In embodiments, a multi-order differencing scheme determines how many levels (orders) of differencing may be applied to an original data set before it is compressed. In embodiments, the original data may be recovered from a compressed data set based on the type of multi-order differencing scheme used to generate the compressed data.

Claims

1. A method for compressing GPS long-term Ephemeris (LTE) data, the method comprising:

grouping the GPS LTE data per parameter with data values of the corresponding parameter taken at different timings;

designating a set of original data values for a parameter in the GPS LTE data to associate with a multi-order difference scheme; and

using the multi-order difference scheme associated with the parameter to compress the set of data values.

2. The method of claim 1, further comprising:

determining a reference value, the reference value being an original value of the parameter;

determining a set of first-order difference values, the first-order difference values being difference values between neighboring original values of the parameter;

determining a reference value bit length to encode the reference values;

determining a difference value bit length to encode the first-order difference values; and

storing a compressed data record, the compressed data record including the reference value bit length, the difference value bit length, the reference value, and the set of first-order difference values;

wherein the parameter associated with the multi-order difference scheme includes “

health”

.

3. The method of claim 1, further comprising:

determining a first reference value, the first reference value being an original value of the parameter;

determining a set of first-order difference values, the first-order difference values being difference values between neighboring original values of the parameter;

determining a second reference value, the second reference value being a first-order difference value within the set of first-order difference values;

determining a set of second-order difference values, the second-order difference values being difference values between neighboring first-order difference values of the parameter;

determining a first reference value bit length to encode the first reference value;

determining a second reference value bit length to encode the second reference value;

determining a second-order difference value bit length to encode the second-order difference values; and

storing a compressed data record, the compressed data record including the first reference value bit length, the second reference value bit length, the second-order difference value bit length, the first reference value, the second reference value, and the set of first-order difference values;

wherein the parameter associated with the multi-order difference scheme includes “

uraidx”

.

4. The method of claim 1, further comprising:

determining a first reference value, the first reference value being an original value of the parameter;

determining a set of first-order difference values, the first-order difference values being difference values between neighboring original values of the parameter;

determining a second reference value, the second reference value being one of the first-order difference values of the parameter;

determining a set of second-order difference values, the second-order difference values being difference values between neighboring first-order difference values of the parameter;

determining a second-order difference value bit length to encode the second-order difference values;

designating a bit length associated with the parameter as the bit length for the first reference value and the second reference value; and

storing a compressed data record, the compressed data record including the bit length for the first and second reference values, the second-order difference value bit length, the first reference value, the second reference value, and the set of second-order difference values;

wherein the parameter associated with the multi-order difference scheme includes “

Omega0”

.

5. The method of claim 1, further comprising:

determining a first reference value, the first reference value being an original value of the parameter;

determining a set of first-order difference values, the first-order difference values being difference values between neighboring original values of the parameter;

determining a set of second-order difference values, the second-order difference values being difference values between every two first-order difference values of the parameter;

determining a second reference value and a third reference value, the second reference value and the third reference value being first-order difference values within the set of first-order difference values;

determining a second-order difference value bit length to encode the second-order difference values;

designating a bit length associated with the parameter as the bit length for the first reference value;

determining a bit length for the second reference value and the third reference value; and

storing a compressed data record, the compressed data record including the bit length for the first reference value, the bit length for the second and third reference values, the second-order difference value bit length, the first reference value, the second reference value, the third reference value, and the set of second-order difference values;

wherein the parameter associated with the multi-order difference scheme includes “

af0”

, “

af1”

, or “

e”

.

6. The method of claim 1, further comprising:

determining a first reference value, the first reference value being an original value of the parameter;

determining a set of first-order difference values, the first-order difference values being difference values between neighboring original values of the parameter;

determining a second reference value, the second reference value being a first-order difference value within the set of first-order difference values;

determining a set of second-order difference values, the second-order difference values being difference values between the second reference value and the first-order difference values of the parameter;

determining a set of third-order difference values, the third-order difference values being difference values between every two second-order difference values;

determining a third reference value and a fourth reference value, the third and fourth reference values being designated from the set of second-order difference values;

determining a set of fourth-order difference values, the fourth-order difference values being difference values between every four third-order difference values;

determining fifth, sixth, seventh, and eighth reference values designated from the set of third-order difference values;

determining a fourth-order difference value bit length to encode the fourth-order difference values;

designating a bit length associated with the parameter as the bit length for the first reference value;

determining a bit length for the second reference value and the third reference value, and determining a bit length for the fifth, sixth, seventh, and eighth reference values; and

storing a compressed data record, the compressed data record including the bit length for the first reference value, the bit length for the second and third reference values, the bit length for the fifth, sixth, seventh, and eighth reference values, the fourth-order difference value bit length, the first through the eighth reference values, and the set of fourth-order difference values;

wherein the parameter associated with the multi-order difference scheme includes “

m0”

.

7. The method of claim 1, further comprising:

designating four original values as first, second, third, and fourth reference values;

determining a set of first-order difference values, the first order difference values being difference values between every four original values of the parameter;

designating four first-order difference values within the set of first-order difference values as fifth, sixth, seventh, and eighth reference values, respectively;

determining a set of second-order difference values, the second-order difference values being difference values between every four first-order difference values within the set of the first-order difference values;

designating a second-order difference value as a ninth reference value;

determining a set of third-order difference values, the third-order difference values being difference values between neighboring second-order difference values;

determining a third-order difference value bit length to encode the third-order difference values;

designating a bit length associated with the parameter as the bit length for the first, second, third, and fourth reference values;

determining a bit length for the fifth, sixth, seventh, and eighth reference values;

determining a bit length for the ninth reference value; and

storing a compressed data record, the compressed data record including the bit length for the first, second, third and fourth reference values, the bit length for the fifth, sixth, seventh and eighth reference values, the bit length for the ninth reference value, the third-order difference value bit length, the first through the ninth reference values, and the set of third-order difference values;

wherein the parameter associated with the multi-order difference scheme includes “

asqrt”

, “

omega”

, “

crs”

, “

crc”

, “

cus”

, “

cuc”

, “

cis”

, “

cic”

, “

omegadot”

, “

deltan”

, “

idot”

, or “

i0”

.