Keywords: Enveloppe convexe, polygone aléatoire, générateur

Un générateur de polygones convexes aléatoires dans un disque

Résumé :

Nous proposons un algorithme qui génère un polygone aléatoire défini par l'enveloppe convexe de n points aléatoires indṕendants et uniformément distribués dans le disque, sans avoir à générer explicitement tous les points.

Introduction

Let D be a disc in R 2 with radius R centered at o, and (x 1 , . . . , x n ) a sample of n points uniformly and independently distributed in D. Let's define the polygon P n as the convex hull of (x 1 , . . . , x n ), and f 0 (P n ) its number of vertices. This kind of polygon has been well studied, and using [START_REF] Bárány | Random polytopes in smooth convex bodies[END_REF][START_REF] Reitzner | Random polytopes[END_REF] one can easily see that

Ef 0 (P n ) = c n 1 3 + o(n 1 3 ) (1)
where c = 2 4 3 3 -1 3 Γ( 5 3 )π 5 3 ≈ 3.383228964 and Γ denotes the usual Gamma function. To generate such a polygon, one can explicitly generate n points uniformly in D and compute the convex hull. For a very large number of points, it could be interesting to generate fewer points to get the same polygon, for example to evaluate the constant that are not explicitly known for the asymptotic distribution of the perimeter, or other parameters such has the higher moments of the extremal points. In this note, we propose an algorithm that generates far fewer points at random in order to get P n , so that the time and the memory needed is reduced for n large.

Algorithm

