Full text of DOI:10.1002/j.2161-4296.2003.tb00336.x

A High-Integrity and Efficient GPS Integer
Ambiguity Resolution Method
M. F. ABDEL-HAFEZ, Y. J. LEE, W. R. WILLIAMSON, J. D. WOLFE, and J. L. SPEYER
University of California-Los Angeles, Los Angeles, California
Received February 2003; Revised August 2003
ABSTRACT: An efficient method for obtaining the admissible integer ambiguity hypotheses within a probabilistic
volume is combined with an integer hypothesis testing method to reduce the convergence time to the GPS carrier-phase
integers with high probability. The baseline coordinates, float ambiguities, and their covariance matrices are first
estimated using a Kalman filter. To reduce the hypothesis set, the covariance matrix decorrelation method, which is the
major contribution of the least-squares ambiguity decorrelation adjustment (LAMBDA) method, is then applied. The
reduced admissible hypotheses are tested by the multiple-hypothesis Wald sequential probability test (MHWSPT) to
select, with a given probability, the most likely hypothesis. This method considerably reduces the computational time
needed to solve the integer ambiguity resolution problem at each epoch.
NOMENCLATURE
INTRODUCTION
ꢀki
.
k-th satellite code measurement at receiver i
Doppler measurement between satellite k
and receiver i
k-th satellite carrier-phase measurement at
receiver i
Doppler shift between satellite k and receiver i
A wide range of applications of GPS require
achieving centimeter-level accuracy. For those appli-
cations, GPS carrier-phase measurements must be
used. Therefore, fast and reliable methods have been
developed for resolving the carrier-phase integer
ambiguity. Once this ambiguity has been resolved,
the carrier-phase measurement acts like a high-
accuracy GPS code measurement.
Most of the schemes in the literature start with
treating the integer ambiguity as a float. After gener-
ating an initial estimate of the integer using the GPS
code measurement, a hypothesis space is set, and the
integer ambiguity is determined using a ꢇ2 test [1–3].
These algorithms all lack a proof of convergence. More
theoretically involved algorithms that treat the inte-
ger ambiguity as a random integer vector can be found
in [4] and [5]. Currently, real-time results are not
available for these algorithms.
One of the most widely used methods for GPS
integer ambiguity resolution is the least-squares
ambiguity decorrelation adjustment (LAMBDA)
method [6–8]. The LAMBDA method has been
found to be quite efficient in processing data in the
float estimation and using a transformation that
preserves the probability volume. The heuristic
aspect of the procedure is in resolving the integer
from the float process. On the other hand, the
multiple-hypothesis Wald sequential probability
test (MHWSPT) [9–11] has been found to be a very
efficient method for converging to the correct
integers. This method is essentially a nonlinear
sequential filter that, after conditioning of the meas-
urements, is optimal.
ꢀik
ꢁki
.
ꢁik
Nik k-th satellite initial integer number of wave-
lengths from receiver i (integer ambiguity)
xk k-th satellite position vector
xi i-th receiver position vector (vehicle’s posi-
tion)
ꢂ carrier-phase wave length
c speed of light in vacuum
ꢃk k-th satellite clock delay
.
ꢃk k-th satellite clock drift
ꢃi i-th receiver clock delay
ꢃi i-th receiver clock drift
.
Ik k-th satellite ionospheric delay
Tk k-th satellite tropospheric delay
Ek k-th satellite transmitted ephemeris set error
MPik k-th satellite code multipath error at
receiver i
mpik k-th satellite carrier multipath error at
receiver i
ꢄik code receiver noise
ꢅik carrier-phase receiver noise
ꢆki Doppler measurement noise
NAVIGATION: Journal of The Institute of Navigation
Vol. 50, No. 4, Winter 2003–2004
Printed in the U.S.A.
295

