No, that’s not a typo. Mike wanted to go deep; really deep, and figure out what’s actually behind a GPS signal.

Probably every single one of us has used GPS (Global Positioning System), perhaps without even realising. Whether it’s on your phone, your Fitbit, your in-car navigation, or on a boat. The GPS really came into use in the mid 90s, but the last decade has seen exponential growth of GPS-enabled devices, and ready-access to tiny GPS receivers with unbelievable accuracy. Mike from New Zealand was curious about what’s actually behind GPS; and not just the satellites, but what data is being received and decoded in a split second, which tells us where on earth we are? We caught up with him to find out what he learned.

Many of us would have played with GPS receivers to obtain location coordinates, but rarely do we think beyond that output data. What made you take on the journey of understanding how the GPS works at a fundamental level?

When I was younger I spent a lot of time hiking and biking in the hills, using just a map and compass for navigation. When affordable hand-held GPS units first became available they were the most amazing of tools. Although they are now ubiquitous, I’ve always wondered just exactly how do they calculate where we are? In 2013 I saw an article on the Hackaday blog, about a homemade GPS receiver by Andrew Holmes. I put this on my project “to do” list, and set about slowly acquiring the hardware and knowledge required to make it happen.

That thirst for knowledge often sparks some interesting questions. What hardware did you need to receive the raw GPS data?

I used an inexpensive active GPS antenna from Ali Express, coupled to a KiwiSDR board from SeeedStudio.com. The Kiwi SDR board is actually aimed at being a Software Defined Radio that can be accessed over the internet, but also includes a GPS front-end. I then patched wires onto the test points, and used a Digilent Nexys 2 FPGA development board to capture the raw signal samples that are being received by the front-end of the GPS. They are then sent to a laptop to be recorded for offline analysis. Although the Nexys2 board is an old design and no longer available, it was a good solution for this project, as it has an interface that acts much like an Enhanced Parallel Port, allowing it to transfer the 2MB/s of raw data without missing any samples.

That’s a reasonable amount of bandwidth! How did you get started receiving and decoding?

The initial reference point was the “Global Positioning System Standard Positioning Service Signal Specification, which describes how the signal is transmitted, what data is encoded, how it is encoded, and how you can use the information to find your location.

Before I had the ability to record my own data, I scoured the internet and found a single set of raw GPS data; however, the only information available was the recording sample rate and the intermediate frequency of the GPS signal. With a lot of experimenting I was able to detect the signatures of the GPS Space Vehicles (satellites), and eventually decode that the signal was recorded in Nottingham in the UK, and even identify the corner of the building where it was recorded. The company in that building made navigation systems, and from this information, as well as LinkedIn, I was able to track down the person who recorded the data - who now works for the European Space Agency!

The initial version of my software was small (about 700 lines of C) and very simple (built for tinkering with the algorithms rather than speed). It took all night to process three minutes of data. The processing of GPS signals is amazingly simple - just XOR-ing three bits together, and counting how many are set, and once I had a working implementation I was able to speed it up by over 200 times! As the code currently is, it uses about half an Intel CPU core to receive data from eight different satellites. Now on my to-do list is to have the software process data in real time!

Wow - when you consider the amount of data crunching that equates to, it really does make commercial GPS receivers seem even more impressive! What unexpected surprises did you find amongst all that data?

One thing that I didn’t realise is just how high the GPS Space Vehicles’ orbits are, and how weak the GPS signals are. They are approximately 20,000km away, they transmit with about 25W of power, and the signals need to be received with a non-directional antenna (because you need to receive more than one at a time). They are in a “semi-synchronous orbit” - they orbit the earth every 12 hours.

Also, the data rates are also really, really slow - only 50 bits per second. This slow rate is why it takes 30 seconds to get a GPS position fix from a receiver “cold start” - at the slow rate, it takes this long for the Space Vehicles to transmit their orbital parameters and clock correction factors. It’s pretty amazing how the orbits of the Space Vehicles are known to such high precision - although they are orbiting at thousands of kilometres per hour, the orbit is known to within a few centimetres.

It’s a good thing that orbital precision is there when you have hundreds of millions (or billions) of dollars worth of satellite up there! Was there anything you can take away from the experience, other than a greater understanding of GPS?

