AMELIORATION OF ACQUISITION OF A DEGRADED SIGNAL IN A GNSS RECEIVER EMBEDED IN AN OBSERVATION SATELLITE BY USING DOUBLE BLOC ZERO PADDING METHOD (DBZP)

Dib Djamel Eddine¹⁺ --- Djebbouri Mohamed² --- Taleb Ahmed Abddelmalik³

^1,2Djillali Liabes University Sidi Bel Abbes, Algeria

³Laboratory of automatics, Mechanical and Computer Science Valencienne University France

Keywords: GPS, Acquisition, Correlation, DBZP , AWGN channel, (C / A) code

Article History: Received: 2 May 2017, Revised: 30 May 2017, Accepted: 5 June 2017, Published: 9 June 2017

1. INTRODUCTION

A GPS (Global Positioning System) is a geo-localization system. It includes three segments: Space, Control, and users. GPS signals are transmitted on one frequency, called L1, which contains the code acquisition called coarse (C / A), and the various navigation messages (L1 = 1575.42 MHz).

The satellite of observation belongs to the LEO satellites. Low Earth Orbit is defined as an orbit within a locus extending from the earth’s surface up to an altitude of 2000 Km [1]. Attributing to their high speeds, data transmitted through LEO is handed off from one satellite to another as satellites generally move in and out of the range of earth-bound transmitting stations. Due to low orbits, transmitting stations are not as powerful as those that transmit to satellites orbiting at greater distances from earth’s surface.

As LEO orbits are not geostationary, networks of satellites are required to provide continuous coverage. In our case the average altitude of observation satellite is 700km. Its period of rotation around the Earth is 101 minutes, than we can compute the velocity of the satellite of observation:

Vob=Robdθ/dt =7330 m/s (1)

The period of a GPS satellite is 11h, 58min, 2.05s , as above we compute the velocity of the satellite GPS:

Vgps=Rgpsdθ/dt =3874 m/s (2)

2. GNSS SIGNAL ACQUISITION PRINCIPLE

In GNSS receivers, the first stage of the signal processing is the acquisition. It consists in assessing the presence of GNSS signals, identifying all satellites visible to the user and giving a rough estimation of the incoming signal parameters.

3. CORRELATION OPERATION

As previously said the acquisition aims at deciding either the presence or the absence of the GNSS signal and provides a rough estimation of the code delay and Doppler frequency of the incoming signal. To do so, a replica is locally generated (depending on an estimation of the incoming code delay and Doppler frequency) and correlated with the incoming signal.

The correlation operation is the basic operation performed in the signal processing part of a GNSS software receiver and is dependent upon the GNSS signals properties, particularly the spreading code properties. Indeed, these codes have been carefully chosen to have very good pseudo-randomness properties. This means that they have properties that are close to those of a white noise (this is why they are called Pseudo-Random Noise (PRN) codes)., when the spreading code is correlated with itself, the correlation function result is equal to 1 for a perfect alignment and close to being null for a misalignment or when two different spreading codes are correlated. Figure 1 shows the autocorrelation function between the local and incoming spreading code of the GPS L1 C/A spreading code number 2. The correlation operation is denoted 𝑅𝑐1 and defined by

(1)

Figure-1. GPS L1 C/A autocorrelation function (PRN2)

Ward, et al. [2]

Figure-2. Block diagram of the correlation

Ward, et al. [2]

In a GNSS receiver, the correlation operation consists in correlating the received signal with a local replica of the carrier and spreading code of the received signal. To do so, the received signal is multiplied by a sinusoid and a local spreading code. The resulting signal is then integrated, generating the in-phase correlator output I. As illustrated in Figure 2, the same process is also performed with a shifted sinusoid of /2. This provides the quadrature phase correlator output Q. The acquisition of GNSS signals described in literature is based on the evaluation and processing of the correlator outputs.

In our case the rapidity of acquisition have a essential factor in detection of signal GPS because the high velocity of observation satellite so we have to search a method which is fast ,and can detect the weak signals .

4. DOUBLE-BLOCK ZERO-PADDING (DBZP) METHOD

Several acquisition methods have been developed that aim at accelerating the correlation process. In many of these, the search is parallelized based on the discrete Fourier transform, implemented using Fast Fourier Transform (FFT) algorithms. In this case, the complexity of such a method depends on the size of the vector over which the FFT is executed, and the number of FFTs computed. One approach to optimize the correlation process execution time is to deal with vectors which size is a fraction of the spreading code period. The most well-known acquisition method based on this approach is the Double-Block Zero-Padding as presented initially in literature in [3]. It has been demonstrated by Lin and Tsui [4] and Chibout [5]. That the DBZP consumes less time and power compared to other classical acquisition methods, also based on FFTs.

4.1. DBZP Method Algorithm

The general mathematical model of the Double-Block Zero-Padding acquisition method can be described in 5 steps. The block diagram of the DBZP method is shown in Figure 3.

The concept of the DBZP is the use of many partial correlations over a duration equivalent to a few tens of chips. To do so, the incoming signal and the local code are split into blocks.

Figure-3. Double-Block Zero-Padding (DBZP) method block diagram

Zhang and Ghogho [6]

Initialization :
The input parameters of the DBZP are:

- The coherent integration time 𝑇𝐶,

- The Doppler uncertainty range [𝑓𝐷𝑀in,, 𝑓𝐷Max] where 𝑓𝐷𝑀ax is the maximum expected
value of the incoming Doppler frequency and 𝑓𝐷𝑀𝑖n the minimum.The central frequency of the Doppler frequency range is denoted 𝑓𝐷𝑀e𝑑. In a typical acquisition scheme, the coherent integration time is in general chosen to be equal to the spreading code period 𝑇𝑐1. For an application on GPS L1 C/A signal, it can be several spreading code periods. The Doppler frequency range is in general symmetric with respect to 0 when there is no a priori knowledge on the Doppler. Even if the Doppler frequency range is not symmetric, it is easy to go to the case 𝑓𝐷𝑀e𝑑 = 0, by multiplying the local carrier by exp(−2𝑖𝜋𝑓𝐷𝑀e𝑑𝑛𝑇𝑠) with (𝑛 = 0, 1, … , 𝑁𝑠 − 1). Then 𝑓𝐷,𝑀𝑖n = −𝑓𝐷,𝑀𝐴x. Unlike the serial search acquisition method, the number of DBZP Doppler frequency bins and their resolutions are fixed by the algorithm and cannot be chosen by the user. The number of Doppler frequency bins, denoted 𝑁𝑏 is determined by:

(2)

The number of code delay blocks is chosen to be equal to the number of Doppler frequency bins [7]. It can be deduced that:
- The duration of one block 𝑡𝑏 is:

(3)

- The number of samples per block 𝑁𝑠𝑝𝑏 is equal to:

(4)

- The Doppler frequency resolution Δf is:

(5)

5. STEPS OF DBZP ALGORITHM

Step 1: Pre-processing of the incoming signal

Firstly, the received signal is pre-processed. Indeed, the received complex signal is converted into baseband by multiplying it by a complex carrier exp (−2𝑖𝜋𝑓𝐼f𝑛𝑇𝑠) depending only on the intermediate frequency 𝑓if, which means that the local complex carrier does not try to compensate the incoming Doppler frequency. It is important to understand that only one carrier replica, which does not depend on a Doppler frequency estimate, is generated.

Figure-4. Pre-processing of the incoming signal

Zhang and Ghogho [6]

The resulting 𝑇𝐶 long baseband samples are arranged into 𝑁𝑏 blocks of equal length. Each couple of two consecutive blocks is grouped to form 𝑁𝑏 blocks of size 2𝑁𝑠𝑝𝑏 (thus the name”Double-Block”) and denoted , with 𝑙 = 0, 1, … ,𝑁𝑏 − 1 referring to as the block index. The last block is combined with additional samples as illustrated in Figure 4.

Step 2: Generation of the local spreading code

The second step consists in conditioning the local spreading code. As for the incoming signal, 𝑇𝐶 ms of the local code are generated and splitted up into 𝑁𝑏 blocks of 𝑁𝑠𝑝𝑏 samples. Then, each block is zero-padded and denoted , this means that 𝑁𝑠𝑝𝑏 samples of value 0 are appended to each block as illustrated in Figure 5, where the 𝑁𝑠𝑝𝑏-block composed of 0s is represented by a black box

Figure-5. Pre-processing of the local code

Zhang and Ghogho [6]

Step 3: Partial correlations on the split signals

The third step aims at evaluating the correlation output, computing it by means of FFT. The first 2𝑁𝑠𝑝𝑏-samples block of the incoming signal is circularly correlated with the first zero padded code block. This results in a partial circular correlation, and only the first half is preserved.

Some points in this step should be developed. The 𝑁𝑠𝑝𝑏 output samples represent a partial correlation on 𝑡𝑏 ms (much shorter than a spreading code period) over 𝑁𝑠𝑝𝑏 possible code delays. The partial correlation is illustrated in Figure 6 and can be compared with the full
correlation.

Figure-6. Full and partial GPS L1 C/A autocorrelations

Zhang and Ghogho [6]

When the local and incoming spreading codes are perfectly aligned (or the estimated code
delay is in the neighborhood of the right code delay), the normalized partial correlation is equivalent to the normalized full autocorrelation. The drawback of the partial correlation is that the correlation is done on only a part of the whole spreading code and thus the periodicity and the properties of the spreading code are not kept (the isolation is degraded as it can be observed in Figure 6).

In the DBZP acquisition method, the Zero-Padding is used to go over the non-periodicity of the partial code blocks., when the zero-padding is not used, the normalized autocorrelation function peak is highly attenuated. On the contrary,when the partial correlation is computed using 2𝑡𝑏 of signal and zero-padding the local partial code, the normalized autocorrelation function peak is highly isolated and not attenuated Let us note that only the first part of the correlation is kept, corresponding to the one with the potential peak. On the figures, the partial correlation is done over 𝑡𝑏 for a code delay of 27 chips Knowing that 𝑙 = 0, 1, . . ,𝑁𝑏 − 1 defines the code block pair, the coherent integration interval is assumed to be:

(6)

Furthermore, the phase at

(7)

is assumed to be:

(8)

Based on the classical correlator outputs, the partial in-phase correlator output is:

(9)

Finally

(10)

- 𝑙 = 0, 1, … , 𝑁𝑏 − 1 stands for the l-th partial correlation,
are the in-phase and quadrature phase 𝑙-th partial correlator output,

- is the partial autocorrelation function,
-𝜀𝜏(𝑘, 𝑙) is the code delay in [𝑇0 + (𝑘 − 1)𝑇𝐶 + 𝑙𝑡𝑏 , 𝑇0 + (𝑘 − 1)𝑇𝐶 + (𝑙 + 1)𝑡𝑏]. Strictly
speaking, 𝜀𝜏(𝑘, 𝑙) depends on the slice of time, but it is assumed that the parameters of the incoming signal and local replica are constant during the correlation process
and then, it is assumed that 𝜀𝜏(𝑘, 𝑙) = 𝜀𝜏,
- 𝜀𝜙0(𝑘, 𝑙) = 𝜙0(𝑘, 𝑙) − is the carrier phase error at the beginning of the interval
[𝑇0 + (𝑘 − 1)𝑇𝐶 + 𝑙𝑡𝑏 , 𝑇0 + (𝑘 − 1)𝑇𝐶 + (𝑙 + 1)𝑡𝑏],
- 𝜂 and 𝜂 are the noises at the partial correlator outputs with a variance of

== (11)

It is worth noting that the phase 𝜋𝑓𝐷𝑡𝑏 + 𝜀𝜙0(𝑘, 𝑙) depends on:
- The incoming Doppler frequency 𝑓𝐷 (if 𝑓̂𝐷 is null, otherwise on 𝜀𝑓𝐷 = 𝑓𝐷 − 𝑓̂𝐷),
- The (𝑙 + 1)tℎ signal block
The partial correlator outputs can be stored in a matrix of size 𝑁𝑏 × 𝑁𝑠𝑝𝑏 where:

- There are as many columns as possible code delays: each column contains all the
partial correlator outputs for a given code delay error,
- There are as many rows as partial correlations: each row contains the partial correlator outputs for a given slice of time.

Step 4: Application of the FFT

An 𝑁𝑏-point FFT is applied to the set of the partial correlation outputs corresponding to a given code delay. This permits to determine the Doppler frequency of the incoming signal. It can be assumed that (A/2) 𝑐1
(𝜀𝜏) sinc(𝜋𝑓𝐷𝑡𝑏) is constant for all 𝑙 in ⟦0, 𝑁𝑁𝑏𝑏−1⟧ and can be approximated by (𝐴/2)𝑅𝑐1 (𝜀𝜏) sinc(𝜋𝑓𝐷𝑡𝑏) in the neighborhood of 𝜀𝜏 = 0. Thus, the FFT of the partial correlator outputs provides the DBZP outputs

(12)

where:
-𝜙(𝑘)=𝜋𝑓𝐷𝑡𝑏+(𝜋(N𝑏−1)/N𝑏)(𝑓𝐷𝑇𝐶−𝑚)+𝜀𝜙0(𝑘,0),
- 𝑚 = 0, … , 𝑁𝑏 − 1 is the point where the FFT is taken and corresponds to a Doppler frequency bin,
- 𝜂𝜄𝜄 and 𝜂𝜌 are the complex noises at the DBZP outputs, which expression and variance

(13)

It is interesting to note that the width of the main peak of the sinc term sinc(𝜋𝑓𝐷𝑏) is 2N𝑏/𝑇𝐶 which is larger than the main peak of the sinc term sinc(𝜋𝜀𝑓𝐷𝑇𝐶) (classical serial search) which is 2/𝑇𝐶. However, due to the additional presence of the second sinc term, in the frequency domain, the DBZP output should provide a peak for the frequency bin that corresponds to the right estimation of the incoming Doppler frequency, for a right estimation of the code delay. The peak width corresponds to the frequency resolution 1/𝑇𝐶.

Step 5: Permutation of code blocks:

In the process previously described, only code delays in the first code delay time slice [0,𝑡𝑏[ are tested. To try all code delays, the local code blocks are circularly permutated: the 𝑁𝑏-th block becomes the first block, the first block becomes the second block, etc 𝑁𝑟 permutations like this can be done to explore the whole code delays. The incoming signal blocks are kept unchanged. Let us note that if the coherent integration time 𝑇𝐶 is equal to the spreading code period, the number of circular permutations corresponds to the number of blocks 𝑁𝑟 = 𝑁𝑏. However, if 𝑇𝐶 is longer than one spreading code period (e.g. for GPS L1 C/A with 𝑇𝐶 = 10 ms [8] the number of circular permutations reduces to 𝑁𝑟=N𝑏/(𝑇𝐶/𝑇𝑐1) due to the spreading code periodicity. Indeed, the code block because the first 𝑁𝑟 blocks describe spreading code period and the next 𝑁𝑟 blocks are a repetition of the first 𝑁𝑟 blocks. The DBZP matrix output is of size (𝑁𝑏 × 𝑁𝑟𝑁𝑠𝑝𝑏), each row corresponding to a Doppler frequency bin and each column to a code delay.

6. CONCLUSION

The intention of this paper has been to propose a new computationally efficient acquisition method for GNSS software receivers. From the literature, it results that methods based on parallelization (in time or frequency domain) perform the acquisition operation efficiently due to the use of FFT. In general, it is more efficient to perform many FFTs on small vectors than one FFT on a large vector. Based on this, the Double-Block Zero-Padding (DBZP) is pointed out as one of the most computationally efficient acquisition method for GPS L1 C/A due the use of partial correlations and a high level of parallelization (in code and frequency). all steps of the DBZP acquisition method were delved into details. This analysis permitted to mathematically express the DBZP outputs and investigate its performance. It has been shown that the signal-to-noise ratio at the DBBZP output and at the classical correlator output are the same. But the DBZP method is faster than classical method so we have a gain in time and good localization of observation satellite.

REFERENCES

[1] T. Sakai, K. Kobayashi, S. Kubota, M. Morikura, and S. Kato, "Soft-decision Viterbi decoding with diversity combining (mobile satellite communications)," presented at the Global Telecommunications Conference, 1990, and Exhibition.'Communications: Connecting the Future', GLOBECOM'90., IEEE, 1990.

[2] P. Ward, J. W. Betz, and C. Hegarty, GPS satellite signal charactristics, in understanding GPS: Principles and applications: Artech House, 2005.

[3] D. M. Lin, J. B. Y. Tsui, and T. Howell, "Direct P(Y)-code acquisition algorithm for software GPS receivers," in Proceedings of the 12th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 1999). Nashville, TN (USA), 1999, pp. 363 – 368.

[4] D. Lin and J. B. Y. Tsui, Comparison of acquisition methods for software GPS receiver. Salt Lake City, UT: ION GPS, 2000.

[5] B. Chibout, "Application of indoor and urban GNSS localisation techniques to space navigation," PhD Thesis, ENAC, Toulouse, France, 2008.

[6] W. Zhang and M. Ghogho, "Improved fast modified double-block zero-padding (FMDBZP) algorithm for weak GPS signal acquisition," in Proceedings of 18th European Signal Processing Conference (EUSIPCO 2010). Aalborg (Denmark), 2010.

[7] N. I. Ziedan and J. L. Garrison, "Bit synchronization and Doppler frequency removal at very low carrier to noise ratio using a combination of the Viterbi algorithm with an extended Kalman filter," in Proceedings of the 16th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS/GNSS 2003), 2001, pp. 616-627.

[8] N. I. Ziedan, GNSS receivers for weak signals. Boston, London: Artech House. INC, 2006.