GPS Pseudo-range and Positioning

[chingkui]

I am trying to see how a GPS works by analyzing the data it collects. Basically, I have the pseudorange, satellites positions and also the GPS receiver location data I got from a GPS, and I was expecting to reproduce the positions reported by the GPS to high accuracy by solving the pseudorange equations based on the satellite locations and pseudoranges reported at the same instance. However, I found out that the best I could get is within about 0.5 meters and sometimes, the deviation is as big as 100+ meters (most of the cases, the deviation is around 1 to 10 meters). I don't think there is any error in my pseudo-range solver, and I begin to suspect that a GPS doesn't only use pseudo-range information for positioning, as I have made the following observations:
1) Sometimes, the GPS could only obtain less than four pseudo-range/satellite location data, and the pseudo-range equations are unsolvable. But the GPS still would produce positioning data;
2) The positioning solution of the pseudo-range equations could fluctuate greatly from time to time, while the variation of the positioning data the GPS gave me appear to be much smoother.
Does anyone know what algorithm a GPS usually use? Do they use some form of Kalman filtering or maybe other data that I have not considered?
Thanks.

 

[jbunniii]

I am trying to see how a GPS works by analyzing the data it collects. Basically, I have the pseudorange, satellites positions and also the GPS receiver location data I got from a GPS, and I was expecting to reproduce the positions reported by the GPS to high accuracy by solving the pseudorange equations based on the satellite locations and pseudoranges reported at the same instance. However, I found out that the best I could get is within about 0.5 meters and sometimes, the deviation is as big as 100+ meters (most of the cases, the deviation is around 1 to 10 meters). I don't think there is any error in my pseudo-range solver, and I begin to suspect that a GPS doesn't only use pseudo-range information for positioning, as I have made the following observations:
1) Sometimes, the GPS could only obtain less than four pseudo-range/satellite location data, and the pseudo-range equations are unsolvable. But the GPS still would produce positioning data;
2) The positioning solution of the pseudo-range equations could fluctuate greatly from time to time, while the variation of the positioning data the GPS gave me appear to be much smoother.
Does anyone know what algorithm a GPS usually use? Do they use some form of Kalman filtering or maybe other data that I have not considered?
Thanks.

The pseudoranges aren't noiseless; 0.5 meters is about as accurate as you can hope for if you're using only the civilian signal. A 0.5 meter error in range corresponds to a 1.6 nanosecond timing error, which is literally down in the noise considering that the code chips are nearly a microsecond long and that the signal levels are low enough that you can only measure the "average" satellite range over an interval of milliseconds or longer.

Most navigation algorithms will attempt to produce a solution even if you feed them fewer than four measurements (particularly if you have fed them >= 4 recently); they may do this by assuming that the altitude and/or local clock frequency have not changed since they were last calculated. To the extent that these assumptions are wrong, the position error will grow.

Also, the geometry even with four satellites can be poor, causing inflated position errors, and this problem grows if you have fewer satellites.

Yes, most commercial receivers use a Kalman filter or similar. Are you performing a straight least-squares solution?

Finally, how have you verified that you don't have any algorithmic or programming errors in your solution?

 

[chingkui]

Yes, most commercial receivers use a Kalman filter or similar. Are you performing a straight least-squares solution?

Finally, how have you verified that you don't have any algorithmic or programming errors in your solution?

Yes, I am looking for a least-squares solution. For the cases when there are only four satellites, I am sure my algorithm is correct, as the least-square solution is also the exact solution, and I have verified the solution by subsituting them back to the equations. But for the cases with more than four satellites, I am only sure the solution I got satisfy the necessary conditions for optimal solutions, and the algorithm usually converge, whether it is actually optimal, I have no proof of that. The algorithm I am using comes from the textbook "The Global Positioning System & Inertial Navigation" by Farrell and Barth, it is an iterative algorithm based on linearization of the pseudorange equations. It can be shown that the terminating condition gives a stationary point of the least square function. However, I am not sure if that would definitely be a global optimal solution mathematically. In those cases the algorithm doesn't converge, I suspect that it is caused by bad geometric configuration of the satellites. Basically, I am making an assumption that whenever the algorithm converge, I am getting an optimal solution, though I have not yet been able to prove that rigorously.

Do you know of any algorithm that would definitely give an optimal solution?

Thanks.

 

[jbunniii]

Yes, I am looking for a least-squares solution. For the cases when there are only four satellites, I am sure my algorithm is correct, as the least-square solution is also the exact solution, and I have verified the solution by subsituting them back to the equations. But for the cases with more than four satellites, I am only sure the solution I got satisfy the necessary conditions for optimal solutions, and the algorithm usually converge, whether it is actually optimal, I have no proof of that. The algorithm I am using comes from the textbook "The Global Positioning System & Inertial Navigation" by Farrell and Barth, it is an iterative algorithm based on linearization of the pseudorange equations. It can be shown that the terminating condition gives a stationary point of the least square function. However, I am not sure if that would definitely be a global optimal solution mathematically. In those cases the algorithm doesn't converge, I suspect that it is caused by bad geometric configuration of the satellites. Basically, I am making an assumption that whenever the algorithm converge, I am getting an optimal solution, though I have not yet been able to prove that rigorously.

Do you know of any algorithm that would definitely give an optimal solution?

Thanks.

