Hacker News Reader

Comment by jblok | Hacker News Reader

With functioning clocks, Galileo is accurate to within a metre, according to this article. That's crazy - I had no idea it was that accurate.

View on HN

With India, China and Russia launching their own positionning systems, I wonder if it would be possible to interpolate an even higher precision by listening to all 5 signals at the same time.

(I don't know enough about signal processing to know if that's a possibility or not.)

Not only is it possible, it's already done in many (most?) smartphones made over the past few years, at least for the Russian GLONASS system. As China's BeiDou and Galileo become operational, those will presumably be incorporated too.

However, I'd guess that most of the improvement in user experience comes from the higher reliability than higher accuracy. Even if the errors from all systems were completely uncorrelated (which they are not), averaging the location reported by four systems gives you at most a factor of 2 in improved accuracy. On the other hand, if your chance of being able to lock onto enough satellites (within a given number of seconds) for one system is 80%, the chance that you can lock on to at least one of the four systems becomes 99.8%.

I'm having trouble to grasp how you get a factor 2 improved accuracy if you have data from four uncorrelated systems all having the same accuracy.

Where can I find more information about this?

If your N samples are independent and distributed with the same error sigma, then the error of the averaged result is sigma/sqrt(N). (And of course, sqrt(4) = 2.)

You can calculate this directly by computing the variance of a sum of independent Gaussian random variables. Can't find a great link for further reading, but someone else might be able to help you out.

I'm glad there are people who know what all this means so I can tap a button, say "navigate to the grocery store" to my phone, and not spend brain cycles learning and maintaining knowledge of the wide range of math/programming/engineering specialties I'd otherwise have to master.

Everyone should know the central limit theorem though, simply for its own sake! It's worth the brain cycles :)

https://en.wikipedia.org/wiki/Central_limit_theorem

I had an intuitive sense of this. People saying "half the population has a below average IQ!" always elicited a head tilt from me. I just didn't know there was enough to say on the subject to fill a 8k word wikipedia article.

I'll file this next to the formula I whip up when I want to figure out how much a trip costs based on mileage and fuel prices.

It's sometimes important to actually work out the math to overcome cognitive biases and faulty intuition.

Phrasing the statement as "Think of how dumb an average person you meet on the street is. Now realize that half of all people are even more dumb than that." primes the brain to denigrate the intelligence of a random person, leading to a wrong conclusion.

Another example relates to your formula for fuel economy - some locales use distance-per-volume (miles per gallon) while others use volume-per-distance (liters per 100 km). Intuition may suggest that upgrading from a 15 mpg vehicle to a 20 mpg vehicle is comparable to going from a 30 mpg vehicle to a 35 mpg vehicle - but it's not! Using the reciprocal more accurately describes the emissions and costs related to different fuel economies over the wide range of values that you'll measure in modern vehicles: The example compares a 15.7 -> 11.6 L/100km change and a 7.8 -> 6.7 L/100km change. These units make it much easier to intuit the results.

Doing the math occasionally is a good habit to get into!

The intuition should be that "Half the population has below average X" is untrue for the vast majority of situations, because most real things have a skewed distribution.

AFAIK IQ is a peculiar case because of how IQ is defined.

A lot of natural processes produce results that are normally distributed. So given a large sample, a continuous value range, no bounds (or far away bounds) and a lack of obvious skew the intuition "half the population is below average" has a good chance to be (approximately) true.

Of course IQ is a made up thing that we just defined to behave that way.

Yes, the obvious counter-example is that almost the entire population has more than the average number of legs.

Haha an academic advisor of mine told me once that CLT was the only important thing I had learned that year.

I doubt uncorrelatedness. If the frequencies are very close then the systems share to some degree one source of error: ionospheric lightspeed variations.

In principle, a sufficiently smart device could lock onto one satellite of each system, and in the aggregate they'd be enough. But that would require some serious engineering.

It's not just precision, but availability of the signal and speed. Having more signals in natural and urban canyons improves accuracy and speed when there are more satellites.

One-chip GPS/GLONASS multiconstellation receivers have been on the market for some time. Millions of consumer units sold. Many smartphones have them.

Quad-constellation (GPS, GLONASS, Galileo, BeiDou) receiver chips have been on the market for some time.