We show here how these two methods can be
combined such that a very efficient and accurate
scheme results. The essential approach is to use the
ambiguity covariance matrix decorrelation process
of the LAMBDA method to effectively reduce the
number of hypotheses. These hypotheses are then
tested using the MHWSPT. A summary of the pro-
cedures for the proposed method is as follows:
obtain a compact hypothesis set, as seen in the small-
sized dashed box of Figure 1(b). This small hypothe-
sis space is transformed back to the original space as
shown in Figure 1(c). At this last stage, and with this
small-sized hypothesis space, the MHWSPT is con-
ducted to fix the integer ambiguity by sequentially
processing a uniquely formed measurement residual
given these hypotheses.
The major contribution of the proposed method is
that the reduced hypothesis set obtained from the
covariance matrix decorrelation increases the effi-
ciency and reliability of the algorithm while retain-
ing the proven convergence criteria. Numerical
examples provided at the end of the paper show the
efficiency of the proposed method.
1. Using a Kalman filter, the baseline coordi-
nates, float ambiguities, and their covariance
matrices are estimated as initial values.
2. The original ambiguity space is transformed
into the approximately decorrelated one using
the decorrelation transformation based on the
ambiguity covariance matrix decorrelation that
preserves the integer nature of the ambiguity.
3. The integer ambiguity searching set in the
transformed integer ambiguity space is con-
structed, and the set is retransformed back to
the original ambiguity space. A new hypothesis
set, which is largely reduced compared with the
original one, is constructed in the original space.
4. The MHWSPT is performed on the new set of
hypotheses, and the integer ambiguity is
resolved.
GPS OBSERVABLES
GPS receivers provide several types of GPS
measurements. These measurements include
coarse/acquisition (C/A)-code–derived pseudo-
range measurements, P-code–derived pseudorange
measurements, carrier-phase measurements, and
Doppler measurements. The latter three can be meas-
ured on two carrier frequencies—L1 and L2. The GPS
receivers also provide, at a much lower frequency, the
ephemeris data from which we extract the positions of
the GPS satellites. The code measurement of satellite
vehicle k by receiver i can be represented as
Considering a two-dimensional integer ambiguity
problem, Figure 1 shows a schematic diagram for
steps 1 through 3 of the proposed method. Figure 1(a)
shows the ellipse defined by the float integer covari-
ance matrix with a dashed box surrounding the inte-
ger hypotheses that need to be tested to obtain the
correct integer ambiguity. The large correlations
between the float integers that are indicated by this
highly elongated ellipse explain why it is difficult to
define a small integer hypothesis space. By trans-
forming the original space in Figure 1(a) to a decor-
related space as in Figure 1(b), it becomes easy to
ꢀki ꢊ
'
xi ꢋ xk
'
ꢌ cꢃk ꢌ cꢃi ꢌ ꢍk ꢌ ꢎk ꢌ Ek
ꢌ MPki ꢌ ꢄki
(1)
while the carrier-phase measurement is repre-
sented as
ꢂ(ꢁki ꢌ Nki ) ꢊ
'
xi ꢋ xk
'
ꢌ cꢃk ꢌ cꢃi ꢋ Ik ꢌ Tk
ꢌEk ꢌ mpki ꢌ ꢅki
(2)
Similarly, the Doppler measurement between satel-
lite vehicle k and receiver i is described as
k
k
k
ꢀi ꢊ ꢁi ꢌ cꢃ˙ ꢌ cꢃ˙ i ꢌ ꢆik
(3)
˙
˙
For a particular satellite, when the GPS measure-
ment at the slave vehicle, subscript s, is differenced
from the GPS measurement at a base vehicle in close
proximity, subscript b, the common-mode errors are
.
removed (these include Ik, Tk, Ek, cꢃk, cꢃk). This is the
single-differenced measurement that can be obtained
for all satellites in view. By differencing two single-
differenced measurements—for example, the single-
differenced measurement of satellite l from that of
satellite k—we remove the receiver clock bias and the
receiver clock drift from the estimation problem. Thus,
the following double-differenced code, carrier-phase,
and Doppler measurement equations are obtained:
ꢈꢉꢀk1 ꢊ ͉͉xb ꢋ xk͉͉ ꢋ ͉͉xs ꢋ xk͉͉
Fig. 1–Schematic Flow of Integer Ambiguity Space Trans-
formations
ꢋ (͉͉xb ꢋ x1͉͉ ꢋ ͉͉xs ꢋ x1͉͉) ꢌ ꢈꢉꢄ (4)
296
Navigation
Winter 2003–2004

ꢂ(ꢈ∆ꢁk1 ꢌ ꢈ∆Nk1) ꢊ
'
xb ꢋ xk
xb ꢋ xl
'
ꢋ
'
xs ꢋ xk
xs ꢋ xl
'
'
the state propagation; and ␻V models the relative dis-
tance acceleration. By defining
ꢋ
'
'
ꢋ
'
΂
ꢌ ꢉꢈꢅ
΃
ꢈꢉ␳– (k)
˜
(5)
(6)
ꢈꢉ␾(k) ꢊ ꢈꢉ␾(k) ꢋ
ꢂ
˙
˙
˙
˙
k1
k
1
ꢈꢉꢀ ꢊ ꢁb ꢋ ꢁks ꢋ (ꢁb ꢋ ꢁ1s) ꢌ ꢈꢉꢆ
˙
–
˜
ꢈꢉ␳(k) ꢊ ꢈꢉ␳(k) ꢋ ꢈꢉ␳(k)
Note that we assume the multipath error to be
negligible. Here we seek to resolve the integer ambi-
guity ꢈꢉNk1 for all satellites k, k ϶ 1, in view. We
then linearize these equations about a nominal base
and slave trajectories and stack all satellites’
double-differenced measurements in vector form to
obtain
–
˙˜
˙
ꢈꢉ␳
(k) ꢊ ꢈꢉ␳˙(k) ꢋ ꢈꢉ␳(k)
The linearized measurement equations for the three
measurements become
˜
ꢈꢉ␳
ꢉH
0
0
0
ꢋI
0
0
0
ꢉx
N
˜
ꢈꢉ␾
ꢊ
–
΄ ΅ ΄
΅΄ ΅
ꢈꢉ␳ ꢊ ꢈꢉ␳ ꢌ ꢉHꢉꢏx ꢌ ꢈꢉ␩
(7)
(8)
˙
˜
˙
ꢈꢉ␳
ꢉH ꢉx
–
ꢂ(ꢈꢉ␾ ꢌ ꢈꢉN) ꢊ ꢈꢉ␳ ꢌ ꢉHꢉꢏx ꢌ ꢈꢉ␤
y(t)
C(t)
9
˙
˙
˙
ꢈꢉ␳ ꢊ ꢈꢉ␳ ꢌ ꢉHꢉꢏx ꢌ ꢈꢉ␥ (9)
ꢈꢉ␩
ꢈꢉ␤ ꢋ ꢈꢉ␩
where ꢉH is the differenced linearization matrix that
represents the receiver–satellite geometry. The
unknowns in the above equations are ꢈꢉN, ꢉꢏx, and
ꢌ
(11)
ꢂ
ꢈꢉ␥
΄
΅
˙
ꢉꢏx. To make the integer ambiguity resolution
v(t)
scheme converge more rapidly, we generally combine
the L1 and L2 measurements into a “widelane” meas-
urement with a longer wavelength. Nevertheless, the
proposed method was used only for L1 GPS integer
ambiguity resolution, as will be shown in the experi-
mental results.
We also linearize the slave measurement equation
around the base position, such that
ꢉꢏx ϵ ꢉx ꢊ xb ꢋ xs
This approach is valid when the base and slave
receivers are in close proximity, say, a few kilometers.
An estimate of the baseline, float ambiguity, and
relative velocity is obtained using a Kalman filter of
the form
KALMAN FILTER FOR FLOAT SOLUTION
We use a Kalman filter to generate an initial esti-
mate of the integer ambiguity without enforcing the
integer nature of the ambiguities. This is what is
referred to in the literature as the float integer ambi-
guity. The filter utilizes both the double-differenced
code measurement and the double-differenced carrier-
phase measurement. We also use the double-
differenced Doppler measurement to enhance the
estimation accuracy, since it is a very clean signal in
comparison with the code measurement.
˙
T
ꢋ1
ˆ
ˆ
X(t) ꢊ A(t)X(t) ꢌ P(t)C (t)V(t)
ˆ
ꢐ y(t) ꢋ C(t)X(t)
(12)
΄
΅
where the estimator error covariance P(t) is given as
T
˙
P(t) ꢊ A(t)P(t) ꢌ P(t)A (t)
ꢋ P(t)CT(t)Vꢋ1(t)C(t)P(t) ꢌ W (13)
the covariance P(t) is explicitly decomposed as
Therefore, the state of the float filter includes the
relative distance between the two receivers (ꢉx), the
ˆ
ˆ
Qxˆ
Qxˆ N Qxˆ V
float integer ambiguity (N), and the relative velocity
.
ˆ
ˆ
ˆ ˆ
between the two receivers (ꢉx). Note that, from this
P(t) ꢊ Qxˆ N QN
QN V
(14)
΄
΅
point on, we denote N ϵ ꢈꢉN for short. Thus, the
dynamic equations are described as
ˆ
ˆ
ˆ
ˆ
Qxˆ V QN V QV
and V ꢊ E[vvT], W ꢊ E[wwT], where E is the expec-
tation operator.
˙
ꢉx
0 0
ꢊ 0 0 0
I
ꢉx
N ꢌ ␻
˙
0
˙
Figures 2 through 6 show the results of the Kalman
filter for a zero baseline experiment with the following
experimental conditions:
N
N
΄ ΅ ΄ ΅΄ ΅ ΄ ΅
(10)
ꢉx¨
0 0 0 ꢉx
␻
V
˙
X(t)
A(t) X(t)
w
● Place–rooftop of UCLA Engineering Building
● Receiver–Ashtech Z12
where the process noises ␻N and ␻V are used as filter-
● Sampling rate–2 Hz
tuning parameters; ␻ keeps the filter open during
N
Vol. 50, No. 4
Abdel-Hafez et al.: High-Integrity and Efficient GPS Integer Ambiguity Resolution
297