The solution is only as good as your measurements. Where are you getting your pseudoranges from? Do you know anything about what sorts of algorithms the receiver used to produce them? (Generally some sort of carrier and code tracking loops, but these can vary greatly from one receiver design to another, resulting in different error statistics on your pseudoranges.)

Also, where are you getting your satellite positions from? Are you using the 50 bit per second data from the satellites to decode the almanac and ephemeris, and computing the satellite positions from these? Are you sure that you are computing them at the right instant of time?

No, there's no optimal solution in general. The optimality of either the least-squares or the Kalman filter solution assumes, among other things, that the measurement errors are Gaussian, but that is not the case for pseudoranges. Even if you obtained a solution that correctly modeled the measurement error, you would still have unpredictable user motion and clock error causing unmodeled errors in velocity, acceleration, and higher derivatives.

And that doesn't even take into account real-world effects such as uncompensated atmospheric delays, multipath, cross-correlation between different satellites' PRN codes, interference from other sources, nonlinearities in the receiver electronics, quantization effects in the digital processing, etc. All of this stuff is probably present in your pseudorange data to some degree.

 

[chingkui]

I try to find out the information about the receiver, but couldn't find what algorithm it is employing.
Right now, I have this question occupying my mind, how does a receiver determine what time the message it just received is sent? Is it just by the time stamp? Different part of a message is sent at a different time, and the error can be big in terms of distance. Just as you said, how do I determine what is the right instant of time?

 

[jbunniii]

The civilian GPS signal is organized as follows:

1 frame per 30 seconds
5 subframes per frame (1 subframe = 6 seconds)
250 bits per subframe
20 milliseconds per bit
1023 C/A chips per millisecond

GPS time is by definition exactly 604800 seconds per week, and rolls over to 0 once per week. No leap seconds are added. GPS differs from UTC by an integer number of seconds (currently 14 I believe).

The signal transmitted by each satellite is aligned such that "chip 0, millisecond 0, bit 0, subframe 0, frame 0" starts precisely at the GPS week rollover.

The data bitstream includes a time tag for each subframe, so in principle if you know what the time is modulo 6 seconds, you add that to the time tag and that's the GPS time.

You can achieve this knowledge one step at a time as follows:

1) Align your replica C/A code with the one in the incoming signal. You do this by correlating with the signal and looking for the peak. The offset that gives you the peak is called the "code phase" and can be expressed in fractions of a millisecond. Once you know the code phase, you are aligned with the incoming signal modulo 1 ms.

2) A GPS data bit is 20 ms long, hence you might be at one of 20 possible alignments relative to the data bits. If you accumulate the magnitudes of 20-ms integrate-and-dumps at each of the 20 alignments, you will over time see a triangular shape. The "bin" with the highest magnitude corresponds to the correct alignment. Once you have this, you are now aligned with GPS time modulo 20ms.

3) The subframes contain certain bits that you can use to synchronize yourself with the subframe. This is called "frame synchronization". Once you have done this, you are aligned with GPS time modulo 6 seconds.

4) The subframes also contain a time tag that tell you the GPS time at which the subframe started. (This increments by 6 seconds each subframe.) Decode this and add it to your modulo-6-second time, and voila, you have total GPS time.

Normally you only have to do steps 2-4 once per satellite. As long as you maintain code synchronization, there's no way you can lose bit or frame synchronization. All you need to do is keep track of code phase and how many C/A intervals have elapsed since synchronization.

Since both the satellite and user are generally moving, and the user's time reference drifts relative to GPS time, the code alignment will also drift unless you track it using a feedback loop of some kind. There are a lot of architectures for doing this; a simple one compares the correlation energy at two delays that are, say, one chip apart. The difference is proportional to the time misalignment. You can then use this to adjust your time alignment.

If you maintain this alignment, then at any given instant you can sample your code NCO, along with these numbers, which you keep track of: milliseconds since start of current bit; number of bits into the subframe; GPS time at start of subframe. Add all this together to get a very precise GPS time. The sampling instant pinpoints a very specific point on the GPS signal itself. The time you calculate in this way means "this point on the GPS signal was TRANSMITTED by the satellite at this GPS time."

You also need to know the time of the sampling instant according to your local clock. Then take the difference of these two times - that is precisely your pseudorange in units of time - simply multiply by the speed of light to convert to distance, if desired.

It's called a pseudorange because you are using two different clocks: you are comparing the following two times:

1) the GPS system time at which the signal was transmitted
2) the local time at which the signal was received.

If local time = GPS time, then pseudorange = range. But local time is normally at some unknown offset from GPS time, and the unknown offset changes with time. Fortunately this time offset is the same for all satellites, so it's just one extra unknown. The navigation algorithm solves for it along with user position and velocity, as long as you have enough satellite measurements for it to resolve this. (It needs >= 4 satellites in general.)

 

[tictaclp]

I put two navegator working together , tracking , but in a fixed position to get a plot of the solutions. They were different . One navegator gave me a 5m*10m rectangle and the other a 10m*15m and crossed.
Other thing. Observations or measurings(pseudoranges) are quite of the same precision. Depending your positional precision on your geometry and your accuracy on what satellites are in your solution.
If the number change and or the satellites change you will have a different solution most of the time less than 10 meters different.
But if you can get the same satellites you can check a lineal dimension at the meter level .

 

[agmateo]

how does the ground gps receiver compute the distance of the user? Is it ratio and proportion of similar triangles? cosine law? linear algebra using matrices or gauss elimination?

 

[tictaclp]

It is not clear for me what means for you "the distance of the user" . Thanks