7
$\begingroup$

For positioning using GNSS, a typical introduction text (example PDF) introduces the concept of pseudo ranges as roughly being the time between transmission of a GNSS signal by the satellite $s$ and the time of reception by the receiver $r$, multiplied by the speed of light:

$P = (T_r - T_s) \cdot c$

Then it is explained that $(T_r - T_s)$ can be determined by shifting the local (to the receiver) replica of the PRN code until the it lines up (correlates) with the received signal.

However, a PRN code for GPS L1 C/A is 1 millisecond long, and depending on where the satellite is, the travel time for the signal from the satellite to the receiver can be anywhere between about 65 ms (directly overhead) to 86 ms (just above the horizon). You can fit about 20 PRN codes in there. That means that there is ambiguity in the pseudo range, and none of the sources I have read (so far) addresses that ambiguity (they address the ambiguity in the context of carrier phase tracking, but that's another topic).

The aforementioned PDF mentions it briefly:

The basic information that the C/A code contains is the time according to the satellite clock when the signal was transmitted (with an ambiguity of 1 ms, which is easily resolved, since this corresponds to 293 km).

but without detailing how to "easy resolve it". (Left as an exercise for the reader?)

Question: how is the ambiguity in pseudo-range resolved in code-based positioning?

I'm maybe missing something obvious. Some possible answers I can think of, but cannot substantiate enough:

  1. When solving the navigation equation, you solve for the receiver clock error. This error term absorbs the common number of code cycles among all satellite channels.
  2. When starting the tracking, find e.g. the start of the telemetry word (or some other marker) in the navigation data in all satellite channels. Set the "nearest" satellite to 65 ms pseudo range and then proceed as in (1).
  3. There is some synchronization mechanism that allows the receiver to synchronize within 1 ms of GPS time.

I'm interested in answers for both GPS and Galileo in particular, but generally applicable answers are welcome too. Further references are also appreciated.

$\endgroup$
7
  • $\begingroup$ For a "cold start", once one receives a "broadcast ephemeris" from four satellites you have four satellite trajectories. I don't know, but it certainly seems that at least for terrestrial locations limited to the surface of the Earth there can't be a geometrical solution if one of the paths is assumed to be 293 km longer or shorter. For a "warm start" where there's a good estimate of where the satellite is based on recently saved ephemerides, this seems to be possible right away. It's possible that for space-based GPS location (from the ISS) the ambiguity might occasionally pose a challenge. $\endgroup$
    – uhoh
    Commented Dec 5, 2021 at 19:57
  • $\begingroup$ But how to prove that mathematically I don't know. $\endgroup$
    – uhoh
    Commented Dec 5, 2021 at 19:57
  • 4
    $\begingroup$ You can read the ESA GNSS book here. Chapter 5 describes all needed equations to compute pseudo-range measurement, including all delays to considerate. $\endgroup$
    – GuillaumeJ
    Commented Dec 6, 2021 at 14:26
  • 1
    $\begingroup$ @Prakhar the way I interpreted it for my answer is that if you look only at the C/A code and ignore everything else, then since the C/A code repeats exactly every 1 ms, you don't know how many full milliseconds have elapsed. The solution, of course, is don't ignore everything else. $\endgroup$
    – Ryan C
    Commented Dec 7, 2021 at 17:23
  • 1
    $\begingroup$ @RyanC that is indeed the gist of my question. Thanks for an elaborate answer; I had found an answer myself as well, which I will post too. $\endgroup$
    – Ludo
    Commented Dec 7, 2021 at 19:46

2 Answers 2

3
$\begingroup$

Nothing in navigation signal processing is as simple as most descriptions make it sound. Signal detection theory is essentially probabilistic, so algorithms make their best guesses at the likeliest thing that might have happened, but there's always an error rate. Solving for the integer offsets can be done, if you are sufficiently careful and clever in defining an optimization procedure, as investigated in this thesis[1] and this paper[2] by Sandra Verhagen and Peter Teunissen. However, there isn't one common offset: each PRN code carries its own ambiguity. There are also lots of possible tradeoffs between efficiency and accuracy, brute force and clever trickery, memory requirements and processor requirements, etc. To understand any of them in detail, however, needs some background in digital signal processing, which I am not able to provide here, though I will allude to some of it in passing.

There are many possible ways to modify or break the ambiguity. The two algorithms I'll describe are just the ones I find easiest to think in, which says little to nothing about their accuracy or efficiency. It may be helpful to you to read these MIT lecture notes[3] on GPS processing to give an introduction to other various things that have been tried for code tracking, and some comments on making comparisons between them.

Note: Ludo's question regards integer ambiguity in tracking the C/A code. This is not the same as most things you will find if you search on "GPS (or GNSS) integer ambiguity", which talk about tracking the phase of the signal. That's a different problem, that I won't get into here.

Algorithm One: Just Use a Longer Sample

One tradeoff in this case is that the longer the sample you use, the less ambiguous it becomes. Practical fast-response filters involve fancy tricks with multiple comparison voting schemes using many different lag shifts simultaneously to track a peak, as in Chapter 7 of this book[4], but you can get away with much simpler processing if you use a much longer input sequence. Yes, the C/A code repeats every millisecond, but that's not the only modulation present: the signal also contains the navigation message, which has a bit transition every 20 C/A repeats. Having just one or two bits of a nav message tells you very little, but if you use, for example, a full second of data, that's 50 bits of the nav message. That signal, of C/A and nav together, repeats exactly at most once per subframe, and in longer sequences might never repeat at all. When you autocorrelate this, you'll see a peak every 20 ms from just edge-detecting the nav message clock signal, but when you plot them all in a row you'll see the highest spike at the correct lag, with the incorrect ambiguous peaks sloping down away in both directions.

If the bit sequence in the sample you happened to snip out never repeats, there is no more ambiguity: equal length sections with different bit patterns won't correlate as strongly, so you can span the whole space of possible pseudoranges and pick the one best answer. If the bit sequence does repeat, then you have changed the ambiguity by the same amount you changed how long it takes the full C/A times Nav sequence to repeat, which should be the sampling interval (unless the bit pattern itself consists of a short repeating sequence). If you use a full second sample, the remaining ambiguity is not 300 kilometers, but 300 thousand kilometers, which is 3/4 of the way to the moon. You should have no difficulty picking which of those ambiguities might possibly make sense for a near-Earth object.

I do not recommend this as a practical approach! Its only requirement is to be easily explained. It is grossly inefficient, and its accuracy is limited by a basic physics effect you really ought to include in any GNSS processing, which complicates things but also helps break the ambiguity just by proper treatment. That is, since the satellites are in motion, and the receiver motion is not the same, there will be a Doppler shift. The receiver may be assumed to be stationary on the rotating Earth, or have its velocity estimated as part of the overall solution, or assumed to have its velocity known by other means and provided as an auxiliary input. There are errors and clever tricks and all that stuff for each of these, too.

Algorithm Two: Solve Simultaneously for the Doppler Shift

The importance of the Doppler shift to code acquisition is that the C/A code frequency is itself Doppler shifted, so its chip rate and its repeat rate are both increased or decreased by the same fractional amount that the carrier radio frequency is increased or decreased. If you correlate the received signal against your locally-generated C/A code, the Doppler shift will cause yours to misalign with the received signal, and give low scores for all lags, unless you somehow guess the right Doppler shift, and use it to modify your locally-generated code so it properly aligns with the actual bit rate received. This means what you really need to do is run the same correlation procedure against multiple different copies of the code that have their bit lengths altered by a range of possible observed Doppler shifts, then pick the pair of time delay and frequency offset which together give you the best fit. This is done by computing the Complex (or Cross) Ambiguity Function (CAF), and picking the highest CAF peak in two dimensions.

By this method of processing, in which you solve for both the time offset (pseudorange) and the frequency offset (Doppler shift) simultaneously, it is usually possible to get a better answer for each than you would have if you solved for the two offsets separately. It hopefully, but not necessarily, breaks the ambiguity by allowing you to look for inconsistencies, like plausible on their own time delays which CAF to infeasible Doppler shifts, or vice versa.

There is a large body of literature on CAF processing, to which Stein (1981)[5] is the standard extremely condensed introduction. I won't get into any of the gory details, except for one little complication that catches my interest as a physicist: the Doppler shift is proportional to range rate. Therefore, since any number calculated by signal processing must be based on at least some number of samples of the signal, and each of those samples corresponds to some amount of time, the true pseudorange will be different at the beginning of the sample than at the end. It varies continuously in between, so any calculated pseudorange must be some kind of weighted average that represents all the values the instantaneous theoretical pseudorange takes in the time interval of the sample. Therefore, there is technically not just one correct answer to what pseudorange ought to be deduced from a sample. The same thing holds true of the Doppler shift itself! It has one value at the beginning of the interval, and a different one at the end, but the CAF attempts to encapsulate all of that variation into a single best-fit number.

These effects together mean that since although, for signal processing in general, textbook treatments get more accurate and SNR grows as you provide longer samples, taking longer samples naturally turns CAF peaks from nice sharp spikes into low, broad lumps with ill-defined centers, because just one number for pseudorange and Doppler don't do it justice anymore. The faster the range and the range-rate are changing, the less time you can profitably use in computing a single CAF.

References

[1] Sandra Verhagen. The GNSS integer ambiguities: Estimation and validation. Doctoral thesis, Technische Universiteit Delft, 2005. ISBN 90-804-1474-3

[2] Peter J. G. Teunissen and Sandra Verhagen. GNSS Ambiguity Resolution: When and How to Fix or not to Fix? Symposium on Theoretical and Computational Geodesy 6 (143-148), 2008. DOI 10.1007/978-3-540-74584-6_22

[3] Thomas Herring. Principles of the Global Positioning System, lecture 7. MIT Open Course Ware, https://ocw.mit.edu/courses/earth-atmospheric-and-planetary-sciences/12-540-principles-of-the-global-positioning-system-spring-2012/lecture-notes/MIT12_540S12_lec7.pdf

[4] Kai Borre, Dennis M. Akos, Nicolaj Bertelsen, Peter Rinder, and Søren Holdt Jensen. A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach. Springer-Verlag, 2007. ISBN 978-0-8176-4540-3

[5] Seymour Stein. Algorithms for ambiguity function processing. IEEE Transactions on Acoustics, Speech, and Signal Processing 29.3 (588-599), 1981. DOI 10.1109/TASSP.1981.1163621

$\endgroup$
3
  • 1
    $\begingroup$ @uhoh good suggestion, thank you. on your next reread, please let me know if the new pieces clarify that answer. $\endgroup$
    – Ryan C
    Commented Dec 7, 2021 at 2:21
  • 1
    $\begingroup$ @uhoh here you go, section headings upon request. $\endgroup$
    – Ryan C
    Commented Dec 7, 2021 at 23:12
  • 1
    $\begingroup$ "This is not the same as most things you will find if you search on "GPS (or GNSS) integer ambiguity", which talk about tracking the phase of the signal. " - exactly, very frustrating when trying to research this...! $\endgroup$
    – Ludo
    Commented Dec 8, 2021 at 8:07
5
$\begingroup$

Ryan C's answer provides the crux and a lot of useful background information. The crux is:

Yes, the C/A code repeats every millisecond, but that's not the only modulation.

The other information that is modulated on the signal can provide a reference that is not ambiguous.

It is difficult to find details on how receivers solve these problems, probably because receiver manufacturers like to protect their good ideas, but GNSS-SDR is an open-source software defined GNSS receiver that does provide a lot of detail on how it works.

Their approach to pseudo-range computation is explained on their page about observables. The summary is that they use the time-of-week (TOW), which they extract from the navigation message. In GPS the TOW is transmitted every 6 seconds in the handover word (HOW) as part of each subframe of the navigation message. Because all satellites send transmit synchronously, the HOW (or actually, the preamble of the telemetry word that comes just before it) is a common reference point in all the signals from all the satellites.

The satellite with the earliest TOW is assigned a pseudo range of 68.802 ms (not explained, but it corresponds to a satellite that is above the receiver rather than at the horizon) and all the other satellite receiver times are related to that. The resulting set of pseudo ranges is then used as initial guess for the position and then further refined in subsequent iterations. (This is the same approach that is used in the book* that Ryan C references, explained in section 8.4.1.)

This article in "Inside GNSS" explains the same approach graphically. It also introduces a second approach that is straightforward to understand but apparently not used in practice: just wait for a marker in the navigation message on each tracking channel and start counting from there.

*) "A Software-Defined GPS and Galileo Receiver", K. Borre et al., 2007