We start with random polygon P i in D where i is very small, and we increase the number of points until we get P n . The idea is that given the convex hull of small number of points, the number of points generated in D that are deeply inside (and so won't change the convex hull) is a random variable that we can easily simulate, so that we need to generate only the small number of points that are close to the convex hull. The outline of the algorithm is the following :

• Generate a small number of points in D and compute its convex hull;

• Compute the radius of the largest disc centered at o inscribed in the convex hull;

• Choose a number of points to simulate at this step;

• Simulate the number of points that fall in this inscribed disc at this step;

• Generate the rest of the random points in the annulus defined by these two discs and update the convex hull.

• continue this process until the sum of the simulated and generated points is equal to n.

To simplify the notations, we assume D to have radius 1.

Notations

• n is the total number of points simulated and m i is the total number of points from step 1 to step i;

• k i is the number of generated points at step i, and k = i k i is the total number of generated points;

D i D o Figure 1: At step i,
we simulate the number of points that falls in D i and we generate points uniformly in the yellow annulus

• h i is size of the convex hull at step i, and h is the size of the final convex hull.

• p i is the probability to fall in the annulus at step i.

Initialization First, we have to generate a random polytope P i with a small number of points in D such that o is inside the random polytope. This is not too much to ask, as (see [START_REF] Alon | The probabilistic method[END_REF])

P(o ∈ P i ) = 2 -(i-1) i (2)
We initialize the random polygon by generating 100 points in the disc. As the probability that o ∈ P 100 is lower than 1.6 × 10 -28 , it's very unlikely that this is not enough. Otherwise, we add another sample of 100 points, until 0 ∈ P 100.j for some j.

Simulation of Points

At the beginning of each step i of the loop,we are given a polygon P mi , which is the convex hull of m i points. Let s i the number of new points simulated at step i. We choose s i = m i if m i < n log -2 n, and s i = n log -2 n otherwise. Let D i be the largest inscribed disc in P mi centered in o, and r i its radius. Using a simulation of a binomial variable of parameter s i and 1r 2 i , we can evaluate the number of points that falls in D \ D i . As the points in D i won't change the convex hull, we don't need to generate them. Then, we generate the rest of the points uniformly in the annulus D \ D i , and we update the convex hull using a Graham scan.

Generation of random points

To generate random points in an annulus with radii r i and 1, one need to generate the polar angles uniformly in [-π, π) and the squared radii uniformly in [r 2 i , 1). As we want to perform a Graham scan in linear time, the points have to be sorted by their polar angles. This can be done in expected linear time and size, using a bucket sort, as the angles are uniformly chosen, see [START_REF] Thomas | Introduction to Algorithms[END_REF]8.4

Complexity

Clearly the size complexity is max i (h i + k i ) and the time complexity is i (h i + k i ) since the Graham scan and the points generation are linear in the number of points [START_REF] Graham | An efficient algorith for determining the convex hull of a finite planar set[END_REF].

For the initialization, as the probability that 0 ∈ P n decreases exponentially, it is very unlikely that more than one loop is necessary. Let's call p the minimal number of points such that o ∈ P p . Using formula (2), the expectation of p is very small :

E(p) = ∞ j=1 jP(p = j) = ∞ j=1 P(p ≥ j) = 3 i=1 P(p ≥ j) + ∞ j=4 P(o ∈ P j-1 ) = 3 + ∞ j=3 P(o ∈ P j ) = 3 + ∞ j=3 j2 -(j-1) = 3 + 2 = 5.
(3) Thus, the expected size and time complexity of the initialization is O(1).

RR n°8467

For i big enough, we have [START_REF] Bárány | Intrinsic volumes and f -vectors of random polytopes[END_REF]:

E d H (P mi , D) = Θ Å log m i m i ã 2 3 (4)
where d H , the Hausdorff distance, is the maximal distance between a point in P i and the boundary of D.

Recall that D i is the annulus with radii r i = 1d H (P mi , D) and 1 and let p i be the probability that a random point in D falls in D i Using (4), there exist a constant c 0 > 0 such that, for i

large E(p i ) = 1 -r 2 i 2(1 -r i ) < c 0 Ä log mi mi
ä 2 3 . Let' s call i τ the last step i where m i < n log 2 n . At each step i ≤ i τ , k i is a binomial variable with parameter p i and m i < n log 2 n . Thus, for i large enough,

E(k i ) = E(E(k i |p i )) = m i Ep i = O(m 1 3 i log 2 3 (m i )) = O Ç Å n log 2 n ã 1 3 log 2 3 n å = O(n 1
3 ).

(5)

As we choose m i+1 = 2m i , i τ is bounded by log 2 (n).

For i > i τ , k i is a binomial variable with parameter p i and n log 2 n , so using (5) and the fact that

m i > n log 2 n , we get Ek i = O(n 1
3 ). As we simulate at each step i > i τ at least n log 2 (n) , the number of step after i τ is bounded by log 2 (n). Now,

Ek = iτ i=1 Ek i + i>iτ Ek i ≤ O Ñ log 2 3 n Ñ log 2 n i=1 m 1 3 i éé + log 2 n O(n 1 3 ) ≤ O Ñ log 2 3 n Ñ log 2 n i=1 (2 i ) 1 3 éé + O(n 1 3 log 2 n) = O(n 1 3 log 2 n) (6)
At each step i, the expected size of the convex hull is O(m

1 3 i ) = O(n 1
3 ), and

Ek i = O(n 1
3 ). Thus, the expected size complexity is O(n 1 3 ). As our points are sorted according to their polar angle, computing the convex hull with a Graham scan is done in linear time (O(n 1 3 log 2 n)), the generation of the k points and the computation of the largest annulus as well (O(n 1 3 )). Thus, the expected time complexity is O(n

1 3 log 2 n).

Experiments

This algorithm has been implemented in C++, and will be submitted for integration in the CGAL library. As expected, the distribution of Ef 0 (P n ) is asymptotically the same as the theoretical one, see equation (1), with the same constant : This estimation has been done one 1000 experiments for each value of log 10 n. Complexities To evaluate the size complexity, we just compute the largest list of points used in the loop, see Figure 3. The time complexity can be evaluated by estimating the total number of points generated, see Figure 4.

Conclusion

We propose an algorithm that generates random polygons given by the convex hull of random points, without generating all the points. There is no theoretical obstacle to generalize to higher dimension. The theoretical results used for the evaluation of the complexity are known in arbitrary dimension [START_REF] Bárány | Intrinsic volumes and f -vectors of random polytopes[END_REF][START_REF] Reitzner | Random polytopes[END_REF], so the analysis can be done as well. We can reduce the expected time complexity by a logarithmic factor if we allow to increase the expected size complexity by a logarithmic factor. Instead of bounding the simulated points at step i by n log 2 n when m i becomes bigger than n log 2 n , we can choose to always simulate m i points. In this case,

Inria

Figure 2 :

 2 Figure 2: Average size of P n divided by n 1 3

Figure 3 :Figure 4 : Average number of generated points divided by n 1 3 log 2 nFigure 5 :Figure 6 :

 341256 Figure 3: Average maximal size divided by n 1 3

  On the other hand, the expected time complexity is reduced to O(n

  ]. Convex hull of n uniformly chosen points in the disc D Simulated_Points ← 0 ; do Generate min(100,n -Simulated_Points) points in the disc of radius 1; Simulated_Points ← Simulated_Points+min(100,n -Simulated_Points) ; while o is not in the convex hull and Simulated_Points < n ; while Simulated_Points< n do Compute inscribed_radius; p ← inscribed_radius 2 ; if Simulated_Points < n log -2 n then k ← Simulated_Points; else k ← min(⌊n log -2 n⌋,n -Simulated_points); end X ← Simulation of Binomial variable with parameters k, 1p; Generate X points uniformly and sorted in the annulus of radii inscribed_radius, 1; Simulated_Points ← Simulated_Points + k ; Merge the list of the convex hull and the new points; Update the convex hull with a Graham scan on the list; end return Convex hull Algorithm 1: Algorithm of the Generator of Random Polygon in a disc

	Full algorithm
	Data: integer n
	Result:
	Inria

RR n°8467

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

This work was initiated during the 2013 Presage Workshop on computational geometry and probability in Valberg. The authors wish to thank all the participants for creating a pleasant and stimulating atmosphere and Pierre Calka for discussions about potential use of the generator.


Myriam Foucras
email: myriam.foucras@abbia.fr

Bertrand Ekambi
email: bertrand.ekambi@abbia.fr

Olivier Julien
email: ojulien@recherche.enac.fr

Christophe Macabiau
email: macabiau@recherche.enac.fr

Probability of Secondary Code Acquisition for Multi-Component GNSS Signals

Keywords: Pilot component, Secondary code, Autocorrelation, Acquisition I

The number of transmitted GNSS (Global Navigation Satellite Systems) signals has increased significantly with Galileo, Compass and QZSS constellations' ongoing deployment, GLONASS constellation maintenance and the introduction of new GPS signals. All the future GNSS civil signals are composed of two components: one being the pilot component which contains known secondary codes. In order to avoid fully exploit secondary code properties and the bit transition problem on the pilot component allowing long coherent integration for a better tracking, it is necessary to acquire the secondary code. This paper presents a mathematical model that determines the probability of correct acquisition of the secondary code once the spreading code has been acquired. The second point of the paper is the presentation of experimental results which provides some interesting results in terms of secondary code acquisition. The first one is the probability of secondary code acquisition when it is only read once. The second one corresponds to the required time to acquire the secondary code with a high probability for a given C/N 0 . These results, provided for four GNSS signals (GPS L1C, GPS L5, Galileo E1 OS and Galileo E5a/b) permit to compare the U.S GNSS with the European GNSS for several L band frequencies (L1 and L5).

INTRODUCTION

Before having a closer look into the detailed secondary code autocorrelation study, a general view on the secondary codes uses will start the paper.

GNSS signals are composed of a carrier which carries a navigation message and a spreading code sequence which permits to share a band of frequencies between several GNSS satellites signals (in the same constellation or not), via Code Division Multiple access (CDMA). The new generation of GPS signals and Galileo signals are composed of two components: the data component, which is modulated by a data message and the pilot component, which is dataless but contains a known secondary code.

The pilot component is introduced to avoid the data bit transition problem on the data component. Indeed, the pilot component is fully known once the secondary code is demodulated. This leads to longer coherent integration for a robust tracking. The presence of secondary codes on the pilot component mainly results in:

 Better autocorrelation properties of the pilot spreading code by making the overall period much longer  Minimization of cross-correlation and improvement of narrowband interferences suppression through decreasing spectral lines [START_REF] Rushanan | The spreading and overlay codes for the L1C signal[END_REF]  Providing of data message synchronization [START_REF] Stansell | GPS L1C: Enhanced Performance, Receiver Design Suggestions, and Key Contributions[END_REF] Additionally, GPS L1C secondary codes, which are especially very long, provide support for improved reading of clock and ephemeris [START_REF] Betz | Description of the L1C Signal[END_REF] and decrease the number of time ambiguities after locking to the spreading codes [START_REF] Stansell | GPS L1C: Enhanced Performance, Receiver Design Suggestions, and Key Contributions[END_REF].

The paper aims to discuss different secondary code structures, their autocorrelation properties and the probability of secondary code acquisition. Then the paper outline is as follows:

 The first section serves as a review of the studied GNSS signals and their main features. Several points differ from signals as L band frequency, spreading code length, code frequency, etc…  The second section focuses on the secondary codes of the considered signals. Thus, it will be seen that each GNSS signal designers have chosen different secondary code lengths (between 20 and 1800 bits), which induces a different number of secondary codes (between 1 for short secondary codes and one per satellite for long secondary codes).  The third section proposes a mathematical study on the probability of correct acquisition of the secondary code. This is based on the correlator output that contains the secondary code bits which is then correlated with the secondary code to highlight its first bit.  The fourth section exploits Matlab simulation results to determine the threshold demodulation in terms of needed time and sensitivity. Then, the comparison between the four considered GNSS signals can be done based on the secondary code acquisition properties.  Some conclusions are drawn in the last section by reminding the main results of the signals comparison and future works.

II. SIGNAL PROPERTIES

In the case of this study, four GNSS signals are considered: GPS L1C and L5 and Galileo E1 OS and E5a/b, whose frequency plans are presented in Fig. 1.

Fig. 1: GPS and Galileo frequency plans [START_REF]European GNSS (Galileo) Open Service Signal In Space Interface Control Document[END_REF] All the considered GNSS signals are composed of two components: one being the pilot component containing a secondary code. This section gives an overview of the main signal features. Table I and [START_REF] Avila-Rodriguez | On Generalized Signal Waveforms for Satellite Navigation[END_REF] summarize the main technical features which will be developed in this section.

A. GPS signals 1) GPS L1C signal

