Clive D. W. Feather wrote:
In article , Tom
Anderson writes

Unlikely as this may sound, it works by picking up
synchronised radio signals from members of a family of 31 satellites
orbiting 20 000 km above the earth, measuring the time differences
between them with an accuracy of a few nanoseconds, which tells you
the differences in distances to the satellites with an accuracy of a
few metres (out of twenty million - not bad!), then doing geometric
calculations to work out where that means the receiver must be. It's
the kind of thing that if it didn't exist, you'd think it was an
absurd idea.

I don't know if it'll help, but here's how I explain it to my kids.

You're lost because it's foggy or pitch black. You have a map of the
area but can't see any landmarks. You've lost your watch. However, you
know that the local church clocks are accurate, they strike exactly
one second between beats, and each has a different set of chimes so
you can tell which one you're hearing.

You hear a clock chime and strike the hour. 20 seconds later (using
the first set of strikes to time things) you hear another clock.
Since sound travels at 300m/s you know that you're 6km closer to the
first clock than the second one. Some careful thought allows you to
draw a curve on your map which is all the places 6km closer to the
first church than the latter - you are somewhere on that curve.

Meanwhile, 12 seconds after the second clock you heard a third one.
You are therefore 3.6km closer to the second than the third and 9.6km
closer to the first than the third. These let you draw two more lines
that you're also on and, hopefully, all three lines cross at exactly
one place, which is where you are.

GPS uses radio (which moves much faster) rather than sound, and the
transmitters keep moving; however, the signal coming from them says
exactly where they are, so that isn't a problem. Nonetheless the
principle is the same.

How do the receivers cope with dozens of satellites all broadcasting on the
same frequencies? Time splicing?

In article , John Rowland
writes
How do the receivers cope with dozens of satellites

31

all broadcasting on the
same frequencies? Time splicing?

As I understand it, the signals are not on a single frequency but rather
jump around a set of adjacent frequencies ("spread spectrum"). Each
satellite uses a different pattern of jumps repeating every millisecond,
so you can tell which satellite you're picking up by recognising the
pattern, and the different patterns mean that two satellites are never
(or hardly ever) on the same frequency at the same time.

--
Clive D.W. Feather | Home:
Tel: +44 20 8495 6138 (work) | Web: http://www.davros.org
Fax: +44 870 051 9937 | Work:
Please reply to the Reply-To address, which is:

On 20 Apr, 01:42, "Clive D. W. Feather" cl...@on-the-
train.demon.co.uk wrote:
As I understand it, the signals are not on a single frequency but rather
jump around a set of adjacent frequencies ("spread spectrum"). Each
satellite uses a different pattern of jumps repeating every millisecond,
so you can tell which satellite you're picking up by recognising the
pattern

I think how it works is the receiver has to jump between frequencies
on the same pattern as the satellite it wants to listen to. The
receiver therefore needs to know which pattern each satellite is
using, and it also needs a separate tuner for each satellite. Because
most have far fewer tuners than there are satellites (usually 12, vs
30ish) they need to know in advance which satellites are overhead.

So this means a receiver needs to already know current approximate
location and the current time, and the orbit and frequency pattern
information about the satellites. This is why it takes ages for a
brand new or freshly reset GPS unit to get any sort of lock (up to an
hour).

U

--
http://londonconnections.blogspot.com/
A blog about transport projects in London

So this means a receiver needs to already know current approximate
location and the current time, and the orbit and frequency pattern
information about the satellites. This is why it takes ages for a
brand new or freshly reset GPS unit to get any sort of lock (up to an
hour).

And also, presumably, when you turn on the GPS a long way from its location
it was last used?

In article
, Mr
Thant writes
I think how it works is the receiver has to jump between frequencies
on the same pattern as the satellite it wants to listen to.

True, I believe.

The
receiver therefore needs to know which pattern each satellite is
using,

But this will be pre-programmed in some way.

and it also needs a separate tuner for each satellite. Because
most have far fewer tuners than there are satellites (usually 12, vs
30ish) they need to know in advance which satellites are overhead.

So this means a receiver needs to already know current approximate
location and the current time, and the orbit and frequency pattern
information about the satellites. This is why it takes ages for a
brand new or freshly reset GPS unit to get any sort of lock (up to an
hour).

That's not my experience, nor do I see why it needs to be like that.