$\endgroup$
10
  • $\begingroup$ I read somewhere that TOW has count resolution of 1.5 seconds. Does that mean the signal is transmitted at the 1.5 second boundary always? $\endgroup$
    – zephyr0110
    Commented Dec 8, 2021 at 3:11
  • 2
    $\begingroup$ @Prakhar correct. Basically, you use the TLM that comes just before the TOW in the message) as a reference point (there is a preamble in it that is always the same). And then you start counting in milliseconds from there, and then the last partial C/A code for sub-millisecond. This requires that your receiver clock is accurate enough to keep within a millisecond accuracy for at least 6s (until the next TLM comes), which is not that hard. $\endgroup$
    – Ludo
    Commented Dec 8, 2021 at 8:17
  • 1
    $\begingroup$ @Prakhar, the way I understand it is as follows. Using as standalone, all pseudoranges are modulo 1ms (one C/A code period). But assume that there is a "superframe" (SF) of these C/A frames and all satellite start the superframe at the same epoch, then the ambiguity is lifted: use the 1ms that is at the beginning of the SF. One way to have a SF structure is to use a (any convenient) field in the (repeating) nav message. The value of the field is irrelevant, only the epoch of its transmission is used (to flag the beginning of the SF). With the TOW, the SF repeats every 6000 C/A frames. $\endgroup$
    – Ng Ph
    Commented Dec 8, 2021 at 10:56
  • 1
    $\begingroup$ @Prakhar there always must be one constant marker in the nav data, otherwise you wouldn't be able to decode it. In GPS there is a 8-bit preamble in the TLM word for this purpose. $\endgroup$
    – Ludo
    Commented Dec 8, 2021 at 11:17
  • 2
    $\begingroup$ This is indeed a generic synchronisation problem with any TDM (Time Division Multiplex) transmission. Once the principle is understood, there is no math involved. The digital stream is organized into short frames (for fast sync), the short frames are organized in "superframes"(SF), and sometimes SF are organized into longer "megaframes". You need at least one flag, in order to count the SF (or MF). These flags are sometime called Unique Word (UW). Compare this to how we organize time: today is 10th day of the 12th month of 2021. $\endgroup$
    – Ng Ph
    Commented Dec 10, 2021 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.