The baseline estimate is shown in Figure 2. The esti-
mate converges to a small error within a short time
span. This is a result of an accurate float integer ambi-
guity estimation as shown in Figure 3. An estimate of
the relative velocity between the base and slave
receivers is shown in Figure 4. Figures 5 and 6 show
the diagonal elements of the covariance matrices of
the baseline and integer ambiguity estimates, respec-
tively. We are interested in the integer ambiguity esti-
If the covariance matrix Q is very precise in rep-
ˆ
N
resenting the uncertainty in the float integer ambi-
guity, then the above minimization problem should
yield the true integer ambiguity. Because the float
Kalman filter relaxes the constraint relating to the
integer nature of the ambiguities, the float integer
ambiguity covariance matrix may not always be
accurate in representing the deviation of the float
integer ambiguity from the true integer ambiguity.
Hence, we instead use the minimization problem in
equation (16) to obtain the most likely hypotheses.
These hypotheses need to be tested through
a method that will assign probability to the various
hypotheses, and the hypothesis that is in fact the
true integer ambiguity should have an associated
probability that approaches 1. Only after this condi-
tion has been met is this hypothesis declared the
true integer ambiguity.
ˆ
mate Nand its corresponding covariance matrix, QNˆ,
which are used in the next section to determine the
integer ambiguity hypotheses. The covariance matrix
decorrelation algorithm of the LAMBDA method is
used to construct a transformation that will assist in
searching for integer ambiguity hypotheses in a cer-
tain hypothesis space defined by
T
ꢋ1
2
ˆ
ˆ
(N ꢋ N) QNˆ (N ꢋ N) ꢑ ꢇ
(15)
for a statistically selected ꢇ2 value.
To solve the minimization problem in equation (16),
we first need to decorrelate the ambiguity covari-
Q
ˆ
ance matrix N to try to eliminate the correlation
between the transformed ambiguities. This mini-
mization problem will be easier to solve in the new
transformed space.
LAMBDA METHOD FOR DECORRELATING THE
FLOAT INTEGER AMBIGUITY COVARIANCE
MATRIX
The decorrelation of the covariance matrix Q is
constructed to simplify the minimization of the
problem [6–8]
The decorrelation process transforms the
unknown integer ambiguity variables into unknown
innovation variables. Each innovation variable
brings new information that is independent from the
previous variables, thereby transforming the fully
populated integer ambiguity covariance into a diago-
nal matrix that corresponds to the covariance of the
ˆ
N
2
Q
ˆ
ꢋ1
minN
E
'
N ꢋ N
'
(16)
ˆ
N
n
ˆ
where N ʦ R is the set of float vectors of order n,
and N ʦ Zn is the set of integer vectors of order n.
Fig. 2–Zero Baseline Estimate from the Kalman Filter
298
Navigation
Winter 2003–2004

