GPS Receiver project

[hamster_nz]

I'm finally having some success from my GPS receiver (mostly software) project.

The data was captured from test points on the KiwiSDR GPS receiver board (http://kiwisdr.com/), which uses a Skyworks SE4150L front end.

The data was collected by using a Digilent Nexys2 FPGA board, using the EPP / USB interface to send the 16,368MHz bitstream to a PC for recording.

The bitstream has the GPS L1 (1575.42 MHz) signal down-converted to 4,092MHz IF.

From then on it is all offline processing.
- a couple of ms of data is heavily analysed to detect the C/A code from the Space Vehicles (SVs). It tests 16,368 alignments, over twenty one 500Hz-wide frequency bands)
- Each SV signal then tracked for a few ms, to find the peak signal power and drop out any false positives, and allow estimate of the freqency
- The signals are then locked on, using two PID-like control loops to track both frequency and C/A code alignment
- The I/Q data from the locked signal is then decoded to recover the BPSK Navigation data
- Framing of the BPSK is recovered using the Transfer Work and Parity information
- As the SV time calibration and Orbit data subframes are received from each SV, it is decoded to give the NAV information required.
- Every ms, a new snapshot of timing information can be taken, to deduce when the SV transmitted the signal

Code: [Select]

Id,  State, Orbt, Time, WeekNo, FrameOfWeek, msOfFrame, ChipOfCode, fracOfChip
01, LOCKED,  NO,YES,   1850,      109754,      2550,        481,          7 0  29 10 1....
02,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
03, LOCKED,  NO,YES,   1942,       38862,      4356,          6,         61 7   7 16 123..
04, LOCKED, YES,YES,   1942,       92209,      4354,        308,         43 7   7 14 1234.
05,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
06,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
07,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
08,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
09,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
10,ACQUIRE,  NO, NO,      0,           4,      5946,          0,          2 1  -1  0 .....
11,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
12,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
13,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
14, LOCKED, YES,YES,   1942,       92209,      4357,        431,         49 7   7 17 1234.
15,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
16, LOCKED,  NO, NO,      0,           5,      4346,        708,         57 4  29  6 .....
17,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
18,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
19,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
20,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
21,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
22,ACQUIRE,  NO, NO,      0,           0,       534,          0,          1 0  -1  0 .....
23, LOCKED,  NO, NO,      0,       92209,      4349,         35,         35 7   7  9 ...45
24,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
25,ACQUIRE,  NO, NO,      0,           0,       550,          0,          2 0  -1  0 .....
26, LOCKED, YES,YES,   1942,       92209,      4353,        127,         63 7   7 13 1234.
27,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
28,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
29,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
30,ACQUIRE,  NO, NO,      0,           0,         0,          0,          0 0  -2  0 .....
31, LOCKED, YES,YES,   1942,       92209,      4360,        390,         47 7   8  0 1234.
32,ACQUIRE,  NO, NO,      0,           0,         0,          0,          2 0  -2  0 .....
- This timing information (with an accuracy of about 30ns) is then combined with the parameters from the NAV data, to allow calculation of the SV's positions:

Code: [Select]

Location is ( -25130455.31126,   -7725302.46258,   -4938664.23183) @ 553258.49430079
Location is ( -16270394.15858,  -11271476.24594,  -17523671.16328) @ 553258.49748713
Location is ( -26148084.68495,   -4670089.21235,   -1576468.02291) @ 553258.49364161
Location is ( -16596519.86073,   -2385756.26196,  -20618396.91183) @ 553258.50017198

And this is then thrown through a linear equation solver to give a position solution, in Earth Centered, Earth Fixed coordinates, that is then converted to Lat/Long/Alt:

Code: [Select]

Solved is  (     -4582649.395993,        609390.121661,      -4379461.963727) @             0.003112 (alt       6368023.154693)
Lat/Lon/Alt :           -43.642632,           172.425379,                 27.3

I've still got to add a few features to the for things like the ionospheric delay, and I need to reliability lock onto signals that are on the edges between frequency bands during the acquisition phase (it sometimes locks with a 500Hz offset, causing the I/Q data to flip every millisecond). This will increase the number of tracked satellites, and improve accuracy.

Using only standard 'C' libraries only, it is 2300 lines of code. I've structured the code / algorithms used such that I can start off-loading things down into the FPGA hardware.

[hamster_nz]

After tweeking it is now tracking 5 satellites... much nicer fix.

[hamster_nz]

Just in case anybody is interested, I've just pushed all the source code up to GitHub:

