假使宇宙完全符合牛頓力學，有個一致的『時間流』。那麼只要將所有 GPS 衛星與接收器都能『時間同步』，『定位問題』就是藉由接收到的『時間和位置』訊息，求解三條『歐式距離』方程式罷了 。然而由於很難作到衛星與接收器『時間同步』── 原子鐘太昂貴 ──，所以至少需要四顆衛星才能『定位』的哩︰

Problem description

The receiver uses messages received from satellites to determine the satellite positions and time sent. The x, y, and z components of satellite position and the time sent are designated as [x_i, y_i, z_i, s_i] where the subscript i denotes the satellite and has the value 1, 2, …, n, where n ≥ 4. When the time of message reception indicated by the on-board receiver clock is t̃_i, the true reception time is t_i = t̃_i − b, where b is the receiver’s clock bias from the much more accurate GPS system clocks employed by the satellites. The receiver clock bias is the same for all received satellite signals (assuming the satellite clocks are all perfectly synchronized). The message’s transit time is t̃_i − b − s_i, where s_i is the satellite time. Assuming the message traveled at the speed of light, c, the distance traveled is (t̃_i − b − s_i) c.

For n satellites, the equations to satisfy are:

or in terms of pseudoranges,  , as

.^[110][111]

Since the equations have four unknowns [x, y, z, b]—the three components of GPS receiver position and the clock bias—signals from at least four satellites are necessary to attempt solving these equations. They can be solved by algebraic or numerical methods. Existence and uniqueness of GPS solutions are discussed by Abell and Chaffee.^[57] When n is greater than 4 this system is overdetermined and a fitting method must be used.

With each combination of satellites, GDOP quantities can be calculated based on the relative sky directions of the satellites used.^[112] The receiver location is expressed in a specific coordinate system, such as latitude and longitude using the WGS 84 geodetic datum or a country-specific system.^[113]

Geometric interpretation

The GPS equations can be solved by numerical and analytical methods. Geometrical interpretations can enhance the understanding of these solution methods.

Spheres

The measured ranges, called pseudoranges, contain clock errors. In a simplified idealization in which the ranges are synchronized, these true ranges represent the radii of spheres, each centered on one of the transmitting satellites. The solution for the position of the receiver is then at the intersection of the surfaces of three of these spheres.^[114] If more than the minimum number of ranges is available, a near intersection of more than three sphere surfaces could be found via, e.g. least squares.

Hyperboloids

If the distance traveled between the receiver and satellite i and the distance traveled between the receiver and satellite j are subtracted, the result is (t̃_i − s_i) c − (t̃_j − s_j) c, which only involves known or measured quantities. The locus of points having a constant difference in distance to two points (here, two satellites) is a hyperboloid (see Multilateration). Thus, from four or more measured reception times, the receiver can be placed at the intersection of the surfaces of three or more hyperboloids.^[57][58]

Spherical cones

The solution space [x, y, z, b] can be seen as a four-dimensional geometric space. In that case each of the equations describes a spherical cone,^[115] with the cusp located at the satellite, and the base a sphere around the satellite. The receiver is at the intersection of four or more of such cones.

Solution methods

Least squares

When more than four satellites are available, the calculation can use the four best, or more than four simultaneously (up to all visible satellites), depending on the number of receiver channels, processing capability, and geometric dilution of precision (GDOP).

Using more than four involves an over-determined system of equations with no unique solution; such a system can be solved by a least-squares or weighted least squares method.^[110]

Iterative

Both the equations for four satellites, or the least squares equations for more than four, are non-linear and need special solution methods. A common approach is by iteration on a linearized form of the equations, such as the Gauss–Newton algorithm.

The GPS system was initially developed assuming use of a numerical least-squares solution method—i.e., before closed-form solutions were found.

Closed-form

One closed-form solution to the above set of equations was developed by S. Bancroft.^[111][116] Its properties are well known;^{[57][58][117]} in particular, proponents claim it is superior in low-GDOP situations, compared to iterative least squares methods.^[116]

Bancroft’s method is algebraic, as opposed to numerical, and can be used for four or more satellites. When four satellites are used, the key steps are inversion of a 4×4 matrix and solution of a single-variable quadratic equation. Bancroft’s method provides one or two solutions for the unknown quantities. When there are two (usually the case), only one is a near-Earth sensible solution.^[111]

When a receiver uses more than four satellites for a solution, Bancroft uses the generalized inverse (i.e., the pseudoinverse) to find a solution. However, a case has been made that iterative methods (e.g., Gauss–Newton algorithm) for solving over-determined non-linear least squares (NLLS) problems generally provide more accurate solutions.^[118]

Leick et al. (2015) states that “Bancroft’s (1985) solution is a very early, if not the first, closed-form solution.”^[119] Other closed-form solutions were published afterwards,^[120][121] although their adoption in practice is unclear.

 

因為每顆衛星都用『相同頻率』作廣播，加上『相對運動』產生之『都卜勒效應』，所以每顆衛星皆用『唯一』的 PRN 碼︰

GPS信號擷取

簡介

GPS 信號擷取的目的在於獲知所得到的衛星為何，若是有某顆衛星資訊是可得知的，則必須取得此信號的兩個性質：

• 頻率

從規格可以得知 L1 的頻率為1575.42 Mhz，L2的頻率為1227.60 MHz，之後的討論皆以L1做討論，L1 的信號經過一連串的處理之後，頻段 IF=9.548 MHz，從特定衛星得到的頻率並不一定是如規格所給予，而是因為有相對運動的關係，在頻率上產生都卜勒效應，因為衛星的移動，假設 GPS 接收機靜止接收 GPS 信號，都卜勒效應所影響的範圍大約為 5 kHz，如果 GPS 接收機也處於高速移動的狀態下，都卜勒效應所影響的頻率可能會到達 10 kHz。