The GPS L1C signal is one of the new GPS signals and will be transmitted by the next generation of satellites, called GPS III, in 2014-2015. The GPS L1C design has been optimized to provide superior performance, while providing compatibility and interoperability with other signals in the L1 band (GPS L1 C/A but also Galileo E1 OS and QZSS) and improvements in receiver processing techniques.

GPS L1C, defined in [START_REF] Navstar | Global Positioning Systems Directorate Systems Engineering & Integration Interface Specification IS-GPS-800 navstar GPS Space Segment/User Segment L1C Interface[END_REF] and detailed in [START_REF] Stansell | GPS L1C: Enhanced Performance, Receiver Design Suggestions, and Key Contributions[END_REF] and [START_REF] Betz | Description of the L1C Signal[END_REF], consists of two components. Both components are spread by a spreading code; the pilot channel is also modulated by a satellite (overlay) secondary code. There is one secondary code per satellite (210 secondary codes are defined but only 63 are used). This signal provides a number of advanced features, including a power difference in both components: 75% of power in the pilot component for enhanced signal tracking and 25% of power in the data component. At the end, the received signal is represented as follows:

( ) [ ( ) ( ) ( ) ( ) √ ( ) ( ) ( ) ] ( ( ) ) ( )



Where:  is the data sequence  and are the spreading codes on the data and pilot component respectively  is the studied secondary code  √ is the total signal power  is the carrier frequency  is the Doppler frequency  is the initial phase of the signal  is the noise, assumed white Gaussian  and are the subcarriers, which are defined by:

( ) ( ) ( ( )) ( ) { ( ) ( ) ( ) ( )



With the time and MHz.

The GPS L1C implementation of TMBOC is produced by modulating in the pilot component 4 of each 33 spreading code chips (which number mod by 33 is in ) with BOC(6,1) while retaining BOC(1,1) for all other spreading code chips in the pilot component (and also for all of the data spreading code chips). The spreading code is composed of 10230 chips and his period is 10 ms.

2) GPS L5 signal

The GPS L5 signal has been transmitted for the first time on board GPS IIF satellites. The GPS L5 carrier at 1176.45 MHz carries both components in quadrature. The GPS L5 signal presents the particularity to also have a tiered code on the data component, , it is a short code (10 bits) which lengthens the spreading code sequence. This 10-bit Neuman-Hofman will not be studied in this work as it is not on the pilot component.

