Coarse Time Positioning - Inside GNSS - Global Navigation Satellite Systems Engineering, Policy, and Design

Coarse Time Positioning

Q: What is Coarse Time Positioning and how does it work?  

A: Coarse time positioning is used to provide a position fix using inaccurate time information when tracking sufficiently weak GNSS signals such that the navigation message cannot be extracted reliably. This article presents the key aspects of coarse positioning, including some of its challenges. To start, however, we begin by looking at the role of time within a GNSS receiver.

Q: What is Coarse Time Positioning and how does it work?  

A: Coarse time positioning is used to provide a position fix using inaccurate time information when tracking sufficiently weak GNSS signals such that the navigation message cannot be extracted reliably. This article presents the key aspects of coarse positioning, including some of its challenges. To start, however, we begin by looking at the role of time within a GNSS receiver.

Coarse Time Versus Fine Time
Typically GNSS receivers decode timeof- week (TOW) information from the navigation data transmitted by the satellites (SV). This is required to form the complete pseudorange measurements, which are then used to solve for four unknown states — 3D user position and receiver clock bias.

Under good signal conditions, a GPS receiver has to observe the satellite signals for six seconds to decode TOW information. However, under weak signal conditions, the receiver cannot always reliably decode TOW from the navigation data due to high bit-error-rate.

In the latter situation, the receiver can rely on external assistance data to compute a reliable position fix. Assistance information can include a combination of approximate user position, ephemerides, almanac, time, and frequency.

Of these types of aiding, time assistance can be classified based on the level of accuracy of the aiding received. For example, according to the 3rd Generation Partnership Project (see the Additional Reading section at the end of this article), mobile networks can provide time assistance on the order of microseconds or on the order of seconds. The former is often referred to as fine time assistance, when the accuracy is 10 milliseconds or better; and the latter is referred to as coarse time assistance, when the accuracy is on order of seconds.

Fine time assistance not only relieves the receiver from decoding TOW but also helps in accelerating signal acquisition through narrow search windows. Thus, fine time assistance significantly improves the time-to-first-fix (TTFF).

In contrast, coarse time assistance cannot be used directly. This is due to large errors in space vehicle (SV) position resulting from time error. For example, as shown in Figure 1 (at the top of this article), the maximum pseudorange rate of a GPS SV is about 800 m/s. A time-of-week estimate within ±2 seconds when used to compute satellite position translates to a maximum geometric range error of ±1.7 kilometers. User position derived using such measurements can be off by several kilometers.

What’s Coarse Time Positioning?
When only coarse time assistance is available, the receiver can either fall back to trying to decode TOW from the navigation message transmitted by the SVs or estimate TOW as an additional unknown in the navigation solution, that is, in addition to the usual four listed earlier.

Clearly, estimating TOW is advantageous in terms of

  • faster TTFF
  • obtaining a position fix under signal power conditions near or below data decoding threshold, and
  • energy savings obtained by using milliseconds of information to get a position fix instead of tracking SVs for six (or more) seconds to decode TOW.

Algorithms that rely on estimating TOW are referred to as coarse time navigation algorithms.

What’s Required a priori?
The following set of a priori information is typically required to get an estimate of the five states:

  • a valid set of ephemerides (to obtain satellite positions and thus estimated ranges)
  • approximate user position within a few kilometers
  • approximate TOW accurate to within a few seconds
  • sub-millisecond pseudorange measurements.

The sub-millisecond pseudorange measurement is the measure of code phase delay made by the code-tracking loop. These are modulo-1 millisecond measurements — corresponding to the length of the ranging code period which is one millisecond for GPS coarse-acquisition (C/A) code — and lack the integer-millisecond delay part to form an unambiguous pseudorange measurement.

These sub-millisecond pseudorange measurements are used to form a priori measurement residuals — which serve as observations for the unknown states to be estimated. Note that, because sub-millisecond pseudoranges are used as measurements, the resulting receiver clock bias estimate is also a sub-millisecond value and is correspondingly denoted as the “sub-millisecond clock bias”.

In order to avoid extremely large position errors (in excess of tens of kilometers), care must be exercised when using the sub-millisecond pseudoranges. Large position errors result from a combination of sub-millisecond clock bias, measurement noise, and sub-millisecond pseudoranges falling close to the one-millisecond boundary — thus leading to a one millisecond rollover on some measurements.