You listen in on one of the frequencies (call it A) and look for a
regular "blip" (the frequency hopping sequence repeats every
millisecond). If 8 satellites are visible you should get 8 such blips at
various points in the cycle. You choose one of them and pick another
frequency (B) and start listening in an
ABBBBB...BBABBBBB...BBABBBBB...BBABBBB pattern until you get two blips
per millisecond. Hopefully only one or two satellites are using a
pattern which matches that and you can quickly find which. If the
ABBBBB... pattern gives you more than two blips, you've been unlucky and
found two satellites hitting A at exactly the same moment, but again you
pick one of the B hits and go for a third frequency.

For that matter, once you've locked in on an A signal at regular
intervals, you can simply try each of the 31 sequences and see which
ones work.

[Since there are less frequencies than there are steps in the sequence,
it's a bit more complicated than this. But that's the principle.]

I believe most of the delay in syncing up with satellites is reading all
the data from the signal, which is transmitted at a relatively slow
rate.

--
Clive D.W. Feather | Home:
Tel: +44 20 8495 6138 (work) | Web: http://www.davros.org
Fax: +44 870 051 9937 | Work:
Please reply to the Reply-To address, which is:

On Mon, 28 Apr 2008, Clive D. W. Feather wrote:

In article ,
Mr Thant writes

I think how it works is the receiver has to jump between frequencies
on the same pattern as the satellite it wants to listen to.

True, I believe.

I believe it's actually CDMA rather than frequency-hopping. Although the
two are probably equivalent in some deep way.

The receiver therefore needs to know which pattern each satellite is
using,

But this will be pre-programmed in some way.

Yes, this isn't complicated. There's a pseudo-random number generator
algorithm, for which each satellite has its own seed, and the receiver
knows the algorithm and the seeds. The generator and seed are used to
produce a 1023-bit code which is used to modulate the carrier in the CDMA
scheme.

and it also needs a separate tuner for each satellite. Because
most have far fewer tuners than there are satellites (usually 12, vs
30ish) they need to know in advance which satellites are overhead.

So this means a receiver needs to already know current approximate
location and the current time, and the orbit and frequency pattern
information about the satellites. This is why it takes ages for a
brand new or freshly reset GPS unit to get any sort of lock (up to an
hour).

That's not my experience, nor do I see why it needs to be like that.

You listen in on one of the frequencies (call it A) and look for a
regular "blip" (the frequency hopping sequence repeats every
millisecond). If 8 satellites are visible you should get 8 such blips at
various points in the cycle. You choose one of them and pick another
frequency (B) and start listening in an
ABBBBB...BBABBBBB...BBABBBBB...BBABBBB pattern until you get two blips
per millisecond. Hopefully only one or two satellites are using a
pattern which matches that and you can quickly find which. If the
ABBBBB... pattern gives you more than two blips, you've been unlucky and
found two satellites hitting A at exactly the same moment, but again you
pick one of the B hits and go for a third frequency.

For that matter, once you've locked in on an A signal at regular
intervals, you can simply try each of the 31 sequences and see which
ones work.

[Since there are less frequencies than there are steps in the sequence,
it's a bit more complicated than this. But that's the principle.]

That would make perfect sense if the satellites used frequency hopping.

Rather, there's one frequency, producing a stream of bits which are the
sum of the signals from all the satellites. CDMA lets you filter that
stream and recover a single satellite's signal. Basically, the CDMA
decoder takes the raw, summed signal, plus one of the 1023-bit codes, and
gives you back the satellite signal that was modulated with that code. The
code input and satellite signal need to be in sync, so this takes some
time to get right: the modulation is at 1.023 MHz, so it takes 1 ms for a
repetition of the code, and there are 1023 possible offsets of the code
and signal inputs, which will thus take 1.023 seconds to work through.
Once you've got one, you remember it, and try another code, until you've
got enough satellites. Even running through all 30 of the satellite codes
will only take 30 seconds to do this.

I believe most of the delay in syncing up with satellites is reading all
the data from the signal, which is transmitted at a relatively slow
rate.

That's certainly what wikipedia says: the 'navigation message' goes at 50
bits per second, and carries 1500-bit frames, each of which takes 30
seconds to transmit. 600 bits of that are a segment of the 'almanac',
which is a collection of information you need to work out position; the
almanac is 15 000 bits long, so it takes 25 frames to transmit the whole
thing. That's 12.5 minutes. Once you have a copy of the almanac, you can
use the transmitted segments to keep it up to date, but you never have to
do the 12.5 minute wait again. Unless you stop getting updates for some
period of time, eg because the receiver's switched off. The almanac is
valid for 180 days, though, so if it's switched on again inside this time,
it can go straight into action.