Fig. 3–Float Ambiguity Estimate from the Kalman Filter
Fig. 4–Relative Velocity Estimate from the Kalman Filter
Vol. 50, No. 4
Abdel-Hafez et al.: High-Integrity and Efficient GPS Integer Ambiguity Resolution
299

Fig. 5–Baseline Covariance from the Kalman Filter
Fig. 6–Float Ambiguity Covariance from the Kalman Filter
300
Navigation
Winter 2003–2004

innovation variables. This is done by introducing the
conditional integer ambiguity transformation.
We note that for any two, possibly vector, vari-
ables x and y, the conditional mean and covariance
are defined as [12]
1
ˆ
N1 ꢋ N1
ꢒNˆ ,Nˆ ꢒꢋNˆ 2
1
ˆ
2
1
1
N2 ꢋ N2
ꢒNˆ ,Nˆ ꢒNꢋˆ 2 ꢒNˆ ,N
ˆ
ꢒꢋNˆ 2
2/1
1
ꢊ
ˆ
3
1
1
3
2/1
N ꢋ N
΄ ΅ ΄
΅
3
3
ꢔ
ꢔ
ꢔ
M
ˆ
N–N
L
mx/y ꢊ mx ꢌ Pxy Pyꢋy1(y ꢋ my)
(17)
(18)
ˆ
N1 ꢋ N1
ꢋ1
Px/y ꢊ Pxx ꢋ Pxy Pyy
P
yx
ˆ
N
2/1 ꢋ N2
ꢐ
(26)
ˆ
N
3/2,1 ꢋ N3
΄ ΅
respectively, where mx ϵ E[x], mx/y ϵ E[x͉y],
Pxy ϵ E[(xꢋmx) (yꢋmy)T], and Px/y ϵ E[(xꢋmx)
(xꢋmx)T͉y]. Thus, the transformed innovation
variables are represented as follows:
M
ˆ
z –z
Therefore, the integer ambiguity covariance matrix
ˆ
ˆ
z1 ꢊ N1/0 ꢊ N1
(19)
may be decomposed in terms of L and D as
ˆ
ˆ
ˆ
ˆ
z2 ꢊ N2/1 ꢊ N2 ꢌ E (N2 ꢋ N2)(N1 ꢋ N1)
΄
΅
T
QNˆ ꢊ E (N ꢋ N) (N ꢋ N) ꢊ LDLT
(27)
ˆ
ˆ
ꢋ1
΅
΄
΅
2
ˆ
ˆ
E[N1 ꢋ N1]
(N1 ꢋ N1)
΄
ꢊ N2 ꢌ ꢒNˆ , ˆ ꢒꢋˆ 2 (N1 ꢋ N1)
(20)
ˆ
ˆ
2 N1
where D ꢊ diag (ꢒ2ˆ , ꢒ2ˆ , . . . , ꢒ2ˆ
)
Nn/N
N1
N1
N2/1
.
T
ˆ
ˆ
ˆ
where N ꢊ [N1, N2, . . . , Nn] and N ꢊ [N1, N2, . . . ,
Nn] . The covariance of the transformed innovation
variables is given by
Since the LDLT transformation—L lower triangu-
lar with 1’s on the diagonal—is unique, transform-
ing QNˆ in this form will directly give the L and D
matrices. This eliminates the need to hand-calculate
the variance and covariance terms in the L and D
matrices [7].
T
ˆ
2
N1
ꢒ2 ꢊ ꢒˆ
z1
(21)
(22)
ꢒ2z ꢊ ꢒ2Nˆ ꢋ ꢒNˆ ,Nˆ ꢒNꢋˆ 2ꢒNˆ ,Nˆ 1
2
2
2
1
1
2
This conditional least-squares principle can be
used to transform the integer ambiguity covariance
matrix into a diagonal matrix by selecting Z ꢊ L ;
ꢒz ,z ꢊ ꢒNˆ 2,Nˆ 1 ꢋ ꢒNˆ ,Nˆ 1 ꢊ 0
(23)
ꢋ1
2
1
2
thus
Note from equation (23) that there is no correla-
tion between the transformed integer ambiguity z1
and z2. In the same way,
ˆ
z ꢊ ZN
ˆ
T
ˆ
Qzˆ ꢊ ZQN Z ꢊ D
ˆ
ˆ
z3 ꢊ N3/2,1 ϵ N3/(2/1,1)
and the minimization problem of equation (16) can
be represented in the transformed space as
ˆ
ˆ
ˆ
ˆ
ꢊ N3 ꢌ E (N3 ꢋ N3) [(N2/1 ꢋ N2/1) (N1 ꢋ N1)]
΄
΅
2
ˆ
min E
'
z ꢋ z
'
Qzˆ
Z
ꢒ2ˆ
0
ꢒ ˆ
N1
N
2/1 ꢋ N2/1
ꢋ1
ˆ
ˆ
N2/1
ꢐ
While this transformation simplifies the search
for best integer ambiguity candidates while pre-
serving the volume of the search space, it does not
preserve the integer nature of the ambiguities
since the Lꢋ1 elements do not usually belong to the
integer space, [6–8]. Also, since the transforma-
tion is based on conditional least squares, we need
to ensure that the transformed integers are sorted
such that the smallest covariance integers are con-
ditioned first. For all these reasons, a special form
of the Gaussian transformation that preserves the
integer nature of the ambiguities is used for the
ambiguity transformation based on the LAMBDA
method [6–8].
2
΄0 ΅ ΄N ꢋ N ΅
1
1
ꢒ2ˆ
0
ꢋ1
ˆ
ˆ
N
2/1 ꢋ N2/1
N2/1
ꢊ N3 ꢌ ꢒꢓˆ ,ꢓˆ 2/1 ꢒꢓˆ ,ꢓ
ˆ
΄
΅
3
3
1
2
΄0 ΅ ΄N ꢋ N ΅
ꢒˆ
1
1
N1
ꢊ N3 ꢌ ꢒNˆ 3,Nˆ 2/1ꢒNꢋˆ 2 (N2/1 ꢋ N2/1)
ˆ
ˆ
2/1
ꢋ2
ˆ
ꢌ ꢒꢓˆ 3,Nˆ 1ꢒNˆ 1 (N1 ꢋ N1)
(24)
Again, z3 is uncorrelated with z1 and z2. In general,
iꢋ1
Ni/ I ꢊ Ni ꢌ
ˆ
ꢒꢋˆ 2 (Nj/J ꢋ Nj)
Ni,Nj /J Nj /J
(25)
ˆ
ˆ
ˆ
ꢒ ˆ
͚
jꢊ1
Thus, after decorrelating the covariance matrix, we
can easily and with small computational time deter-
mine the integer hypotheses that lie within a specified
ˆ
ˆ
where Ni/I ϵ Ni/(iꢋ1,iꢋ2, . . . ,1). Thus in matrix form, we
obtain
Vol. 50, No. 4
Abdel-Hafez et al.: High-Integrity and Efficient GPS Integer Ambiguity Resolution
301

