A Novel Acquisition Scheme for a GPS Software Receiver Based on Two Stand-Alone One-Dimensional Search Processes

Abstract

To improve the capturing speed of a GPS software receiver, a novel acquisition scheme is presented. First, by compensating the frequency of the intermediate frequency signal to improve its cyclicity, the signal-to-noise ratio (SNR) of the intermediate frequency signal can be improved by using coherent average algorithm. Second, the C/A code start of every satellite is searched through the delay−multiply configuration, then the delay and accumulation unit is put forward to pretreat the multi-frequency signals. Lastly, the separation and estimation of Doppler-shift components are fulfilled by frequency domain analysis on post-treatment signals; therefore, the two-dimensional searching process in conventional acquisition scheme is transformed into two one-dimensional searching processes in the proposed acquisition scheme. In the proposed acquisition scheme, a shorted fast Fourier transform (FFT) version is adopted, which can greatly reduce the computation burden without degradation on performance. Sampled data from GPS receiver and simulated GPS signals are used for simulation experiments. Simulation results indicate that the proposed acquisition scheme is an effective one by much decreasing the acquisition time.

1 Introduction

The Global Positioning System (GPS) has been one of the most excellent navigation systems at present. It is widely used for its outstanding navigation performance in military and civil applications. Originally, GPS receivers consist of a Radio Frequency (RF) front-end, an Applications Specific Integrated Circuit (AISC) for signal processing, and a CPU core for higher level functions. However, design flexibility of the GPS receiver is constrained by an AISC that is hardwires with predefined acquisition and tracking channels, correlator, and control loop characteristics. So a software GPS receiver is the best solution for currently GPS receiver design.

In the design of a software GPS receiver, first operation is the signal acquisition that decides either the presence or the absence of the signal under test. Most acquisition schemes based on the principle that the local receiver replicates the GPS signal with different PRN codes and performs correlation with the incoming signal, then compares these correlation process yields various peaks with a detection threshold to test for acquisition success. These acquisition schemes also provide a rough estimation of the code delay and the Doppler frequency of the incoming signal. But the phase of the received signal relative to the available replica sequence, owing to additional modulation such as a Doppler effect and/or a receiver clock inaccuracy, can have any possible value due to uncertainties in time and position. It is also possible that the receiver may not know the exact apparent satellite frequencies or which of the possible satellites are visible in the sky.

The basic idea of signal acquisition is to search over a predicted time-frequency uncertainty zone [1]. The incoming signal and the local code are correlated for a predetermined time interval with a candidate code-phase and frequency assumptions. After the integration, a statistical test is applied to the correlation results to determine if a signal acquisition has been reached or not. If it has been, the acquisition is terminated and the receiver starts the tracking stage; if not, the search continues and moves to the next code-phase and frequency option. Therefore, those acquisition schemes are based on the two-dimensional searching process, which must do a search in several code-phase and frequency planes, one plane for each possible satellite.

In this paper, the two-dimensional searching process in conventional acquisition scheme is transformed into two one-dimensional searching processes, thus improves the capturing speed.

2 A Novel Fast Acquisition Scheme

2.1 Frequency Compensating and Coherent Average Filter

The acquisition process contains three steps: First, the improving of the signal-to-noise ratio (SNR) of the Intermediate Frequency (IF) samples by compensating its frequency. Second, the searching of the initial point of the C/A code through the utilization of delay and multiply method. Third, estimating the Doppler frequency components with the delay and accumulation unit after the removing of C/A code. Figure 1 shows the block diagram of this acquisition scheme.

Fig. 1

Architecture of GPS fast acquisition scheme

To a satellite signal, the signals of other satellites are noises. So the received IF signal can be expressed as:

$$ s_{\text{IF}} \left( t \right) = \sqrt {{P}} C_{i} \left( t \right)D_{i} \left( t \right)\cos \left[ {2\pi \left( {f_{\text{IF}} + f_{di} } \right)t + \theta_{i} } \right] + u_{i} \left( t \right) $$

(1)

where P is the total signal power, $C_{i} (t)$ is the normalized C/A code of satellite i, $C_{i} (t) \in \{ - 1,1\} ,\;f_{\text{IF}}$ is the intermediate frequency of carrier, $f_{di}$ is the carrier Doppler, and $\theta_{i}$ is the initial carrier phase, $u_{i} \left( t \right)$ represents the Gaussian white noise with the equalizing value of zero and the variance of $\sigma_{u}^{2}$. If the sampling frequency is $f_{s}$, the sample points per 1 ms signal is N, the total ms of the signal for acquisition is M, Eq. (1) can be expressed in complex representation as:

$$ s_{i} (n) = \sqrt {{P}} D_{i} (nt_{s} )C_{i} (nt_{s} ){\text{e}}^{{j2\pi \left( {f_{\text{IF}} + f_{di} } \right)nt_{s} }} + u_{i} (nt_{s} ) $$