https://github.com/hamsternz/Full_Stack_GPS_Receiver

[Ian.M]

As Github is based in California, its a good thing that the US has dropped the ITAR export control restriction on "receivers designed for producing navigation results above 60,000 feet altitude and at 1,000 knots velocity or greater", as prior to this change, if your code had got too good, you could have run afoul of the draconian ITAR regulations!

[hamster_nz]

As Github is based in California, its a good thing that the US has dropped the ITAR export control restriction on "receivers designed for producing navigation results above 60,000 feet altitude and at 1,000 knots velocity or greater", as prior to this change, if your code had got too good, you could have run afoul of the draconian ITAR regulations!

Good to know!

[hamster_nz]

Do you have any plan / interest to commit some test data from a satic location as you plotted in your examples along with some sample analysis output of that data to allow some unit / system testing with known data input and expected output to help validate any future algorithmic changes?

TLDR: Yes.

Evaluating the performance is quite interesting. Some things are quite simple to evaluate (e.g. the number of satellites you get a lock on with a given data set, time to first fix and so on), and some things are quite hard.

One of the harder things to evaluate is the tuning the control loops. Super stable loops are quite 'sloppy' as the parameter being actively managed drifts and is nudged in the right direction. Tuning the same loop up to track very tightly and it results in oscillations and sometimes even failure.  One thing I do want to do is to record datasets which have edge cases in it - maximum Doppler shifts and so on.

But what I will do is add some features to allow easily record what has been found, maybe a report of statistics on completion.

[NivagSwerdna]

Are you able to track the phase of the signals?  Pseudoranges and phase would be very interesting.  (VP Oncores that did this and could be used for differential surveying)

[hamster_nz]

Are you able to track the phase of the signals?  Pseudoranges and phase would be very interesting.  (VP Oncores that did this and could be used for differential surveying)

The input currently has been converted to an Intermediate Frequency, so absolute phase of the original carrier has been lost.

[KE5FX]

Nifty.  How does the sampling process work, though?  The example signal file at www.jks.com/gps/gps.html is "1-bit sign I-only data, not I&Q", with "sample rate 5.456 MHz, IF = 4.092 MHz."  That would mean that if it's not I/Q data, then it wasn't sampled properly. 

[hamster_nz]

Nifty.  How does the sampling process work, though?  The example signal file at www.jks.com/gps/gps.html is "1-bit sign I-only data, not I&Q", with "sample rate 5.456 MHz, IF = 4.092 MHz."  That would mean that if it's not I/Q data, then it wasn't sampled properly.

Although the iIF is at 0.75 of the sample rate it still all works just fine, and it doesn't need to be I+Q sampled. You are actually locking onto the 1kHz repeats of the Gold Code, not the IF.

As long the intermediate frequency you are testing with is within 500 Hz of the downconverted SV's carrier, and you have the Gold code aligned to about 0.5us, you end up with a stream of 1kHz I+Q pairs that rotate by less than 180 degrees per millisecond. By monitoring that signal's phase vector you are able to adjust the i.f. frequency to achieve a solid lock.

 I've also got samples files I've taken at 16.368MHz - 3x the data rate, take 3x longer to process, and the results are not 3x better.

[hamster_nz]

Discovered the magic needed to greatly improve the position fix - the early/late tracking of the Gold code is narrowed from +/- 1.0 chip to +/- 0.75 chip, greatly reducing 'slop'.

Performing a moving average on 11 solutions (over 0.55s) gives a circle with about a 10m radius - so it is now tracking to around 33ns.

[Kalvin]

Performing a moving average on 11 solutions (over 0.55s) gives a circle with about a 10m radius - so it is now tracking to around 33ns.

Excellent results! Do you know - or have you tried - how well the Kalman filter would perform compared to the moving average?

[hamster_nz]

Performing a moving average on 11 solutions (over 0.55s) gives a circle with about a 10m radius - so it is now tracking to around 33ns.

Excellent results! Do you know - or have you tried - how well the Kalman filter would perform compared to the moving average?

When receiving in a fixed location, a Kalman filter would have very little advantage, out of maybe weighting the different Space Vehicles based on signal strength. For a fixed receiver the limitation is really in tracking the 1.023MHz code chips - each are about 300m 'long' in wavelength. Currently I am tracking the phase of these within around +/-5% or so. It is actually a bit harder than this sounds, as there is a 50/50 chance that the next chip will be the same binary digit, so you don't have any phase transition half the time (e.g. "...11..." or "...00..." vs "...01..." or "...10...")