• 碼相位

碼相位代表C/A 碼開始的正確資料區塊

目前來說，做 GPS 信號擷取的方法都是根據 GPS 信號的特質來做處理，衛星信號是由 32 個不同的偽隨機雜訊（Pseudorandom Noise,PRN）序列區隔，而上述所說的特質就是指這些偽隨機雜訊序列的彼此之間的幾乎沒有互相關，只有自己本身和自己只有在沒有延遲的情況下，自相關函數才會有極值。假設接收到的信號  是由  個可得知的衛星信號組合而成。

會運用接收機本身的偽隨機雜訊序列產生器產生 衛星的偽隨機雜訊序列，再透過改變碼相位和振盪器所產生的載波頻率不同，來與接收到的信號做處理比對，而這幾種方法分別為：

• 直接搜尋（Serial Search）
• 平行頻率空間搜尋（Parrallel Frequency Space Search）
• 平行碼相位搜尋（Parrallel Code Phase Search）

 

這指出『快速定位』和『處理渠道』 channel 之關係也︰

How many GPS channels make sense?

The answer is complex due to the way the GPS system operates, so I’m going to simplify a number of things so you understand the principle, but if you are interested in how it’s really implemented you’ll need to go find a good GPS reference. In other words, what’s written below is meant to give you an idea of how it works, but is technically wrong in some ways. The below is not correct enough to implement your own GPS software.

Background

All the satellites transmit on essentially the same frequency. They are technically walking all over each others’ signals.

So how does the GPS receiver deal with this?

First, each satellite transmits a different message every mS. The message is 1024 bits long, and is generated by a pseudo random number generator.

The GPS receiver receives the entire spectrum of all the transmitters, then it performs a process called correlation – it generates the specific sequence of one of the satellites, multiplies it by the signal input, and if its signal matches a satellite’s signal exactly then the correlator has found one satellite. The mixing essentially pulls the satellite’s signal out of the noise, and verified that 1) we have the right sequence and 2) we have the right timing.

However, if it hasn’t found a match, it has to shift its signal by one bit and try again, until it’s gone through all 1023 bit periods and hasn’t found a satellite. Then it moves on to trying to detect a different satellite at a different period.

Due to the time shifting (1023 bits, 1,000 transmissions per second), in theory it can completely search a code in one second to find (or determine there’s nothing) at a particular code.

Due to the code shifting (there are currently 32 different PRN codes, one each for each satellite) it can therefore take 30+ seconds to search each satellite.

Further, doppler shift due to the speed of the satellite relative to your ground speed, means that the timebase could be shifted by as much as +/- 10kHz, therefore requiring searching about 40 different frequency shifts for a correlator before it can give up on a particular PRN and timing.

What this means

This leaves us with a possible worst case scenario (one satellite in the air, and we try everything but the exact match first) of a time to first fix off a cold start (ie, no information about the time or location of the receiver, or location of the satellites) of 32 seconds, assuming we don’t make any assumptions, or perform any clever tricks, the received signal is good, etc.

However, if you have two correlators, you’ve just halved that time because you can search for two satellites at once. Get 12 correlators on the job and it takes less than a few seconds. Get a million correlators and in theory it can take a few milliseconds.

Each correlator is called a “channel” for the sake of marketing. It’s not wholly wrong – in a sense, the correlator is demodulating one particular coded frequency at a time, which is essentially what a radio receiver does when you switch channels.

There are a lot of assumptions a GPS receiver can make, though, that simplify the problem space such that a generic 12 channel receiver can get a fix, in the worst case, in about 1-3 minutes.

While you can get a 3D fix with a 4 channel GPS, when you lose a GPS signal (goes beyond the horizon, or you go under a bridge, etc) then you lose 3D fix and go to 2D fix with three satellites while one of your channels goes back into correlation mode.

Now your receiver starts to downloaded the ephemeris and almanac, which allows the receiver to very intelligently search for signals. After 12 minutes or so it knows exactly which satellites should be in view.

So the search goes pretty quickly because you know the position and code for each satellite, but you still only have a 2D fix until you actually find a new satellite.

If you have a 12 channel receiver, though, you can use 4 of the strongest channels to provide your fix, a few channels to lock onto backup satellites so it can switch the calculations to them if needed, and several channels to keep searching for satellites the receiver should be able to see. In this way you never lose the full 3D fix.

Since you can only see up to 12 satellites, why would you need more than 12 channels?

There are 24 or so GPS satellites operating at any given time, which means that on one point on the earth you can really only see half of them.

But remember – you can only search for one satellite per correlator, so the primary reason to increase correlators past twelve is to improve the time to first fix, and the main reason to improve that is for power consumption.

If your GPS chipset has to be powered all the time, it’s a 100mW power drain all the time. If, however, you only need to turn it on once per second for only 10mS each time, then you just cut your power consumption down to 1mW. This means your cell phone, location beacon, etc can operate for two orders of magnitude longer time on the same set of batteries while still maintaining a full real time fix on their location.

Further, with millions of correlators, one can do more exact searches which can help reduce the effects of radio reflections in urban canyons (tall buildings in big cities used to foul up GPS receivers with fewer correlators).

Lastly, while only 4 satellites are needed to get a 3D fix, good receivers use more satellites in its position algorithm to get a more accurate fix. So only a 4 channel receiver is required, but a 12 channel receiver can get more accuracy.

Conclusion

So the millions of correlators:

• Speeds up satellite acquisition
• Reduces power consumption
• Reduces likelihood of losing a 3D fix even in urban canyons
• Provide better sensitivity, allowing fixes in dense forests, and even in some tunnels
• Provides better positioning accuracy