The GPS L5 chipping rate of 10.23 MHz leads to a spreading code period of 1 ms (10 230 chips). The GPS L5 signal structure is given in  and for more details, refer to the ICD [START_REF] Navstar | Global Postioning Systems Directorate Systems Engineering & Integration Interface Specification IS-GPS-705 Navstar GPS[END_REF] and [START_REF] Kaplan | Understanding GPS: Principles and applications[END_REF].

Where:

 is the Neuman-Hofman on the data component (10 bits)  is the Neuman-Hofman on the pilot component (20 bits), the studied secondary code

B. Galileo signals 1) Galileo E1 OS signal

The Galileo E1 OS signal, the Galileo analog of GPS L1 C/A, is described in [START_REF]European GNSS (Galileo) Open Service Signal In Space Interface Control Document[END_REF]. The data and pilot, in-phase, components are modulated by CBOC(6,1,1/11), which implies the use of two subcarriers (at and ) as defined in the Galileo E1 OS expression signal .

( ) √ ( ) ( ) ( ) ( ( ) ) √ ( ) ( ) ( ( ) ) ( ) 
Galileo E1 OS differs from GPS signals (and Galileo E5 signals as it will be seen) by its spreading code period which is equal to 4 ms (for 4092 chips) instead of 1 or 10 ms.

( ) [ ( ) ( ) ( ) ( ) ( ) ( ) ] ( ( ) ) ( )



Where and are the data and pilot subcarriers defined by:

( ) √ √ ( ) ( ) √ ( ) ( ) ( ) √ √ ( ) ( ) √ ( ) ( )  2) Galileo E5 a/b signal
The Galileo E5 signal is composed of four components and the signal power is divided evenly in 4. There are two data components (in-phase components): E5a-I and E5b-I which carry two different navigation message (F/NAV and I/NAV) and two associated pilot components (quadrature components): E5a-Q and E5b-Q. According to [START_REF]European GNSS (Galileo) Open Service Signal In Space Interface Control Document[END_REF], the wideband Galileo E5 signal is generated with constant envelope Alternate Binary Offset Carrier (AtlBOC) modulation. It is a modified version of BOC with code rate of 10.23 MHz and a subcarrier of 15.345 MHz. Because the two sidebands (E5a and E5b) can be processed independently, the Galileo E5 signal can also be considered as two separate Quadrature Phase Shift Keying (QPSK) signals with a carrier frequency of 1176.45 MHz and 1207.14 MHz (around the central frequency 1191.795 MHz). In the paper, to be equitable, Galileo E5a and Galileo E5b are considered as two signals then the power dedicated to each pilot component is similar to the power of Galileo E1 OS or GPS L5 pilot component (an half). Then, the Galileo E5 signal can be represented as follows:

( ) ( ) ( ) ( ( ) ) ( ) ( ) ( ) ( ( ) )
 

Where:  stands for or  and are the initial phases The spreading codes and are sequences of 10230 chips which are spread in 1 ms at the code rate of 10.23 MHz.

III. SECONDARY CODE FEATURES

For the purpose of the presented study herein on the probability of secondary code acquisition, it is necessary, to first compare secondary code features (length and number of secondary codes) and secondary code autocorrelation properties (isolation).

For all of the GNSS signals, each bit of the secondary code is modulated to one period of the spreading code, the spreading code period, noted as , (Table I) is equal to the secondary code bit duration (Table II).

TABLE II. SECONDARY CODE FEATURES

Length Bit duration

Number of secondary codes

Pilot Power allocations

GPS

√

The notation is used to express the power of the pilot component.

As introduced, the paper focuses on the probability of secondary code acquisition. To do so, the secondary code autocorrelation function is defined:

( ) ∑ ( ) ( ) 
Where is the number of secondary code bits Because the secondary code is a binary sequence of and , the autocorrelation function is maximum for (the maximum value being 1). The other values taken by the autocorrelation function are more or less close to 0. The better autocorrelation function is in general for the one that has the lower values in absolute value; in other words, the higher isolation between the first maximum and the others.

A. GPS signals 1) GPS L1C signal

The pilot component of GPS L1C signal is modulated by secondary codes (one code per satellite) and called sometimes overlay code because it comes into play an overlaid on the pilot component. The length of the secondary codes is 1800 bits, which corresponds to the number of symbols on a data frame for L1C. One of the criteria used to create the family of the GPS L1C secondary codes was the good auto and crosscorrelation properties. As it can be seen in Fig. 3 which gives the maximum normalized autocorrelation function for each satellite, the maximum autocorrelation is -24.78 dB (also given in [START_REF] Rushanan | The spreading and overlay codes for the L1C signal[END_REF] for even auto-correlation).

2) GPS L5 signal

The GPS L1C secondary codes are the longest of the considered secondary codes and at the contrary, the GPS L5 secondary code is the shortest (20 bits). There is only one secondary code for GPS L5, . Due to its length, the GPS L5 secondary code autocorrelation properties cannot be as good as GPS L1C. Indeed, the maximum autocorrelation is only -13.98 dB as it is given in Fig. 4 and Table III which gives also the distribution.

B. Galileo signals 1) Galileo E1 OS signal

The Galileo E1 OS secondary code properties are close to GPS L5 secondary code ones. Indeed, there is only one Galileo E1 OS secondary code and its length is 25 bits. However, the maximum autocorrelation is higher: -18.42 dB. 2) Galileo E5 a/b signal The short-duration primary code of Galileo E5 (1 ms) is balanced by a long-duration secondary code modulation [START_REF] Kaplan | Understanding GPS: Principles and applications[END_REF]. The Galileo E5 secondary codes are predefined with sequences of lengths up to 100 bits. The autocorrelation properties of secondary codes are quite good and similar for Galileo E5a-Q and E5b-Q. The autocorrelation maximum is at -21.94 dB (the same for both Galileo E5 pilot components). V. The difference between each code is the distribution (which slightly differs).