volume. We need to use a method that assigns a prob-
abilistic measure for each of the hypotheses. There-
fore, the MHWSPT is used to recursively determine
the probability that each hypothesis is the correct
integer ambiguity given the measurement history, as
will be seen in the next section.
the measurement sequence up to the current time,
Fi(k), i ꢊ 1 . . . m. This is explicitly expressed as
Fi(k) ꢊ P(Ni͉r0, r1, . . . ,rk)
(33)
By Bayes’ rule, this can be expressed as
P(Ni,r&r0, r1,
P(r(k&) r0, r1,
,rkꢋ1)
k
ꢔ ꢔ ꢔ
,rkꢋ1
Fi(k) ꢊ
(34)
)
ꢔ ꢔ ꢔ
THE MULTIPLE HYPOTHESIS WALD SEQUENTIAL
PROBABILITY TEST
Applying Bayes’ rule to the numerator of equa-
tion (34), we obtain
This method was first introduced in [9]. Recently it
was used in [11] for the problem of integer ambiguity
resolution. The MHWSPT is a statistical method used
for the validation of integer ambiguity. It blends both
code and carrier-phase measurements to form a resid-
ual that is used to obtain the probability of a certain
integer hypothesis being the correct integer ambiguity.
While the carrier-phase measurements are sufficient
for this method to converge on the correct integer
ambiguity, combining them with the code measure-
ments speeds up the method’s convergence [11].
The residual is defined for the i-th integer hypoth-
esis, Ni, as follows:
P(Ni, rk͉r0, r1, . . . ,rkꢋ1) ꢊ P(rk͉Ni, r0, r1, . . . ,rkꢋ1
)
ꢐ P(Ni͉r0, r1, . . . ,rkꢋ1 (35)
)
Since we assume that the measurement sequence
is iid, we have
P(rk͉Ni, r0, r1, . . . ,rkꢋ1) ꢊ P(rk͉Ni)
ϵ fi(r(k))
(36)
(37)
Therefore, by noting that
P(Ni͉r0,r1, . . . ,rkꢋ1) ꢊ Fi(k ꢋ 1)
we have
P(Ni, rk͉r0, r1, . . . ,rkꢋ1) ꢊ fi(r(k)) ꢐ Fi(k ꢋ 1)
The numerator of equation (34) can be expressed as
r1 (k)
˜
ꢂꢈꢉ␾ (k)
˜
΄ ΅ ΄ ΅
r(k) ꢊ
ꢊ E (k)ꢔ
r2 (k)
ꢈꢉ␳ (k)
˜
P(r(k)|r0, r1,
,rkꢋ1) ꢊ P(r(k))
ꢔ ꢔ ꢔ
ꢈꢉ␤ ꢋ ꢂNi ꢌ ꢈH(k)ꢉꢏx(k)
ꢈH(k)ꢉꢏx(k) ꢌ ꢈꢉ␩
˜
m
ꢊ E (k)ꢔ
΄
΅
ꢊ
P(Nj,r&r0,r1,
,rkꢋ1)
ꢔ ꢔ ꢔ
͚
k
jꢊ1
ꢋꢂꢔE(k)
E(k)ꢔꢈꢉ␤
ꢊ
Ni ꢌ
(28)
m
΄ ꢋꢂꢔI ΅ ΄ꢈꢉ␤ ꢋ ꢈꢉ␩΅
ꢊ
fj(r(k)) ꢐ Fj(k ꢋ 1) (38)
͚
~
jꢊ1
where E, defined below for n double-differenced
measurements, is a projection that eliminates the
term associated with ꢉꢏx
Hence,
Fi(k ꢋ 1) ꢐ fi(r(k))
(39)
Fi(k) ꢊ
m
͚
(2nꢋ3)ꢐ2n
jꢊ1 Fj(k ꢋ 1) ꢐ fj(r(k))
E
0
˜
E ꢊ
(29)
΄I ΅
ꢋInꢐn
nꢐn
The probability density function of r(k) given any
integer hypothesis Ni, fi(r(k)) is calculated, assum-
ing a Gaussian residual r(k), as
and E is the left annihilator of the single-differenced
measurement matrix ꢈH. The remaining residual is
essentially an independent and identically distrib-
uted (iid) sequence for which the MHWSPT is theo-
retically suited. This iid measurement sequence has
mean and covariance given by
ꢋ1[ri(k)ꢋm(Ni,k)] V ꢋ1(k)[ri(k)ꢋm(Ni,k)]
T
˜
2
fi(r(k)) ꢊ Cꢔexp
The set of possible integer hypotheses is deter-
mined by first averaging the code position estimate
over some time period. This is called the float mode.
The corresponding integer number of widelane
wavelengths is then computed, denoted the base
hypothesis. The possible set per double-differenced
measurement is then computed by taking a number
of integers around that value. After the set of all
possible integer hypotheses has been determined,
we initialize Fi(0) (all integer hypotheses are usual-
ly set to be equally probable) and start sequentially
propagating Fi(k) at each GPS time epoch, k. This
process is essentially a nonlinear filter. After some
time, we note that all Fi(k) are almost identically
zero except for the correct integer hypothesis, which
ꢋꢂꢔE(k)ꢔNi
m(Ni, k) ꢊ
(30)
(31)
΄ ΅
T
ꢋꢂꢔNi
˜
˜
˜
V(k) ꢊ E(k)ꢔVꢔE(k)
respectively, where
Vcar. 0nꢐn
V ꢊ
(32)
΄0 ΅
Vcode
nꢐn
The MHWSPT [9, 11] recursively calculates the
probability that each of the integer hypotheses under
consideration is the correct integer ambiguity given
302
Navigation
Winter 2003–2004