For example: STA8090GA, It's automotive Grade GPS/Galileo/Glonass/Beidou/QZSS receiver

http://www.st.com/content/ccc/resource/technical/document/da...

> With India, China and Russia launching their own positionning systems, I wonder if it would be possible to interpolate an even higher precision by listening to all 5 signals at the same time.

First: Only Navstar-GPS, GLONASS and (in near future) Galileo will have worldwide coverage. Perhaps in future (but according to http://www.navipedia.net/index.php/BeiDou_Future_and_Evoluti... not before 2020) BeiDou will also have global coverage. IRNSS only has regional coverage.

So in near future we will only have three sources (not five).

Now for the simple mathematical trick: Model the position of the three systems as normal distributed random variable with same \mu, but different \sigma (\sigma_1, \sigma_2, \sigma_3). These three sigmas have to be measured. Now a convex combination of these random variables is again normal distributed, but with different \sigma (let's call it \sigma^* ) (easy exercise or look it up). Now just compute the coefficients of the convex combination that minimize \sigma^*.

Or you could just say that, for N independently distributed samples, the accuracy improves by a factor of at most sqrt(N) :)

This does only hold if the standard deviation \sigma is the same for all of the normal distributed variables. This is not the case here: Galileo is supposed to be more precise than Navstar-GPS (no surprise, since it is the newer system) - though I know that the US government is working on to increase the precision for Navstar-GPS. On the other hand (source: http://www.navipedia.net/index.php/GLONASS_Performances#GLON...) GLONASS is less precise than Navstar-GPS.

Well, I said "at most", so it holds for all sigma_i. As you know, when the sigma_i are very different, then the accuracy is approximately given by the best accuracy (smallest sigma_i), so there's very little improvement from averaging.

> Well, I said "at most",

OK, you are right. This can indeed be shown.

(warning: armchair expert, I've just read a bunch of wikipedia pages)

I believe there's still sources of systemic error that would affect all the signals similarly, such as atmospheric interference, so even taking (for example) the average of the reported position from all the services may not improve accuracy that much.

https://en.wikipedia.org/wiki/Error_analysis_for_the_Global_... is a good read.

The typical approach seems to be to consider all the visible satellites together (rather than solving for the position indicated by each constellation and averaging them).

So in practice having more satellites means that a good position measurement is possible more of the time.

You can also reduce some of the atmospheric interference by modeling it using both the L1 and L2 signal.

Apparently they wanted to make it even more accurate, but got pushback from USA before they feared it would be used by hostile forces.

I'm very disappointed that the EU bowed to their demands. It is the second clear sign I know that Europe dances to the USA's pipe; the other one was the grounding of the bolivian presidents plane in 2013.

I hope that Europe eventually stops giving in to demands by the USA.

[0] https://en.wikipedia.org/wiki/Evo_Morales_grounding_incident

Or maybe the European team simply agreed with the concern?

That is not the case. There was no valid concern.

GPS is US military. They can block access to the civilian one for any reason.

But if Galileo is on, they don't have the power to block it. Unless they jam its frequency. But as they use that same frequency, it would jam GPS. So, without officially giving a reason, they forced the EU to be on a different frequency.

There is no concern with using the same frequency. The US simply wants, and got, the ability to jam Galileo.

https://en.wikipedia.org/wiki/Galileo_(satellite_navigation)...

Selective availability was disallowed by executive order in 2000. Block III satellites will not even have the capability to disable the civilian signal.

Block III satellites will not even have the capability to disable the civilian signal

So we have been told, but it's just a firmware update (or equivalent).

Anything disallowed by executive order can be allowed again by executive order.

Now, that is a valid concern. So far the first I read. Maybe some countries in Europe also wanted to see Snowden catched.

You do understand that the security concerns of Europe and the US are mostly overlapping right?

Exactly, mostly. I think Europe should have efficient and effective measures to ensure it's safety also when they don't align.

Would there be a reason why GPS with 10m accuracy is OK but Galileo with 1m is not?

GPS has better than 10m accuracy in another operating mode. Only the military is allowed to use that one, though. Then they don't want Galileo being 1m accurate? Probably same military reasons.

> GPS has better than 10m accuracy in another operating mode. Only the military is allowed to use that one, though.

This has not been true since May 2000, when GPS "Selective Availability" was turned off. Civilian and military receivers have the same accuracy now.

http://www.gps.gov/systems/gps/modernization/sa/

No, that's not true. The military has access to different codes and frequencies that aren't available for civilian use, which can be used to apply further corrections to the computed location. Selective Availability was not the only difference between civilian and military GPS.

https://www.quora.com/Is-there-any-difference-between-milita...

As far as I understand, the remaining differences between military and civilian GPS don't matter much for accuracy. The military may still have the advantage of ionospheric correction, but civilians can use other augmentation systems like WAAS[1] with similar results. I think the military signals are mostly intended to protect against signal spoofing and jamming.

[1] https://en.wikipedia.org/wiki/Wide_Area_Augmentation_System

Thanks for that link. Never heard of it. That's some mind-blowing tech and accuracy.

Those extra frequencies were what I was thinking about. If they're still closed, then military still cripples GPS. The points of military vs civilian for this discussion would still apply.

I didnt know about that. Thanks for thd tip. So, the civilian GPS devices have the PPS signal and accuracy the military had?

Do you know of any examples when USA has stopped or changed its course on what can be considered its internal matters, or space area?

> It is the second clear sign I know that Europe dances to the USA's pipe

There are plenty more. My favourite: https://en.wikipedia.org/wiki/SWIFT#U.S._control_over_transa...

The US will stop pressuring the Europe once Europe has 10 or more carrier groups and an equal or so number of nuclear ballistic missiles.

This is actually untrue. The US didn't like that the EU was using bands close to GPS so if there was a conflict where the Russians or Chinese were using Galileo to target American troops, the US would have no choice but to shoot down or otherwise disable Galileo satellites by force. No one wants this, so the EU chose a different frequency that could be jammed without jamming GPS. Accuracy was never a concern. Galileo can't do better than a meter for many reasons, not the least of which is number of satellites, clock accuracy, and cost.

https://en.wikipedia.org/wiki/Galileo_(satellite_navigation)...

Then Europe should treat shooting down of Galileo satellites as an act of war and react as such.

It's not Europes business to make it easy for the USA to wage war.

So rather than make a technological change, which according to the parent post has no effect on the quality of the end system, Europe should wage war on the US if the US did something aggressive to protect it's troops in the middle of what I assume would already be World War 3? (an overt conflict with Russia or China?)

If whatever the USA are planing to do is in Europes interest, they can ask to turn Galileo off. If it is really in Europes interest, they will do so.

Localized jamming sounds a lot less disruptive than turning off the system for the entire world.

You could also turn off Galileo only in some areas.

No you can't.

Why shouldn't it be possible to turn off only those satellites that are visible in a certain area? I don't see any argument in your favour.

Satnav sattelites are not geosynchronous what are you going to do press on and off every time passes over?

You do understand that satellites are not light bulbs right?

Of course you could turn sending the signal on and off depending on the time or where they are.

A satellite is not a lightbulb.

That's also not a counter argument. Radio transmissions can be turned on and off.

Wouldn't this cripple the system over a much wider area than intended? The are from which a satellite in LEO is visible is ~5000km in diameter.

Galileo isn't in LEO https://en.wikipedia.org/wiki/Medium_Earth_orbit but yes, shutting off the signal would mean that a radius of about 7000 (GPS sats can be seen across about 6500~ miles depending on the exact orbit and angle, Galileo will have more coverage since they are at a higher orbit, if you really want to know here is how you calculate it http://gis.stackexchange.com/questions/77651/how-to-find-rin...) miles has no SatNav...

Jamming can shut down GPS in any range from 10M to 100,000M turning the transmitters of effectively shuts down GPS to half the globe. ]

It's not about making it easy for the US. Shooting down satellites is not going to be a tough problem for the US military. It's about convincing the US not to do that.

It's like not leaving food out to avoid attracting bears. Sure, it would be nice if the bears would just not bother you in the first place. But you can't influence their behavior directly, you can only influence what you do.

It might be easy for the US to shoot down satellites, but so it might be for Europe.

The whole point of this story is that the USA wants to be able to act without Europe possibly having a say. That Europe agreed was wrong, I think.

My whole point is that the USA can act without Europe having a say, whether Europe likes it or not. It's only reasonable for Europe to take that into account in what they do.

You can take some principled stand to make some sort of abstract point nobody will understand, and have the USA shoot down your satellites in the case of war. Or you can make a small change to your design and have the USA leave them alone. I don't see why taking the second option is so terrible.

If Europe had created Galileo like originally envisioned the USA could not jam Galileo without also jamming GPS. Hence they would need to ask Europe to turn of Galileo or turn Galileo off for them, i.e. shooting down the satellites, which Europe should treat as an act of war. Hence, neither of both options go without Europe having a say.

The abstract point here is akin to mutually assured destruction. It keeps peace.

Having Galileo like originally envisioned and Europe taking a robust defensive strategy w.r.t. to it's satellites would mean GPS for everybody or for nobody or war with Europe. And Europe should make sure nobody wants war with them.

The frequencies were selected to allow for easy compatibility with GPS not because the EU didn't want the US to be able to selectively jam Galileo.

No one in Europe really thinks of a war with the US as a real possibility and since the know what ICBM stands for they also know they've lost before the first shot is fired.

> and have the USA shoot down your satellites in the case of war.

And then we shoot down their satellites, too. The US acting like they can do whatever they want is extremely annoying and has to end, they’re just a country, not the king of the world.

> they’re just a country, not the king of the world.

Militarily and economically the US is an empire (by definition, as its growth is tied to warfare, expansion, and dominance). Just like the British empire was before it.

For example - it has 400 major, and another 400 minor, bases (some with nuclear-ready weapon systems) stationed in foreign countries. While no foreign country has a base in the US.

It's like giving the bully your lunch so they leave you alone.

It's more like giving the bully his favorite seat. You can stand on principle, but the result will be more or less the same either way, and giving him what he wants doesn't hurt you.

I think bullies should be treated with confrontative aggressiveness wherever possible until they stop bullying.

That's a great strategy when you're a member of a society that mostly doesn't put up with bullying, and will ultimately be on your side if their aggression gets too much attention. It's a terrible strategy when you're living in an anarchy and the bully is as mighty as everybody else put together.

Yes. That's why I think a federal EU with united army and foreign policy stands a much better chance of achieving beneficial outcomes for its citizens.

The strategy is also great if you can guarantee the bully mutual complete destruction.

Of course, it cuts both ways.

With the constellations on different frequencies, European powers also have the ability to engage in localised GPS jamming while leaving Galileo available for their military.

Blowing up 1 or more satellites will also increase the amount of orbital debris floating around.

There is already something near 1 million pieces of space junk being actively tracked to avoid possible collisions with existing space vehicles/satellites.

This space junk problem eventually reaches a point where no orbital vehicles will be able to reach, stay in, and/or pass into space.

Europe is part of NATO and has major incentives to cooperate with the US. In the scenario where the US would have to shoot down Galileo sats, would most likely be one where the US is protecting Europe from China or Russia as we're talking WWIII. I imagine this little story is little more than a tempest in a teapot designed to enrage Euro nationalists. The reality is that when you're in a shared defense agreement, your weapons systems, including nav systems, need a high level of cooperation. A frequency shift isn't the tragedy you're making it out to be.

> Europe is part of NATO

Some of Europe is. Austria, Cyprus, Finland, Ireland, Malta, Sweden etc aren't.

You are being pedantic for no reason neither of those nations is a substantial military power.

Except Cyprus they're all in the PfP program though: http://www.nato.int/cps/en/natolive/topics_82584.htm

Austria, for example, participated in missions in Africa, Afghanistan, the Balkans (KFOR, etc).

You really should learn about the subject you're trying to argue about.

PfP isn't a mutual defense agreement, it's more like lets play airsoft together. Hence Russia is a participant, not exactly a NATO membership candidate or ally.

In the case of a hot war between the US and Russia, the first victims (of mushroom clouds) will be every single EU NATO member that hosts US bases and US nuclear weapons.

So I'm not quite sure what the gain is for those members as they will not survive (the US might, but they won't).

In the scenario you mentioned Europe could turn off Galileo if deemed necessary, no need for the USA to shoot it down. The solution taken just makes it easier for USA to wage war against Europes interests.

Europe isn't a single entity. Imagine a conflict in Eastern Europe that the US is part of. The rest of Europe has built its infrastructure on Galileo and shutting it down means major economic and infrastructure issues for Europeans not involved in the conflict. The US asks them to turn it off, but Merkel says no. Or Greece says no because Putin promised them $200m in aid. EU decisions have to be unanimous. Now what? Lets stop pretending European nations, even members of NATO, all care about each other. There's no polite discourse here. Just naked self-interest that's easy for the enemy to game.

Merkel might decide that she wants nothing to do with Russia taking Estonia, Romania, and Bulgaria. This is why we need technical solutions, not political ones. Banking on Europe being nice to each other is hilariously short-sighted and ahistoric.

Note, Europeans are free to leave NATO whenever they wish if they don't like our defense posture and technical requirements. I imagine letting the Russian military loose is probably not within Europe's self-interest, so enforcing technical requirements that protect all of Europe makes sense. It leaves less room for cowardly players like Merkel to appease expansionist dictators like Putin. If anything, the US did European security a favor with this policy.

What is an enemy for the USA might not be an enemy of Europe. I can just repeat myself. If it is in the interest of Europe to turn Galileo off, they can do so. If it is not in their interest, they shouldn't do so. Now, that the decision making in the EU is inefficient might be an _internal_ issue that needs to be solved, not be workedaround by giving the USA the final say.

> EU decisions have to be unanimous.

That's not true.

Treating an ally shooting down your satellites because those satellites are being used against them as an act of war is pretty short sighted.

Purposely designing your satellites in order to force them to do so in the event of a war is even more short sighted.

If American satellites were being used to guide missiles at Europe, you'd be pretty PO'd.

You realize that most of Europe is in NATO with the US, right?

What's the fear with more accuracy?

From my (completely layman) perspective once you've got a meter or so of accuracy, you've got what you need for weapons.

What's further accuracy get you that some nations are against everyone having?

A similar thing happens with commercial imagery satellites. Companies are forced to downsample their high resolution govt-only images to 30cm for the general public.

That's slightly different though, better imagery makes it possible to resolve more features.

With the improved positional accuracy it's a 2 meter circle vs a 1 meter circle. What tactics does a 1 meter circle enable that the 2 meter circle does not enable?

Also, DigitalGlobe only has 30 cm capability:

https://en.wikipedia.org/wiki/WorldView-4

Who is downsampling (DigitalGlobe/GeoEye was downsampling earlier 40 cm imagery for Google, to 50cm)?

My understanding is that it's not exactly "by force" but rather a condition of funding. The U.S. Government is probably Digital Globe's largest customer.

No, it is by force. It is similar to ITAR regulations. If you break that rule, your management team is probably going to jail. It would be akin to spying for a foreign power. Source: I used to do some consulting for a satellite imagery company.

There's no fear about accuracy - the plan is that Galileo will charge for high precision services. Indeed, you can buy centimeter-precision GPS services right now for applications like surveying and precision farming [1] - those are small markets, of course; self-driving cars are the real prize.

The objection from the US amounted to the fact an early Galileo design would have reduced their ability to degrade satellite navigation in war zones. Later the design was changed, so the US can jam Galileo - which avoids the US objection, but makes Galileo less useful as a backup.

[1] http://www.trimble.com/Positioning-Services/Trimble-RTX.aspx

To me that's surprisingly inaccurate. With a corrected system, no ground reference data, we can get 10cm RMS, no?

With appropriate ground corrections 5 cm is pretty easy with the current US satellites. Sub-meter in real time is also fairly easy with the help of WAAS broadcasts and good receivers. But if consumer hardware (like a typical $200 Garmin receiver) could reliably have sub-meter accuracy that would be a big improvement. But I'm no expert on the actual math of GPS.

Anyone around here know details on the encryption used by Galileo, Beidou, and GPS? Google does not turn up much. It would be interesting to hear about how they're doing this.

With the constraints that they have (receivers not necessarily always online to receive key updates, extremely low bandwidth to work with, systems depend heavily on this information, fast locks are important) it would not surprise me if the encryption scheme has big holes in it.

On the other hand, some of these constraints can be dealt with by making receivers fall back to the unencrypted signal until they're locked long enough to get their new keys. And given that this is military, they might err on the side of security rather than accessibility. So who knows.

Reply on news.ycombinator.com