Autocorrelation function Distribution

C. Secondary code comparison

Table VI summarizes the secondary code autocorrelation isolation for each secondary code. As it can be seen, the minimum isolation is -13.98 dB. This value is obtained for GPS L5-Q, the shortest secondary code.

As it is understandable, the more the secondary code length is, the less the maximum autocorrelation is. Then, Galileo E1 OS seems to be a good compromise between secondary code length and autocorrelation isolation. Galileo E5 a/b has a better autocorrelation isolation for a longer secondary code (in bits) but similar secondary code period.

IV. PROBABILITY OF CORRECT ACQUISITION

Let us interest in the probability of correct acquisition of the secondary code.

A. Secondary code acquisition method

The successive secondary code bits are successively read and correlated with the actual secondary code (with a possible secondary code bit delay). The proposed method is detailed in three steps, each one is mathematically explained: a)

Acquiring the signal by giving an exact estimation of the code delay, Doppler frequency and phase of the incoming signal (using the autocorrelation function of the spreading code). The associated correlator output computation is given in Appendix A and its expressions is:

( ) ( ) ( ) (8)
Where:  ⟦ ⟧ is the index of the considered secondary code bit  ( ) stands for the th coherent summation on the th secondary code bit: there are ms between two successive integrations ( ) and ( ) on the ith bit  ( ) can be modeled as a centered Gaussian noise with a variance equal to [START_REF] Bitar | Advanced GPS signal processing techniques for LBS services[END_REF] Let us remark that here the phase error is assumed to be null, in the section V.C, some results are presented assuming a more realistic case, that means with a residual phase tracking error; the mathematical development when considering a not null phase error is given Appendix B.

b)

The technique can be enhanced by coherent accumulation over the duration of several secondary code periods. Mathematically, the summation over the th secondary code bit is:

( ) ∑ ( ) ∑ ( ) ∑ ( ) ( ) ( ) (9)
This leads to a reduction in noise impact because the resulting noise ( ) is a Gaussian distribution with null mean and a variance equal to . It can be seen as the coherent integration on ms. Then, ̂( ), the normalized ( ) correlator output by can be seen as an estimator of the th secondary code bit ( ). Galileo E5b [START_REF] Bitar | Advanced GPS signal processing techniques for LBS services[END_REF] becomes:

̂( ) ( ) ( ) ( ) (10)
The noise is a Gaussian distribution with null mean and the variance is given by (11) and represented in Fig. 8. c)

( ) ( ) (11)
The last step is the correlation with secondary code to perform the determination of the bit delay, noted as ( can be seen as )

̂( ) ∑ ̂( ) ( ̂) ∑ ( ) ( ̂) ∑ ( ) ( ̂) ( ) ( ̂)



At the end, the noise ( ̂) is a Gaussian distribution with null mean. The variance of ( ̂) is . Noises for each point of ̂( ) are identically distributed but there are not independent. Indeed, due to the correlation with the same noise sequence , the correlation term, given by the covariance , corresponds to the autocorrelation function. Then, for different from :

( ( ) ( )) (| |) (13)

B. Probability of correct secondary code acquisition

The probability of correct secondary code acquisition consists in evaluating the probability to estimate in a right way the parameter that means to find the first bit of the secondary code. To determine it, the maximum secondary code autocorrelation function is studied. Then the probability of correct secondary code acquisition is equivalent to the probability that the maximum value of ̂( ) is for such as ( ) . It is then appropriate to mathematically develop the probability of secondary code acquisition even if the obtained expression is not as simple as it is wanted. Let

( ) ( ) ( ( √ )) 
Where the error function ( ) is defined by:

( ) √ ∫ 
Then, the density of probability is given by:

( ) √ ( )



To develop the mathematical model, let us assume that there is no bit delay, then is the only random variable such as . Let us introduce the random variable which is the maximum of the others :

. Now, the probability of secondary code acquisition, denoted as is:

( ) ( )  To evaluate , let us first determine the distribution of the random variable , by evaluating cumulative distribution function, . To do so, the independence between the random variables is supposed, it can be done because the autocorrelation function is close to 0 (section III.C).

(

( ) ∏ ( ) ∏ ( ( √ )) ) ( ) ( ( ) ) ( ) ∏



Then, the probability of secondary code acquisition can be computed knowing the distribution of and .

( )

∫ ( | ) ( ) ∫ ( | ) ( ) ∫ ( ) ( ) ∫ ( ) ( ) ∫ ( ) ( ) √ ∫ ∏ ( ) ( )



It is extremely difficult to check and exploit this expression (Mathematica can provide an approximation by means of numerical analysis to approach the integral). The other parameter is the number of coherent accumulations . The objective is to determine for which the probability of correct secondary code acquisition is satisfying (higher to 0.99). Then, the required time to correct acquire the secondary code can be computed. It is the number of coherent accumulations multiplied by the secondary code period (in ms).

V. SIMULATION RESULTS

A. Simulation scheme

The simulation scheme consists in evaluating the probability of secondary code acquisition depending on the total received signal power and on the required time. To do so, the secondary code estimator as defined in ( 10) is simulated as the secondary code plus a random noise with null mean and a variance of . Then, the correlation function with a local secondary code is computed using:

̂ ( ( ) ( ̂) ̅̅̅̅̅̅̅̅ ) (20)
Where is the discrete Fourier Transform operator

Based on the output of the correlation operation, the successful secondary code acquisition is declared when the highest point of the correlation function corresponds to the correct synchronization. Matlab simulations are run a large number of times (10 000) to determine the probability of correct secondary code acquisition (the ratio of correct detection of the maximum over the number of runs).

B. Simulation results considering perfect phase tracking

In a first time, the simulations are run assuming that the carrier phase tracking is perfect. Two results are investigated:

 The first one is the probability of secondary code acquisition on one secondary code period.  The second result consists in studying the required acquisition time to reach a probability of secondary code acquisition greater than 99% for a given C/N 0 . The simulation results are presented by means of tables and figures: the parameter C/N 0 , for figures, represents the total received signal power to compare the signals performance and for tables the pilot component power to compare secondary codes not influenced by the difference on the power on the pilot component.

1) set to 1

The first result is the probability of correct secondary acquisition knowing that is set to 1 (the secondary code is only read once) and for three values of C/N 0 .

As it can be anticipated, the GPS L1C signal (in red) is the best one in terms of probability of secondary code acquisition for a given C/N 0 . This is mainly due to the very long secondary code period (18 s) compared to the others (around 100 ms). It also represents a case that might be optimistic as GPS L1C receiver might use another acquisition technique (such as partial correlation) to speed up the acquisition.

GPS L5 and Galileo E1 OS have secondary codes properties and pilot component power shares that are close but their probabilities of secondary code acquisition present notable differences. Indeed, for a given probability of acquisition, there can be a difference of 5 dB and for the same C/N 0 , there can be a difference of 0.2 on the probability of acquisition, Galileo E1 OS (in blue) being the best. This can be explained by the variance of the noise which is higher for smallest values of (as pointed out in Fig. 8). The probabilities of secondary code acquisition for each Galileo E5 secondary codes are very similar (difference lower than 0.025), then Galileo E5a-Q is not differentiated from Galileo E5b-Q and is represented in cyan. It is between the probabilities of secondary codes acquisition for GPS L5 and Galileo E1 OS. Then, for the same secondary code period (100 ms), Galileo E1 OS is better than Galileo E5a, mainly due to the variance depending on the spreading code period.

Table VII To take into account the difference of power on the pilot component, Table VII is given. The probability of secondary code acquisition is given depending on the power on the pilot component. As discussed in previous figure, GPS L1C is the better one followed by Galileo E1 OS. Galileo E5 is between GPS L5 and Galileo E1 OS in terms of probability of secondary code acquisition.

  = 0 GPS L1C GPS L5 Galileo E1 OS Galileo E5 a
2) Probability of desired secondary code acquisition set to 0.99

The second result consists in estimating the required time to correctly (with a probability of 99%) acquire the secondary code. Fig. 10 presents results for GPS L5, Galileo E1 and E5; GPS L1C is not considered since it has been seen in the previous section that the probability of secondary code acquisition is equal to 1 whichever the considered C/N 0 above 15 dB-Hz. The Galileo E5a needs more time than GPS L5 and Galileo E1OS which are very close because for low C/N 0 . The Galileo E5a probability of secondary code acquisition is close to the one of GPS L5 but the secondary code period is longer than GPS L5 secondary code period. The GPS L5 secondary code period is shorter (20 ms) than the Galileo E1 OS or E5a and b secondary code period (100 ms); this explains why the GPS L5 seems to be a curve whereas Galileo E1 and E5a seem to be a line and then results. Table VIII, which provides the required time to reach a given probability of secondary code acquisition for a given received pilot component power of C/N 0 completes the results presented previously.

TABLE VIII. REQUIRED TIME TO A PROBABILITY OF ACQUISITION OF 99%

(20 DB-HZ ON THE PILOT COMPONENT)

(in ms) GPS L1C-P 1 18000 GPS L5-Q 6 120 Galileo E1-C 2 200 Galileo E5a-Q/ E5b-Q 2 200
For the same secondary code period (100 ms) for Galileo E1 and E5, the required time to reach the probability of secondary code acquisition of 99% is the same, namely two secondary code periods. GPS L5 needs more coherent accumulations but because GPS L5 secondary code is shorter (20 ms), the total required time is lower.

C. Simulation results considering realistic phase tracking

After studying the better case -with a null phase error-, let us interest in the more realistic case. The phase error represents the error between the incoming signal carrier phase and the local one.

follows a Gaussian distribution [START_REF] Garcia-Pena | Optimization of Demodulation Performance of the GPS and Galileo Navigation Messages[END_REF] with a null average and a variance defined by [START_REF] Kaplan | Understanding GPS: Principles and applications[END_REF]:

( ) ( ) (21)
The mathematical model is developed in Appendix B. Then, for realistic simulation results, the term in ( ∑ ( ) ) will have a not negligible impact on the secondary code acquisition performance.

For secondary code demodulation, as it is done for data demodulation, the first correlator output computation and the second one for the same secondary code bit is delayed by the secondary code period. Then, phase errors can be supposed to be uncorrelated because the secondary code period is largely greater than the loop convergence time. Then, for simulations, the phase error is supposed to be a centered Gaussian distribution with the variance given by (21). The secondary code is correlated with a secondary code sequence affected by

( ∑ ( )
) plus noise. For one coherent integration, each secondary code bit is multiplied by ( ), for two coherent integrations, it is multiplied by the average of two cosine terms, etc… Let us remark that if the follows a Gaussian distribution, (

) seems to be also a Gaussian distribution even if ( ) is not distributed as a Gaussian.

When the phase error is greater than 1 rad, the tracking loops lose lock. For a C/N 0 of 15 dB-Hz, only 80% of the randomly generated phase errors are lower than 1 radian. As a consequence, a C/N 0 above 20 dB-Hz is considered because lesser than 2% of the values are greater than 1 radian. Fig. 11 provides the probability of secondary code acquisition when considering phase tracking error. The variance of the phase error is inversely proportional to the sensitivity and to the spreading code period . Then, as it is the case for the noise variance in Fig. 8., the variance is maximal for equal to 1 ms. At 20 dB-Hz, in the worst case, for GPS L5 and Galileo E5a, the variance is 0.6 rad compared with 0.225 for Galileo E1 OS and 0.15 for GPS L1C. This results in higher degradations in the probability of secondary code acquisition (Fig. 11) and for a given C/N 0 more time to reach the same probability of secondary code acquisition (Fig. 12) for the L5 band GNSS signals. The case GPS L1C is not discussed because one coherent integration is 18 seconds which is largely outside of reasonable acquisition time interval. When considering not null phase error and for all of the other signals, GPS L5 secondary code needs 260 ms to be acquired 99% of time. Due to a longer secondary code period, Galileo E1 OS needs 300 ms. Galileo E5a needs more time (500 ms) because it suffers from relatively long secondary code period (as Galileo E1 OS) but a higher variance value compared to Galileo E1 OS.

For the same given C/N 0 of 20 dB-Hz, the probability of Galileo E5 secondary code acquisition becomes 0.14 (Fig. 11) when considering phase error instead of 0.4 (Fig. 9) when the assumption of no phase error is done. This explains the considerable expansion of the required time to reach the same probability.

VI. CONCLUSION

In this paper, a study on secondary codes was done. Four secondary code classes (GPS L1C, GPS L5, Galileo E1 OS and Galileo E5a/b) are compared in terms of autocorrelation.

In a first part, the features of each one are reminded. The length of secondary codes can be very different between 20 and 1800 bits, which implies different secondary code autocorrelation isolation properties. Indeed, for the GPS L1C, which is the longest secondary code (1800 bits), the isolation is 24.78 dB but for the GPS L5, which is the shortest secondary code (20 bits), the isolation is only 13.98 dB (more than 10 dB of difference). The Galileo E1 OS seems to be a good compromise between secondary code length and isolation; with 25 bits, the isolation is 18.42 dB. The GPS L5 secondary period (20 ms) is 5 times lower than the Galileo E1 OS and E5 (100 ms) and 90 times than the GPS L1C secondary code period.

Then, the paper focuses on the probability of secondary code acquisition. Simulation provides results in terms of probability of secondary code acquisition versus the secondary code acquisition time and sensitivity. Due to its length, the GPS L1C secondary code provides the better probability of secondary code acquisition for a given sensitivity (even low) but 18 seconds are required. The Galileo E1 OS is still one of the most interesting compromise between probability of secondary acquisition and required time, due to its spreading code period (secondary code bit) which is longer than the one of GPS L5 and Galileo E5. Indeed, the Galileo E5 secondary code acquisition performance depends on the considered sensitivity (total signal power or only one pilot component power). Even if the better case is considered (pilot component power), the Galileo E5 secondary code acquisition performance is not as better as Galileo E1 OS which has the same secondary code period. The GPS L5 secondary code acquisition performance is quite good due to its short secondary code period (only 20 ms).

As seen, the assumption of perfect phase tracking is an ideal case because when considering phase tracking error, the performance of secondary code acquisition is degraded: some more coherent integrations are needed to reach the probability of 99% of secondary code acquisition: 3 for Galileo E5a, 1 for Galileo E1 OS and around 5 for GPS L5.

In the context of this study, it is difficult to compare the GPS L1C due to its very long secondary code period. Galileo E1 OS is better than Galileo E5 and maybe the one which proposes the best compromise between secondary code period (which implies secondary code acquisition time) and probability of secondary code acquisition.

For the special case of GPS L1C, it may be interesting to study secondary code acquisition by means of partial correlations. In a first time, the number of kept secondary code bits (completed by zero bits to reach the length of 1800 bits) should be determined to provide reasonable isolation: 125 bits are sufficient to reach an approximate isolation of -14 dB (GPS L5 secondary code autocorrelation isolation) but it corresponds to 1.25 second. To reach the Galileo E5a secondary code autocorrelation isolation, a zero-padding of an half of the length of the GPS L1C secondary code is sufficient but at least 8 seconds are needed. Then, the reduction in number of bits is interesting but still leads to long partial correlations.

This work focuses on GPS and Galileo signals, two signals are not studied: GPS L2C and Galileo E6, for commercial service, which contain a pilot component but they do not carry a secondary code. The work can be extended to the other GNSS constellations, namely Glonass, QZSS, Beidou…

Fig. 2 :

 2 Fig. 2: GPS L1C (Code 1) normalized autocorrelation function

Fig. 3 :

 3 Fig. 3: Normalized autocorrelation maximum for all of the 63 GPS L1C secondary codes

Fig. 4 :

 4 Fig. 4: GPS L5 secondary code autocorrelation function

Fig. 5 :

 5 Fig. 5: Galileo E1 OS secondary code autocorrelation function As GPS L5, Galileo E1 OS autocorrelation function is composed of a few values (3 for Galileo E1 OS and 4 for GPS L5).

Fig. 6 :

 6 Fig. 6: Galileo E5 a/b-Q (first codes) autocorrelation function Fig. 6 and 7 give the autocorrelation function for the first codes of Galileo E5a and E5b. For all of the Galileo E5 a and b secondary codes, the values taken by the secondary code autocorrelation function are the same and given in TableV. The difference between each code is the distribution (which slightly differs).

Fig. 7 :

 7 Fig. 7: Galileo E5a/b-Q (first code) autocorrelation function (in dB)

Fig. 8 :

 8 Fig. 8: Noise variance versus the C/N0

  can be understood that the probability of correct secondary acquisition depends on the considered signal through:  The integration time, which corresponds to the spreading code period (1, 4 or 10 ms)  The secondary code length (20, 25, 100 or 1800 bits)  The carrier to noise density C/N0 through √  The values taken by the secondary code autocorrelation function (| ̂|)

Fig. 9 :

 9 Fig. 9: Probability of secondary code acquisition for 1 coherent accumulation

  code acquisition -K = 1 -

Fig. 10 :

 10 Fig. 10: Required time to reach a high probability of secondary code acquisition

Fig. 11 :

 11 Fig. 11: Probability of secondary code acquisition for 1 coherent accumulation and a not null phase error

Fig. 12 :

 12 Fig. 12: Required time to reach a high probability of secondary code acquisition considering a not null phase error

TABLE I .

 I SIGNAL FEATURES

	Signal		Modulation	Central frequency	Spreading code length	Code frequency
	GPS L1C		TMBOC (6,1,4/33)	1575.42 MHz	10230 chips 10 ms	1.023 MHz
	GPS L5		BPSK(10)	1176.45 MHz	10230 chips 1 ms	10.23 MHz
	Galileo E1 OS	CBOC (6,1,1/11)	1575.42 MHz	4092 chips 4 ms	1.023 MHz
	Galileo	a	QPSK	1176.45 MHz	10230 chips 1 ms	10.23 MHz
	E5	b	QPSK	1207.14 MHz	10230 chips 1 ms	10.23 MHz

TABLE III .

 III GPS L5 SECONDARY CODE AUTOCORRELATION DISTRIBUTION

	Autocorrelation function	Distribution
		In dB	On 20 In %
		-13.98 dB	3	15%
			14	70%
		-13.98 dB	2	10%
	1	0 dB	1	5%

TABLE IV .

 IV GALILEO E1 OS SECONDARY CODE AUTOCORRELATION

		DISTRIBUTION
	Autocorrelation function	Distribution
		In dB	On 25 In %
		-27.96 dB	18	72%
		-18.42 dB	6	24%
	1	0 dB	1	4%

TABLE V .

 V GALILEO E5A -CODE 1 AUTOCORRELATION DISTRIBUTION

TABLE VI .

 VI SECONDARY CODES AUTOCORRELATION ISOLATION

		Length	Period	Autocorrelation maximum
		(in bits)	(in ms)	Real value in ||	(in dB)
	GPS L1C-P	1800	1800	0.058	-24.78
	GPS L5-Q	20	20	0.2	-13.98
	Galileo E1-C	25	100	0.12	-18.42
	Galileo E5a-Q	100	100	0.08	-21.94
	Galileo E5b-Q	100	100	0.08	-21.94

APPENDICES

A. Classical acquisition correlator output

The GNSS incoming signal can be modeled as:

( ( ) ) ( ) Where:

 and are the incoming code delay and Doppler frequency which are locally estimated by ̂ and ̂  and are the power on the data and pilot component Let us denote the spreading code period, the length of the secondary code, the coherent summation number and ⟦ ⟧ the index for the considered secondary code bit. Then, the th inphase correlator output of the th secondary code bit results in the integration of the incoming signal multiplied by a local replica of the pilot sequence (pilot spreading code and pilot subcarrier).

( )

Where :  ( ) and ( ) are assumed to be null (right Doppler frequency and code estimation) because the acquisition stage is supposed to be done  ( ) is the cross-correlation (between the data and pilot spreading codes) and is supposed to be null  ( ) is phase error The received noise is assumed to be white and Gaussian with a noise level of . Then at the correlator output, the noise ( ) is assumed to be Gaussian with null mean and its variance is equal to (refer to [START_REF] Bitar | Advanced GPS signal processing techniques for LBS services[END_REF]).

The same correlation process can be done for pilot component in quadrature: the received signal is multiplied by ( ) ( ) ( ( ̂) ) and the same correlator output ( ) ( ( )) ( ) is obtained.

B. Secondary code acquisition considering phase error tracking

In this appendix, the secondary code acquisition steps are developed again but considering phase error: a) Acquiring the signal by giving an exact estimation of the code delay and Doppler frequency of the incoming signal (using the autocorrelation function of the spreading code). The associated correlator output computation is given in and its expressions is:

Where:  is the phase tracking error. In the context of this paper, neglecting the effect of the local oscillator phase noise, it is assumed to have a variance [START_REF] Kaplan | Understanding GPS: Principles and applications[END_REF] equal to

Where  , the carrier loop noise bandwidth chosen to be equal to Hz.

b)

The technique can be enhanced by coherent accumulation over the duration of several secondary code periods. Mathematically, the summation over the th secondary code bit is:

This leads to a reduction in noise impact because the resulting noise ( ) is a Gaussian distribution with null mean and a variance equal to . It can be seen as the coherent integration on ms. Then, ̂( ), the normalized ( ) correlator output by can be seen as an estimator of the th secondary code bit ( ). becomes:

The last step is the correlation with secondary code to perform the determination of the bit delay, noted as ( can be seen as )

̃( ) ( ̂) Where ̃ is an approximate of the autocorrelation function At the end, the noise ( ̂) is a Gaussian distribution with null mean. The variance of ( ̂) is .