If the receiver is moving, then a Kalman filter would far superior to a simple average at predicting where you are - as it can take past history (as well as input from other sensors) into account. Even when moving at 100km/hr, a 0.55s average will be spread over 20m or so of travel, so would only lag about 10m from actual position.

[Kalvin]

Thank you, hamster. After your reply I did some googling, and if I understood correctly the Kalman filtering may improve the positional accuracy if some other sensor data, for example IMU sensor data or velocity data, is used along with GPS location data. So, if the IMU sensor or velocity sensor indicates that the device is at rest, the Kalman filtering should improve the accuracy? Thus if you know that the GPS receiver should be at rest - the IMU sensor and velocity sensors data will provide static zero information -  you probably could use Kalman filtering after all as you know that the device has not been moving.

I also tried to find whether a median filtering or Outlier Removal via Hampel Filter would outperform the mean filtering. As the GPS domain is strange for me I couldn't make any conclusions. Here is a nice summary about common filtering techniques:
https://se.mathworks.com/help/signal/examples/signal-smoothing.html

[Conrad Hoffman]

Excellent link on smoothing. Not a clue about this application, but I've recently been fooling with Savitzky-Golay filters. They're quite easy because you can use pre-calculated numbers for them. Their strength seems to be not displacing peaks in time. I'm doing audio processing where that's important. http://www.statistics4u.info/fundstat_eng/cc_savgol_coeff.html

Some BASIC code, if one were crazy enough to use that-

Code: [Select]

SUB SG_Smooth15(nSamples AS LONG, dLen1 AS LONG)                'Savitzky-Golay filter, # of points = 15
    LOCAL i AS LONG
    FOR i = 7 TO nSamples - 7
        @sData[i] = (-78 * @pData[i - 7] -13 * @pData[i - 6] + 42 * @pData[i - 5] + 87 * @pData[i - 4] _
                    + 122 * @pData[i - 3] + 147 * @pData[i - 2] + 162 * @pData[i - 1] + 167 * @pData[i] _
                    + 162 * @pData[i + 1] + 147 * @pData[i + 2] + 122 * @pData[i + 3] + 87 * @pData[i + 4] _
                    + 42 * @pData[i + 5] - 13 * @pData[i + 6] -78 * @pData[i + 7]) / 1105
    NEXT
    MEMORY COPY sData, pData, dLen1                             'copy filtered data to reference array for next run
END SUB                 

[hamster_nz]

Excellent link on smoothing. Not a clue about this application, but I've recently been fooling with Savitzky-Golay filters. They're quite easy because you can use pre-calculated numbers for them. Their strength seems to be not displacing peaks in time. I'm doing audio processing where that's important. http://www.statistics4u.info/fundstat_eng/cc_savgol_coeff.html

Some BASIC code, if one were crazy enough to use that-

Code: [Select]

SUB SG_Smooth15(nSamples AS LONG, dLen1 AS LONG)                'Savitzky-Golay filter, # of points = 15
    LOCAL i AS LONG
    FOR i = 7 TO nSamples - 7
        @sData[i] = (-78 * @pData[i - 7] -13 * @pData[i - 6] + 42 * @pData[i - 5] + 87 * @pData[i - 4] _
                    + 122 * @pData[i - 3] + 147 * @pData[i - 2] + 162 * @pData[i - 1] + 167 * @pData[i] _
                    + 162 * @pData[i + 1] + 147 * @pData[i + 2] + 122 * @pData[i + 3] + 87 * @pData[i + 4] _
                    + 42 * @pData[i + 5] - 13 * @pData[i + 6] -78 * @pData[i + 7]) / 1105
    NEXT
    MEMORY COPY sData, pData, dLen1                             'copy filtered data to reference array for next run
END SUB                 

I'll have to look into Savitzky-Golay filters - I've never heard of them before. Looks to be a specific form of a FIR filter. I had a quick look at the kernel - looks to be an inverted parabola? Humm...

[hamster_nz]

Over the weekend I got the Space Vehicle acquisition code to work reasonably well, and improved the visual display a little.

Currently takes 1m07 to run through 3m17 of data, and at the end is tracking eight SVs. With the test data I have, the first track is in 3 seconds, First fix from a cold start (with zero almanac) is 81 seconds. With cached NAV data it is 26 seconds.

I'm just about ready to connect it directly to the GPS frontend and process live data.

Code: [Select]