approaches 1. At the instant when a certain correct
integer hypothesis threshold probability is met, we
declare the corresponding hypothesis to be the true
integer ambiguity.
EXPERIMENTAL RESULTS
The algorithm was tested under various condi-
tions and environments to verify its functionality.
We show here results of a zero baseline test, static
as well as dynamic car tests (2.31 m baseline), and a
highly dynamic two-aircraft real-time simulation
test (40 m baseline). While most results shown are
for widelane GPS effective signals, the ability of the
proposed algorithm to resolve L1 integer ambiguity
is also verified through experimental results. The
discussion that follows assumes use of widelane
GPS measurements unless stated otherwise.
Figure 7 presents real-time results for a zero-
baseline test. The figure shows the probability
associated with 10 integer hypotheses out of a total
of 100 hypotheses. The true hypothesis was hypothe-
sis 8, and the MHWSPT detected it correctly when
the corresponding probability exceeded the thresh-
old probability. One can see that the probability asso-
ciated with the correct hypothesis converged fairly
quickly to approach 1.
Figure 8 presents the baseline estimation error
after the integer ambiguity was fixed for the zero
baseline experiment. The figure shows the expected
high carrier-phase estimation accuracy due to the
low-magnitude measurement noise. This is also a
result of the elimination of the common-mode errors
and receiver clock biases in the double-differenced
carrier-phase measurement.
THE LAMBDA-ASSISTED WALD TEST
When the MHWSPT was introduced in the previ-
ous section, the methodology for selecting the inte-
ger ambiguity hypotheses was discussed. It was
noted that initially, the float integer estimator is
performed for a number of epochs assumed suffi-
cient for convergence. Then, the resulting float
ambiguity is rounded to the nearest integer, denoted
the base hypothesis. The integer hypotheses are
selected by taking ꢕ2, or possibly more, integers
around the base hypothesis for each satellite meas-
urement integer ambiguity. This scheme produces a
large number of integer hypotheses—for instance,
3,125 hypotheses when six satellites are in view.
It is here where the LAMBDA covariance matrix
decorrelation algorithm becomes very useful. The
LAMBDA decorrelation algorithm is used to decor-
relate the integer covariance matrix, thereby reduc-
ing the time needed to search for all possible
hypotheses in the covariance matrix ellipsoidal vol-
ume represented in equation (15). Thus, a quick
search for hypotheses with small ꢇ2i is performed
such that ꢇ2i ꢖ ꢇ2 for each hypothesis i.
ꢇ2 is fixed to some value that will guarantee to a
certain probability that the correct integer hypoth-
esis is among the candidates enclosed by the covari-
ance matrix ellipsoidal volume. This is equivalent
to fixing the volume of the ellipsoidal region to a
value that will guarantee the existence of a certain
number of candidates within that volume. Checking
the maximum ꢇ2i will indicate the probability of
having the correct hypothesis in that volume.
Therefore, to be more certain that the covariance
matrix ellipsoidal volume will enclose the true
integer ambiguity, enough time is allowed for the
Kalman filter to converge. At the same time, the
ellipsoidal volume is enlarged to cover more
hypotheses. Thus, the ꢇ2 value is fixed to obtain at
least 100 candidates; for the hardware-in-the-
loop simulation (HILSIM) experiment discussed
below, ꢇ2 ꢊ 197.0.
These hypotheses are then passed to the
MHWSPT. The MHWSPT will sequentially update
the probability that each integer hypothesis is
the correct integer ambiguity given the measurement
history up to the current time. Once a certain integer
hypothesis probability is very close to 1.0, usually
taken to be Fi(k) ꢗ 0.999, that integer hypothesis is
declared the correct integer ambiguity. In the next
section we present various real-time experimental
results for the proposed method.
The algorithm was tested in a real environment
by placing two receivers 2.31 m apart, fixed to the
rooftop of a car. The range between the two receivers
was estimated in real time when the car was static
and when it was moving at a speed of around
30 km/h. In the latter test, the carrier-phase integer
ambiguity resolution scheme was initiated after the
start of the motion.
Figure 9 shows the probability of the various
hypotheses being the correct integer ambiguity. As in
the above zero baseline experiment, as well as in the
experimental examples to follow, the probabilities
associated with 10 out of a total 100 hypotheses are
shown. It can be seen that the correct integer ambi-
guity was detected, but a longer convergence time
was required in comparison with the zero baseline
experiment. It can also be noted that the probability
associated with the correct hypothesis (hypothesis 8)
was not strictly increasing as a function of time. This
result is most likely due to environmental GPS signal
errors, such as small-magnitude multipath errors.
Figures 10 and 11, respectively, show the results
of the carrier-phase–based range estimation for the
static and dynamic car tests after the integer ambi-
guity had been resolved. It can be seen that the
range error is close to zero mean. The deviation of
the estimation error around the mean is within the
double-differenced carrier-phase noise level.
Vol. 50, No. 4
Abdel-Hafez et al.: High-Integrity and Efficient GPS Integer Ambiguity Resolution
303