In other words, not all sub-millisecond measurement residuals carry the same receiver clock bias. There could be measurements with an additional integer-millisecond offset. In order to obtain a reliable estimate of user position, we must ensure that all sub-millisecond pseudorange residuals are consistent.

A numeric example from Frank van Diggelen’s book, A-GPS: Assisted GPS, GNSS, and SBAS, is as follows. A sample sub-millisecond pseudorange residual (Δt) vector in units of seconds is given below:

See Equation (1), (above right) 

where d1 and d2 are the range error due to a combined effect of user position error and TOW error, and represents the respective observation noise. If ε2, ε4 and ε5 are all negative, then the modulus operation would yield:

See Equation (2), (above right) 

As mentioned before, clearly the third measurement lacks an integer-millisecond offset. Hence, this set will lead to large position errors.

Correcting Integer-Millisecond Rollovers
Integer-millisecond rollovers can be detected and corrected by making use of the accuracy of a priori position and time information available. If the effect of a priori information inaccuracy on the geometric range error does not exceed 75 km, it can be shown that the difference between measurement residuals cannot exceed 0.5 ms. The relation between measurement residuals (Δt) of SVk and SVn, their respective unknown integer-millisecond offsets (ΔNk, ΔNn) and geometric range error (δr) is given by:

See Equation (3), (above right) 

It is desired that ΔNk – ΔNn = 0. Assuming the effect of noise is negligible, the following inequality holds true:

See Equation (4), (above right) 

Returning to the example in equation (2), and assuming the second measurement is chosen as a reference, clearly the third measurement would violate the condition described in equation (4). Correspondingly, a correction of +1 millisecond should be applied to the third measurement to produce the following corrected vector (Δ) of measurements:

See Equation (5), (above right) 

Rather, if the third measurement is chosen as reference, then the resultant vector of corrected sub-millisecond pseudorange residuals would be:

See Equation (6), (above right) 

Either of the above corrected vectors would work well, as the integer-millisecond offsets are common across all measurements in both cases. The fact that the integer-millisecond offsets differ between the two cases is inconsequential because this difference will be absorbed in the estimated receiver clock bias state.

The condition of |δrmax| ≤ 75 kilometers in equation (4) can be further relaxed when a reference SV is chosen such that the effect of SV position error and user position error along the line-of-sight is negligible, e.g., if the reference satellite is at zenith. In such a case, the maximum range error (δrmax) for any given SVk, kn, can be about 150 kilometers.

A word of caution: as with any estimator, adding an additional unknown (TOW error) will increase the uncertainty in estimating the standard four unknowns (user position and common clock bias). Nevertheless, the algorithm is capable — under appropriate conditions — of providing position solutions as accurate as in the four-state case.

Of course, achieving this depends on several factors, including measurement accuracy, satellite geometry, the correlation of the estimated TOW with the other states, and so forth. For more information, please refer to the resources listed in Additional Resources.

Thus, coarse time navigation is a useful feature in both standalone (for hot starts) and AGPS to get a faster position fix under demanding conditions.

Additional Resources
For information about assistance information, refer to:
3GPP TS 25.171 (2011), 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; “Requirements for support of Assisted Global Positioning System (A-GPS); Frequency Division Duplex (FDD), Release 10, Dt. 04-2011,” available here
For more details about coarse time algorithms and/or for alternate integer-millisecond corrections, see:
[1] Lannelongue, S., and P. Pablos (1998), “Fast acquisition techniques for GPS Receivers”, Proceedings of the 54th Annual Meeting of The Institute of Navigation, June 1–3, 1998
Muthuraman, K., J. Brown and M. Chansarkar (2012), “Coarse Time Navigation: Equivalence of Algorithms and Reliability of Time Estimates”, published in the Proceedings of the Institute of Navigation – International Technical Meeting 2012, 30 January 30–February 1, 2012, Newport Beach, California
van Diggelen, F., (2009), A-GPS: Assisted GPS, GNSS, and SBAS, Artech House, first edition
[4] van Diggelen, F., (2002), “Method and Apparatus for Time Free Processing of GPS Signals,” United States Patent, Patent No: US 6,417,801, Date of Patent: July 9, 2002