Update at  195.000    Acquiring 29
Channel status:
SV, WeekNum, FrameOfWeek,     msOfFrame,  earlyPwr, promptPwr,   latePwr, frame, bitErrors
23,    1942,       38729,  2001.1655120,     89461,   1110140,    125161,  12345       0
03,    1942,       92342,  2007.5771226,    271183,   4084861,    152405,  12345       0
14,    1942,       92342,  2006.9831913,    169201,   3817052,    223213,  12345       0
26,    1942,       92342,  2005.1505016,    131473,   2327256,    141497,  12345       0
31,    1942,       92342,  2010.4623747,    303547,   6850993,    251145,  12345       0
04,    1942,       92342,  2006.0406834,    134309,   3619075,    157964,  12345       0
22,    1942,       92342,  2010.4915444,    110075,   6369297,    146286,  12345       0
16,    1942,       92342,  1999.1110117,    123204,    988464,     62537,  12345       0



Space Vehicle Positions:   BAD TIME DETECTED - SV position dropped
sv,            x,            y,            z,            t
23, -10332457.50,  13443819.33, -20441422.71, 554054.00768279
 3, -10332457.50,  13443819.33, -20441422.71, 554054.00768279
14, -16698154.35, -12949614.61, -15924944.22, 554054.00704834
26, -25841408.28,  -4860111.89,  -4072673.60, 554054.00566661
31, -15305881.89,  -4074165.08, -21307244.57, 554054.01025238
 4, -24522414.32,  -7782155.47,  -7385698.32, 554054.00603940
22, -18729989.63,  10711501.63, -15288354.25, 554054.01043638


Solution ECEF:  -4582619.86,    609345.20,  -4379474.77,     0.00394
Solution LLA:     -43.64293,    172.42588,        10.66


[hamster_nz]

TLDR: The end result is noise in the noise in the raw fixes is down from around 15m RMS to 2m RMS (see attached plot of 1700 fixes, 10ms apart), for the same data set. It still wanders a little, but is not a random spray of fixes.

I spent a few nights improving my GPS receiver code a little. Lots of time extracting numbers and and graphing them.

The NCO value for tracking of the carrier frequency was oscillating slowly - not enough to drop lock - but enough to waggle BPSK constellation around a bit. Increasing the responsiveness of the IIR filter in the control loop got rid of that.

The early/late tracking for the Gold code was also improved. The bits in the code get stretched or compressed by the Doppler shift of the satellite, it is only by about +/- 3ppm, but enough to be problematic. If you don't allow for it you loose lock pretty quickly, and I make allowances for it by a small tuning factor I add every millisecond to the code phase, which is other wise locked to 1023 bits per millisecond.

Over the weekend I added a coarse and fine tracking. The coarse tracking runs for about 100 ms after acquisition, allowing the signal to be locked and an appropriate tuning factor to be found, and then the fine tracking takes over giving only minor nudges as needed.

The other big improvement was to use the Doppler shift of the carrier to predict initial amount of correction required at the during the switch to tracking (before a solid carrier lock is obtained). This allowed for a much quicker switch between the coarse and fine tracking modes - rather than taking about 5 seconds to settle down it now does it in about 100ms.

[albert22]

Thanks for sharing your nice project.
I am curious about your design choices:
The KiwiSDR already has an FPGA  you choose to use an external board, do you need it because the kiwsdr does not have a USB interface or there is another reason ?.
I wonder if the software could run on the BB instead of sending the data to the PC.
 
Regards

[Leo Bodnar]

Very nice project!  I have used SE4110 for ghetto direct GPS sampling and offline processing.  Yes, this is PIC24 in there.  I was only interested in a few sats acquisition and collecting pseudoranges at the time for later processing for a very low energy use project.

A lot of manufacturers get ITAR rules wrong - device is subject to export regulations when altitude AND speed limits are exceeded simultaneously.

Cheers
Leo

[hamster_nz]

Thanks for sharing your nice project.
I am curious about your design choices:
The KiwiSDR already has an FPGA  you choose to use an external board, do you need it because the kiwsdr does not have a USB interface or there is another reason ?.
I wonder if the software could run on the BB instead of sending the data to the PC.
 
Regards

It was a bit of a hack.

The other FPGA was used because the comms from the KiwiSDR to the BeagleBoard is set up for using a serial protocol, perhaps I2C or SPI depending on what you put in the FPGA. That was a little light on the bandwidth for what I wanted to do (16M 2-bit samples per sec, plus 33% for sequence numbers is about 5MB/s).

It was far easier to tack on at a few test points, and then use the other board where I know I can get 11MB/s and go to the laptop's HDD.

Once I get the design working well in s/w I intend to push the low-level channel code into the FPGA, but for now it is far quicker to experiment in software.