Homemade GPS Receiver | Hacker News Reader

Homemade GPS Receiver

holmea.demon.co.uk

299 pointselemeno66 comments

That page is amazing. I'm astounded that someone can build a GPS receiver from scratch, not to mention writing the code that interprets the GPS signals. The difficulty is mind-boggling!

There's some wonderful quotes in the page that just hint at the complexity involved:

"Originally, by not transforming satellite positions from earth-centred-earth-fixed (ECEF) to earth-centred-inertial (ECI) coordinates, I was effectively ignoring Earth's rotation during the 60 to 80 ms that signals were in flight."

"The above solutions were generated without compensating for ionospheric propagation delays using parameters in page 18 of subframe 4 which should be applied because this is a single frequency receiver. Ionospheric refraction increases path lengths between users and satellites."

Some of his other projects are pretty impressive as well - I'm taken by the FORTH computers myself.

This is immensely impressive.

What strikes me is that the math and all the corrections would not be all that alien to a sextant user from 100 years ago. To determine position using a sextant you also start with an estimated position and an accurate clock. You compensate for drift during your measurements, for dip and refraction, you solve the equations for several celestial bodies etc.

Less than 100 years ago, GPS wasn't a nav tool until the mid 90s. Astro nav was the standard right up until then and is still taught to masters today. We have calculators for atmospheric diffraction but the long hand method is still used.

Fun fact, the Boeing 747 features a sextant port for convenient celestial navigation in flight.

Wow.

Was it ever used?

Can't find much information about it, but what I did find says that it got significant use in the early years of the 747. It makes sense, as the 747 long predates civilian GPS, and other electronic navigation techniques were not completely reliable for long flights. I don't know that there were many radio beacons available for long over-water flights, and pilots probably liked cross-checking their INS.

While searching, I was reminded of another interesting fact, that the SR-71 had a fully automated celestial navigation system that could get still a position fix on the ground in the middle of the day, and was more accurate than an INS on long flights.

  that could get still a position fix on the ground in 
  the middle of the day

What! Surely the sky would outshine the stars... did it use light outside of the visual spectrum?

Check out fancyketchup's sibling comment to yours, which shows far more knowledge than I have. Short version: infrared.

