A COMPUTATIONALLY EFFICIENT AMBIGUITY
RESOLUTION TECHNIQUE
Ron Hatch, Tenny Sharpe, NavCom Technology, Inc.
BIOGRAPHY
Ron Hatch is the Director of Navigation Systems at
NavCom Technology, a company of which he was a cofounder. He has developed a number of innovative
techniques for processing GPS measurements and has
obtained more than a dozen patents related to GPS. Ron is
currently the president of the Institute of Navigation, is a
Fellow of the ION and has received the Kepler and
Thurlow awards from the ION.
Mr. Tenny Sharpe is Director of Advanced Development
at NavCom Technology Inc. Mr. Sharpe received a B.S.
in Physics from Case Institute of Technology and a M.S.
in Computer Science from the University of California,
Los Angeles. Mr. Sharpe has over 30 years experience in
the development of aerospace and industrial electronics.
His specializations are software and systems design for
GPS navigation systems.
ABSTRACT
A new method of carrier-phase ambiguity resolution is
described. The new technique is a variation of the leastsquares residual search technique in the ambiguity
domain. It uses a very efficient algorithm to compute the
residuals associated with each potential combination of
ambiguities to be tested. Several other techniques are
employed to simplify the calculations and to enhance the
probability of identifying the correct ambiguity vector.
The intent is to minimize the number of data epochs
required to correctly identify the integer ambiguity values.
The capability of the technique to rapidly identify the
correct ambiguity vector is illustrated by plotting the
results of scoring runs which exercise the search
algorithms using recorded field data taken over different
rover-to-base separation distances. To maximize the
number of searches exercised in these runs, as soon as the
ambiguity vector is identified, the results are cleared and a
new search is initiated with all navigation parameters reinitialized. Some navigation results are also shown which
are typical of RTK carrier-phase navigation results.
INTRODUCTION
The RTK ambiguity resolution technique implemented
within the NavCom dual-frequency receiver has several
unique features designed to minimize the computational
task while ensuring that a minimal data collection interval
is required. The fundamental approach is similar to
several least-squares residual search techniques which
have been employed by others. [1-4]
The first unique feature is that the base station transmits
corrections rather than the raw data, which most RTK
implementations transmit. This has several advantages:
1) it offloads part of the computation from the user
receiver to the base station receiver; 2) it allows code
smoothing of the base station data to occur even before
the user receiver is turned on, which ensures a more
accurate initial code solution; 3) it simplifies the
processing algorithms because no differencing across
receivers is required.
The second unique feature is a simplified computational
technique to generate the residuals resulting from
candidate ambiguity vectors. This technique is the main
subject of the paper and will be explored in some detail.
The search process is a two-stage process which depends
upon the availability of dual-frequency measurements at
both the base-station receiver and the user receiver. First a
wide-lane search is performed and up to 10 ambiguity
vectors, which meet specific requirements (e.g. residuals
less than a threshold value) are saved for further
processing. In the second stage, each of the ambiguity
vectors determined in the first stage are tested by
searching each satellite (except the first to avoid
redundant clock solutions) across the two narrow-lane
ambiguity values which result in a narrow-lane measured
range closest to the corresponding wide-lane measured
range. Those narrow-lane combinations, which meet a
number of specific criteria, are scored and if more than
one are acceptable their relative score is used to determine
whether or not one of them can be declared the correct
ambiguity vector.
λφφ
INITIAL CODE SOLUTION
The primary motivation in the initial code solution is to
obtain the most accurate code solution possible with as
few measurement epochs as possible. Since the baseline
distances over which the ambiguities can be easily
resolved are typically less than 15 kilometers, it is
assumed that the ionospheric refraction effects can be
modeled at both base station and user with sufficient
accuracy that the residual ionospheric errors are almost
negligible. This means that the largest errors, which will
affect the differential code solution, will be the multipath
effects upon the dual-frequency code measurements. The
combination of code measurements which has the
minimum multipath error (or at least very close to the
minimum) is the frequency-weighted sum of the code
measurements. This combination also has the advantage
that it is exactly matched in ionospheric refraction effects
by the wide-lane difference carrier-phase measurement.
This means that it can be smoothed by the wide-lane
carrier-phase measurement with an increasing time
constant, i.e. the multipath error will become smaller and
smaller as the satellite is continuously tracked.
Because the base-station receiver is typically put in
operation long before the user receiver, our choice of
generating the code and carrier phase corrections at the
base-station receiver allows the base-station code
measurements to be smoothed such that most of the
multipath error is removed before the code corrections are
generated. This means that the multipath noise
contributed by the base station receiver is largely
eliminated. This represents a substantial advantage over
the normal practice of sending raw base-station
measurements to the user.
The frequency weighted combined measurement is:
+
PfPf
where f represents the frequency and P the pseudorange
code measurement
The carrier-phase measurement which is affected by the
same amount of ionospheric refraction error is:
where N is the integer ambiguity,
measurement and
By setting equation (1) equal to equation (2) and solving
for the wide-lane ambiguity, N
floating ambiguity can be computed each epoch.
N
=
P
.
NC
λ
the wavelength.
=
w
+
+
)(
ff
21
2211
+
PfPf
2211
λ
w
(1)
ff
21
)(
−+= (2)
ww
21
φ
is the carrier-phase
, a new value for the
w
)(
φφ
−−
(3)
21
This value for the wide-lane floating ambiguity value can
be improved each epoch by computing the recursive
average over all epochs up to the present time. This
smoothed value of N
equation (2) to give a smoothed carrier-phase
pseudorange:
One can use the process represented by equations (1)
through (4) at both the base-station receiver and at the
user receiver. At the base station the smoothed carrierphase pseudorange is differenced with the true range to
yield a pseudorange correction which, after removing the
common clock effect, is sent to the user receiver. At the
user receiver the correction is applied to the combined
frequency-weighted code measurement as represented by
equation (1). A wide-lane carrier-phase correction is also
generated at the base station by arbitrarily selecting a
whole-lane integer in equation (2) and differencing it with
the true range. The whole-lane error, which is made by
arbitrarily selecting the ambiguity value at the base station
is absorbed into the whole-lane ambiguity value at the
user receiver. After clock removal, this carrier-phase
correction is sent to the user receiver and applied to the
wide-lane carrier-phase measurement as represented by
equation (2). The significant advantage to this process, as
indicated above, is that, due to the separate smoothing, the
multipath corruption of the base station measurements is
usually largely removed even before the user receiver is
turned on. This means that the initial smoothed code
measurements at the user receiver are more accurate and a
more accurate code solution will be obtained.
At the user receiver, the corrected and smoothed value of
equation (4) for each satellite is now used in a leastsquares process to obtain an initial code solution.
WIDE-LANE SEARCH
While the process described above, i.e. equation (4), gave
us a set of floating (non-integer) ambiguity values for
each satellite, a better set (fewer degrees of freedom) can
be obtained from the initial code solution. Also we note
that given a set of integer ambiguities, a second set,
differing from the first by a constant integer value for
each satellite, will result in the same identical spatial
position but with a different clock value. Because our
clock solution is of no interest and can be selected
arbitrarily, this means that we can constrain one of the
ambiguity values arbitrarily. In our process, we choose to
use the highest elevation satellite as the reference satellite
and force its ambiguity value to zero. Using the initial
code position solution, we can compute a range, R, to
each satellite and set it equal to the measurement
represented by equation (2). Solving the result for the
ambiguity value and subtracting the ambiguity value of
the highest elevation satellite gives:
can then be substituted back into
w
NC
λφφ
)(
−+= (4)
ww
21
2
)()(/)(
ZHX
IHX
λφφλφ
=
+
w
rii
RRN
w
rrii
φφφφλ
−+−−−= (5)
2121
where the superscript, i, represents each satellite in turn
and the superscript, r, represents the reference satellite—
in this case the highest elevation satellite.
Our initial wide-lane carrier-phase RTK solution involves
rounding the floating ambiguities so obtained to their
integer values, substituting these values into equation (4)
and computing a new least-squares position solution. The
floating ambiguity given by equation (5) is used in the
search process to sequentially select the closest integer
values over the selected search range.
We have found that searching over the four closest values
is almost always sufficient to include the true ambiguity
value. Given n satellites this means that there will be 4
n-1
permutations of the ambiguity vector. Thus, there will be
1024 permutations when six satellites meet the
appropriate elevation criterion and 4096 when seven
satellites are available. With each ambiguity permutation
a set of wide-lane carrier-phase measurement residuals
can be computed. It is these residuals which play a
prominent role in determining the correct set of integer
ambiguity values. However, obtaining the residuals by recomputing a least-squares solution for each permutation is
computationally prohibitive. A much faster way to
compute the residuals is to use a residual sensitivity
matrix, S.
RESIDUAL SENSITIVITY MATRIX
Given the linearized measurement equation:
where H is the sensitivity matrix (i.e. the direction cosines) of
the state vector (position and clock corrections), x, to the
innovations (difference between the measurements and their
expected value), z.
zHx = (6)
Equation (6) can be expanded to include a set of position
and clock corrections corresponding to a set of
innovations:
= (7)
Now if we want to see the separate effect on the position
of a single whole-cycle change in the ambiguity value of
each satellite, Z will become the identity matrix (or
depending on units, the identity matrix times the scalar
wavelength).
= (8)
The least-squares solution for X is then:
TT
1
= (9)
−
HHHX
)(
For a weighted least-squares solution this becomes:
111
−−−
= RHHRHX
TT
)(
(10)
where R is the measurement covariance matrix.
Note that the left hand side of equation (9) or (10) can be
pre-computed and when multiplied by the appropriate
column of the identity matrix (or scaled identity matrix)
gives the appropriate column of X, which is the associated
change in the position and clock caused by the integer
ambiguity change.
Multiplying equation (9) by H tells us how much that
change in position will affect the innovations.
TT
1
= (11)
−
HHHHHX
)(
Now if we subtract this change in the innovations from
the input value of the innovations (I) we get the effect on
the residuals of a whole cycle change in the ambiguity
value for each satellite. This is called the residual
sensitivity matrix, S, and is given by:
TT
1
−= (12)
−
HHHHIS
)(
The residual sensitivity matrix, S, for a weighted least
squares solution is:
111
−−−
−= RHHRHHIS
The S matrix has a number of interesting properties. It is
symmetric. It is idempotent, i.e. S=S
TT
)(
2=S3
=… The sum of
(13)
any row or column equals zero, i.e. residuals are zero
mean. The length of any row or column is equal to the
square root of the associated diagonal element. Since the
solution vector, x, has four elements, the rank of S is n-4
where n is the number of satellites.
The residuals of the initial RTK solution, described in the
prior section are updated by adding the product of the S
matrix and the matrix formed by scaling the identity
matrix diagonal elements by the specific permutation of
changes in the integer ambiguity values to be tested. The
ten permutations with the smallest root-sum-square (rss)
of residuals are saved for further narrow-lane processing
if their rss residuals is less than an acceptable threshold
value.
STEPPING TO THE NARROW-LANE
Assuming the differential ionospheric refraction is
negligible allows us to equate the narrow-lane range to
the wide-lane range. Thus:
Solving equation (14) for the L
9
4
17
NN
ambiguity value gives:
1
9
NN (15)
3(
w
17
)()(
−+
−+=
21111
9
4
17
(14)
ww
)
φφ
211
It is interesting to note that the deviation from an integer
value obtained for N
in equation (15) is identical in
1
3
information content to the deviation one will obtain in
attempting to step to any other narrow or wide-lane
ambiguity value. While the deviation is not always the
same, it is either the fractional complement or a multiple
of the same fraction. Thus to step to N
analogous equation:
Similarly, the equation to compute the ambiguity value
for the average of the carrier-phase on L
typically gives the most accurate position) is:
Obviously there is no noise present in the value for N
any of the equations above. The noise in the computed
value of the integer ambiguity arises from the
amplification of the multipath corruption of the carrierphase measurements in the right-hand term of the above
equations. This noise rarely exceeds one-cycle. Thus, a
search for the narrow-lane ambiguity value which
minimizes the rss residuals, need only test for the two
integer values closest to the value computed in the above
equations.
SCORING THE INTEGER COMBINATIONS
The wide-lane integer combinations with rss residuals less
than a threshold, or if more than ten, the ten combinations
with the smallest rss residuals are subject to the narrowlane search and assigned a score. Like a golf score, the
lowest scores are considered the best scores. The score
assigned to each combination is a function of a number of
parameters. The factors considered in assigning a score
include the following: 1) the narrow lane residuals; 2) the
refraction corrected residuals; 3) the L
separation (note that the matrix defined by the left hand
side of equation (9), which is needed to compute the S
matrix, can be used to compute the position updates or
position separation simply by multiplying by the
appropriately scaled search permutations); 4) the distance
from the code solution; 5) the number of the wide-lane
integers in the permutation which selected the larger
(greater than 0.5) fractions; and 6) the number of narrowlane integers in the permutation which selected the larger
fractions.
The above factors are used to assign a score to each
permutation which meets a number of criteria. Among the
criteria is that the score be less than a threshold value, and
9
3
NN (16)
w
17
1
4
NN (17)
wA
34
9
3(
17
9
3(
17
one obtains the
2
9
4
−+=
4
−+=
1
)
φφ
212
17
and L2 (which
1
9
)
φφ
21
17
and L2 position
w
in
that threshold value is itself a function of the separation
distance between the base station and the user. If no
permutation is selected as the correct permutation, the
scores are cumulated from epoch to epoch.
The best integer ambiguity permutation is assigned a
differential score. This differential score is the difference
between the second best permutation and the best. If there
is no second best permutation which is acceptable then
the differential score of the best permutation is the
difference between the score threshold and the best
permutation’s score. If the differential score is large
enough the best permutation is accepted as the correct
integer ambiguity set. However, if there are fewer than
seven satellites involved in the ambiguity search, the
entire process is repeated and several repeated selections
of the same integer ambiguity permutation is required for
final acceptance as the correct set of integers.
While the above process is a bit complicated, when seven
or more satellites are available, it often provides the
correct integer ambiguity set in a single epoch.
Identifying the wrong set of integers as the correct set
typically occurs only a few times out of 1000 attempts.
When at least seven satellites are available integer
ambiguity failure is extremely rare.
TEST RESULTS
The RTK ambiguity search process described above has
been incorporated into NavCom’s dual-frequency OEM
GPS receivers. However, in order to more easily evaluate
the ambiguity resolution process, an offline version was
also built. The offline capability allows one to perform
scoring runs in which the ambiguity search process is
repeated over and over. As soon as one set of integer
ambiguity values is declared correct, the search process is
reinitialized (which takes one epoch) and a new search is
performed.
Figures 1 and 2 show the results of processing 10 hours of
short baseline (approximately 10 meters) in a scoring run.
13,659 successful searches were conducted. 84% of the
searches were accomplished in a single epoch.
Figure 3 and 4 show the results of processing
approximately an hour and a half of data collected over a
5 kilometer baseline. 1,772 successful searches were
conducted of which 82% were accomplished in a single
epoch.
The navigation accuracy is shown in a bull’s eye plot in
Figure 5. The standard deviation in north, east and up
were 4, 5 and 11 millimeters respectively.
4
NCT2000D RTK Search Times
90
Average Search Time (seconds) 1.6
Maximum Search Time (seconds) 50.0
60
30
0
Search Time (seconds)
-30
Short Baseline RTK Integer Ambiguity Resolution Scoring Run
10 Hours, 13,659 Searches
-60
012345678910
Time (hours)
Figure 1. Short Baseline Scoring Run Search Time vs. Run Time
25
20
15
10
Number of Satellites in Search
5
0
80.0%
60.0%
40.0%
20.0%
0.0%
NCT2000D RTK Search Times
84%
Average Search Time (seconds) 1.6
Maximum Search Time (seconds) 50.0
Short Baseline RTK Integer Ambiguity Resolution Scoring Run
10 Hours 13,659 Searches
1%
6%
RTK Search Time (epochs)
2%
2%
1%
1%
0%
0%
0%
0%
3%
12345791113152025
Figure 2. Short Baseline Scoring Run Histogram of Search Times
5
NCT2000D RTK Search Times
90
Average Search Time (seconds) 1.46
Maximum Search Time (seconds) 21.00
60
30
0
Search Time (seconds)
-30
5Km Baseline RTK Integer Ambiguity Resolution Scoring Run
1.25 Hours 1,772 Searches
-60
0 0.25 0.5 0.75 1 1.25
Time (hours)
Figure 3. Five Kilometer Scoring Run
25
20
15
10
5
0
Number of Satellites Used in Search
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
NCT2000D RTK Search Times
82%
Average Search Time (seconds) 1.46
Maximum Search Time (seconds) 21.00
5Km Baseline RTK Integer Ambiguity Resolution Scoring Run
1.25 Hours 1,772 Searches
8%
12345791113More
4%
1%
2%
Search Time (epochs)
3%
0%
0%
0% 0%
Figure 4. Five Kilometer Scoring Run
6
NavCom RTK Navigation 24 Hours on a Stationary Point
0.05
0.04
0.03
0.02
0.01
0
-0.01
-0.02
Position Error North (meters)
-0.03
-0.04
-0.05
-0.08 -0.07 -0.06 -0.05 -0.04 -0.03 -0.02 -0.01 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08
Average (cm.) -0.1 -0.1 0.4
Std. Dev. (cm.) 0.4 0.5 1.1
2 cm
NCT2000D receivers
NCT2000A antennas
Position Error East (meters)
East North Up
1 cm
9 meter baseline
Figure 5. RTK Navigation Results – Horizontal Position Scatter Plot
CONCLUSION
A new approach to the ambiguity resolution process has
been described. It is computationally efficient, in that a
simple process is used to compute the residuals without
first computing a position solution. Position solutions are
computed (also using a simplified process) only when the
residuals indicate the particular integer ambiguity
permutation has a high probability of being the correct
set. Using a wide-lane search before stepping to a narrow
lane search, is also efficient in that fewer permutations are
required to cover the same three-dimensional search
region. The frequency-weighted code combination
ensures a starting position with minimal multipath
corruption and the longer the search takes the better the
initial code solution becomes because of the codesmoothing employed. As shown by the test results, the
search procedure is highly reliable and 80% or more of
the searches are successfully completed in a single epoch.
REFERENCES
1. Han, Shaowei, and Chris Rizos (1997). Comparing
FPS Ambiguity Resolution Techniques, GPS World,
vol. 8, no.10, pp.54-61.
2. Hatch, Ron, and Hans-Juergen Euler (1994).
Comparison of Several AROF Kenematic
Techniques, Proc. ION GPS-94, pp. 363-370.
3. Hwang, Patrick Y.C. (1991). Kinematic GPS for
Differential Positioning: Resolving Integer
Ambiguities on the Fly, Navigation, vol. 38, no. 1,
pp.1-15.
4. Pratt, M., B. Burke, and P. Misra (1997). SingleEpoch Integer Ambiguity Resolution with GPS L1L2 Carrier Phase Measurements, Proc. ION GPS-97,
pp. 1737-1746.
7
Loading...