GPS - my final offering

If you are still with me - you only have to endure one more post on GPS related information. 
OK... you really didn't have to breathe that sigh of relief now ;-)

Last time I wrapped up the basics on how GPS achieves the seemingly miraculous job of using a constellation of satellites to have you know where on Earth you are.  But it seems I left you with a bit of a problem... the location you are getting reported is too inaccurate. OK, so you should know what city you are in, and maybe what side of the tracks you are on.  But if you don't already know this, GPS accuracies are not likely the biggest of your problems!

So what is wrong?  Several things:  Leap seconds, Einstein and more Einstein.

What, you ask, the heck, is a leap second????  First off, let me get the disappointment done with early.  What I know is limited... so you will just have to Wikipedia this for the gory details.  Bottom line:  just as every now and then calendars are adjusted with an extra day (leap years), so is our time occasionally in need of a minor tweak.  Every so often, Earth standard time is nudged by a second.  Keeps the time bean counters happy, or something like that.  But unfortunately for the makers of GPS satellites, their atomic clocks are not adjustable.  So each time we nudge time by a second, the GPS time and Earth time deviate by another second.  We currently have something like 24 leap seconds since this practice was started.  If we did not adjust for this, just accounting for Earth's rotation, we would be off by 6-7 miles or so. 
So now we adjust for this, and we are quite a bit closer to the mark.  But still off...   so let's go visit Einstein.

Who doesn't know Einstein?  I mean really.  But many don't know much about what he brought to the physics world.  Something about relativity, speed of light and energy. 
We will ignore the ever famous E = mc squared.  But the speed of light and relativity are very important to GPS.  Radio signals travel at the constant speed of light. And that is how we generally know how long the Satellite signals should take to travel from the Satellite to where we are.  I say generally - because I lied.  Again.  The speed of light is NOT constant.  It is constant only in a true vacuum, as in space.  But it tends to change speeds a little in an atmosphere, and also tends to bend a little as it goes though some of the atmosphere's layers.  This is akin to when you are looking into a pool and things look a little distorted.  Same thing happens to these Satellite signals.  Again, more corrections need to be layered in if we really want to be accurate!    Closer still... but there are 2 more effects that we need to address if we want accuracy that will help us navigate as drive the streets.

In Einstein's Special theory of Relativity, among its many implications, is that as you travel relative to another object at any significant speed, your clock slows down.  Time just happens slower for you.  And while our Satellites are zipping along pretty darn fast, the effect is minor.   But still just big enough that we need to account for the change in the speed of the clock on the Satellite.

Later Einstein published his General Theory of Relativity.  Very complicated - but again, I'll bottom line it for you.  Gravity curves space-time.  And our GPS satellites are experiencing slightly different gravity than you and I are here on the surface.  So the space-time they are zipping past has a slightly different curvature than you and I do, and this too, translates into a clock that ticks a little faster than ours on the surface. 

So when we account for Time dilation (Special theory of Relativity), Time contraction (General theory of Relativity), speed of light and its refraction through the atmosphere, and leap seconds - we now have a very accurate GPS position estimate. 

And that little box sitting on your dash?  The one you just take for granted.  It does all of this - just so you don't get lost making the wrong turn somewhere!

GPS - Gets a *little* complicated...

Who doesn't love a good GPS unit?  Makes for a hard time to get lost when driving in unfamiliar places.  But, there is an awful lot of stuff going in in that teeny little box you take for granted.
Remember on my last post - how I said 

"Not so complicated after all - is it?"

As I alluded, that is a bit of a white lie.  Before I continue, an important caveat.  This is not a technical blog.  it is my aim to give a word explanation with near zero math.  As such I will at times simplify a concept to a degree that technically speaking, it is incorrect.  For those with knowledge about the subject, please indulge me a little!

OK - back to some explanations.

Yes, the concept of triangulating your position from satellite locations is in principle not hard to wrap your head around.  All you need to know if the exact position of all the satellites, and the exact distance from each satellite to where you are.  Satellite positions are the easy part.  There are some pretty accurate ways to get their positions - in fact, part of the message these satellites embed in their radio signals is this very information. 

The harder part is to determine just how far you are from any one satellite.  Since we don't have a long enough yard stick, we instead measure the time it takes from a signal leaving the satellite to reach us.  Then, knowing the speed of propagation of light, we get the corresponding distance. 

That sounds good, but we are still left with some information we need.  We need to knew just when that timing signal left the satellite, and we need to have a synchronized clock on hand for us to measure the interval.  Sadly, we don't automatically have information about the time of departure for any of the satellite's timing radio signals.  To make matters worse, we don't have accurate enough clocks on our tiny GPS receiver to accurately measure our distance.  Each satellite has an atomic clock on board.  You are not likely to have a spare one to use on hand!

It looks like we are at an impasse right?  Wrong.  Here comes a curve ball.

