Full Stack GPS Receiver

From raw RF samples of the GPS L1 C/A signal to a position fix, in a completely open fashion

Similar projects worth following
GPS-enabled location and timing services has become a key technology in the current age of mobile technology. This project is to explore how they work, at a level below that of the standard NEMA sentences that most GPS modules provide for the user interface.

Although it includes the details of obtaining raw GPS samples at an intermediate frequency using a little bit of hardware and FPGA hacking, this project is a software GPS receiver.

Over time I expect to improve this (in both positioning performance and software performance), and eventually use it as a model for an open FPGA based GPS receiver.

Many debugging and instrumentation features will be added, allowing tweaks and tuning of the algorithms to be objectively measured.

I also hope that it will be used as a reference for others, who explore GPS technology at its lowest levels.

This project has a small hardware component.

Development boards and custom FPGA software were used to obtain data sets consisting of raw 1-bit samples, taken at 16.368 MHz. A complete set of GPS NAV data is transmitted every 30 seconds, so it is essential that at least a minute's data is captured - requiring 120MB of storage. Because of the importance of timing information, it is also essential that every sample is captured. To do this with the equipment I had on hand, a small FPGA-based solution is used.

The bulk of the project is software. The software has to perform the following actions:

- Acquire the GPS signals from the satellite - finding the approximate frequency and phase . All satellites transmit on the same frequency, but signals a Doppler shifted and have taken many milliseconds to travel the to reach the antenna.

- Locking onto the carrier. From a rough ball-park frequency we need to get an absolute frequency lock to ensure good data reception

- Locking onto the phase of the GPS C/A code that is transmitted by the satellite. This generates the sub-microsecond timing information which is required to produce a location fix. As light travels at about 300,000,000 m/s this needs to be resolved with about 30ns of accuracy

- Reception of 50bps BPSK data (the 'NAV' messages)

- Decoding of the NAV data

- Calculating the position and time at which the signals were transmitted

