Research of Weak GPS Signal Acquisition Algorithm

Shijun Tian Yiming Pi

Dept of Electronic Engineering Dept of Electronic Engineering
University of Electronic Science and Technology of China University of Electronic Science and Technology of China
Chengdu, Sichuan Province, China Chengdu, Sichuan Province, China
tianshij@uestc.edu.cn ympi@uestc.edu.cn

Abstract-GPS has been broadly applied in every fields of our progresses until a decision variable in one code/frequency
social life, since the environment around us has been becoming bin is greater than a predefined threshold. This predefined
more and more complicated, satellite navigation positioning detection threshold, which is a function of the noise floor and
technology with low SNR gains more and more attention. required detection statistics, in part determines the receiver's
However, the current GPS signal structure and signal power acquisition performance. Most commercial receivers can use
levels are barely sufficient for indoor applications. Errors due a signal only if its SNR is greater than about 35- 37 dB-Hz
to multi-path and noise associated with weak indoor signals [1,2]. The signal sensitivity for an indoor signal is normally
limit the accuracy and availability of GPS in difficult indoor 10 - 30 dB lower than that of line of sight signal. So most
environments. This paper present an overview of GPS
GPS signal acquisition techniques, which are considered to
positioning technologies based on indoor environments. An
adapted acquisition algorithm based on differential correlation be adequate on positioning capability in outdoor
is introduced. Analyzes two common methods for improving environment are not satisfactory for application with weak
the SNR of the test statistic: coherent integration (COH) and signals.
non-coherent integration (NCR), then points out their There is a great amount of attention on exploring the
disadvantage when used in low-SNR circumstance. By means techniques for location estimation in weak signal
of math model, the adapted acquisition algorithm based on environment. It has been investigated in [3] that the
differential correlation (DF) is introduced in detail. With the
attenuation and interference to the received GPS signal are
help of simulation, the simulation results indicate that this
severe in stringent circumstance. Different types of technique
algorithm can acquire GPS signal with low SNR using the
shorter time. have been proposed to overcome the problem, which can be
categorized into the Assisted-GPS methods, COH and NCH.
The A-GPS methods primarily utilize the messages coming
I. INTRODUCTION from the cell-based systems to assist the acquisition of the
Global Positioning System (GPS) receivers must acquire received GPS signal. In order to improve signal sensitivity,
the COH acquisition technique maximize the COH period.
and track the pseudorandom codes and carrier signals from
several GPS satellites. In order to track and decode the However, for too weak signal, processing gain obtained
through COH may not be sufficient for detection. In addition,
information in GPS signal, an acquisition method must first
the existence of navigation bit transition limits the COH
be used to detect the presence of the signal. Once the signal
period to 20 ms, normally 10 ms without the external aiding,
is detected, the necessary parameters must be obtained and
using the current L1 signal, although the block acquisition
passed to a tracking program. Information such as the
navigation data can be obtained from the tracking program. scheme proposed in alleviates the navigation bit-transition
The acquisition mode estimates the PRN code phase and the problem using the COH method. However, the long COH
carrier Doppler shift via a search process. These quantities time increases the number of frequency search cells, which
are then used to initiate tracking, which continuously updates in tum increases the time to first fix. Meanwhile, the COH
them. time is also limited by the user dynamics and the quality of
the front-end oscillator. Using NCH technique, integration
GPS signal acquisition and tracking are notoriously can be extended for much longer periods but the processing
difficult when signals are weak. The general architecture of gain suffers severely because of the squaring loss is incurred.
acquisition units for weak GPS signals can be categorized as Squaring loss increases as pre-squaring SNR decreases,
either software-based, where the time domain code phase leading to a fundamental limit to the sensitivity of this
ambiguity is tested in parallel on a DSP via a single Fast technique [4].
Fourier Transform(FFT), or hardware-based, where multiple
In this paper, an adapted acquisition algorithm based on
correlators are simultaneously dedicated to the hypothesis
test in several dwells. For both types, an acquisition search DF is proposed for GPS acquisition under weak signal

978-1-4244-2064-3/08/$25.00 ©2008 IEEE 793

