Method and apparatus for reducing satellite position message payload by adaptive data compression techniques

• US 9,250,327 B2
• Filed: 03/05/2013
• Issued: 02/02/2016
• Est. Priority Date: 03/05/2013
• Status: Active Grant

• Current Assignee: SubCarrier Systems Corporation
• Original Assignee: SubCarrier Systems Corporation
• Inventors: Kelley, David Charles, Berchin, Gregory John
• Primary Examiner(s): GREGORY, BERNARR E
• Application Number:
  US13/785,514
• Publication Number:
  US 20140253369A1
• Time in Patent Office: 1,064 Days
• Field of Search: 342/175, 342/195, 342/350, 342/352, 342/353, 342/357.2, 342/357.39, 342/357.4, 342/357.47, 342/357.48, 342/358, 342/385, 34235721-35725, 342/357.31, 342/357.44, 375211-215, 375219-236, 375240-24017, 341/50, 341/63, 370/229, 370/235, 370/236, 370/239, 370/240, 370/241, 370/252, 382/232, 382/233, 382/239, 701/400, 701/408, 701468-471, 708/100, 708/200, 708/203
• US Class Current: 1/1
• CPC Class Codes: G01S 19/071 DGPS corrections
• CPC Class Codes: G01S 19/074 providing integrity data, e.g. WAAS
• 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

An adaptive method by which Differential GNSS corrections may be compressed. Each measurement datum to be transmitted to a rover for satellite navigation purposes is decomposed into two parts, namely, an anchor value and a delta value, and in some instances an added third part termed a nonce value is used. Encoding parameters such as the number of bits assigned to each part of the measurement datum, the order of the models used to convey positional data, and scaling constants in the models, are adjusted adaptively based on changing data and/or transmission medium characteristics. Adaptive compression also allows for anomalous conditions such as out-of-range data values to be handled gracefully.

Claims

1. A device comprising a transmitter and at least one receiver:

the transmitter configured for at least one of obtaining and determining data elements from one or more sources, the data elements representing measurements or other information associated with one or more entities, and by means of data compression and encoding, representing an ensemble of the data elements as a set of messages that are transmitted via one or more suitable transmission media, and

the receiver configured for receiving, decoding, and decompressing messages created by the transmitter so as to reconstitute data elements contained within the messages, and further configured for deriving and evaluating the measurements or other information represented by the reconstituted data elements, such that a composite size of the messages is significantly smaller than a composite size of a set of messages representing the same data elements in an uncompressed form, and

the transmitter being configured for controlling an achievable fidelity of reconstitution of the data elements, by the receiver, by means of an alteration of one or more parameters in the data compression and encoding, and

the transmitter being configured for adaptation of compression and/or encoding parameters in response to changing requirements, situations, or data, and

the transmitter and receiver being configured for accommodation of one or more anomalous data elements that cannot be represented by the encoding, such anomalous elements being identified by means of signals encoded in the messages.

2. The device of claim 1, wherein the data elements include range, range-rate, range corrections, or quantities related to range, and corresponding times, or parameters used in the determination thereof, associated with observations of one or more GNSS satellites by one or more GNSS reference stations at fixed locations on the surface of the Earth, or

the data elements include parametric models or other representations that are functions of time, and from which range, range-rate, range corrections, or quantities related to range, and corresponding times, or parameters used in the determination thereof, are derived by evaluation of the parametric models or other representations, and

the messages represent information that is transmitted by one or more GNSS reference stations to one or more mobile or stationary GNSS rovers via one or more transmission media, as a part of an implementation of GNSS differential range correction.

3. The device of claim 2, wherein compression and encoding parameters are known to both the transmitter and the receiver because:

a. compression and encoding parameters are predetermined and either fixed, or changed according to a schedule, or

b. compression and encoding parameter values are changed by the transmitter, then transmitted to the receiver when changed, or

c. compression and encoding parameter values are changed by external entities, then conveyed to the transmitter and the receiver when changed.

4. The device of claim 3, wherein compression and encoding parameters associated with each GNSS satellite signal are unique to each signal.

5. The device of claim 3, wherein some or all of a set of compression or encoding parameters are shared among more than one GNSS satellite signals.

6. The device of claim 5, wherein the transmitter transmits one or more sets of compression or encoding parameters to the receiver by means of an index to a mutually shared table or list of such parameters.

7. The device of claim 3, wherein the transmitter transmits one or more sets of compression or encoding parameters to the receiver by means or one or more auxiliary communications methods.

8. The device of claim 3, wherein compression or encoding parameter values are transmitted more frequently than a rate at which the values actually change, such that an amount of time that passes between when the receiver begins to receive data messages from the transmitter, and when the receiver has received a complete data message and begins decoding, is thereby reduced.

9. The device of claim 2, wherein data elements are decomposed into:

a. a set of long-term values, represented at full or at reduced numerical accuracy;

values or representations of which are transmitted infrequently, and

b. a set of short-term values, represented at full or at reduced numerical accuracy;

values or representations of which are transmitted frequently, and

c. a set of residuals;

values or representations of which are transmitted as necessary, that provide instantaneous corrections to data elements reconstituted only from the long-term and short-term values such that reconstituted data elements match original data elements to within an increased numerical accuracy.

10. The device of claim 9, wherein the set of long-term values represents full quantities of corresponding original data elements, to within a desired numerical accuracy.

11. The device of claim 9, wherein the set of short-term values represents differences between a set of current data elements and a corresponding set of recent previous data elements, to within a desired numerical accuracy.

