1. INTRODUCTION
The first stage in the operation of a Global Navigation Satellite System (GNSS) receiver is the acquisition of the satellites in view, which provides rough estimates of the signal parameters, such as code delay τ and Doppler shift f d of the Signal-In-Space (SIS) transmitted by the satellites. This activity is performed by the so-called ‘acquisition block’ for initial synchronization. These rough estimates will have to be refined later by subsequent signal tracking modules.
With the advent of the new GNSS, such as Galileo (European Union, 2010) and the modernized Global Positioning System (GPS) (Kaplan, Reference Kaplan2006), new signals and new modulations have been introduced in order to meet the growing demand of location, navigation and positioning services. Among the several modulation novelties, the introduction of a higher bit rate of data and the adoption of tiered codes obtained by cascading secondary and primary codes are examples of these innovations. The bit sign transition could possibly occur in any primary code period within the received GNSS signals processed in the acquisition stage. If Fast Fourier Transform (FFT) is used to perform the circular correlation, a bit sign transition occurring within the integration period may cause a splitting of the main peak of the Cross Ambiguity Function (CAF) into two smaller side lobes along the Doppler shift axis (Sun et al., Reference Sun, Lo Presti and Fantino2009). This is usually a critical aspect in all the acquisition methods where the data is processed in blocks.
In general, the detection ability is often enhanced by post correlation integration techniques, such as coherent integration and non-coherent integration. It is well known that increasing the coherent integration time will bring improved acquisition sensitivity but the presence of bit sign transitions limits the achievable maximum performance. Similarly, the acquisition sensitivity could also be improved by increasing the non-coherent integration numbers but the non-coherent integration approach is based on the sum of squared envelopes of correlator outputs, which presents the so-called side effect of a relevant squaring loss (Borio et al., Reference Borio, Fantino and Lo Presti2006). In order to mitigate the CAF peak impairments and also enhance the acquisition sensitivity, in this paper a novel two steps based bit sign transition cancellation method is proposed to overcome the CAF peak splitting impairments.
The main effect of the CAF peak splitting along the Doppler shift axis in the search space is an erroneous frequency estimation, while as far as the code delay is concerned, the CAF peak splitting effect produces a correlation amplitude reduction, without changing the peak position (Sun et al., Reference Sun, Lo Presti and Fantino2009). The main idea of the proposed two steps based bit sign transition cancellation method is to take advantage of these two disjointed effects on the CAF peak along the code delay and the Doppler shift axes, respectively. This method recovers the code delay in the first acquisition step so as to roughly remove the bit sign transition in the received signal segment for the recovery of the correct estimate of the Doppler shift in the second acquisition step. In order to speed up both acquisition steps, the fast acquisition approach based on FFTs is usually adopted.
In order to validate the proposed method, Monte Carlo simulations have been used. The signal selected for conducting the testing activity is the Galileo E1 Open Service (OS) Binary Offset Carrier (BOC) (1,1) signal, where the spreading code is modulated by fake data with the correct rate. A preliminary performance analysis of the proposed method has been carried out by means of histogram plots of the estimated Doppler frequency shift as well as histogram plots of the estimated code delay. The results show that the proposed technique could provide better detection rates of Doppler frequency shift and code delay estimates than the conventional fast acquisition approach.
A more detailed performance analysis has been performed by evaluating Receiver Operating Characteristic (ROC) curves by means of Monte Carlo simulations for various Carrier-to-Noise power density ratio (C/N0) values (Marcum, Reference Marcum1960). The presence of data sign transitions in the received GNSS signals makes the coherent evaluation of the CAF quite difficult, therefore a combination methodology between coherent integration and non-coherent integration over multiple code periods is usually adopted to provide reliable code delay estimate for the initialization of the signal alignment in the second acquisition step, especially dealing with weak GNSS signals. Finally the acquisition performance is also evaluated in terms of a Signal-to-Noise-Ratio (SNR) curve. The analysis results reveal that the proposed technique provides superior acquisition performance over the conventional fast acquisition approach.
In summary the objective of this paper is two-fold:
• First, to describe and analyze the bit sign transition problem present in the received GNSS signals and then to propose an innovative two steps based bit sign transition cancellation method to overcome the CAF main peak splitting impairments in order to fit the new generation GNSS signal modulations.
• Secondly, to compare the acquisition performances between the proposed technique and the conventional fast acquisition approach.
The analytical results show that the proposed acquisition technique could overcome the bit sign transition problem present in the received GNSS signals, and it is able to provide much improved performance and enhanced acquisition sensitivity in comparison with the state-of-the-art fast acquisition schemes.
2. SIGNAL AND SYSTEM MODEL
The signal at the input of a GNSS receiver, in a one-path additive Gaussian noise environment, can be written as follows:
that is the sum of N s useful signals emitted by N s different satellites, and of a noise term η RF(t). η RF(t) is a stationary Additive White Gaussian Noise (AWGN) with power spectral density (PSD) N 0/2. The expression of the SIS transmitted by the i th satellite and received at the antenna usually assumes the following structure:
![$$r_{RF,i} (t) = A_i d_i (t - \tau _i )c_i (t - \tau _i ){\rm cos}[2\pi (\,f_{RF} + f_{d,i} )t + \varphi _{RF,i} ]$$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn2.gif?pub-status=live){kind=small}
where:
A i is the received signal amplitude of the i th useful signal at the output of the receiver antenna, and the signal power is given by P i=A i2/2.
d i(t) is the navigation data message, Binary Phase Shifting Key (BPSK) modulated.
c i(t) is the spreading sequence which is given by the product of several terms and it is assumed to take value in the set {−1, 1}.
τ i, f d,i and φ RF,i are the code delay, the Doppler shift and the initial carrier phase offset introduced by the transmission channel on the i th signal, respectively.
f RF is the carrier frequency which depends on the GNSS signal band under analysis. For the Galileo E1 OS signal case, f RF=1575·42 MHz.
In general, the spreading sequence c i(t) can be expressed by the product of several terms:
where:
c 1,i(t) is the periodic repetition of the primary spreading code.
c 2,i(t) is the secondary code.
s b,i(t) is the sub-carrier.
The sub-carrier s b,i(t) is the periodic repetition of a basic wave that determines the spectral characteristics of r RF,i(t). Two examples of the sub-carrier signals are BPSK and BOC. The BPSK is adopted by the GPS Coarse Acquisition (C/A) signal; with the advent of new GNSSs (e.g. Galileo), BOC(1,1) modulation has been adopted in the Galileo E1 OS signal. The primary spreading code c 1,i(t) consists of a unique sequence of chips which exhibits the orthogonal property necessary to avoid interference among different signals. Denoting with T c the chip interval, 
, where c 1,i,k is the k th chip of the Pseudo Random Noise (PRN) sequence for the i th satellite with a chip rate R c=1/T c, and 
is a unitary rectangular window with the duration T c. d(t) is a sequence of data bits, whose duration is T b. Tb is much greater than T c, with T b=4 ms in the Galileo E1 OS signal case and T b=20 ms in the GPS C/A case. In the case of the Galileo E1 OS signal the primary spreading code c 1,i(t) is a PRN with the chip rate R c of 1·032 MHz and the repetition period T p=T b=4 ms, which means that there is a potential bit sign transition in each primary code period; while there is always a sequence of at least 10 primary code periods free of bit sign transitions in the case of the GPS C/A signal. It is also known that the Galileo E1 OS pilot channel (E1-C) signal is based on primary and secondary codes, by using the so called tiered codes construction (European Union, 2010). Tiered codes are generated modulating a short duration primary code by a long duration secondary code sequence. The secondary code has a code length of 100 ms including 25 chips. The secondary code acts exactly as the navigation message for the Galileo E1 OS data channel (E1-B) signal and it can be the cause of a sign reversal in the correlation operation over the integration time interval. From this point of view the impact of bit sign transitions on the primary spreading code has no difference between the data channel and the pilot channel signal components.
The noise term η RF(t) is assumed to be a zero-mean stationary AWGN process. In reality the noise will be neither Gaussian nor white, however the Gaussian approximation is justified by the Central Limit Theorem (CLT), which is found to be accurate in practice. In addition, the sampled noise process is not white, as successive noise samples are correlated and the white noise assumption is only an approximation.
The input signal y RF(t) defined in Equation (1) is received by the receiver antenna, down-converted, and filtered by the receiver front-end. In this way, the received signal before the Analog-to-Digital (A/D) conversion is provided as follows:
![$${y(t) = & \sum\limits_{i = 1}^{N_s} {\tilde r_i + \eta (t)} = \sum\limits_{i = 1}^{N_s} {A_i d_i (t - \tau _i )\tilde c_i (t - \tau _i )} {\rm cos}[2\pi (\,f_{IF} + f_{d,i} )t + \varphi _i ] + \eta (t)} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn4.gif?pub-status=live){kind=small}
where:
f IF is the receiver Intermediate Frequency (IF).
represents the spreading sequence after filtering of the receiver front-end.
represents the spreading sequence after filtering of the receiver front-end.Here the simplifying condition (Equation 5) is assumed and the impact of the front-end filter is neglected. η(t) is the down-converted and filtered noise component.
In a digital receiver, the IF signal y(t) in Equation (4) is sampled through an Analog-to-Digital Converter (ADC). The ADC generates a sampled sequence y(nT s), obtained by sampling y(t) at the sampling frequency f s=1/T s. From now on the notation x[n]=x[nT s] will be adopted to indicate a generic sequence x[n] to be processed in any digital platform. After the IF signal is sampled and digitized, neglecting the quantization impact, the following signal model is obtained:
![$$y[n] = \sum\limits_{i = 1}^{N_s} {A_i d_i [n - \tau _i /T_s ]\tilde c_i [n - \tau _i /T_s ]{\rm cos}(2\pi F_{D,i} n + \varphi _i ) + \eta [n]} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn6.gif?pub-status=live){kind=small}
where, F D,i=(f IF+f d,i)/f s=(f IF+f d,i)T s.
The spectral characteristics of the discrete-time random process η[n] depend on the type of filtering, the sampling and decimation strategies adopted in the front-end. If the choice on the sampling frequency f s=2B IF=4f IF is adopted, the IF signal and noise are sampled at Nyquist rate, where B IF is the bandwidth of the front-end. In this case, it is easy to know that the noise variance becomes:
![$$\sigma _{IF}^2 = E[\eta ^2 (t)] = E[\eta ^2 (nT_s )] = N_0 B_{IF} = \displaystyle{{N_0} \over 2}f_s $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn7.gif?pub-status=live){kind=small}
Another important parameter for the noise characterization is its auto-correlation function:
![$$R[m] = E\{ \eta [n]\eta [n + m]\} = \sigma _{IF}^2 \delta [m]$$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn8.gif?pub-status=live){kind=small}
which implies that the discrete-time random process η[n] is a classical Independent and Identically Distributed (I.I.D) Wide Sense Stationary (WSS) random process, or a white sequence. δ[m] is the Kronecker delta function.
Due to the orthogonality property of the spreading code sequences, the different GNSS signals are separately analysed by the GNSS receiver. Without loss of generality only a single satellite is considered in the following analysis and the index i for a satellite is dropped. The resulting signal is written as
![$$y[n] = Ad[n - \tau /T_s ]c[n - \tau /T_s ]{\rm cos}(2\pi F_D n + \varphi ) + \eta [n]$$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn9.gif?pub-status=live){kind=small}
3. GNSS SIGNAL ACQUISITION PROCESS
The conventional GNSS signal acquisition scheme is shown in Figure 1: the received input GNSS signal y[n] is multiplied by two orthogonal reference sinusoids at the frequency 
, split at the In-phase (I) and Quadrature (Q) branches, after the multiplication with a local code replica ![${\it c}_{{\it loc}} [{\it n} - {\it \bar \tau} /{\it T}_{\it s} ]$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqnU5.gif?pub-status=live){kind=small}
, delayed by 
, including the primary PRN spreading code sequence and the sub-carrier. The resulted signals on the in-phase and quadrature branches are coherently integrated, leading to the I component 
and Q component 
, respectively. The correlator outputs of the I and Q branches are then combined to form a complex correlation variable 
at Equation (10):
![$${Y(\bar \tau, \bar F_D ) = & Y^I (\bar \tau, \bar F_D ) + jY^Q (\bar \tau, \bar F_D ) = \displaystyle{1 \over N}\sum\limits_{n = 0}^{N - 1} {y[n]c_{loc} [n - \tilde \tau /T_s ]{\rm exp}(\,j2\pi \bar F_D n)}} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn10.gif?pub-status=live){kind=small}
where N denotes the coherent integration time, which is the number of samples used in the evaluation of the correlation between the received and local signals. The In-phase and Quadrature components are then squared and summed, removing the dependence from the input signal carrier phase φ. It is possible to obtain a two-dimensional decision variable 
in a coherent integration period, which is written as:
![$$S(\bar \tau, \bar F_D ) = |Y(\bar \tau, \bar F_D )|^2 = [Y^I (\bar \tau, \bar F_D )]^2 + [Y^Q (\bar \tau, \bar F_D )]^2 $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn11.gif?pub-status=live){kind=small}
By considering Figure 1, it is clear that all the operations before squaring blocks are linear. Their impacts on the useful signal and on the noise can be studied separately. In particular the In-phase and Quadrature components 
and 
are given by the following forms (Hegarty et al., Reference Hegarty, Tran and Dierendonck2003; Bastide et al., Reference Bastide, Julien, Macabiau and Roturier2002):
where:
R(·) is the cross-correlation between the local code and the filtered incoming code.
- is the difference between the Doppler frequency shift of the local carrier and that of the incoming signal.
- is the difference between the local code delay and the incoming code delay, normalized by the sampling interval T s.
Δφ is the difference between phases of received and local carriers.
d is a value in the set {−1, 1} that represents the effect of the navigation message or of the secondary code.
ηI and ηQ are two independent centered Gaussian correlator output noise Random Variables (RV) corresponding to the In-phase and Quadrature branches respectively, which are obtained by processing the noise term in Equation (9).
is the difference between the Doppler frequency shift of the local carrier and that of the incoming signal.
is the difference between the local code delay and the incoming code delay, normalized by the sampling interval T s.Non-coherent integration: the input composite signal y[n] is correlated with a delayed and modulated code replica, producing the final decision variable 
.
It is clear to know that the In-phase and Quadrature components 
and 
consist of signal and noise components. The signal components assume the following approximated expressions:
The correlator noise outputs ηI and ηQ can be obtained in the following:
![$$\eqalign{ & \eta ^I = \displaystyle{1 \over N}\sum\limits_{n = 0}^{N - 1} {\eta [n]c_{loc} [n - \bar \tau /T_s ]{\rm cos}(2\pi \bar F_D n)} \cr & \eta ^Q = \displaystyle{1 \over N}\sum\limits_{n = 0}^{N - 1} {\eta [n]c_{loc} [n - \bar \tau /T_s ]{\rm sin}(2\pi \bar F_D n)}} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn14.gif?pub-status=live)
Since it has been assumed that the noise term in Equation (9) is a white sequence and the considered blocks are linear, both ηI and ηQ are the linear combinations of the samples of the Gaussian process η[n], therefore they are two Gaussian RVs with zero mean and with equal variances obtained as:
![$$\eqalign{ {\rm Var}[\eta ^I ] =& {\rm E}[(\eta ^I )^2 ] - {\rm E}^2 [\eta ^I ] \cr =& \displaystyle{1 \over N}\sum\limits_{n = 0}^{N - 1} {\sum\limits_{m = 0}^{N - 1} {E\{ \eta [n]\eta [m]\} c_{loc} [n \!- \bar \tau /T_s ]{\rm cos}(2\pi \bar F_D n)}} \cdot c_{loc} [m - \bar \tau /T_s ]{\rm cos}(2\pi \bar F_D m) \cr =&\displaystyle{1 \over {N^2}} \sum\limits_{n = 0}^{N - 1} {\sigma _{IF}^2 {\rm cos}^2 (2\pi \bar F_D n)} \cr\approx & \displaystyle{1 \over {2N}}\sigma _{IF}^2} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn15.gif?pub-status=live)
Similarly, ![${\rm Var}[\eta ^Q ] \approx {\textstyle{1 \over {2N}}}\sigma _{IF}^2 $](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqnU18.gif?pub-status=live){kind=small}
. Therefore, denote ![${\rm Var}[\eta ^I ] = {\rm Var}[\eta ^Q ] = \sigma _n^2 $](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqnU19.gif?pub-status=live){kind=small}
. Since the code multiplication and the subsequent integration operation act as a low-pass filter, it is possible to show that ηI and ηQ can be considered uncorrelated and thus independent. In this way 
and 
result in two independent Gaussian RVs.
Usually the presence of a satellite is declared when the decision variable 
passes a pre-determined threshold β for fixed values of 
and 
. If there is no useful signal present, or the received signal is not perfectly aligned with the local code replica, that is under null hypothesis H 0, a threshold crossing results in a false alarm event; on the other hand, if the useful signal is present and it is correctly aligned with the local code replica, that is under alternative hypothesis H 1, when the threshold β is passed, a detection event occurs. The false alarm and detection probabilities can be defined as follows:
where 
is the Conditional Probability Density Function (CPDF) of the decision variable 
under H 0 hypothesis; and 
is the CPDF of 
under H 1 hypothesis.
If the local and received signals are not perfectly aligned or the useful signal is absent, that is under H 0 hypothesis, due to the quasi-orthogonality properties of the spreading codes, the decision variable 
is a central χ 2 RV with 2 Degrees of Freedom (DOF). When the local signal replica is aligned with the received signal (
and 
), that is under H 1 hypothesis, 
is a non-central χ 2 RV with 2 DOFs and with non-centrality parameter λ:
![$${\lambda = & E^2 [Y^I (\bar \tau, \bar F_D )] + E^2 [Y^Q (\bar \tau, \bar F_D )] = \displaystyle{{A^2} \over 4}\displaystyle{{\sin ^2 (\pi N\Delta F)} \over {(\pi N\Delta F)^2}} R^2 (\Delta \tau ) \approx \displaystyle{{A^2} \over 4}} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn19.gif?pub-status=live){kind=small}
By using the properties of central and non-central χ 2 RVs, the models of the false alarm and detection probabilities for a single primary code period can be obtained as:
where Q 1(a, b) is the generalized Marcum Q-function of order 1, defined as:
The RV
represents the basic element for the decision variable that will be determined at the final acquisition stage. When non-coherent integration is employed, the decision statistic is obtained by squaring 
and 
and then summing K different realizations of these RVs, which is written as:
![$$S_K (\bar \tau, \bar F_D ) = \sum\limits_{k = 0}^{K - 1} {|Y_K (\bar \tau, \bar F_D )|^2} = \sum\limits_{k = 0}^{K - 1} {[(Y_k^I (\bar \tau, \bar F_D ))^2 + (Y_k^Q (\bar \tau, \bar F_D ))^2 ]} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn23.gif?pub-status=live){kind=small}
where an index k is introduced to distinguish different realizations of 
and 
, which are obtained by considering consecutive, non-overlapping portions of the input signal y[n] and can be assumed statistically I.I.D. K is the non-coherent integration number.
If the useful signal is not present or if it is not correctly aligned with the local replica, 
is a central χ 2 distributed RV with 2K DOFs; otherwise, when the useful signal is present and properly aligned with the local replica, 
and 
are non-zero mean Gaussian RVs, hence 
is a non-central χ 2 RV with 2K DOFs and with non-centrality parameter λ K:
Similarly, by using the properties of non-central and central χ 2 RVs, it is easy to obtain the false alarm and detection probabilities when non-coherent integration strategy is adopted:
where Q K(a, b) is the K th order generalized Marcum Q-function.
4. CAF EVALUATION BY FFT AND BIT SIGN TRANSITION PROBLEM
In this section the CAF evaluation method by using the FFTs to perform circular correlation, which is known as FFT in the time domain, is analysed in detail. It is well-known that FFT can be used to perform fast circular correlations, so FFT based methods are often adopted to evaluate CAF (Van Nee et al, 2005; Akopian, Reference Akopian2005). This method is extremely efficient because it works on vectors in a parallel way; however, it is sensitive to CAF peak impairments due to the presence of bit sign transitions in the received GNSS signals.
By applying the results of the Maximum Likelihood (ML) estimation theory, it is possible to show that the best estimates of the code delay and the Doppler shift in the presence of AWGN are based on the maximization of the CAF. In the FFT based fast acquisition scheme, a signal vector y={y[0], y[1], …, y[N−1]} of N samples is extracted from the incoming IF signal and multiplied by a local complex signal 
, so as to obtain a sequence ![$q_l [n] = y[n]e^{ - j2\pi (\,f_{IF} + \bar f_d )nT_S} $](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqnU43.gif?pub-status=live){kind=small}
for each 
value, that is for each Doppler bin in the search space.
The sequence q l[n] is then FFT-transformed and multiplied by the complex conjugate of the FFT of the local code replica c loc[n] including the primary PRN code sequence and the sub-carrier s b,loc[n]. Finally the inverse FFT is made so as to obtain the Cross Correlation Function (CCF) 
, which can be evaluated in the following form:
![$$R_{y,r} (\bar \tau, \bar f_d ) = {\rm IDTFT}\{ {\rm DTFT}[q_l [n]] \cdot {\rm DTFT}[c_{loc} [n]]^{*}\} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn27.gif?pub-status=live){kind=small}
where DTFT and IDTFT stand for the well-known Discrete Time Fourier Transform (DTFT) and Inverse Discrete Time Fourier Transform (IDTFT), respectively.
In the current fast acquisition scheme based on DTFT, the FFT is used to perform DTFT, as shown in Figure 2. The local code generator also includes the sub-carrier.
The parallel acquisition scheme: the CAF is determined by using a circular convolution employing efficient FFTs. The code generator also includes the sub-carrier.
A CCF evaluated by applying a classical serial scheme and a circular CCF by using FFTs coincide only in the presence of periodic sequences. The presence of a bit sign transition in the data vector completely destroys the code periodicity, thus leading to serious peak impairments in the search space. Since the FFT based acquisition scheme takes advantage of parallel processing of the data vector, it is extremely efficient, but given its intrinsic nature of processing blocks of data, this method may suffer from the CAF peak splitting impairments due to the presence of bit sign transitions. In case of Galileo E1 OS data channel (E1-B) signal, the bit sign transition could possibly occur in any time interval of 4 ms (equivalent of a single code period).
It is possible to show that the presence of bit sign transitions does not destroy the possibility of detecting the satellites in view, but it introduces an error in the selection of the estimated pair ![${\it \hat p} = [\hat \tau, \hat f_d ]$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqnU46.gif?pub-status=live){kind=small}
, where 
is the estimated code delay and 
is the estimated Doppler shift in the acquisition stage. In fact when the local code replica matches the received signal perfectly, a code stripping process can be applied to y[n], obtaining the following signal:
![$$\eqalign{x[n] = & Ad[n - \tau /T_s ]c[n - \tau /T_s ]c_{loc} [n - \tau /T_s ]{\rm cos}(2\pi F_D n + \varphi )e^{ - j2\pi \bar F_D n} \cr = & Ad[n - \tau /T_s ]{\rm cos}(2\pi F_D n + \varphi )e^{ - j2\pi \bar F_D n}} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn28.gif?pub-status=live){kind=small}
The CAF envelope becomes:
![$$S_{y,r} (\tau, \bar F_D ) = \left| {\sum\limits_{n = 0}^{N - 1} {x[n]}} \right| = \left| {\sum\limits_{n = 0}^{N - 1} {Ad[n - \tau /T_s ]{\rm cos}(2\pi F_D n + \varphi )e^{ - j2\pi \bar F_D n}}} \right|$$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn29.gif?pub-status=live){kind=small}
where the term d[n−τ/T s]cos(2πF Dn+φ) can be written as:
![$${b_\tau [n] = & p_N [n]d[n - \tau /T_s ]{\rm cos}(2\pi F_D n + \varphi ) = p[n]{\rm cos}(2\pi (\,f_{IF} + f_d )nT_s + \varphi )} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn30.gif?pub-status=live){kind=small}
with the presence of a rectangular window function p N[n] in the interval n∈[0, N−1], which has an unitary amplitude. In case of bit sign transition the function p[n]=p N[n]d[n−τ/T s] reverses the bit sign being a two-pulses signal. Equation (29) can be regarded as the DTFT of a sinusoidal function modulated by p[n], which behaves as a sort of sub-carrier. This effect on the CAF peak is to split its power into two different smaller side lobes along the Doppler shift axis in the search space. By using the Euler formula cosα=1/2(ejα+e −jα) and introducing the discrete time function p[n], the analytical expression of the spectrum in Equation (29) can be obtained as:
![$$\eqalign{R_{y,r} (\tau, \bar f_d ) = & Ap[n]{\rm cos}[2\pi (\,f_{IF} + f_d )nT_s + \varphi ]e^{ - j2\pi (\,f_{IF} + \bar f_d )nT_s} \cr = & \displaystyle{1 \over 2}A\sum\limits_{n = 0}^{N - 1} {\,p[n]\{ e^{\,j[2\pi (\,f_d - \bar f_d )nT_s + \varphi ]} + e^{ - j[2\pi (2f_{IF} + f_d - \bar f_d )nT_s + \varphi ]} \}}} $$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn31.gif?pub-status=live)
The second high frequency term in Equation (31) can be neglected, so we can obtain:
![$$R_{y,r} (\tau, \bar f_d ) \approx \displaystyle{1 \over 2}Ae^{\,j\varphi} \sum\limits_{n = 0}^{N - 1} {\,p[n]e^{\,j2\pi (\,f_d - \bar f_d )nT_s}} = \displaystyle{1 \over 2}Ae^{\,j\varphi} \left\{ {\sum\limits_{n = 0}^{N_\tau - 1} {\,p[n]e^{\,j2\pi (\,f_d - \bar f_d )nT_s}} - \sum\limits_{n = 0}^{N_\tau - 1} {\,p[n]e^{\,j2\pi (\,f_d - \bar f_d )nT_s}}} \right\}$$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn32.gif?pub-status=live)
The two terms in Equation (32) are two truncated geometrical series, which can be easily summed giving the result (Lo Presti et al., Reference Lo Presti, Zhu, Fantino and Mulassano2009):
![$$R_{y,r} (\tau, \bar f_d ) \approx & \displaystyle{1 \over 2}Ae^{\,j\varphi} \left\{ {e^{\,j\alpha _1} \displaystyle{{{\rm sin}[\pi (\,f_d - \bar f_d )N_\tau T_s ]} \over {{\rm sin}[\pi (\,f_d - \bar f_d )T_s ]}} - e^{\,j\alpha _2} \displaystyle{{{\rm sin}[\pi (\,f_d - \bar f_d )(N - N_\tau )T_s ]} \over {{\rm sin}[\pi (\,f_d - \bar f_d )T_s ]}}} \right\}$$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn33.gif?pub-status=live){kind=small}
where:
α 1=
.α 2=
.
.
. In the correct Doppler shift bin 
, Equation (33) becomes:
![$$R_{y,r} (\tau, \bar f_d )|_{\bar f_d = f_d} \approx \displaystyle{1 \over 2}Ae^{\,j\varphi} [N_\tau - (N - N_\tau )]$$](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20151022042206496-0160:S0373463311000543_eqn34.gif?pub-status=live){kind=small}
which becomes zero when N τ=N/2. This means that the CAF peak completely disappears in the correct Doppler shift position when the bit sign transition occurs in the middle of the code period. However, the detection information of the satellites in view is not lost as the function in Equation (31) exhibits side lobe peaks, which can be properly exploited to recover the information of the code delay and Doppler shift estimates. In Section 5, a two steps based bit sign transition cancellation acquisition method will be described to recover the CAF peak in presence of bit sign transitions.
To show the CAF peak splitting effect in the search space of the signal acquisition stage for a GNSS receiver, we have simulated the Galileo E1 OS data channel (E1-B) signal containing navigation data message with the symbol rate of 250 symbols/s, which means that there is a possible bit sign transition at each PRN code period. The acquisition experiments have been performed with a Doppler shift f d of 3500 Hz, a code delay τ of 2 ms and a C/N0 value of 45 dB-Hz. This C/N0 value represents a relatively optimistic situation, which has been considered to show the CAF peak splitting effect and then to motivate the modification to the state-of-the-art acquisition scheme. In Figure 3, the CAF envelope is evaluated based on the fast acquisition scheme in case of no bit sign transition. When a bit sign transition is introduced to the signal, the CAF main lobe splitting effect can be clearly seen in Figure 4. In this case the FFT based fast acquisition scheme suffers much from the CAF peak loss caused by the presence of the bit sign transition.
CAF envelope of the Galileo E1 OS data channel signal when no bit sign transition occurs.
CAF envelope of the Galileo E1 OS data channel signal when a bit sign transition is present.
Two plots extracted from the CAF envelopes in Figure 3 and Figure 4 are provided in Figures 5 and 6, respectively. The upper curves represent the sections of the CAF envelopes in the Doppler shift domain (which are energy spectrum functions) at the correct code delay bin; the lower curves indicate the CCF in the code delay domain at the right Doppler shift bin.
In Figure 5, it is known that the CAF peak locates its position correctly along the code delay and Doppler shift axes respectively in the absence of bit sign transition in the received GNSS signals. When dealing with the bit sign transition case, in the upper plot of Figure 6 it is clearly observed that the CAF main peak is divided into two different smaller side lobes along the Doppler shift axis, leading to a wrong Doppler shift estimation; while from the lower plot of Figure 6 it is evident that the presence of bit sign transition does not impair the code delay estimate as the CAF main peak is located in the correct code delay bin but with a reduced correlation peak amplitude, therefore it is possible to know that the CAF main peak position in the search space does not change in the code delay domain whenever bit sign transition is present or absent in the received GNSS signal.
Curves extracted from the CAF envelope without bit sign transition.
Curves extracted from the CAF envelope in presence of a bit sign transition.
In order to further evaluate the CAF peak splitting effect dependent on the bit sign transition position in the received GNSS signal segment, an appropriate SNR metric is adopted, which is defined as the ratio of signal power to the noise power corrupting the signal:
where:
- is the circular correlation function value specific for the CAF main peak position in the search space when only useful signal is present.
- is the expected value of the squared CAF envelope due to only noise contribution.
is the circular correlation function value specific for the CAF main peak position in the search space when only useful signal is present.
is the expected value of the squared CAF envelope due to only noise contribution.Here, SNR compares the level of a desired correlation power for the useful signal to the level of averaged background correlated noise power. In order to determine the SNR values, Monte Carlo simulations have been performed with different positions of bit sign transitions present in the received signal segment y for several C/N0 values. In the simulation tests three code periods are coherently integrated and the bit sign transitions occur in the code periods alternatively. The simulation results are given in Figure 7, where the SNR values tend to decrease when the bit sign transitions move towards the middle position in the code period of the input signal segments, resulting in about 3·5 dB loss. The CAF peak splitting effect varying with the bit transition position in the received signal segment will be further evaluated by ROC curve in Section 6.
SNR evolutions dependent on the bit sign transition positions in the received GNSS signal segments: three code periods are coherently integrated.
5. TWO STEPS BASED BIT SIGN TRANSITION CANCELLATION METHOD
In this Section, a two steps based bit sign transition cancellation method is proposed to overcome the problem of CAF peak splitting caused by the presence of bit sign transitions in the received GNSS signals. The idea of this proposed technique is to exploit the fact that the CAF peak splitting occurs only in the Doppler shift domain, while in the code delay domain the CAF peak position remains almost unchanged. In the first acquisition step the code delay is estimated so as to tentatively align the local code sequence with the bit sign transition present in the received signal segment, while in the second acquisition step the Doppler shift is estimated. In other words, the estimated pair 
is obtained in two consecutive steps. The first acquisition step aims to get code delay estimate 
by using the FFT-based fast acquisition approach and usually the Doppler shift estimation 
is not performed in the first step as it could be erroneous due to the CAF peak splitting effect.
Noise reduction techniques, such as coherent integration and non-coherent integration strategies, can be adopted to increase the acquisition sensitivity. The coherently integrated CAF envelope 
in the first acquisition step can be written as:
where:
- is the n th contribution in the coherent integration process
N 1 is the number of the code periods applied to the coherent integration process in the first acquisition step.
is the n th contribution in the coherent integration process Non-coherent integration can be performed after the coherent integration operation. The non-coherently integrated CAF envelope 
can be written as:
where:
- is the k th coherently integrated CAF envelope in the non-coherent integration process.
K 1 is the non-coherent integration number for the computation of
.
is the k th coherently integrated CAF envelope in the non-coherent integration process.
. In the first acquisition step the estimated pair 
is obtained as follows:
In this acquisition step, only the estimated code delay is retained as valid, and the Doppler shift estimate is discarded as it could be possibly affected by the CAF peak splitting error (as shown in Figure 6).
In the second acquisition step the estimated code delay value achieved in the first acquisition step is used to extract a new signal vector aligned with the local code replica. In this way the effect of the bit transition practically disappears, even if the alignment is not perfect. Coherent integration and non-coherent integration can be again adopted in the second acquisition step. The coherently integrated CAF envelope 
evaluated in the second step can be written as:
Similarly, the non-coherently integrated CAF envelope 
in the second step is provided as:
Therefore, in the second acquisition step, a new estimate pair 
can be achieved as follows:
and only the Doppler shift estimate 
is retained. The code delay estimate 
should give a null value due to the new signal alignment performed in the second acquisition step. Therefore the code delay estimate can be discarded or it may be further used to refine the estimated code delay value obtained in the first acquisition step.
CAF envelope of the Galileo E1 OS signal evaluated by the two steps based bit sign transition cancellation method for a C/N0 value of 45 dB-Hz in presence of bit a sign transition.
The CAF envelope in the search space evaluated by using the two steps based bit sign transition cancellation method (for one primary code period) is shown in Figure 8. Two CAF peaks appear at the correct Doppler shift value (f d=3500 Hz). This is due to the fact that the code delay is zero in the second acquisition step, the bit sign transition practically disappears, and there exist two typical correlation triangles which appear at the beginning and the end positions in the code delay domain, respectively. This result is better highlighted in Figure 9: the upper plot shows that the CAF peak locates its position in the correct Doppler shift bin; the lower plot shows that the local code replica aligns perfectly to the bit sign transition position in the received signal segment because of the right recovery of the code delay estimate achieved in the first acquisition step.
Curves extracted from the CAF envelope evaluated by the two steps based bit sign transition cancellation method in presence of a bit sign transition.
6. SIMULATION RESULTS WITH GALILEO E1 OS SIGNAL
In order to validate the proposed two steps based bit sign transition cancellation technique, simulation tests have been performed on the simulated Galileo E1 OS BOC(1,1) signal, where the spreading code is modulated by navigation data with correct bit rate. First, the behaviour of the proposed technique is given in terms of histograms of the Doppler shift and code delay estimated values; secondly, ROC as well as SNR curves have been addressed in order to further assess the acquisition performance of the proposed technique in comparison with the conventional acquisition approach.
A preliminary performance analysis of the proposed technique has been carried out by means of histogram plots of the Doppler shift and code delay estimates. The simulation scenario considers Galileo E1 OS signal with code delay τ of 2·5 ms, Doppler shift f d of 3500 Hz and C/N0 of 30 dB-Hz. The Monte Carlo simulation campaigns have been repeated for 1000 times and the histograms of the estimates of and are provided in Figures 10 and 11, respectively.
The upper plot in Figure 10 denotes the histogram of the Doppler shift estimates using the conventional fast acquisition approach. It is easy to know that the Doppler shift estimates deviate much from the correct value (f d=3500 Hz) due to the CAF peak splitting impairments. The conventional fast acquisition approach shows inadequate performance when dealing with bit sign transition problem. The lower plot in Figure 10 is the histogram of the Doppler shift estimates evaluated by the proposed acquisition method; it can be easily observed that the obtained Doppler shift estimates with the proposed technique are much more concentrated around the correct Doppler shift value. The proposed methodology is able to partially mitigate the CAF peak splitting impairments, which outperforms the conventional fast acquisition approach.
Histograms of the Doppler shift estimates for two cases: the fast acquisition approach and the two steps based bit sign transition cancellation method when N=6 and C/N0=30 dB-Hz.
Figure 11 shows the comparison between the histograms of the code delay estimates for the aforementioned acquisition techniques. The upper histogram of the code delay estimates is evaluated by the conventional fast acquisition approach and the lower one is achieved by the proposed method. In Figure 11, it is easily shown that the proposed method provides improved detection rate for the code delay estimates in comparison to the conventional acquisition approach.
Histograms of the code delay estimates for two cases: the fast acquisition approach and the two steps based bit sign transition cancellation method when N=6 and C/N0=30 dB-Hz.
A more detailed performance analysis has been performed by evaluating a ROC curve, which is a graphical plot of the sensitivity, plotting the behaviour of the detection probability versus the false alarm probability, or equivalently, of the missed detection probability versus the false alarm probability of a binary classifier system as its discrimination threshold is varied. The performance criteria is proved to be qualified to make comparisons among different acquisition strategies in terms of actual performance.
The presence of bit sign transitions in the received GNSS signals reduces the benefits derived by coherently extending the integration time for such a reason in both acquisition steps of the proposed two steps based acquisition methodology a combination strategy between coherent integration and non-coherent integration is usually adopted. In the simulations, different code period options for the coherent integration and non-coherent integration operations have been selected to compare the performances between the aforementioned acquisition techniques. For all the simulations, the parameters reported in Table 1 have been adopted.
Simulation Parameters
The CAF main peak splitting effect dependent on the bit sign transition position in the received signal segment is presented here in terms of ROC curve. Simulation tests were made for three typical bit sign transition distribution cases: bit sign transition present in the middle or border positions, or randomly distributed in the received signal segment, which are implemented by the fast acquisition scheme for a C/N0 value of 38 dB-Hz. The simulation results are shown in Figure 12, which indicate that the acquisition performance degrades greatly when the bit sign transition occurs in the middle position of the signal segment, while the acquisition system provides better performance when the bit sign transition moves towards the border position of the signal segment; when dealing with the GNSS signal in presence of bit sign transition randomly distributed in a primary code period, the acquisition performance lies in between the two aforementioned cases. In the following performance analysis GNSS signals with randomly distributed sign transitions are considered in the ROC evaluations.
ROC comparison varying with the bit sign transition position by using the two steps based bit sign transition cancellation method when C/N0=38 dB-Hz, N=1, K=1.
Comparison between fast acquisition approach and two steps based bit sign transition cancellation method when N=2, K=6 and the C/N0 values are 32 and 34 dB-Hz, respectively.
Figure 13 depicts the performance comparisons among three acquisition cases: the conventional fast acquisition approaches in presence or absence of bit sign transitions, and the proposed acquisition method with sign reversals during the correlation. The simulations have been made considering coherent integration for two primary code periods (N=2) and six non-coherent integration operations (K=6) when the C/N0 values are 32 dB-Hz and 34 dB-Hz, respectively. The results in Figure 13 show that the proposed method provides improved performance in terms of detection probability over the conventional fast acquisition approach when the received signal presents the bit sign transitions. On the other hand, from the simulation results in Figure 13, it is also clearly shown that much improved detection probability can be obtained when the C/N0 value increases from 32 dB-Hz to 34 dB-Hz while keeping the operations of coherent integration and non-coherent integration unchanged.
In Figure 14 the acquisition performance comparison is outlined varying the non-coherent integration number and keeping the coherent integration time unchanged. The results shown in Figure 14 highlight that improved performance can be achieved by using the proposed acquisition technique when the non-coherent integration number K increases from 3 to 5 but with fixed coherent integration period N=2.
This trend is even more evident for high C/N0 values. When the C/N0 value increases to 38 dB-Hz, as shown in Figure 15, fewer non-coherent integration operations are required for the proposed acquisition technique to achieve a good estimate of the code delay in order to initialize the new signal alignment properly in the second acquisition step. It is clearly observed that the proposed method provides much improved performance in comparison with the conventional fast acquisition scheme, which could aid the acquisition stage of a GNSS receiver in real situations.
Finally the acquisition performance comparison is also presented in terms of SNR curve, which is the detection probability plotted versus the input C/N0 value for a fixed false alarm probability. Simulations for the SNR curve are made for a selected false alarm probability Pfa of 10−3. In Figure 16, it shows that the proposed acquisition method outperforms the conventional fast acquisition scheme in presence of bit sign transitions. The analysis results have proved the validity and effectiveness of the proposed technique, which is able to mitigate the CAF peak splitting impairments caused by the presence of bit sign transitions in the received GNSS signals.
Comparison between the fast acquisition approach and the two steps based bit sign transition cancellation method for a case of C/N0=35 dB-Hz.
Comparison between the fast acquisition approach and the two steps based bit sign transition cancellation method for a case of C/N0=38 dB-Hz.
SNR curve comparison between the fast acquisition approach and the two steps based bit sign transition cancellation method for Galileo E1 OS signal when N=2, K=6 and Pfa=10−3.
7. CONCLUSIONS
The presence of a data message or secondary code which modulates the primary spreading code in the new generation GNSS signals introduces a potential bit sign transition in each primary code period. The acquisition methods based on block processing of the received GNSS signals, such as the conventional fast acquisition scheme using FFTs, collide with the bit sign transition problem. The bit sign transition present within an integration period usually causes a splitting of the CAF main peak into two smaller side lobes along the Doppler shift axis in the search space constructed during the acquisition stage of a GNSS receiver, which results in a substantial performance degradation.
In this paper, a novel two steps based bit sign transition cancellation method has been proposed to deal with the bit sign transition problem present in the new generation GNSS signals. This proposed acquisition technique has been thoroughly considered and extensively analysed from a statistical viewpoint. False alarm and detection probabilities for the proposed acquisition strategy have been evaluated by Monte Carlo simulations, which are presented by ROC as well as SNR curves to support the theoretical analysis. In order to bring a whole view of the acquisition performance picture, the ROC and SNR curves for the state-of-the-art fast acquisition approach are also shown for comparison purposes.
In detail, from the developed analysis, it is clearly shown that the presence of bit sign transitions reduces the detection rate of the conventional fast acquisition scheme in a significant way, while the proposed two steps based bit sign transition cancellation technique effectively mitigates the CAF peak splitting impairments and provides more reliable signal detection in presence of bit sign transitions; therefore, the proposed acquisition methodology improves the acquisition performance and can be applied to the new generation GNSS signals where the navigation data stream or secondary codes could change the bit polarity every primary code period.
The proposed novel technique provides improved performance over the conventional fast acquisition approach in presence of bit sign transitions, which satisfies the requirements of the new generation GNSS signal modulations. It is important to emphasize that a greater computational load is generally required to perform the acquisition process for the new generation GNSS signals when the two steps based acquisition scheme is adopted.
ACKNOWLEDGEMENTS
This work is supported by the Chinese Fundamental Research Funds for the Central Universities.
