Hacker News Reader

Comment by joosters | Hacker News Reader

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."

View on HN

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.

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

Reply on news.ycombinator.com