The IR filter helps, but (this is sort-of speculation because I don't have any knowledge of the system outside of reading the patents), I think the major processing gain comes from the shutters. In fact, I think the patents said that it could work (albeit much less effectively) without the IR pass filter.

The basic idea is a form of synchronous detection or lock-in amplification: The shutters are arranged so that a point source is occluded at a fixed frequency, while an area source will be only partially occluded at any given time. Due to the way it is designed, area sources should add little to the time-varying component of the photodetector signal. The lock-in amplifier is essentially a very narrow notch filter (centered at the "star occlusion frequency"), so it completely rejects the DC component from the sky.

There is a little more to it than what I'm writing, mainly because you need to not just detect the point source, but also estimate the star's position within the field of view (which IIRC is done by comparing the phase of the time-varying star signal to a reference point on the shutters).

You're right, that is by far the more interesting part of the system. Thanks for elaborating, that's really cool.

Jupiter, Venus, Sirius and, at the very limit, even Canopus are visible with the naked eye during the day. It's just hard to "get a lock" on them because contrast is so low. But if they are close to a large, fixed, easily visible reference (the Moon, a tall building, a tree) then suddenly they pop into view. The first two are easy, the third is doable in good conditions, the last is difficult and requires excellent conditions and a keen eye.

You need more than a few stars for navigation, of course, but I would assume with a good sensor, proper filtering, and nice optics, a computer could see enough stars during daytime to perform navigation.

There are some really interesting patents related to this (search for variations on celestial navigation at USPTO or Google Patents). Apparently it is possible to track stars in full daylight using a single photosensitive device behind an IR-pass filter (stars radiate IR, but the atmosphere doesn't scatter significant IR from the sun) and a clever arrangement of shutters. Several of the most interesting patents are refinements to allow the system to work well during dawn and dusk, when the background brightness of the sky varies greatly with elevation above the horizon.

http://virginflightdeck.blogspot.com/2010_09_01_archive.html

search for "periscopic sextant"

Funner fact, the Trident II D5 ICBM shoots up to low altitude orbit and then fixes its location with a star sight! GPS is assumed missing in the global thermonuclear war scenario.

Except for one thing. GPS computation is one of the few things we deal with in daily life that actually requires relativistic compensation to be accurate. The satellites are moving so quickly (relative to the receiver) and experience such less gravity, that the rate of time passing for them is measurably different than the rate of time passing for the receiver. Enough so that if you did not compensate for the difference in the rate of time-passage you'd actually be quite off in your location measurement.

Some back-of-the-envelope numbers (and precision calculation) here: http://physics.stackexchange.com/questions/1061/why-does-gps...

And where are those corrections taken into account in this page?

Some of the relativistic error (time dilation) is taken care of on the satellites themselves by tweaking the 10.23 MHz frequency generators to run at 10.22999999543 MHz.

The author actually mentions a third source of relativistic error without saying it's relativistic error: the Sagnac effect. ("Originally, by not transforming satellite positions from earth-centred-earth-fixed (ECEF) to earth-centred-inertial (ECI) coordinates, I was effectively ignoring Earth's rotation during the 60 to 80 ms that signals were in flight.")

The Sagnac skew would still occur in a non-relativistic universe. All that's needed is a finite speed for light.

However, yes, relativity further complicates it.

It's interesting to consider that GPS as a concept simply wouldn't work at all if the speed of light were infinite.

I think you'll find a whole lot more wouldn't work if the speed of light were infinite. Life, for example.

"Were there an infinite value for the speed of light, light itself would not exist at all."

http://www.scientificamerican.com/article.cfm?id=why-isnt-th...

These paragraphs are very deep, and quite revelatory as to the nature of relativity and the Universe itself:

The speed of light is strange in that it has the same value independent of the relative velocity between the source and the observer. This fact is an experimental one that can only make sense if relative motion changes the relationship between space and time intervals to keep the distance covered by light per unit time the same for all observers.

The fact that space and time must get mixed up to keep the speed of light constant implies that, in some sense, space and time must be the same, despite our habit of measuring space in meters and time in seconds. But if time and space are similar to the extent that they can be converted one into the other, then one needs some quantity to convert the units--namely, something measured in meters per second that can be used to multiply seconds of time to get meters of space. That something, the universal conversion factor, is the speed of light. The reason that it is limited is simply the fact that a finite amount of space is equivalent to a finite amount of time.

Refer to method GetClockCorrection() of class EPHEM at line 155 of file ephemeris.cpp in C++ source code links at bottom of page.

I have to join in to say that this page (which exists since some time, only has recently be updated) is really impressive, and a very good educational material for everyone wanting to really understand the workings of GPS.

Nevertheless it's not the only attempt, bug a very good one, at "open source GPS" projects. There's at least http://www.gnss-sdr.org/ which is a more software-centric approach being able to work with different receiver frontends. And I've just found another FPGA project at http://www.witchnav.cz/.

Naturally the software-only solution will burn a lot of CPU in the correlators, so I'd expect a software solution to require a multi-GHz machine, whereas the GPS receiveres with FPGA (such as the one linked to) works easily on a pretty low-performing Raspberry-Pi.

Many standalone recievers are just that- completely standalone. They just spit out a string of coordinates and other information on configurable intervals.

There is some sort of international agreement, originally intended to prevent the use of off-the-shelf GPS components in building cheap missiles. The agreement prevents all GPS receivers from providing data when their altitude is higher than some number (10 km I think), and their speed is above some number (hundreds of km/h IIRC).

Some GPS vendors read the above in terms of an OR function, instead of an AND function. In other words, their receivers stop functioning above that altitude no matter what the speed is.

That prevents some off-the-shelf GPS receivers from being used to build stratospheric balloons, since these things can climb all the way to 30 km altitude, or more. Other GPS receivers are built on an AND function, and work well with strato balloons. Sometimes it's a bit tricky to tell if a given receiver is an AND or an OR.

I assume, if you build a DIY GPS receiver, you can even ignore any such limitation altogether, right? That might well be illegal where I live, I'm not sure, and I have no intention to build such a thing anyway. I'm just asking in principle.

EDIT: This is the COCOM limit:

In GPS technology, the phrasing "COCOM Limits" is also used to refer to a limit placed to GPS tracking devices that should disable tracking when the device realizes itself to be moving faster than 1,000 knots (1,900 km/h; 1,200 mph) at an altitude higher than 60,000 feet (18,000 m).[2] This was intended to avoid the use of GPS in intercontinental ballistic missile-like applications.

http://en.wikipedia.org/wiki/CoCom

You can certainly ignore both limits in your homemade-receivers, but if you ever want to ride faster than 1900km/h you will have to account for an increased doppler shift (I hope I'll not help any terrorists by explaining that ;-) ), and even though I (in the end) realized that this is not as dramatic as thought at first, just let me write down some calculations:

Doppler shift is the change of the percieved frequency when either source or receiver move towards another, or away from another. Canonical example: Sound of a emergency vehicle's horn when passing by.

Normally you never see the satellites ride directly towards you (or away from you) but the path is pretty orthogonal to your line-of-sight. So you only account for a fraction of the 14'000 km/h speed of the GPS satellites to cause frequency shifts of the signal. (Max. example listed on the homepade-GPS page is ±5 KHz of doppler, which is relatively 3.3×10^−6 of the GPS frequency, even though the GPS satellite rides at 1.8×10^−5 the speed of light).

If you'd fly with 1900 km/s (1.8×10^−6 of the speed of light) directly towards the GPS bird, this movement will increase the frequency you receive by 1.8×10^−6 × 1,5 GHz = 2.7 kHz. So please increase your doppler search range from ±5 KHz to ±8 KHz to be able to successfully steer your homemade cruise missiles at that the COCOM limit speed, increase more if faster. This will slow down your time-to-first-fix, obviously.

The other limit of 10km is easier to ignore, though. It would only become relevant once you can no longer exclude some solutions to the formulae that lie outside of the GPS satellite's orbit (imagine four coplanar GPS birds used for calculation). And in practice proabably it's sane to assume a position that is not wider than 100km from the earth's surface, again, if you don't plan to ride your DIY receiver to the ISS, or maybe even geostationary orbit.

Here's another chap who designed his own GPS+GLONASS receiver back around 1992: http://lea.hamradio.si/~s53mv/navsats/theory.html

The best bit is that all the diagrams, schematics and PCB layouts are hand-drawn.

Hmm. I don't see any mention of whether this design complies with the COCOM Limits, an agreement that GPS devices should disable themselves when at an altitude above 60,000 feet and a speed faster than 1,000 knots.

Probably not

Which is funny, because to know you're higher/faster than allowed you need to calculate that from GPS data

In practice, not sure how this is achieved, but for speed this may even be a limitation of the circuit (for example, if you can't compensate for the doppler effect at that speed or has to add some other processing - still, the doppler effect should be small)

1000 knots is still +/- 1.5 Mach (at sea level) so Concorde and fighter jets should use a special GPS (but this is very fast)

> Which is funny, because to know you're higher/faster than allowed you need to calculate that from GPS data

Actually, no. All military aircraft have inertial navigation packages that, among other values, provide altitude above the elipsoid, position, and velocity vector. When available, these systems are fixed periodically to GPS-based measurements.

Yes, but GPS modules can't expect to have this information input into them. See http://en.wikipedia.org/wiki/CoCom

You're right from the point of view of the aircraft/missile, where several pieces of information are put together (GPS, barometric, inertial, etc) for navigation purposes.

Right, minor brain fart. I was thinking at the systems level, but the requirement is for the module to cut itself out, not have an external system do it.

I don't think there's a requirement to completely shut down, only a requirement to cut off your data output. You can keep calculating your speed and position, you just stop telling the outside world.

The problem is, COCOM says:

GPS devices should disable themselves when at an altitude above 60,000 feet AND a speed faster than 1,000 knots

Whereas some vendors read it:

GPS devices should disable themselves when at an altitude above 60,000 feet OR a speed faster than 1,000 knots

Which effectively disables your cheap GPS dongle in your home-made stratospheric balloon, which is quite capable of reaching 30 km, above the COCOM altitude spec.

Sometimes it's quite tricky to figure out if a given receiver is an AND or an OR.

You could maybe beg/steal/borrow a GPS simulator[1] and test your candidate receivers with it. Best do it in a Faraday cage though, unless you want to upset some Very Serious Important Things[2], and (likely government) owners thereof.

Probably way out of budget range for hobby stuff though

[1] One is the WelNav GS720: http://www.t-e.com.tw/GS-720.pdf

[2] A Simple Demonstration that the Global Positioning System (GPS) is Vulnerable to Spoofing: http://www.ne.anl.gov/capabilities/vat/pdfs/GPS-Spoofing-%28...

Doppler shift due to observer speed will almost always (i.e. for anything other than an actual ballistic missile, and even then only a missile traveling west) be less than the doppler shift due to satellite speed for a stationary observer. So, artificially restricting the doppler spread isn't an effective method of implementing the COCOM restrictions. It would also make PLL lock-up more difficult.

Concorde is old enough that its operators probably never went to the trouble of doing the paperwork to have a GPS integrated with the rest of the NAV system. For its (relatively) short flights, an internal navigation system plus VHF or LF radionav works adequately (and there were very few, if any, GPS/WAAS approaches certified by the time of its retirement).

Those limits are to prevent its use in intercontinental missiles. If intends to build one, I guess he'll have bigger problems than the speed at which his GPS receiver works. If you were thinking about the case where he sells it to someone making a missile, I guess that if someone is able of getting a missile capable of intercontinental flight, a GPS receiver won't be the missing bit.

I'm a software developer gone electrical/computer engineer and this is still a very high-level overview. You need to understand many advance physics topics like RF, antennas design, extremely complicated DSP algorithms, hardware architecture and design for the FPGA, etc. The breadth and deep understanding of very hard topics is VERY different than most web developers/people on here that write toy utilities programs then post a link to Github..

Interesting resubmission. Originally submitted >500 days ago, but today's submission simply put a # at the end of the URL, and thus avoided duplicate detection.

Not that I mind--this is one of the more awesome articles submitted to HN or really anywhere.

Perhaps the resubmission is due to the May 2013 update on the page.

Oh, likely, but the duplicate detection is based on URL matching, not on newness of content. See the other submission at https://news.ycombinator.com/item?id=5717674 and note that the referenced URL does not have the # at the end that this one does.

That's a common way to resubmit. It's apparently a feature of HN (as in pg obviously knows about it and chooses to keep it the way it is).

I think you meant https://news.ycombinator.com/item?id=3065619. Interesting find.

How about this one:

https://news.ycombinator.com/item?id=5699429

Whatever. I'm glad people are looking at this because it is incredible.

EDIT: I do wonder, however, that the link from 3 days ago only has one point, which is what it had as soon as it was created. Presumably elemeno appended the "#" before he submitted the link, because if he had just submitted the link then the 3-day-ago link would have at least two points. Is automatically adding the hash a thing that people do? Is reposting non-hashed links from several days before with added hashes a thing that people do?

I guess since this version of the link has been upvoted 201 times, elemeno actually has provided a valuable service to HN.

Just to close the circle, this one also has a hash at the end:

https://news.ycombinator.com/item?id=5721006

The three days ago one didn't come up when I first put the URL in, though the 500+ days ago one did. Quite possibly I was simply lucky in that I posted near the start of the UK work day, thus making it likely to get noticed by people in Europe and then the US, also quite possibly there's a bit of extra magic in how HN deals with dupes and how quickly it forgets about submissions that get no love.

Very weird! The really old one didn't come up for me. It came up for you, but the 3-day-old one didn't. I would speculate that we're seeing the CAP Theorem in action, except I know I've read that HN is hosted on a single box.

Pretty much. I saw it had been submitted before, but that it was over a year and a half ago and the page had been recently updated, so it seemed like it would be an acceptable resubmission. Plus, it's a pretty damn cool project!

This is really amazing

I had no idea it was this complex. Well, in a way it is simpler than I imagined (since he's using an antenna with an amplifier), and the FI amplifier is "simpler" as well.

The most interesting parts for me is the demodulation, and the code phrases search using FFT.

No wonder you need a FPGA to do the heavy lifting.

One of the best posts here in days! Posts like this is why I read hacker news!

It blows my mind that all that complexity is baked into your smartphone

The interesting thing is that smartphones throw cellular tower triangulation into the mix to speed the fix, so in a sense, they are more complex.

The main thing that speeds the fix is the fact that they download the satellite positions over the data network. Satellite positions are embedded in the GPS signal, but they are transmitted very slowly. That is, I believe, the 50bps NAV signal he discusses on that page. It takes about 30 seconds to download it all over the GPS signal, while it can take <1s to grab it from your local cell tower. This is also the big reason why "warm starts" of standalone GPS receivers that have only been off for an hour or two are so much faster: the position data is good for a few hours, but after that it has to be downloaded again.

So cell phone GPS receivers have everything needed for standalone GPS, and position assistance from other sources as you mention, and the ability to load satellite position data from other sources. All this on a chip that probably costs less than $10 in bulk.

Another great project in the area of DIY GPS is http://gnss-sdr.org/project It implements a GNSS/GPS receiver using software defined radio (SDR). They also support the RTL2832U based SDR (http://www.rtlsdr.org/), which is a cheap way to get started.

This is one of those times one regrets going to IT instead of EE. I can make sense of 10% of it.

Sure, he designed it, but I don't think those nice printed PCBs are "homemade". I'd be more impressed if it were through-hole construction. Still, it's pretty cool.

Doubtful you can get an FPGA of that class in a thru-hole package. The dude was smart to shop out the PCB instead of spending weeks trying screen and drill his own.

Good point. Any idea what ballpark speed one would need?

Speed of the FPGA? FPGAs are given speed grades, but the actual design dictates the max speed. Different logic sections, depending on pipelining, size, which pins they are connected to can run at different speeds. You might have an overall max speed/critical path of say 50mhz, but you might be able to safely run a small section of the design at 200mhz.

But, you can make your calculations massively parallel on an FPGA. So the clock speed does not compare at all to a typical processor.

Not like it's really that hard to solder SMD. I soldered 40-pin SMD all the time with nothing more than a fine-tip soldering iron, a syringe full of flux, and a magnifier or microscope.

You probably can get FPGA in CPGA package that has similar performance to that Spartan3, but these things are meant for high reliability and wide temperature range military/aerospace applications (you get either THT or really funky SMT packages there) and certainly beyond the budget of most hardware companies, not to say any hobbyist.

What are you, Etsy? :P

He didn't fab his own silicon, package his own dies, or even machine his own connectors!

The hard (and interesting) parts are the design and testing/debugging phases. Building your own PCB to handle various RF signals at this sort of level is non-trivial in both time and money, and doesn't really gain you much.

There's no reason why it should be through-hole either, and indeed, good luck finding suitable parts in those packages. SMD manual soldering isn't particularly hard either, although time consuming. If you have a reflow or spare toaster oven, you can do it a whole lot faster too.

I do agree, but to be fully pedantic,

  L1 and L2 are hand-wound microwave chokes with
  very high self-resonant frequency, mounted
  perpendicular to one another and clear of the
  ground plane. Wind 14 turns, air-cored, 1mm
  inside diameter from 7cm lengths of 32swg
  enamelled copper wire. Checked with the tracking
  generator on a Marconi 2383 SA, these were good
  to 4 GHz.

I've designed, drawn, corroded, and soldered entire soundcards, synthesizer blocks, and various systems with microprocessors, back in the day. All by hand.

To quote Linus, it's quite "studly" to operate like this, but the result is big and ugly. Fabbed PCBs are much more compact.

Reply on news.ycombinator.com