(2)

where $t_{s} = 1/f_{s}$ is the periodic time, $Nt_{s} = 1\,{\text{ms}},\;n \in [0,MN - 1]$. The SNR of $s_{i} (n)$ can be expressed as:

$$ {\text{SNR}} = \frac{P}{{\sigma_{u}^{2} }} $$

(3)

Because of the navigation data bit period is 20 ms, the 180° phase changes potentially occur every 20 ms. But it occurs at most once between two continuous 10 ms signals. So the duration of coherent integration is typically limited in 10 ms signals, that is to say $M \le 10$.

To be simple, assuming $D_{i} (nt_{s} ) = 1$ in the M ms incoming signals for acquisition, multiply discrete signal $s_{k} (n)$ with $p_{k} (n)$ which is frequency compensated signal generated locally, the new signal $s_{i}^{'} (n)$ can be expressed as:

$$ \begin{aligned} s_{i}^{{\prime}} (n) &= \sqrt {P} p_{i} (n)s_{i} (n) \\ &= C_{i} (nt_{s} ){\text{e}}^{{j2\pi (f_{\text{IF}} + f_{di} + \Updelta f)nt_{s} }} + u_{i} (nt_{s} ){\text{e}}^{{j2\pi \Updelta f_{{}} nt_{s} }} \\ \end{aligned} $$

(4)

where $p_{i} (n) = e^{{j2\pi \Updelta f_{{}} nt_{s} }} ,\quad n = 0,1, \ldots ,N - 1$. The coherent average result in

$$ \begin{aligned} Y_{i} (n) &= \frac{1}{M}\sqrt {P} \sum\limits_{k = 0}^{M - 1} {s_{i}^{{\prime}} (n + kN)} \\ &= \frac{1}{M}\sqrt {P} s_{i}^{{\prime}} (n)\sum\limits_{k = 0}^{M - 1} {{\text{e}}^{{j2\pi (f_{\text{IF}} + f_{di} + \Updelta f)kNt_{s} }} } + \frac{1}{M}\sum\limits_{k = 0}^{M - 1} {u_{i} (nt_{s} )} {\text{e}}^{{j2\pi \Updelta f_{{}} (n + kN)t_{s} }} \\ \end{aligned} $$

(5)

Provided the delay time $\Updelta f$ is chosen appropriately, the following equation is guaranteed:

$$ {\text{e}}^{{j2\pi (f_{\text{IF}} + f_{di} + \Updelta f)Nt_{s} }} \approx 1 $$

(6)

Equation (4) can be written as follows:

$$ Y_{i} (n) = s_{i}^{{\prime}} (n) + u^{\prime} \left( n \right) $$

(7)

where $u^{\prime} \left( n \right) = \frac{1}{M}\sum\nolimits_{k = 0}^{M - 1} {u_{i} (nt_{s} )} {\text{e}}^{{j2\pi \Updelta f\;(n + kN)t_{s} }} ,u^{\prime} \left( n \right)$, is also the Gaussian white noise with the equalizing value of zero and the variance of ${\raise0.7ex\hbox{${\sigma_{u}^{2} }$} \!\mathord{\left/ {\vphantom {{\sigma_{u}^{2} } M}}\right.\kern-0pt} \!\lower0.7ex\hbox{$M$}}$. The SNR of $Y_{i} (n)$ can be expressed as:

$$ {\text{SNR}} = \frac{P}{{{\raise0.7ex\hbox{${\sigma_{u}^{2} }$} \!\mathord{\left/ {\vphantom {{\sigma_{u}^{2} } M}}\right.\kern-0pt} \!\lower0.7ex\hbox{$M$}}}} = M \cdot \frac{P}{{\sigma_{u}^{2} }} $$

(8)

Obviously, compared with $s_{i}^{{\prime}} (n),\;Y_{i} (n)$ has the same characteristics, but enlarges M times in SNR.

2.2 Estimation of the Code Delay

Ignoring the impact of noise and assuming $D_{i} (t) = 1$, the incoming signal contains two satellites here in [3]:

$$ s(t) = \sqrt 2 C_{1} (t)\cos \left( {2\pi f_{1} t} \right) + \sqrt 2 C_{2} (t)\cos \left( {2\pi f_{2} t} \right) $$

(9)

where $f_{di}\cdot i = 1,2$ is the Doppler shift of satellite i, $f_{i} = f_{\text{IF}} + f_{di} ,\,i = 1,2$ is the carrier frequency with Doppler shift. The code delay and carrier phase shift are ignored in Eq. (9), the slightly shifted version of the incoming IF signal is represented as:

$$ \begin{aligned} s\left( {t - \tau } \right) &= C_{1} \left( {t - \tau } \right)\cos \left( {2\pi f_{1} \left( {t - \tau } \right)} \right) \\ & \quad + C_{2} \left( {t - \tau } \right)\cos \left( {2\pi f_{2} \left( {t - \tau } \right)} \right) \\ \end{aligned} $$

(10)

where $\tau$ is the sample delay. The product of the incoming IF signal and its delayed version can be expressed in four parts:

$$ s(t)s(t - \tau ) = {\text{item}}1 + {\text{item}}2 + {\text{item}}3 + {\text{item}}4 $$

(11)

there into

$$ \begin{aligned} {\text{item}}1 &= C_{1} (t)C_{1} (t - \tau )\{ \cos (2\pi f_{1} \tau ) - \cos [2\pi f_{1} (2t - \tau )]\} \hfill \\ {\text{item}}2 &= C_{2} (t)C_{2} (t - \tau )\{ \cos (2\pi f_{2} \tau ) - \cos [2\pi f_{2} (2t - \tau )]\} \hfill \\ {\text{item}}3 &= C_{1} (t)C_{2} (t - \tau )\{ \cos (2\pi f_{2} \tau + 2\pi f_{1} t - 2\pi f_{2} t) - \cos [2\pi (f_{1} + f_{2} )t - \tau ]\} \hfill \\ {\text{item}}4 &= C_{2} (t)C_{1} (t - \tau )\{ \cos (2\pi f_{2} \tau + 2\pi f_{2} t - 2\pi f_{1} t) - \cos [2\pi (f_{1} + f_{2} )t - \tau ]\} \hfill \\ \end{aligned} $$

From the item1 to item4, the high-frequency terms, such as $\cos [2\pi f_{1} (2t - \tau )]$ in item1,$\cos [2\pi f_{2} (2t - \tau )]$ in item2, item3 and item4, can be easily filtered out by the pre-detection filter (accumulate and dump). So Eq. (11) can be expressed as:

$$ \begin{aligned} s(t)s(t - \tau ) &= C_{1} (t)C_{1} (t - \tau )\cos (2\pi f_{1} \tau ) \\ & \quad + C_{2} (t)C_{2} (t - \tau )\cos (2\pi f_{2} \tau ) \\ \end{aligned} $$

(12)

If the sample delay $\tau$ will be carefully chosen, $\left| {\cos (2\pi f_{i} \tau )} \right|\;(i = 0,1,2)$ is close to unity. Actually, $\cos (2\pi f_{i} \tau )$ can be considered to be as one part of the incoming signal amplitude which is expected to be as high as possible. Since the $f_{\text{IF}}$ is known according to the front-end frequency plan, a series of sample delay values can be found to meet this requirement. Then Eq. (12) can be rearranged as:

$$ s(t)s(t - \tau ) = C_{1} (t)C_{1} (t - \tau ) + C_{2} (t)C_{2} (t - \tau ) $$

(13)

where $C_{i} (t)C_{i} (t - \tau )$ $i = 1,2$ belongs to the same family as the Gold code, and the code delay is the same as that of $C_{i} (t)$. Then its autocorrelation and cross-correlation can be used to find the code delay.

If the incoming signal contains more than two satellites, it will come to a similar conclusion.

2.3 Estimation of the Doppler Frequency

Proverbially speaking, acquisition process for a certain satellite $i$, once the code delay of C/A code is found, the Influence of $C_{i} \left( t \right)$ can be removed by multiplied with the $C_{i}^{{\prime}} \left( t \right)$ duplicated locally which has the same stuct of $C_{i} \left( t \right)$, that is $C_{i}^{{\prime}} \left( t \right) = C_{i} \left( t \right)$.

Taken the acquisition process for satellite 1 for example, by multiplied with $C_{1}^{{}} (t)$, Eq. (9) can be expressed as:

$$ \begin{aligned} h(t) &= [C_{1} (t)\cos (2\pi f_{1} t) + C_{2} (t)\cos (2\pi f_{2} t) + u(t)] \times C_{1}^{{}} (t) \\ &= \cos (2\pi f_{1} t) + C_{1} (t)C_{2} (t)\cos (2\pi f_{2} t) + u(t)C_{1}^{{}} (t) \\ \end{aligned} $$

(14)

If the effect of noise is not too strong, the frequency component $f_{1}$ in Eq. (14) can be found from either FFT or DFT. This method appears excellent and attractive, but unfortunately the GPS signal consists of the superposition of all GPS signals in view of the antenna, and is processed by parallel channels in the receiver, then the real RF signal of GPS is mixed-frequency signal which contains several satellites’ frequency components with almost the same power. So the effect of frequency component $f_{2}$ cannot be ignored. So frequency domain analysis cannot distinguish $f_{1}$ from $h(t)$ in Eq. (14). Therefore, delay and accumulation unit is put forward to accomplish the frequency components separation and selectable estimation.

The output signal after pretreatment of delay and accumulation unit can be written as follows:

$$ \begin{aligned} h^{{\prime}}(t) &= h(t) + h(t - \tau ) \\ &= \cos (2\pi f_{1} t) + C_{1} (t)C_{2} (t)\cos (2\pi f_{2} t) + \cos (2\pi f_{1} t)\cos (2\pi f_{1} t) \\ &\quad + \sin (2\pi f_{1} t)\sin (2\pi f_{1} t) + C_{1} (t - \tau )C_{2} (t - \tau )\cos (2\pi f_{2} t)\cos (2\pi f_{2} \tau ) \\ &\quad + C_{1} (t - \tau )C_{2} (t - \tau )\sin (2\pi f_{2} t)\sin (2\pi f_{2} \tau ) + \xi (t) \\ \end{aligned} $$

(15)

In the above equation, the noise signals in $h'(t)$ is $\xi (t)$, and $\xi (t) = C_{1} (t)n(t) + C_{1} (t - \tau )n(t - \tau )$. Similar to Eq. (12), if the sample delay $\tau$ will be carefully chosen, $\left| {\cos (2\pi f_{i} \tau )} \right|\;(i = 0,1,2)$ is close to unity, that is

$$ \left| {\cos (2\pi f_{i} \tau )} \right| \approx 1,\left| {\sin (2\pi f_{i} \tau )} \right| \approx 0,i = 1,2 $$

(16)

Inserting Eq. (16) into Eq. (15) yields

$$ h(t)' = 2\cos (2\pi f_{1} t) + c_{1} (t)c_{2} (t)\cos (2\pi f_{2} t) + c_{1} (t - \tau )c_{2} (t - \tau )\cos (2\pi f_{2} t) + \xi (t) $$

(17)

As dissertated before, $C_{1} (t)C_{2} (t)$ is belongs to the same family as the Gold code which is also evaluated by ±1 compared Eq. (17) with Eq. (14), it is apparently that the frequency component $f_{1}$ is selectable enhanced and $f_{2}$ is weakened. Now the frequency component $f_{1}$can be easily identified through FFT analysis.

Thus, the whole fast acquisition process of mixed-frequency GPS signals is completed.

2.4 Performance Analysis

Commonly speaking, we consider calculation burden is depend on the times of FFT and IFFT. So the performance comparison of common FFT fast acquisition based on two-dimensional searching process and the presented acquisition one-dimensional searching process is mentioned in theory.

Approximately, assuming the maximum Doppler velocity result from the movement of orbit is 0.9 km/s, and the vehicle move toward the earth is about 1 km/s. Thus the maximum Doppler shift is [4].

$$ f_{d\hbox{max} } = \frac{{f_{l} \upsilon_{r\hbox{max} } }}{c} = \frac{1575.42\,{\text{MHz}} \times (1000 + 900)\,{\text{m/s}}}{{3 \times 10^{8}\,m/s}} \approx 10\,{\text{kHz}} $$

(18)

The Doppler frequency searching range is $f_{0} \pm 10\,{\text{KHz}}$, the step length of searching process is selected as 500 Hz and C/A code frequency is 1.023 MHz. Taken the real GPS signal supplied by [6] which contains five satellites as acquisition source and based on these hypotheses, the calculation times when utilizing those three acquisition methods are contrastively noted in Table 1 [5].

Table 1 Contrast of two acquisition schemes

3 Simulation and Result

Using the real Intermediate Frequency GPS signal as acquisition source, which is collected using Zarlink GP2015 RF IC and Cypress FX2 USB interface board, with the intermediate frequency of 1.405 MHz and the sampling frequency of 5.7142 MHz, the acquisition time of common FFT fast acquisition is 143.6 s and the acquisition result is suggested in Table 2, meanwhile the acquisition time of proposed acquisition scheme is 6.4 s and the acquisition result is suggested in Fig. 2.

Fig. 2

Acquisition result of proposed acquisition scheme

Fig. 3

Acquisition result of satellite 7, step size = 500 Hz

The acquisition result of proposed acquisition scheme is suggested in Figs. 4 and  5.

Fig. 4

Estimation the code delay of satellite 7

Fig. 5

Estimation the frequency of satellite 7

Table 2 and Figs. 2, 3, 4, 5 show the similar acquisition results of common FFT fast acqusition and the proposed acquisition scheme, and indicate the validity of proposed acquisition scheme in code delay estimating process.

Table 2 Acquisition result of common FFT fast acquisition

4 Conclusions

A novel acquisition scheme based on two stand-alone one-dimensional search processes for a GPS software receiver has been described. Simulation results show that the performance of proposed acquisition scheme is similar with the common FFT fast acqusition, but the acquisition speed is much faster than that of the common FFT fast acqusition.