It is amazing that the most advanced technology like GPS can be explored on a hobbyist’s budget. Things that would require a very expensive research lab and an equally expensive budget can now be built in a garage or on a workbench in the spare room! Another thing I discovered was that Digital Signal Processing (DSP) and Software Defined Radio (SDR) isn’t that hard, and can actually be quite interesting code to write. The range of inexpensive SDR hardware that has recently come onto the market has really created a whole new hobby, at the intersection of Ham Radio and Home Computing. If you want to get started in DSP, they have an excellent introduction is a book that is available for free.

That sounds like a great resource to get started with. We’re definitely in a world where “anything is possible” - imagine if Einstein lived in an iPhone era! What unexpected challenges did you face with this project?

It is really hard to make something this complex work correctly, without a proven implementation to compare against; all it takes is having one wrong value (e.g. the time of week is out by six seconds) and the position will be unable to be found. Also, I know virtually nothing about control loop theory, so I should probably read more about this and actually do a decent design, rather than just empirical testing.

iode       = 4B
M0         = -1.96696360836378514314048970846
delta_n    = 5.28236288876009244797414042094e-09
e          = 0.00913695234339684247970581054688
sqrt_A     = 5153.7914524078369140625
omega_0    = -0.248065636243747916767077299482
i_0        = 0.929460680202385813863941166346
w          = 0.581836914791512338496204392868
omega_dot  = -8.26677291570257726900144621112e-09
idot       = -2.81440294546514755206673727254e-10
Cuc        = -2.682209014892578125e-07
Cus        = 6.78189098834991455078125e-06
Crc        = 232.3125
Crs        = -4.875
Cic        = 4.470348358154296875e-08
Cis        = -1.0430812835693359375e-07
Toe        = 180000

This is an example of the Orbital Parameters for Space Vehicle 15. They allow the GPS receiver to calculate exactly where a Space Vehicle was when it transmitted the signal. ‘sqrt_A' is the square root of the orbit’s average distance from the centre of the earth - 26,561,561.671 metres.

1111111111000111000100111011001010111011110101000
1111010010101000001011111111010101010111101000011
1010010001100101101011001111010110001100111111001
0101010011001100101001111101001110000100011011001
0001010011011110111010101110011001110111011100111
0101001110100000111101101110000110001001010010110
0110100010001011010010111010011000101100000010100
1001011111011110001100011011101100001111001001110
0101100010000110111111100111000110101001010000100
0010010110111110101110001011100100001111101101010
1000101111011001110011111000001110010010101100101
1110010111000001010110110011000011010110111010001
0101111110100011100110111001010001101000000110010
0100010000010011011010011110011010101100001011101
1010001100001001111111011100011110000001110110110
0010100010011001000001101001001111011111000101010
1101000010100000001011011011110011110001000111111
0110001110101101010000110011011000001100000000110
110110101110101111000010101001000010110010011000
0010001001000000100000000010010010011010011010111
11001100011111001000111011111100001110000000

This 1023-bit string is one of the two special Gold codes that allow all the GPS satellites to transmit on the same frequency. When repeated It contains every sequence of 10 bits other than “0000000000”. Two different Gold codes are combined with the GPS data signal, making it like noise, but still allowing a receiver find the signal.

It’s true that proof of concept and a working product can often look quite different. What knowledge have you now gained regarding GPS that would save you time if you tackled this from scratch again?

There are lots of hidden, elegant ideas that have been used to make GPS work. The simplicity of how the special “Gold Codes” are generated, the way that the data is transmitted so as to make it simple to receive, the way you can minimise the CPU time required to acquire the Space Vehicle signals. Even what seems to be trivial, like the selection of the intermediate signal frequency, has hidden depths. Being aware of these subtleties and taking advantage of them could make a repeat of this project much simpler.

Awesome. The GPS system as a whole is definitely genius, and it seems there are some layers well beyond what most of us think about. What is in the pipeline for you next?

I’ve got a few projects on the go, I am working on some audio processing using a Raspberry Pi “plate” and an FPGA board, I am also playing around with ESP8266 WiFi modules and the MQTT protocol, in an attempt to make an environmental monitoring platform and security system for home. I’m also trying to reinvent/rewrite my FPGA website. We are just about to move to a new house, so I am also looking forward to setting up my new workbench.

Sounds fantastic. Thanks for taking us through your exploration of GPS signals!