Although the 12.5 minute figure is based on receiving all the segments one
after another. Since each satellite is transmitting segments
independently, if they were arranged cleverly, you should be able to
receive several at once, which would reduce the time taken. I don't know
if they are arranged cleverly, or if the satellites transmit in sync with
each other.

tom

--
megaptera novae angliae, soundwork chris draper, push, pull, open, ..

In article , Tom
Anderson writes
I think how it works is the receiver has to jump between frequencies
on the same pattern as the satellite it wants to listen to.
True, I believe.
I believe it's actually CDMA rather than frequency-hopping. Although
the two are probably equivalent in some deep way.

You're right, and I mis-read.

Yes, this isn't complicated. There's a pseudo-random number generator
algorithm, for which each satellite has its own seed, and the receiver
knows the algorithm and the seeds. The generator and seed are used to
produce a 1023-bit code which is used to modulate the carrier in the
CDMA scheme.

It's actually even simpler than that. There are two 10-bit shift
registers which each generate a 1023 bit sequence. The second one has
the property that if you take any two intermediate bits and XOR them
together, you get the same 1023 bit sequence but shifted by some number
of bits. The output of the first register and two intermediate bits of
the second register are XORed together to form the 1023-bit code. Each
satellite uses a different pair of intermediate bits.

Rather, there's one frequency, producing a stream of bits which are the
sum of the signals from all the satellites. CDMA lets you filter that
stream and recover a single satellite's signal. Basically, the CDMA
decoder takes the raw, summed signal, plus one of the 1023-bit codes,
and gives you back the satellite signal that was modulated with that code.

Right - the mathematics to do this turns out to be very simple (well, to
programmers it will).

The code input and satellite signal need to be in sync,

Or you record one cycle of the data and run all 1023*31 possibilities
through the algorithm.

That's certainly what wikipedia says: the 'navigation message' goes at
50 bits per second,

Right; thus 20 copies of the 1023-bit pattern per bit. The data bit is
XORed with the code to produce the transmitted signal.

--
Clive D.W. Feather | Home:
Tel: +44 20 8495 6138 (work) | Web: http://www.davros.org
Fax: +44 870 051 9937 | Work:
Please reply to the Reply-To address, which is:

On Mon, 28 Apr 2008, Clive D. W. Feather wrote:

In article , Tom Anderson
writes

Rather, there's one frequency, producing a stream of bits which are the sum
of the signals from all the satellites. CDMA lets you filter that stream
and recover a single satellite's signal. Basically, the CDMA decoder takes
the raw, summed signal, plus one of the 1023-bit codes, and gives you back
the satellite signal that was modulated with that code.

Right - the mathematics to do this turns out to be very simple (well, to
programmers it will).

The code input and satellite signal need to be in sync,

Or you record one cycle of the data and run all 1023*31 possibilities through
the algorithm.

Doh! Yes, that would be rather quicker.

Although it's actually a bit more complicated than this, since the signals
from the satellites won't be in sync at the CDMA modulation level (the
time of flight of the signal being 60 ms, variable by tens of ms, and the
modulation period being 1 us), so the way the signals add isn't just a
straightforward addition of bits, it's a situation called asynchronous
CDMA. But still, you take a roughly similar approach, i think. Anyway, the
electronics bods have worked it all out!

tom

--
catch my hand and come with me - close your eyes and dream

In uk.transport.london message ,
Sun, 20 Apr 2008 01:42:16, Clive D. W. Feather clive@on-the-
train.demon.co.uk posted:
In article , John Rowland
writes
How do the receivers cope with dozens of satellites

31

all broadcasting on the
same frequencies? Time splicing?

As I understand it, the signals are not on a single frequency but
rather jump around a set of adjacent frequencies ("spread spectrum").
Each satellite uses a different pattern of jumps repeating every
millisecond, so you can tell which satellite you're picking up by
recognising the pattern, and the different patterns mean that two
satellites are never (or hardly ever) on the same frequency at the same
time.

ftp://tycho.usno.navy.mil/pub/gps/gpssy.txt, "GPS SIGNAL
CHARACTERISTICS". Let us hope that their technology is better than
their spelling.

--
(c) John Stockton, nr London, UK. Turnpike v6.05.
Web URL:http://www.merlyn.demon.co.uk/ - w. FAQish topics, links, acronyms
PAS EXE etc : URL:http://www.merlyn.demon.co.uk/programs/ - see 00index.htm
Dates - miscdate.htm moredate.htm js-dates.htm pas-time.htm critdate.htm etc.