Remember the triangulation analogy - where if you want to know where you are, you need to have 2 landmarks and a distance to each one?  A general rule, is that you can get one piece of information for each landmark you have.  So one landmark... you only know one thing... the distance you measured.  Not very helpful.  Two landmarks, and you can determine your latitude and longitude.  What happens if you have 3 landmarks?  Turns out that if the 3 landmarks are well placed, you can find your height/altitude with respect to these landmarks.  So going back to satellites.... 

If we know time where we are, we then need 3 Satellites to get our location (latitude, longitude, and height/altitude).  But there is a trick we can use to help us out, when we don't know what time it is where we are.  Turns out if you triangulate on 4 satellites, you get 4 pieces of information.  With the right math, you can make the 4th item of information be your time!  One problem down.

Now... for the Satellite time.  If you recall, the Satellites broadcast their own position to assist us here on the ground to knew where they are.  But - "where" implies a location, and that really does not mean anything without the proper time.  And indeed, that is how we get Satellite timing - they send it to us!

With all this information on hand, we can now let a smart computer chip do the complicated math for us, and extract our time, height, latitude and longitude.  All we need is 4 well placed GPS satellites.

This could be the end of the story, and is the end of this blog post.  But wait...

The position we just calculated seems to be off the mark a little.  Miles off!

How can ever we use this to navigate streets and such?  What are we missing?  Stay tuned :-)

GPS - A Primer

It has come to my attention that some people may not be too familiar with the details of GPS (refer to my last post).

So let me start by removing the acronym.  GPS stands for Global Positioning Satellite.  But it really is not one satellite.  The term is used more broadly to describe all the 20 to 30 US based satellites used for navigational purposes, as well as most Earth based units that receive and use these satellite signals.

Nice image courtesy of Wikipedia

They work an an age old principle, often summarized as "triangulation".  Triangulation is by no means a new method.  It was used as far back as the 6th century BC by the Greek philosopher Thales to determine the height of pyramids.  It is also commonly used for surveying, navigation (land, sea an air), astronomy, and during warfare - to aim weapons accurately.
For basic triangulation, you need to have 2 known reference points (landmarks).  Wherever I am, as long as I have line of site, I can then get the compass direction to each of my reference points.  In geometry terms, I am just drawing an angled line from each of my reference points on a map, and find out where the 2 lines meet.  Presto!  I now know where I am as accurately as I measured the angles and know the exact locations of the reference points.  It also turns out that we can do almost the same calculation if we know the distance from the 2 reference points, without knowing the angles.
And that, in a nutshell, is what the GPS satellites help with.  Each GPS receiver has a circuit that can decode the radio waves from each satellite.  The satellites embeds distance markers in the radio signals they send, so my GPS receiver can extract the distance from my position to each of the satellites.  Also, satellites have known orbits, so even though they zip along at just under 9000 miles per hour, at any given time we know very precisely where they all are.  The only difference from the previous example, is that we now use more than 2 reference points, and we not only get our latitude and longitude, but also altitude.
Not so complicated after all - is it?

Next post - I will tell you why it really is that complicated!

A Geek's Christmas gift

If anyone of you was ever in doubt - please know I am a certified geek.  Really.
With that out of the way, let me show you a picture of the gift I got from my lovely wife Holly:

What - most of you are thinking - the heck - is that???

It is a GPS chip, and yes, she only knew to get it because I put it on my Amazon wish list.  If you have not tried that before - it is a great way to share gift ideas, especially if you are tough giftee as I am.

So it is a GPS chip.  The key circuit included in most of the Garmin and TomTom GPS car navigation systems.  I have to take a quick detour here and just say that I am constantly amazed at the progress technology has made over the last 20 years.  I used to work at TRW (now a part of Northrop), and did some pretty sophisticated work with GPS satellites and missile tracking.  What used to be a box the size of a desktop computer (or bigger), plus some pretty heavy duty processing power, now easily fits in a device that is about the size of a wristwatch and can be powered off a couple AA batteries.

So after futzing around with gizmo for a while, I now have it assembled and working with an Arduino microprocessor (shown below):



I am now able to decode all the GPS data coming off the chip, and using an Excel macro, read and process the information in real time.  As with any new toy, I like to understand all the gory details before I start to use it in some project...

For example... the precision of the unit *could* get me to knowing my position (latitude, longitude and height) to within about half a foot.  Unfortunately, its accuracy is only about 5-10 meters.  Good enough for most car navigation, but not so hot for my needs.  I am hoping to be able to reduce the errors a little with some judicious algorithms after analyzing the errors to which the device is susceptible.

But the greatest improvement I will likely achieve is using a system with 2 GPS devices - one stationary, the other able to move about the vicinity.  The stationary GPS will be at a known location.  It will broadcast the error between where it thinks it is, and where it actually is - to the mobile GPS - allowing it to correct for systematic errors.
I would like to use this unit for some kind of autonomous vehicle that could rove the yard - at some point it may even have some function - but for now it is just fun to get something to work for the sake of it.

I know my posts are once a blue moon, but maybe, just maybe, I can try to make that happen instead once every moon.