12. The device of claim 11, wherein the set of short-term values represents differences between a set of current data elements and a most recently transmitted set of long-term values.

13. The device of claim 12, wherein reconstitution of the set of current data elements depends only upon a set of short-term values and the most recently transmitted set of long-term values, such that reconstitution of the set of current data elements is possible even in cases where one or multiple more-recently transmitted sets of short-term values has not been received.

14. The device of claim 11, wherein the set of short-term values represents differences between a set of current data elements and a sum of a most recently transmitted set of long-term values and at least one set of recently transmitted short-term values.

15. The device of claim 11, wherein compression is achieved because the differences have smaller magnitudes than corresponding full quantities of the current data elements, and thus encoding of differences results in a smaller message payload than does encoding of full quantities of data elements.

16. The device of claim 9, wherein the set of residuals represents differences between a set of current data elements and:

a. a most recently transmitted set of long-term values, or

b. a sum of a most recently transmitted set of long-term values and at least one recently transmitted set of short-term values.

17. The device of claim 9, wherein multiple individual long-term, short-term, or residual values are decomposed into a sum of a value common to all the individual values and an excess value unique to each the individual value, and transmitted in lieu of the multiple individual values.

18. The device of claim 17, wherein data compression is achieved because fewer message bits are required to represent the single common value and multiple unique excess values than are required to represent the multiple individual values.

19. The device of claim 9, wherein:

a. long-term values are transmitted at a rate based upon a rate at which the data elements change, a fidelity with which the reconstituted data elements must match the original data elements, some constraints upon transmission bandwidth or data payload, or an ability of the receiver to tolerate data starvation, and

b. short-term values are transmitted at a rate based upon a rate at which the data elements change, a fidelity with which the reconstituted data elements must match the original data elements, some constraints upon transmission bandwidth or data payload, or an ability of the receiver to tolerate data starvation, and

c. residual values are transmitted at a rate based upon a fidelity with which the reconstituted data elements must match the original data elements, or some constraints upon transmission bandwidth or data payload.

20. The device of claim 19, wherein compression is achieved because encoding of the parameters results in smaller message payload than does encoding of values from which models or other representations are derived.

21. The device of claim 9, wherein:

a. data elements consist of parametric models or other representations that are functions of time, and

b. parameters of the parametric models or other representations are transmitted instead of values that parametric models or other representations represent, and

c. the receiver is configured for evaluation of the parametric models or other representations, and the parametric models or other representations are evaluated by the receiver with respect to a current time or with respect to a past time, to reconstitute associated values that parametric models or other representations represent, to within a desired numerical accuracy, or

d. the receiver is configured for evaluation of the parametric models or other representations, and the parametric models or other representations are evaluated by the receiver with respect to a future time, to estimate future values that parametric models or other representations represent.

22. The device of claim 21, wherein the parametric models or other representations are used to estimate future values, and the receiver is configured to tolerate periods of data starvation by utilizing the estimated future values in lieu of some missing measured future values, in an event of inability to receive one or more signals from the transmitter or purposeful reduction in transmission rates of long-term values, short-term values, or residuals.

23. The device of claim 19, wherein each the parametric model or other representation incorporates an independent set of scale factors for each of long-term values, short-term values, and residuals.

24. The device of claim 19, wherein the device further comprises means for adapting its configuration to exploit trending information regarding data elements when available, or to remain operable when the trending information is absent.

25. The device of claim 9, wherein one or more long-term values remain constant for some periods of time spanning two or more long-term transmission epochs.

26. The device of claim 25, wherein the transmitter transmits, in addition to each constant long-term value, one or more indications of a number of long-term transmission epochs over which associated long-term value remains constant.

27. The device of claim 25, wherein the transmitter transmits each of the constant long-term values in an associated initial message, and omits each of the constant long-term values in at least one subsequent message.

28. The device of claim 2, wherein the transmitter adaptively changes compression or encoding parameters for one or more sets of data elements.

29. The device of claim 28, wherein a quality metric is considered when adapting compression or encoding parameters, consisting of the following, individually or in combination:

a. a fidelity with which data elements reconstituted from transmitted messages match original data elements,

b. an ability of parametric models or other representations of data elements to mathematically estimate future values,

c. a time that passes between when the receiver begins to receive data messages from the transmitter, and when the receiver has received a complete data message and begins decoding.

30. The device of claim 28, wherein the adaptive changes are applied such that the quality metric for data elements reconstituted by the receiver is maximized within a constraint upon allowable maximum average or instantaneous size of the messages.

31. The device of claim 28, wherein the adaptive changes are applied in order to minimize an average or instantaneous size of messages being transmitted by the transmitter while satisfying the quality metric for data elements reconstituted by the receiver.

32. The device of claim 28, wherein compressed message payload contents are selected so as to achieve a balance between message content, message payload size, and message transmission rates, in response to evolving trends in the data elements themselves.

33. The device of claim 2, wherein a data value that falls outside a range that can be represented within an associated current allocation of message payload in a current long-term, short-term, or residual message, or is otherwise anomalous, is accommodated by:

a. an indication, within the message, that the data value is out of range, and

b. utilization of a portion of the remaining message capacity to temporarily extend range of the value such that it can be represented, or

c. an indication, within the message, that the data value is anomalous and thus cannot be represented, is corrupt, or is missing.

34. The device of claim 1, wherein one or more data elements are encrypted prior to encoding into messages.

35. The device of claim 1, wherein one or more messages are encrypted prior to transmission, or are transmitted via encrypted channels or media.