- Calculating the solution for the antenna's location.

  • 1 × Kiwi SDR board, plus BeagleBone Black This board was used as a source of the GPS samples, by attaching test points to the FPGA dev board
  • 1 × Digilent Nexus-2 FPGA board This board was used to capture the raw GPS sample information, buffer ir, and then provide the data stream to a PC over USB
  • 1 × Generic GPS active antenna Nothing special - Sourced from Deal Extreme
  • 1 × A laptop or any other computer

  • Search bands vs runtime vs channels found

    Mike "Hamster" Field05/08/2017 at 11:35 0 comments

    I performed some quick experiments of search time vs channels found. Here's the results:

    Search Bands | Channels found | Time
        21       |      6         |  48.202
        31       |      8         |  65.194
        41       |      9         |  92.639
        51       |      9         | 103.231
        71       |      7         |  99.600

    It looks like 31 or 41 is a good balance between runtime and performance.

  • Acquisition code working!

    Mike "Hamster" Field05/08/2017 at 05:37 0 comments

    Over the weekend I wrote some simple acquisition code. The method is rather simple, but effective.

    The +/-5kHz band is 31 evenly spaced local oscillators - each 330 Hz apart. At any given time, one Space Vehicle is being searched for, over all 31 frequencies. Each of 1023 phase alignments is tested for 2ms, and each test is offset by 1us from the last one. When a 'sniff' of a signal is received, a channel is assigned to it and it tries to achieve lock. If a better 'sniff' is seen, the channel is reset with the new values, and once again tries to achieve lock.

    The scheduling of which SV is being acquired changes depending on if lock is achieved, if any 'sniffs' were found, and an initial setting of priorities from a text file. At the moment, this uses about 15% of a CPU Core (out of a current total of around 30%).

    One problem was that when a channel starts to lock, it can fall one of two ways - either onto the correct frequency (yay!) or fall to 500Hz to one side (wah!). If it falls to one side the channel's in-phase value alternates between + and - every millisecond, rather than staying steady for 20ms. My fix for this was when you have half a second of bad NAV data, but still have a signal lock then adjust the NCO by 500 Hz, towards (and past) the initial frequency. This jumps the channel pretty much directly into lock.

    All in all the results have been pretty good: - It has been able to tease out 8 channels from a test data set:

    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
    Next effort will be to work out how to better keep the NAV bit message alignment in the presence of data errors (the cause of the "BAD TIME" for SV 32)...

  • Speed and accuracy greatly improved!

    Mike "Hamster" Field05/03/2017 at 10:39 0 comments

    I thought up a away to improve the speed - now uses about 3% of a CPU core per channel. The speedup also allows the early/late tracking that is used to follow the Space Vehicle's Gold code to be change from +/- 1 .0 chip (1/1023th of a ms) to +/-0.75 chip.

    This allows more accurate tracking, giving more accurate pseudoranges and more precise fixes. Adding an averaging filter removes quite a bit of the remaining noise too.

    Now I am in the ballpark of a commercial GPS module!

    Here is the console output as it runs, showing it as it tracks 7 channels:

  • Fast solutions now working

    Mike "Hamster" Field04/28/2017 at 09:42 0 comments

    I've got the fast version now generating positioning solutions. Here's a screenshot after processing 400MB of raw samples.

    196 seconds of data was processed for seven channels in 88.9 seconds, - 45% CPU usage. Looking Great!

    Now to work on to a speedy satellite acquistion code.

  • 200x speedup in tracking

    Mike "Hamster" Field04/26/2017 at 22:23 0 comments


    The initial version of the software was slow - it took over 6 hours to process 200 seconds of 16Mb/s data. This was expected, as the system was processing one bit at a time, one channel at a time, and was made that way to allow me to get the techniques correct before focusing on performance.

    I've completed a new version of the channel tracking code (in the fast_fsgps directory) that now processes data in 'gulps' of 32 bits at a time.

    This greatly speeds things up, and I can now process the same dataset in 110 seconds.

    Debugging this code was one of the harder things I've done. I hit odd compiler behavior (you can't shift an 'int' 32 bits) and just my own stupidity a few times, but it now works cleanly and very quick.

    Now to incorporate the NAV message code, to get position fixes in real time.

    It will also make control loop tuning a lot quicker to test.

    PS. I Just notice that I left some debugging code in place, where math was replaced with a loop to help find a fault. It is now 300x faster!

  • Tuning the early/late correlator

    Mike "Hamster" Field04/13/2017 at 20:46 0 comments

    I've been fine-tuning the the process by which the timing and phase of the Gold codes is followed. This has approximately halved the spread of the fixes.

    The points are 20ms apart, so an average of a second's worth of points would be less spread - absolute error is about 15m.

    There is still a bit of room for refinement of the process. I played around with a PID loop for a few nights, but it doesn't seem to be that suited to the process. It tends to bounce around due to the noise in the system. However the (a-b)/(a+b) discriminator (where 'a' is the late code power and b is the early code power) is great for assessing the relative performance of new methods.

  • ​Verifying the final steps in the solution

    Mike "Hamster" Field04/09/2017 at 11:27 0 comments

    Sometimes it is easier to work backwards. If you have positions for multiple Space Vehicles, and a position in Earth Centered, Earth Fixed (ECEF) coordinates, how can you verify it?

    An example position could be (3851787, -78307, 5066308)

    At there is a tool to convert from ECEF (in km, not meters) to Lat/Long/Alt.

    Converted to Lat/Long/Alt the output you get is:

    Latitude,Longitude, Height (ellipsoidal) from ECEF

    Latitude : 52.93473 deg N

    Longitude : 1.16467 deg E

    Height : 174.1 m

    This looks intuitively OK (somewhere in England, at a reasonable altitude). So the next step is to check this on a map. For Latitude, N is positive and S is negative. For longitude W is positive and E is negative.

    A quick search on Google Maps for "52.93473, -1.16467" will show where the solution is. For these numbers you should be somewhere just south of Nottingham in England.

    But what do you do if the final location is wrong?

    For debugging, you can also run this process backwards, but you will also need to find your altitude. For me the best tool for this is google Earth.

    Once you have latitude, longitude and altitude you can convert your known position to ECEF position using the above website.

    You can then run the calculations backwards to see what errors exist in your Space Vehicle positioning.

    For example, the five Space Vehicles used had the following X,Y,Z and transmit time:

    SV A ( 10796463, -11059512, 21468778) @ 466786.70444515
    SV B ( 25624907, 5493917, 6376860) @ 466786.69914821
    SV C ( 17562614, 17600801, 9306610) @ 466786.69828776
    SV D ( 12436654, 8851501, 21813026) @ 466786.70476175
    SV E ( 18466455, 6615577, 17512965) @ 466786.70642941

    The distance in each axis can be calculate by subtracting the known position (3851787, -78307, 5066308):

    SV A ( 6944676, -10981205, 16402470)
    SV B ( 21773120, 5572224, 1310552)
    SV C ( 13710827, 17679108, 4240302)
    SV D ( 8584867, 8929808, 16746718)
    SV E ( 14614668, 6693884, 12446657)

    The straight line distance can now be calculated with d = sqrt(x*x+y+y+z*z)

    SV A 20,925,018.76
    SV B 22,513,018.04
    SV C 22,770,985.88
    SV D 20,830,121.85
    SV E 20,330,171.52

    The time of flight for the signal can be calculated by dividing the distance by the speed of light (299,792,458 m/s):

    SV A 0.069,798,349
    SV B 0.075,095,344
    SV C 0.075,955,833
    SV D 0.069,481,807
    SV E 0.067,814,152

    If you add this time of flight to the transmit time they should all be equal:

    SV A 466786.774,243,500
    SV B 466786.774,243,555
    SV C 466786.774,243,593
    SV D 466786.774,243,558
    SV E 466786.774,243,553

    So in this case, the range of times of about +/- 50ns or so - equating to +/- 15m.

  • Finding an raw data source for initial experments

    Mike "Hamster" Field04/06/2017 at 02:58 0 comments

    It is very hard to find raw RF data for analysis. The only source I was able to find on the internet was

    It contains a 59 MB file, that has the following properties:

    • Sample rate - 5.456 MHz
    • Sample size - 1 bit per sample
    • Sample order - within a byte bit 0 is the earliest sample, and bit 7 is the latest sample
    • Intermediate frequency (IF) - 4.092 MHz.

    It is important to note that the intermediate frequency is above half the sample rate - this will cause signals to be aliased down to 4.092 - (5.456/2) = 1.364 MHz, and the spectrum to be inverted.

    If you download this file, and combine it with the project's C source, you will be able to experiment with this project and obtain a valid position fix. To do this, use the following command line

    fsgps -s 5456000 -i 4092000  gps.samples.1bit.I.fs5456.if4092.bin

View all 8 project logs

Enjoy this project?



JDat wrote 05/09/2017 at 19:32 point

What about COCOM limits? Will it work reliably with my high power rocket?

  Are you sure? yes | no

Mike "Hamster" Field wrote 05/09/2017 at 21:34 point

You would be better of logging the raw RF data and processing it after recovery. Without testing I suspect that some of the tracking loops would most likely unlock with sudden heavy acceleration, as they can't react quick enough.

If you did that you could process the same data multiple times, to get a good solution even over the expected "unexpected" discontinuity. 

It would also minimize your power/weight requirements.

  Are you sure? yes | no

Bruce Land wrote 04/07/2017 at 14:13 point

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates