A Full Stack GPS Receiver

The usual way of adding GPS capabilities to a project is grabbing an off-the-shelf GPS module, plugging it into a UART, and reading the stream of NMEA sentences coming out of a serial port. Depending on how much you spend on a GPS module, this is fine: the best modules out there start up quickly, and a lot of them recognize the logical AND in ITAR regulations.

For [Mike], grabbing an off-the-shelf module is out of the question. He’s building his own GPS receiver from the ground up using a bit of hardware and FPGA hacking. Already he’s getting good results, and he doesn’t have to futz around with those messy, ‘don’t build ballistic missiles’ laws.

The hardware for this build includes a Kiwi SDR ‘cape’ for the BeagleBone and a Digilent Nexus-2 FPGA board. The SDR board captures raw 1-bit samples taken at 16.268 MHz, and requires a full minute’s worth of data to be captured. That’s at least 120 Megabytes of data for the FPGA to sort through.

The software for this project first acquires the GPS signal by finding the approximate frequency and phase. The software then locks on to the carrier, figures out the phase, and receives the 50bps ‘NAV’ message that’s required to find a position solution for the antenna’s location. The first version of this software was exceptionally slow, taking over 6 hours to process 200 seconds of data. Now, [Mike] has improved the channel tracking code and made it 300 times faster. That’s real-time processing of GPS data, using commodity off-the-shelf hardware. All the software is available on the Gits, making this a project that can very easily be replicated by anyone. We would expect the US State Department or DOD to pay [Mike] a visit shortly.

Of course, this isn’t the first time someone has built a GPS receiver from scratch. A few years ago, less than 1-meter accuracy was possible with an FPGA and a homebrew RF board.

70 thoughts on “A Full Stack GPS Receiver

      1. Google “on the gits”
        > theGits – wikiPedia – The Gits were an American punk rock band, formed in Yellow Springs, Ohio in 1986. Known for their part in the burgeoning Seattle music scene of the early …

        Google “gits”
        > Ghost in the Shell is a Japanese media franchise originally published as a seinen manga series of the same name written and illustrated by Masamune Shirow.

        Google ex dee
        > plebians

  1. This kind of knowledge should be banned and authors convicted of supporting terrorism. Didn’t we have enought of terrorist attacks in Europe? Next thing you know there’ll be GPS guided VBIEDs rolling in Paris, Warsaw, Rome or Berlin.

    1. I think a standard off the shelf GPS would work fine for terrorists if they can’t find enough suicide bombers. Why jump on someone who is trying to have a deeper understanding of how GPS works?

      1. This was sarcasm. Also, in Warsaw we have no problems with terrorists. The only one we had recently was considered mentally impaired and was heavily inspired by our version of DHS.

          1. The politicians might not read HaD themselves, but somebody doing yet-another-report for them that makes terrorists from (white-hat) hackers and people like this might…
            (Of course my initial comment was more a joke, but somehow not entirely. :-/ )

      2. Seconded, the rules prevent you from going supersonic and high (in very simplified broad terms). They stop you making an icbm and not much more. You could already use a cheap gps module for a tomahawk missile type device. Sometimes it is worth looking at the present options in detail and thinking.

        1. Me I dont see why there would be a problem with getting from point A to point B with out a GPS.
          There are so many things that you can use to get close with out a GPS and then use the GPS when you are close, or so many other things to use when you are close to point B.
          If you have the will you can do anything.
          Im just glad they are not any smarter.

    2. I think people who want to suppress knowledge should be banned from here as terrorists already have access to ready built mil spec guidance systems on the black market.

    1. COCOM limits on commercial GPS. You can’t buy a GPS receiver that can give a position when it’s over 18000m or going over 1900km/h. This is so the average person can’t build a precision guided missile.

      1. Though the average person would have a lot of difficulty building the rest of the ballistic missile they’re not exactly small or cheap.
        Ironically a large crude missile such as something alone the lines of an Atlas is a lot easier to build than something like a Minute Man which is why there was a decade between them despite the US government burning through trucks loads of money to get there.
        Of course once you can build something along those lines you probably also have the resources to build a star tracker and precision gyroscopes.
        The Atlas managed a CEP of 1500 feet using a very primitive guidance system.

      2. If NK really wanted to nuke the USA they’d load up a bomb into a shipping container and detonate it via remote Imarsat once the GPS tells them it’s docked in LA.
        Still using GPS within the rules and not violating ITAR :)

    2. Brian is referring to the GPS regulations within ITAR that you can’t have a GPS receiver that will work above a certain speed OR above a certain altitude. The limits are 18,000m altitude or 512m/s.
      Obviously you can certainly make systems that are ITAR controlled even with a COTS GPS (cruise missiles and self guided torpedoes are moderately frowned upon), but they try to discourage it

      1. Brian is referring to regulations, which say you can’r have gps receiver that works above certain speed AND altitude. When your device is BOTH too fast and too high, it should stop working. But many device manufacturers implement it as OR condition as you said, so only one condition is enough to cripple your device, so you have to watch for it when you make high altitude balloon.

        1. There’s a big difference between “can not” and “may not”.

          After hearing “you can’t do that”, the hacker’s response is “clearly I can, since I just did”.

  2. Seriously – this guy re-invents the wheel in DSP (an amazing feat) and this thred is now about terrorism? WTF??
    Can we talk about DDS tuning and zeroing out Doppler effects? Perhaps A discussion about Costas loops or gold-codes? Please lets take this from the criminal justice campus to the engineering campus.. Here – I will start:

    How did he recover (with nanosecond accuracy) the carrier freqency from the 1.x Mhz c/a chipping? How did you do your coarse acq?

    1. I think the first guy was a troll and everyone fell for it.

      It’s excellent that someone is trying to do this and document their work. My interest in GPS is not about positioning so much, but getting accurate timing information out. To that end, most GPS receivers have a PPS output, but most generate that output from a GPIO pin on some sort of microcontroller-like gizmo that has its own internal clock that’s not necessarily synchronized with GPS. The result of that is quantization error. Some timing receivers include an NMEA sentence that tells you what the most recent quantization error was so that you can compensate for it yourself.

      But I wonder if this guy’s approach might result in the ability to obtain timing information in a way that doesn’t result in the quantization error being in there in the first place. And furthermore, can he get timing results that are on a par with what existing commercial solutions can achieve?

      1. With this setup I can tell when each sample was taken, down to about +/- 10ns or so. However, due to the FIFO on the FPGA board, and USB bridge on the FPGA bard, and the whole USB stack I can’t tell exactly what time on the CPU processing the data.

        It would be possible to run a counter on the FPGA board, and then push back a calibration value e.g. on clock x of 16368000 set pin high for 163680 cycles) to generate a referenced PPS signal (although it would lag slightly). You could even use DDR or SERDES on the FPGA pin, to get sub-cycle accuracy on the rising edge.

        If the calculation was closer to the ADC hardware the result would be better.

  3. Guys! It’s no 90-ties. High altitude balloons fly 30+ KM with GPS without any problems. So positioning over 18 KM works. Been there done that. Few weeks ago got problems with 2 KM rocket. There is limit 4G for GPS. That’s a problem. But. There are plenty of projects on internet with open source GPS. Check Copenhagen suborbitals. Expensive, but with source on github. Comment 4 lines and COCOM isn’t problem (in theory). Also Google for rtl-sdr gnss. And my favorite: http://www.aholme.co.uk/GPS/Main.htm

    Everything started with one clever HAM guy, who build DIY GPS receiver on 1992: http://lea.hamradio.si/~s53mv/navsats/theory.html

    So, question: What COCOM?

    Just pool finger out of your *ss and look around.

    About project: this is interesting, because it’s look portable and possible to put on high power rocket if done correctly.

    1. If you put the acquisition on the rocket, recorded 2MB/s during the launch and recovered it, you could then process it from the comfort of your laptop.

      This would allow you to account for the kick in the guts the control loops get from the sudden heavy acceleration.

      PS. Not sure how good crystals and SAW filters are with the stresses of launch – it might detune them a little.

      1. “PS. Not sure how good crystals and SAW filters are with the stresses of launch – it might detune them a little.”

        A problem solved long ago. I have a paper on quartz crystals in missiles from the 1950’s.

  4. For all the people who are telling me I should not be receiving signals, I’ve added these two lines.

    if(sqrt((*sol_x)*(*sol_x)+(*sol_y)*(*sol_y)+(*sol_z)*(*sol_z)) > 6373133)
    sol_x = sol_y = *sol_z = 0.0;

    There – fixed that for you. Can we now talk tech? Please?

    1. Excellent job, Mike! I’ve long wanted to do something like this, and even read through the book “A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach (Applied and Numerical Harmonic Analysis)”, but never did anything with it.

  5. On that note, can anyone recommend off-the-shelf GPS modules who implement the “and” interpretation of the rule, and how they implement it? (E.g. whether they recover right away after dropping out of the conditions, 1 cold-start time later, or only after a powercycle.) Just after designing an Inventek ISM420 into a gadget, someone wanted to use it on a sounding rocket, and asked if it would continue working at altitude. The answer from mfg (eventually) was a resounding no.

  6. Came here to see some sweet VHDL/Verilog then I found a pure C project. =(.

    Also the way I “would have” faced it was using ephemeris data obtained by SIRF, not NMEA. What do you think?

    1. Oh, I think we hit a name space collision here – no NEMA sentences are involved. The Space Vehicles transmit 1500-bit “NAV” frames as five different 300-bit subframes,

      Subframe one has time correction factors, Subframe two and three contain the ephemeris data, Subframes four and five pages of the almanac, which has cut-down ephemeris data for other Space Vehicles (I don’t use this). The C has to do all the orbital calculations to get the Space Vehicles positions.

      … and hopefully I will get around to pushing the SV tracking to VHDL once it is working well in software.

  7. Mike, you get my seldom earned “slow clap” (think officer and a gentleman) — Hats off to you and our DSP and VHDL /verilog efforts. You are one of the few “greats”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s