environment. The main concept of the DF scheme is to use SeQ: Quadrature-phase integration value
differentially-coherent combining instead of non-coherent
combining of the COH results for the acquisition of GPS S nc : NCH value
signals. Although this method becomes particularly useful
within this context, as we will explain, it has not been I k : 1ms in-phase accumulator output
considered for this purpose so far. Q k : 1ms Quadrature-phase accumulator output
There are two reasons why differentially-coherent
combining becomes particularly attractive within the context TCOH : Number of coherent summations
of GPS signal acquisition. First, differentially-coherent
M: Number of non-coherent summations
combing can only work if the signals to be combined are of
the same polarity. With BPSK data modulation this is From equation (2), it can be seen that NCH requires
normally not the case. However, the data rate of the GPS squaring of the accumulator outputs. As a result, the noise is
navigation message is only 50Hz while the C/A code period squared and can not be cancelled by summation. This non-
is 1msec. That means that at the output of the C/A code linear process induces the so-called squaring loss. The
correlator a sign reversal may occur once every 20 squaring loss depends on the SNR after COR and before
correlation results at most. Thus data modulation will, in the NCH. The higher the SNR before NCR, the lower the
worst case, only lead to a very small loss of about 1 dB, squaring loss.
which means that assistance information may not be required
at all. III. AN ADAPTED ACQUISITION ALGORITHM BASED ON DF
Secondly, the frequency offset of the input signal due to The following is a model of GPS signal that has been
the Doppler effect translates into a constant phase rotation of used in this study
the differentially combined correlation results. Thus, the
Doppler offset, which also has to be determined by the ret) = AD(t)c(t) cos(m!) + net) (3)
acquisition unit, can easily be estimated from the phase of
the differentially combined correlation results. In this model, the constant A is the signal amplitude. The
function D(t) is the GPS data stream. The function c(t) is
This paper first analyzes two common methods for
the C/A PRN code of the received signal. The frequency OJ c
improving the SNR of the test statistic: COH and NCH, then
points out their disadvantage when used in low-SNR is the intermediate frequency carrier to which the L 1 carrier
circumstance. The second section mainly introduced an signal gets mixed in the RF front end. The term n(t) is the
adapted acquisition algorithm based on DF. noise, its power is a 2 .Normally it can be modeled as
Gaussian, band-limited white noise. A 2/2a 2 = SNR ( where
II. COH AND NCH SNR is signal to noise rate).
In general, in order to enhance the signal sensitivity, the
The signals of from both channel I and channel Q are
COH is preferred where the correlation values are
respectively correlated with the local C/A code, and then
algebraically added over a certain period. For a stand-alone
GPS receiver, during acquisition, navigation data bit multiplied by 2COS«(OLt) and 2sin(OJLt) .The correlation
transitions are not known. The COH may actually cancel the duration is equal to the cycle of a C/A code. As a result,
correlation value. Therefore, the integration period is limited channel I gets
to 10 ms. If data aiding is available, the integration time may
be extended to 20 ms or beyond. However, the long COH Ik=Sk+noiselk (4)
time increases the number of frequency search cells, which j=kN+N-l
in tum, increases the time to first fix. Meanwhile, the COH Sk= I AIXj%DClocaJUD cos(mjT)2cos(mJT) (5)
j=kN
time is also limited by the user dynamics and the quality of
the front-end oscillator. Normally, the NCH is implemented Suppose D(t) =1 when these codes are aligned and
after a short period of the COH, which is not influenced by
data bit transitions and the quality of the oscillator. Equation correlated. And then gets
(1) and equation (2) below show the integration schemes of
the COR and NCR, respectively: . (~(uNTJ
TCOH TCOH
Sk = A
SIn -2-
( Jcos
(~o}T(N-l) J'
+ ~OJTkN + nOlselK (6)
ScI = Ilk ScQ=IQ k (1) . ~OJT 2
k=l k=l SIn - -
2
Snc=
k=l
f~Ii+Q~ (2)
Where N is the sampling number in a C/A cycle, T is the
Where, sampling interval.

ScI: In-phase integration value Similarly, the summed result of channel Q is:

794
 NT Where erjinv(x) is the anti-function of
· (I1OJ
SIn - -)
2 . (117(N -1) ).
S k = A-.-(~~)-SIn 2 + I10JTkN + nOlseQk (7) erf(x) = J; }; exp(-t )dt . 2

SIn I1r;r
2
Equation (10) shows the relation among p ,M and
Where noiselk'" noiseQk follow a Gaussian distribution p E ,here p ,N and C is constant. When the wrong
N(0, 2N 0- 2 ) • acquisition probability is determined, P E is also a constant,

Y is used for the test statistic and made equal to so P is only related to N. When the accumulation value
M M exceed the threshold, the code phase and carrier frequency
I/;/;-I+Q;Q;-I' say Y = I/;/;-I+Q;Q;-I' where M is the related to this accumulation value is the result we wanted.
;=1 ;=1
summed times. The use ofDF statistics is to avoid the square
loss that caused by NCR. Compared with COR, the IV. SIMULATION EXPERIMENT
"differential" in acquisition algorithm based on DF makes it Figure 1 validates the previous theoretical analysis, and
not sensitive to navigation data bit transitions. The demonstrates that DF suffers from approximately 3dB less
"accumulation" after differenced makes the requirement of processing loss as compared with NCR in the case of low-
the accumulation algorithm time shorter, and makes the SNR.
frequency difference intolerance higher, the acquisition time
is not long. So, the acquisition algorithm based on DF has an
advantage over COR and NCR on the improvement of SNR.
When codes are aligned, the test statistic Y is also
simplified
I .,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,., , .
-10 l----'--_-'---------'---_---'-------------'--_----:"-::-------,'-,-----~------::-L.------,J
-20 0 5 10
Pre-processing SNR(dB)

Figure 1. Processing loss of DF and NCH

To get the probability density function of Y, the
probability density of the random variable z; should be got The detection probability with data modulation is
firstly. To do easily the analysis, suppose that Z i is a depicted in Figure 2 for M=60, M=SO and TCOH =1 ms.
2M
Again the performance of differentially coherent combining
Gaussian distribution N(0,4N 20- 4 ) • Rence, I Zi is a
;=1 of COR results is about 2dB better than with non-coherent
Gaussian distribution N(O,SM N 20- 4 ) .To compensate the combining of COR results. Under the same processing
2M
segment, the number of DF is inherently one less than the
errors caused by approximation, the used variance of I Zi , number of NCR.
;=1

in fact, is equal to be SpM N 20- 4 •

According to the above analysis, we can determine the

~ 0.7
acquisition threshold establishing a hypothesis testing. ~ 0.6

'tl 0.5

(9)
f 0.4

0.3

sin 2(l1OJTN / 2)
Where C = 2 COS(l1OJTN) .Under the threshold
sin (l1OJT /2)
32
CINO (dB)
p, we can get wrong acquisition probability P E • Substituting
2 Figure 2. Probability of detection (TCOH =1 IDS)

~ = snr into Equation (9), we get

20- Figure 3 and Figure 4 show the effect of increasing the
TCOH (COR time) on two algorithms (DF and NCR). It can
be seen that the use of differentially coherent combining of
COR results, for each scenario (defined by a specific pair of
COR duration and number of DF/NCR accumulations),

795
unanimously improves the detection probability about 3-4 illustrates that DF suffers from approximately 3 dB less
times around the threshold C / No region. processing loss as compared with NCR in the case of low
post-COR SNR, resulting in the detection sensitivity
improvement. The use of DF decision variable can avoid the
square loss caused by NCR. The "accumulation" after
difference shortens the correlation accumulation time length,
and this makes the wrong acquisition rate lower without
increasing the data length. In short, the adapted acquisition
- - - DF,M=80
_._. DF,M=60
- DF,M=40
based on DF has an advantage compared to COR and NCR
-+ NCH,M=80
regarding the improvement of SNR.
-&- DF,M=20
+- NCH,M=60
...... NCH,M=40
..... NCH,M=20

25
ACKNOWLEDGMENT
C/NO (dB)
The author wish to thank colleague of GPS laboratory of
Figure 3. Probability of detection (TCOH =5 ms) university of electronic science and technology of china.
Thanks are due to them for their comments

REFERENCES
j
i 0.5 [1] Surendran, K.Shanmugam, Robert Watson, and John Nielsen,
~ 0.4 --- DF,M=80 "Differential signal processing schemes for enhanced GPS
--_. DF,M=60
O.
-
.....
DF,M=40
NCH,M=80
acquisition", in Proc. GNSS05, Institute of Navigation, Long Beach,
-&-
+-
DF,M=20
NCH,M=60
CA, pp..213-214, Sept. 13-16,2005
..... NCH,M=40
-+- NCH,M=20 [2] Dafesh, T.Fan, "A novel approach to enhancing the sensitivity of CIA
23
C/NO (dB) code GPS receivers", in Proc. Proceeding of ION 57th annual
meeting, Albuquerque, NM, pp.482-485, June. 21-24, 2001
Figure 4. Probability of detection (TCOH =10 ms) [3] Choi.H, DJ.Cho, and SJ.Yun, "A novel weak signal acquisition
scheme for assisted GPS", in Proc. Proceeding of ION GPS 2002,
v. CONCLUSION Portland, OR, pp.l77-179, Sept. 7-11,2002
[4] Bo Zheng, Gerard Lachapelle, "GPS software receiver enhancements
We have examined DF processing and evaluated the for indoor use", in Proc. Proceedings of ION GNSS 2005, Long
performance of DF-based detectors. The theoretical analysis Beach, CA, pp.1139-1140, Sept. 13-16,2005

796