8 ms·
Homemade GPS Receiver
- joosters 13y agoThat 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." !
- elemeno 13y agoSome of his other projects are pretty impressive as well - I'm taken by the FORTH computers myself.
- Luc 13y agoThis 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.
- Toucan 13y agoLess 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.
- mikeash 13y agoFun fact, the Boeing 747 features a sextant port for convenient celestial navigation in flight.
- Florin_Andrei 13y agoWow. Was it ever used?
- mikeash 13y agoCan'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.
- sbierwagen 13y agothat 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?
- mikeash 13y agoCheck out fancyketchup's sibling comment to yours, which shows far more knowledge than I have. Short version: infrared.
- fancyketchup 13y agoThe 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).
- toufka 13y agoExcept 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-depend-on-relativity http://physics.stackexchange.com/questions/1061/why-does-gps...
- grguy 13y agoAnd where are those corrections taken into account in this page?
- aholme 13y agoRefer to method GetClockCorrection() of class EPHEM at line 155 of file ephemeris.cpp in C++ source code links at bottom of page.
- rwg 13y agoSome 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.") See also: http://en.wikipedia.org/wiki/Error_analysis_for_the_Global_Positioning_System#Special_and_general_relativity http://en.wikipedia.org/wiki/Error_analysis_for_the_Global_P...
- Florin_Andrei 13y agoThe 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.
- raverbashing 13y agoThis 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.
- michaelt 13y agoHere's another chap who designed his own GPS+GLONASS receiver back around 1992: http://lea.hamradio.si/~s53mv/navsats/theory.html http://lea.hamradio.si/~s53mv/navsats/theory.html The best bit is that all the diagrams, schematics and PCB layouts are hand-drawn.
- cnvogel 13y agoI 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/ 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/ 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.
- sliverstorm 13y agoMany standalone recievers are just that- completely standalone. They just spit out a string of coordinates and other information on configurable intervals.
- Florin_Andrei 13y agoThere 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 http://en.wikipedia.org/wiki/CoCom
- mherdeg 13y agoHmm. 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.
- raverbashing 13y agoProbably 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)
- vonmoltke 13y ago> 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.
- raverbashing 13y agoYes, but GPS modules can't expect to have this information input into them. See http://en.wikipedia.org/wiki/CoCom 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.
- vonmoltke 13y agoRight, 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.
- fvox13 13y agoSure, 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.
- joezydeco 13y agoDoubtful 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.
- throwaway1979 13y agoGood point. Any idea what ballpark speed one would need?
- tcas 13y agoSpeed 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.
- asynchronous13 13y agoBut, you can make your calculations massively parallel on an FPGA. So the clock speed does not compare at all to a typical processor.
- jff 13y agoNot 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.
- dfox 13y agoYou 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.
- retube 13y agoIt blows my mind that all that complexity is baked into your smartphone
- wglb 13y agoThe interesting thing is that smartphones throw cellular tower triangulation into the mix to speed the fix, so in a sense, they are more complex.
- mikeash 13y agoThe 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.
- wglb 13y agoInteresting 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.
- js2 13y agoPerhaps the resubmission is due to the May 2013 update on the page.
- wglb 13y agoOh, 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 https://news.ycombinator.com/item?id=5717674 and note that the referenced URL does not have the # at the end that this one does.
- js2 13y agoThat'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).
- robobrobro 13y agoI think you meant https://news.ycombinator.com/item?id=3065619 https://news.ycombinator.com/item?id=3065619. Interesting find.
- jessaustin 13y agoHow about this one: https://news.ycombinator.com/item?id=5699429 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.
- hcarvalhoalves 13y agoThis is one of those times one regrets going to IT instead of EE. I can make sense of 10% of it.
- j_m_b 13y agoOne of the best posts here in days! Posts like this is why I read hacker news!
- kyle_martin1 13y agoI'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..
- felixr 13y agoAnother great project in the area of DIY GPS is http://gnss-sdr.org/project 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/ http://www.rtlsdr.org/), which is a cheap way to get started.