Fig. 7–MHWSPT Hypothesis Probabilities, Zero Baseline Experiment
Fig. 8–Baseline Estimation Error after Fixing the Integers, Zero Baseline Experiment
304
Navigation
Winter 2003–2004

Fig. 9–MHWSPT Hypothesis Probabilities, Dynamic 2.31 m Baseline Car Test
Fig. 10–Baseline Estimation Error after Fixing the Integers, Static 2.31 m Baseline Car Test
Vol. 50, No. 4
Abdel-Hafez et al.: High-Integrity and Efficient GPS Integer Ambiguity Resolution
305

Fig. 11–Baseline Estimation Error after Fixing the Integers, Dynamic 2.31 m Baseline Car Test
The algorithm was also tested in a highly dynamic
(SCS) supplies the radio frequency (RF) GPS signals
to the two receivers simulating the base and slave
vehicles—FFIS 1 and FFIS 2—depending on their
true trajectories, which are received in real-time.
The two aircraft in the simulation are undergoing for-
mation flight while moving at a velocity of approxi-
mately 180 m/s.
environment using a UCLA-developed HILSIM facil-
ity (see Figure 12). This facility runs a two-aircraft
nonlinear model simulation and does not assume the
availability of a reference ground station. An
Interstate Electronics Corporation (IEC) two-
frequency GPS Satellite Constellation Simulator
Figure 13 presents real-time results for a dynamic
40 m baseline HILSIM experiment. The figure shows
the probability associated with 10 integer hypotheses
out of a total 100 hypotheses. The MHWSPT still con-
verged to the true integer, in this case hypothesis 3.
Because multipath GPS signal errors are not mod-
eled, it can be seen that the probability of the correct
hypothises continues to increase strictly as more GPS
measurements are processed.
The baseline estimation error for the dynamic 40 m
baseline HILSIM experiment is shown in Figure 14.
In this experiment, the base and slave vehicles are fly-
ing in formation such that they remain around 40 m
apart. Each aircraft is flying at about 180 m/s forward
velocity. This testing environment was of great value
in validating the performance of the algorithm
because of the prior knowledge of the true trajectories
of the base and slave vehicles. The figure indicates
successful resolution of the integer ambiguity even in
such a highly dynamic environment, as seen in the
Fig. 12–UCLA Hardware-in-the-Loop Simulation Facility
306
Navigation
Winter 2003–2004

Fig. 13–MHWSPT Hypothesis Probabilities, Dynamic 40 m Baseline
Fig. 14–Baseline Estimation Error after Fixing the Integers, 40 m Baseline Experiment
Vol. 50, No. 4
Abdel-Hafez et al.: High-Integrity and Efficient GPS Integer Ambiguity Resolution
307

accurate relative position estimate of small error
mean and standard deviation.
Finally, the first column of Table 1 shows the cen-
tral processing unit (CPU) computation time for the
original MHWSPT, which assigned the integer
hypotheses by offsetting ꢕ2 from each double-
differenced measurement base hypothesis. The sec-
ond column shows the CPU computation time used
by the Kalman filter for the float solution and the
LAMBDA decorrelation step. The third column
shows the CPU computation time for the LAMBDA-
assisted Wald test, which takes about 100 hypothe-
ses that are enclosed by the ellipsoidal volume space
of the covariance matrix. The algorithms were timed
using a Linux Pentium III machine. It can be seen
that the original MHWSPT takes considerably more
time than the LAMBDA-assisted Wald test. This is
because the number of hypotheses used by the origi-
nal MHWSPT is 3,125 for six satellites, while the
number for the LAMBDA-assisted Wald test is
around 100. It can be also seen that the CPU
computational time needed to run the LAMBDA
decorrelation algorithm is small. Nevertheless, once
the Kalman filter has converged, the LAMBDA
decorrelation algorithm need be performed only once
before the integer hypotheses in the ellipsoidal vol-
ume are efficiently determined. These hypotheses
are then tested by the MHWSPT as GPS measure-
ments are received until convergence on the correct
integer ambiguity is achieved. It must again be
emphasized that it is necessary to allocate enough
time for the float Kalman filter to converge such that
the resulting float estimate and its corresponding
The ability of the proposed LAMBDA-assisted
Wald test to resolve L1 integer ambiguity was also
verified for all previous examples. Figures 15 and 16
present the results for the 40 m dynamic HILSIM
experiment. Figure 15 shows the probability of the
integer hypotheses being the correct integer ambi-
guity. It can be seen that processing the L1 GPS sig-
nal results only in a slower probability convergence
speed. This result is expected since less information
is being processed. It is also a consequence of the
small L1 wavelength compared with the widelane
wavelength. Therefore, the effect of GPS measure-
ment noise on integer ambiguity resolution will be
greater when the L1 integer ambiguity is being
resolved than when the widelane integer ambiguity
is being resolved. Despite the slower integer ambi-
guity convergence speed, however, L1 integer ambi-
guity resolution remains of interest to many
researchers because of the low cost of L1 receivers
compared with their dual-frequency counterparts.
Figure 16 shows the resulting relative position
estimation accuracy after the L1 integer ambiguity
has been resolved. It can be seen that when L1 GPS
signals are used, the estimate deviation around the
mean is small compared with the case in which
widelane signals are used. This result is due to the
added measurement noise when one is constructing
the widelane measurement from the L1 and L2 GPS
measurements.
Fig. 15–MHWSPT Hypothesis Probabilities, Dynamic 40 m Baseline, L1 only
308
Navigation
Winter 2003–2004

Fig. 16–Baseline Estimation Error after Fixing the Integers, 40 m Baseline Experiment, L1 only
Table 1—Computation Time Statistics (milliseconds)
hypotheses within a highly elongated covariance
manifold. The hypotheses are then tested sequen-
tially, and the probability of each hypothesis being
the correct integer ambiguity is calculated recur-
sively as new GPS measurements are sampled. An
integer hypothesis is declared the correct hypoth-
esis when its probability approaches 1. On the
other hand, the probabilities of wrong hypotheses
will approach zero. This new method is named the
LAMBDA-assisted Wald test. Real-time results
illustrating the accuracy and low computational
time requirement of the method have been pre-
sented.
LAMBDA-
Original
Kalman Filter
and LAMBDA
Assisted
Trial
MHWSPT
MHWSPT
1
2
3
4
5
6
7
8
9
21.932
21.866
21.902
22.331
21.886
21.944
22.077
21.883
22.953
21.878
3.597
3.588
3.593
3.590
3.606
3.589
3.599
3.600
3.593
3.592
0.424
0.429
0.424
0.423
0.424
0.430
0.429
0.433
0.426
0.426
10
Mean
22.0652
3.595
0.427
ACKNOWLEDGMENTS
This research was supported by NASA Ames
under Grant No. NAG2-1484 and by NASA Goddard
under Grant No. NAG5-11384.
covariance matrix help define a compact hypothesis
volume space that encloses the correct integer ambi-
guity.
Based on a paper presented at The Institute of
Navigation’s ION GPS-2002, Portland, Oregon, September
2002.
CONCLUSIONS
A high-integrity and efficient method for GPS
carrier-phase integer ambiguity resolution has
been proposed. A Kalman filter that uses code,
carrier-phase, and Doppler GPS measurements is
first used to determine the float integer ambiguity
and its corresponding covariance matrix. The
method uses an efficient covariance matrix decor-
relation algorithm to determine the integer
REFERENCES
1. Hatch, R. R., Ambiguity Resolution in the Fast Lane,
Proceedings of The Institute of Navigation’s ION
GPS-89, 1989, pp. 45–50.
2. Hatch, R. R., Ambiguity Resolution While Moving:
Experimental Results, Proceedings of The Institute of
Navigation’s ION GPS-91, 1991, pp. 707–13.
Vol. 50, No. 4
Abdel-Hafez et al.: High-Integrity and Efficient GPS Integer Ambiguity Resolution
309

3. Min, J.,
A
Carrier Phase Differential Global
Fast GPS Ambiguity Resolution, NAVIGATION,
Journal of The Institute of Navigation, Vol. 4, No. 3,
1997, pp. 373–83.
Positioning System Algorithm for Relative State
Estimation, M.S. Thesis, UCLA, 1999, pp. 34–49.
4. Azimi-Sadjadi, B. and P. S. Krishnaprasad, Integer
Ambiguity Resolution in GPS Using Particle Filtering,
Proceedings of the American Control Conference,
June 2001, pp. 3761–66.
5. Hassibi, A. and S. Boyd, Integer Parameter Estimation
in Linear Models with Applications to GPS, IEEE
Transactions on Signal Processing, Vol. 46, No. 11,
1998, pp. 2938–52.
9. Malladi, D. P. and J. L. Speyer, A Generalized
Shiryayev Sequential Probability Ratio Test for
Change Detection and Isolation, IEEE Transactions
on Automatic Control, Vol. 44, August 1999,
pp. 1522–34.
10. Wald, A., Sequential Analysis, Wiley Mathematical
Statistics Series, New York, NY, John Wiley and Sons,
Inc., 1947.
6. Teunissen, P. J. G., The Least Squares Ambiguity
Decorrelation Adjustment: A Method for Fast GPS
Integer Ambiguity Estimation, Journal of Geodesy,
Vol. 70(1–2), November 1995, pp. 65–83.
7. De Jonge, P. J. and C. C. J. M. Tiberius, The LAMBDA
Method for Integer Ambiguity Estimation:
Implementation Aspects, Publication of the Delft
Geodetic Computing Center, Delft University of
Technology, 1996.
11. Wolfe, J. D., W. R. Williamson, and J. L. Speyer,
Hypothesis Testing for Resolving Integer Ambiguity in
GPS, Proceedings of The Institute of Navigation’s
ION GPS-2001, September 2001, pp. 1522–31.
12. Maybeck, P. S., Stochastic Models, Estimation and
Control, Vol. 1, Navtech Book and Software Store, 1994.
13. Park, C., I. Kim, J. G. Lee, and G. I. Lee, Efficient
Ambiguity Resolution Using Constraint Equations,
IEEE 1996 Position Location and Navigation
Symposium—Plans 1996, IEEE, April 1996, pp.
277–84.
8. Teunissen, P. J. G., P. J. De Jonge, and C. C. J. M.
Tiberius, Performance of the LAMBDA Method for
310
Navigation
Winter 2003–2004