Novel partial correlation method algorithm for acquisition of GNSS tiered signals

  • NAVIGATION: Journal of the Institute of Navigation
  • December 2020,
  • 67
  • (4)
  • 745-
  • 762;
  • DOI: https://doi.org/10.1002/navi.390
PDF

Abstract

This paper presents a new modified Single Block Zero-Padding (mSBZP) Partial Correlation Method (PCM) Parallel Code Search (PCS) algorithm for effective acquisition of weak GNSS tiered signal using coherent processing of its secondary code (SC) component. Two problems are discussed: acquisition of primary codes with a longer period using FFT blocks of limited length, and the utilization of PCS in the presence of SC bit transition. The PCM and SC bit transition forms parasitic fragments in the Cross-Ambiguity-Function (CAF) to devaluate signal detection performance. A novel analysis of this mechanism and its impact is presented. A novel mSBZP-PCM-PCS algorithm is proposed, which does not degrade the CAF. Then, the algorithm is combined with SC bit transition removal schema and sequential search to construct an estimator for weak tiered signal acquisition. The performance of the method is demonstrated by analysis and computer simulation using Galileo E1C and GPS L1C-P signals.

1 INTRODUCTION

Modern GNSS (Global Navigation Satellite Systems) signals are usually constructed as tiered signals using a secondary code (SC) above a primary code. It brings some advantages and disadvantages. The SC improves the tiered signals jamming immunity and the cross-correlation properties, or simplifies the process of navigation message bit frame synchronization. The resulting advantage is potentially higher sensitivity of acquisition. The acquisition is, however, complicated by the presence of the SC and by a long primary code period, which is also often used.

The SC is usually a few bits (4 bits in the Galileo E5B-I) or tens of bits (25 bits in the Galileo E1C, or 20 bits in the BeiDou B1, etc.) long. However, exceptions exist (100 bit in Galileo E5b-Q or up to 1 800 bit of GPS L1C-P). Nevertheless, the primary code is always significantly longer than the secondary one.

The most valuable feature of the SC is that it permits to extend coherent integration time (Pre-detection Integration Time (PIT); Ziedan, 2006) over many periods of primary code with a priori known SC bits (Borio, 2011; Corazza, Palestini, Pedone, & Villanti, 2007; Leclère, Botteron, & Farine, 2017; Mongrédien, Lachapelle, & Cannon, 2006; Tawk, Jovanovic, Leclere, Botteron, & Farine, 2011). It is advantageous in case of weak signal reception, where the increase of non-coherent integration time is not enough. In that case, the non-coherent algorithms or any methods non-sensitive to SC could still be used for acquisition. However, they cannot achieve high sensitivity and therefore are out of the scope of this paper.

The conventional acquisition is a two-dimensional problem (code phase τ and Doppler frequency shift fd estimation) shown in Equation (1), where R is a discrete-time cross-correlation function between signal r[t] and its replica shown in Equation (2). The replica is formed by primary c[t] of length T and secondary SC[t] code of length of NSC. The SC bits are modulo-2 added (⊕) over primary code periods T. Thus, n could be expressed as an integer part of (τ/T). The * symbol denotes complex conjugation. The resulting function is also called the Cross-Ambiguity-Function (CAF).

1 1

2 2

A straightforward realization of Equation (2) is a sequential search algorithm that coherently combines primary code periods according to an SC bit hypothesis to extend PIT easily using any search in the SC index n (Borio, 2011; Corazza et al., 2007; Mongrédien et al., 2006; Tawk et al., 2011). However, the sequential search is time-consuming.

The Parallel Code Search (PCS) algorithm is based on the Wiener-Khinchin theorem (Abu-Rgheff, 2007) using the Discrete Fourier Transform (DFT) of signal and replica shown in Equation (3). The ○ symbol denotes the Hadamard product, i.e., it is a multiplication of the corresponding points of both spectra.

3 3

The PCS offers an acceleration using the FFT (Fast Fourier Transform) algorithm (Van Nee & Coenen, 1991). However, the FFT requires an exact number of samples equal to 2a. The Single Block Zero-Padding (SBZP) is used to adapt the number of signal samples to the required length.

The tiered signal period is too long to be processed with one long FFT in practice. Therefore, processing over separate primary code periods is presumed and shown in Equation (4). The problem then effectively becomes a three-dimensional problem, with an additional dimension of the SC phase n shown in Equation (5).

The code phase τ resulting from the search over T is the primary code phase. The overall code phase is then nT+ τ.

4 4

5 5

Nevertheless, the presence of the unknown position of SC bit transition (bit edge) excludes the utilization of the PCS SBZP algorithm in the primary code phase search. The energy of the CAF is spread in the Doppler shift domain to many peaks out of the main one. The PCS algorithm is based on cyclic correlation and is therefore sensitive to SC bit transition.

The Double Block Zero-Padding (DBZP) is another type of zero-padding which guarantees that at least one whole period will be correlated, even when a transition of navigation message or SC bit sign occurs. It correlates two signal periods padded by zeroes to FFT length on the end of the sequence with a single period of replica padded to the same length. This method is a particular case of linear correlation. The DBZP is SC bit transition insensitive, but requires FFT of double length (Mollaiyan, Santerre, & Landry, 2013; Yang, 2001).

Therefore, the paper’s motivation is to propose a modified PCS algorithm that will be able to apply a hypothesis of SC bit transition for PIT extension too.

Primary codes of modern signals have a longer primary code (> 1023 chips) than was used in previous signals like GPS L1 C/A (Kaplan & Hegarty, 2006; Ziedan, 2006). The number of samples per primary code period T could be longer than the FFT available.

Hence, another paper motivation is acquisition of these modern GNSS signals with their SC and longer primary code period using the FFT units with the same length, as is currently used for fast acquisition of simple GPS L1 CA or Glonass L1OF signals with the shorter primary code period.

The proposed approach uses the Partial Correlation Method (PCM) presented in Fortin, Bourdeau, and Landry (2015). Their approach is based on the PCS SBZP processing of a long primary code period of the tiered signal. They divide the signal into M independent blocks of consecutive signal samples and correlate them using smaller FFT length. After that, they combine correlation sub-results non-coherently, which guarantees insensitivity to SC bit transition. Nevertheless, the approach is not directly applicable to the mentioned PIT extension.

In this paper, only coherent combining is used. The primary thesis is that the effects of single block zero-padding, partial correlation, and SC bit transition problem have the same origin in violation of signal periodicity, which in turn violates the assumption of the cyclic correlation function. These issues are analyzed by means of modeling the bit transition and the partial correlation effects on the Cross-Ambiguity-Function (CAF) by rectangular functions like in Presti, Zhu, Fantino, and Mulassano (2009). Based on this analysis, the PCS modified SBZP PCM algorithm with the SC bit removal schema is proposed.

The processing of the SC component and also the basic component of the used modulation is presumed. The algorithm should be primarily suitable for Galileo E1C and eventually for other similar modern signals. The Galileo E1C signal is used for demonstration throughout the paper, using basic BOC(1,1) component or BPSK-like processing of its composite CBOC(6,1,1/11) signal. Another example is the GPS L1C signal, because of its long primary code (10 230 chips). The processing of the L1C TMBOC(6,1,1/11) signal as BOC(1,1) is assumed. The acquisition of Galileo E5a,b and GPS L5 signals (BPSK(10) with 10 230 bit long primary codes and secondary codes) is possible in the same manner using only higher sampling frequency. Acquisition of other composite signals like GPS L2CM and others using a similar basic component of its composite structure is theoretically possible. The extremely long quasi-periodic signals like GPS L2 P(Y) codes are beyond the scope of this paper and covered by Pang, Van Graas, Starzyk, and Zhu (2003).

This paper is organized as follows. The state of the art is in Section 2. A comprehensive analysis of the mentioned PCM has not been published before. The work (Fortin et al., 2015) is limited only to non-coherent combining, and the behavior of the computed function is not derived. The following sections generalize it (Section 3), derive its loss (Section 3.1), and analyze its behavior concerning non-coherent and coherent combining of sub-results (Section 3.2). The aim is to describe all influences that can affect signal detection. Based on this analysis, the novel modified algorithm is proposed (Section 4), together with a schema applying the SC bit transition hypothesis (Section 4.1). Derivations are supported by Matlab simulations in Section 5. Section 6 is the conclusion.

2 STATE OF THE ART

The weak signal acquisition (Ziedan, 2006) and the PCS algorithm (Leclère, Botteron, & Farine, 2013a, 2013b; Van Nee & Coenen, 1991) is in a center of interest for a long time. However, sensitivity was primarily limited by the presence of navigation message bits, which were not known a priori. Nevertheless, some algorithms like Half-bit, Full-bit, or Circular Correlation with Multiple Data Bits (CCMDB) and mDBZP (Modified Double Block Zero-Padding) algorithms were proposed (Ziedan, 2006). These methods were effective for the basic signals like GPS L1 C/A. However, novel tiered signals offer more possible advantages, such as better sensitivity, and challenges, like SC synchronization/acquisition.

2.1 Tiered signal acquisition approaches

The current tiered signal acquisition approaches could be divided into two groups (Leclère et al., 2017).

The first, and still most common approach, uses an acquisition of the primary code phase that ignores the SC bit sign. The problem is, thus, a two-dimensional search in primary code phase τ and Doppler frequency shift fd. Possible methods are a sequential search with non-coherent integration (Mongrédien et al., 2006) or the PCS using the Double Block Zero-Padding (DBZP) with non-coherent integration (Leclère et al., 2013b, 2013b; Leclère, Botteron, & Farine, 2014). These methods do not increase PIT. Therefore, acquisition complexity does not increase due to a search in the SC phase and search in many Doppler shift bins. However, it does not enable an extension of the PIT in the sense of a weak signal acquisition using the SC of the tiered signal. The sensitivity could be improved by using non-coherent combining only. However, its usefulness is limited by non-coherent loss (Strässle, Megnet, Mathis, & Bürgi, 2007; Ziedan, 2006).

The second approach extends PIT and therefore must take SC into account. The search in the third dimension of SC is performed in a sequential (Borio, 2011; Corazza et al., 2007) or in a parallel way (Tawk et al., 2011). A specific type of SC search is out of this paper’s scope. However, the most crucial concurrent search in the dimension of the primary code phase is always realized sequentially (Borio, 2011; Corazza et al., 2007; Tawk et al., 2011). This simultaneous search in both primary and SC phase dimensions is time-consuming. It is primarily due to quadratic algorithmic complexity of the sequential search in the primary code phase dimension.

In sequential search, the SC bit hypothesis can be applied per each correlated primary code period. In contrast, the PCS SBZP-based algorithm is in conflict with the presence of SC bit transition. The unknown position of SC bit transition within the processed block of the signal does not allow us to apply the SC bit transition hypothesis (Svatoň & Vejražka, 2018). The cyclic correlation in PCS is sensitive to any violation of signal periodicity, which causes a degradation of resulting CAF (Leclère et al., 2013b, 2013b; Presti et al., 2009; Yang, 2001) by parasitic fragments. The CAF degradation is analyzed in Presti et al. (2009) by description using rectangular functions. The CAF corrupts most when the transition of SC bit occurs in the middle of the integration interval. Consequently, the resulting CAF in the Doppler shift domain is divided into two side lobes, and zero value appears at the correct Doppler shift (Presti et al., 2009).

The DBZP-based algorithms are not used due to their insensitivity to SC bit transition presented above and its double-sized length of the required FFT. Therefore, the motivation is to design an appropriate PCS-based algorithm that will be able to apply information about SC bit sign to extend the PIT.

2.2 The problem of long primary code period and limited FFT length

Another problem with an acquisition algorithm based on PCS, which must be solved, is the limited length of available FFT (NFFT). The straightforward processing of the tiered signal period over the whole SC period with a single very long FFT is unrealizable. Therefore, the processing over individual primary code periods only is possible and presumed. However, even the length of modern primary codes could be too long for the straightforward processing of its entire period with a sufficient resolution in single FFT. For instance, their primary code is usually longer than the previously used 1 023 chips. The range is from 2 046 chips of BeiDou B1 signals and 4 092 chips in the case of Galileo E1 signals to 10 230 chips (e.g., GPS L1C, Galileo E5a,b, or GPS L5 and others). A multi-constellation receiver thus requires considerable scalability of its PCS units.

In practical circumstances, available NFFT means a length from 1K (1 024) to 4K (4 096). Such small FFT-PCS-based acquisition units are still the most commonly used (Ahamed, Laveti, Goswami, & Rao, 2016; Fortin et al., 2015; Leibovich, Díaz, García, & Roncagliolo, 2015; Romero-Aguirre, Parra-Michel, Longoria-Gandara, & Aguirre-Hernandez, 2010; Sharma & Chakradhar Naidu, 2018) because of low cost and low power consumption. Although much bigger FFT lengths up to 64 K (65 536) (Garrido, Acevedo, Ehliar, & Gustafsson, 2014; LogiCORE IP Fast Fourier Transform v7.1, 2011), or different mixed Radix algorithms are generally implementable in HW platforms like FPGA (Field Programmable Gate Array) and Systems on the Chip (SoC), they are not practical.

The realization of large FFT wastes HW resources in the case of acquisition of simple signals. Such a straightforward approach can also require a massive amount of padded zeroes (Leclère, Botteron, Landry, & Farine, 2015) for some code lengths. It also does not solve the SC bit transition problem common to all PCS SBZP algorithms. Therefore, an objective argument for scaling the problem to small FFT lengths exists.

Various approaches for long GNSS codes exist. They use the Average Correlation (Starzyk & Zhu, 2001), other averaging, and overlapping methods (Pang & Starzyk, 2003; Pang et al., 2003; Yang, 2001), or various combining and decomposition approaches (Leclère et al., 2012, 2015; Zeng, Qiu, Zhang, Zhu, & Pei, 2018) processing the partial primary code period. The Partial Correlation Method (PCM) uses the property of the primary code that even a short section of the code has good correlation properties (Pang & Starzyk, 2003). However, none of the above methods has enough straightforward scalability to different signals, and they do not take into account the presence of the tiered signal SC component.

A PCM approach that was a little different was presented in Fortin et al. (2015) and inspired by Lin and Tsui (2003). The approach used decomposition of the Galileo E1 signals period and its replica to M single zero-padded blocks. Therefore, it is called the “M-method” in this paper. Then, each block was processed independently by the PCS SBZP algorithm-based acquisition unit using 2 K (2 048) length FFT blocks. Finally, the partial correlation sub-results of each of the M blocks were combined non-coherently. Therefore, an extension of PIT to improve sensitivity was not considered in Fortin et al. (2015).

The advantage of this method is its scalability and easy adaptability to different code lengths and to platforms of different performance. The scaling can be performed nearly in run-time. A different subset of the M blocks can be used for computation according to the available FFT length and latency of the target platform. Its results could be used for comparisons with improvements proposed in the following section.

Other approaches using DBZP and PCM exist, such as the base modified DBZP (mDBZP) method (Ziedan, 2006; Ziedan & Garrison, 2004) and its variants. All mDBZP methods are based on a similar division of received signal to partial correlation blocks. However, these blocks are much shorter, in comparison with the M-method presented above. Then, the blocks are partially correlated using the original DBZP with circular shift of replica spectra. This contrasts with the SBZP used and the circular shift of the original replica in the M-method. Modified DBZP works as a search in the Doppler shift domain. The proper correlation results have to be searched for overall permutations of partial blocks. The original methods were designed for the GPS L1 C/A signal (Ziedan, 2006; Ziedan & Garrison, 2004) and were also applied to Galileo E1 signals (DBZP-Transition Insensitive) (Foucras, Julien, Macabiau, & Ekambi, 2012) later.

The modified DBZP-based methods are presented as effective. However, the major disadvantages are high memory demands and limited resolution in the Doppler shift search. The resolution depends on the length of the partial correlation block. A short length of the block leads to a fine resolution in the Doppler shift; however, it increases the number of permutations, which is undesirable. The mDBZP methods are bit transition insensitive. The way a SC bit transition hypothesis is applied is not obvious in Foucras et al. (2012). The PIT achieved is equal to one primary code period (4 ms). For these drawbacks, these methods are not considered further.

3 Partial correlation method (“M-method”) generalization and analysis

The partial correlation blocks are formed by the division of signal r[t] and replica c[t] of the length of the primary code period T per the number of samples nearest to NFFT to M blocks. After that, each of these M blocks is single block zero-padded (SBZP) to NFFT length when necessary. Each of these blocks is then after that correlated with the corresponding block of the replica. Finally, all M partial correlation sub-results are summed coherently or non-coherently to form a single search. It is depicted in Figure 1 in the time domain. The “cor” means the correlation by the PCS algorithm. The PCM could be generalized for any number of M blocks.

Principle of Partial Correlation Method (PCM)
FIGURE 1

Principle of Partial Correlation Method (PCM)

The code phase could be out of the corresponding M fractional replica window shift. Therefore, it is necessary to do M searches with a replica shifted in each search per one block from the previous search (Fortin et al., 2015). The searches are numbered by parameter s in the range 0.M-1. The circular replica shift in the search s is s.[T/M].

In those M searches, peaks are observed like in SBZP as Head, Partial, or Tail matching with corresponding losses of amplitude (Mollaiyan et al., 2013; Yang, 2001). These potential peak detections occur in two separate neighboring searches, modulo M. The peak spacing is equal to the number of padded zeroes NZ. It is depicted in Figure 2, where the results of each search are depicted for code phases over period T and for the case M = 4.

Results of PCM for examples a) to d) of different τ over a T. Meaning of the search s over range 0 … M-1, for M = 4
FIGURE 2

Results of PCM for examples a) to d) of different τ over a T. Meaning of the search s over range 0 … M-1, for M = 4

The estimated code phase is searched in parallel; however, another search is required over the extra parameter s. The search with the maximal value of the correlation peak is used as a result. The integer part of the code phase is equal to the search number, and its fractional part is equal to the resulting code phase of the search.

For one search s, the resulting CAF of the PCM in Figure 1 could be expressed as the sum of M partial cross-correlation sub-results of two sequences shown in Equation (6), r[t] and c[t], multiplied by the shifted rectangular functions W[m,t] shown in Equation (7). The W-function serves to choose a proper block of r[t] and c[t] in this model. It is expressed as a shifted Heaviside step function shown in Equation (8).

6 6

where

Formula

7 7

8 8

The shape of CAF in the Doppler shift domain computed over an entire primary code period T and without any violation of cyclic correlation is the sinc[πTfd] function and is independent of code phase τ. The PCM CAF differs, as explained below.

Each partial part of the correlation between corresponding blocks of signal r[t] and replica c[t] in the time domain is again modeled by a rectangle function, W’[m,t,τ], shown in Equation (9). The correlated part corresponds to the non-zero value of the function in Figure 3. It will be used for the following analysis of PCM.

9 9

Description of W’-function effect
FIGURE 3

Description of W’-function effect

The sum of W’-functions over M blocks is quasi-periodic. Therefore, its spectrum is discrete and is approximately equal to Equation (10). It is the sum of the Kronecker delta functions on multiples of M/T frequency. The envelope of the spectrum is the spectrum of one W’-function, that is, sinc[πfd[[T/M]-τ]]. An example of overall spectra is depicted in Figure 4 in the range of frequencies of ±M/T [Hz], for four τ:a) τ = 0, b) τ = 1/4, c) τ = 1/2, and d) τ = 3/4 of interval T/M.

10 10

Spectra of the sum of W’-functions for a different τ value on multiples of [M/T] frequency. a) τ = 0, b) τ = 1/4 [T/M], c) τ = 1/2 [T/M], and d) τ = 3/4 [T/M]
FIGURE 4

Spectra of the sum of W’-functions for a different τ value on multiples of [M/T] frequency. a) τ = 0, b) τ = 1/4 [T/M], c) τ = 1/2 [T/M], and d) τ = 3/4 [T/M]

The resulting CAF of PCM in the Doppler shift domain will be a product of the original sinc[πTfd] function and the spectra of the sum of W’-functions, depending on the way of coherent or non-coherent sub-results combining.

3.1 Partial correlation method loss

From Figure 4, it is evident that the peak value of the cross-correlation function is lower than one for a non-zero code phase τ. It is similar to the effect described for a general SBZP (Mollaiyan et al., 2013; Yang, 2001). The overall CAF energy is constant. The cross-correlation peak energy is split into multiple peaks over the Doppler frequency shift axis (Presti et al., 2009); thus, the main correlation peak of PCM is affected by loss. The partial correlation loss (PCM loss) is defined as a relative decrease in the amplitude of a correlation peak. As a consequence, the Peak to Noise Ratio (PNR; Fortin et al., 2015; Molino, Girau, Nicola, Fantino, & Pini, 2008) and carrier-to-noise ratio (C/N0) are reduced accordingly, which is a severe complication for signal detection.

The PCM loss is derived using the W’-function. The energy of the sum of W-functions over m = 1…M is equal to one. However, the energy of the sum of W’-functions used in Equation (10) and in Figure 3 is lower and is proportional to τ. The PCM loss is equal to Equation (11) in dB. The inner sum in Equation (11) is the W’-function mean value over one period T, m = 0…M-1. The PCM loss is independent from the type of sub-result combining.

11 11

The value of PCM loss is limited to 3 dB due to the property of PCM presented in Figure 2, where partial correlation peaks are detected in two neighboring searches with the half amplitude of the peak for the worst case of τ = 1/2 [T/M].

3.2 Analysis of partial correlation with coherent/non-coherent combining

All M sub-results of one partial correlation search could be combined coherently or non-coherently, as is depicted in Figure 5.

Coherent/non-coherent combining in partial correlation
FIGURE 5

Coherent/non-coherent combining in partial correlation

The CAF of the non-coherent combining PCM is expressed by Equation (12) from the original Equation (6) using the square. This PCM combining has the disadvantage of a non-coherent combining loss equal to 10log10(M), due to its coherent time being M-times shorter. An additional loss is caused by the partial correlation loss shown in Equation (11). Consequently, the total loss is equal to their sum shown in Equation (13). The CAF in the Doppler shift domain is affected by the W’-function. It is approximately equal to Equation (14). Its absolute value is depicted in Figure 6 for different code phases and M = 4.

12 12

13 13

14 14

CAF in Doppler shift domain using non-coherent combining of the partial correlation method on multiples of [M/T] frequency. a) τ=0, b) τ=1/4 [T/M], c) τ=1/2 [T/M], and d) τ=3/4 [T/M]
FIGURE 6

CAF in Doppler shift domain using non-coherent combining of the partial correlation method on multiples of [M/T] frequency. a) τ=0, b) τ=1/4 [T/M], c) τ=1/2 [T/M], and d) τ=3/4 [T/M]

The CAF of the coherent combining is not influenced by the non-coherent combining loss. Its total loss is equal just to the loss caused by partial correlation shown in Equation (11). However, the resulting CAF is still a product of the original sinc[πTfd] function and the spectra of the W’-function sum in Figure 4, shown in Equation (10). The CAF in the Doppler shift domain for four exemplary τ code phases is depicted in Figure 7 in absolute value.

Coherent combining results in the Doppler shift domain using the partial correlation method on multiples of [M/T] frequency. a) τ = 0, b) τ = 1/4 [T/M], c) τ = 1/2 [T/M], and d) τ = 3/4 [T/M]
FIGURE 7

Coherent combining results in the Doppler shift domain using the partial correlation method on multiples of [M/T] frequency. a) τ = 0, b) τ = 1/4 [T/M], c) τ = 1/2 [T/M], and d) τ = 3/4 [T/M]

The CAF in Figure 7 contains side lobes on multiples of M/T frequency, whose energy is at the expense of the main-lobe energy. It is a specific disadvantage feature of coherent combining in PCM. Thus, both the side-lobe suppression ratio and detection probability metrics like PNR and First to Second Peak Ratio (FSPR; Fortin et al., 2015; Molino et al., 2008) are decreased. Section 4 is dedicated to the suppression of these effects.

4 Proposed modified single block zero-padding algorithm for PCM

The aim is to suppress effects with an origin in violation of the cyclic property of correlation function caused by PCM processing. The new modified SBZP algorithm for the partial correlation (PCS mSBZP for PCM) is proposed here.

The principal idea is to combine two partial correlations coherently to form one full correlation. The first partial correlation is the result of the original PCM. The second one is a partial correlation of the same signal with the replica circularly shifted by the consecutive partial block [T/M].

The algorithm in Figure 8 coherently combines sub-results from M blocks to form s-th search, and it is after that coherently combined with the results of (s + 1)-th search shown in Equation (15). It requires computing two searches per period T simultaneously. The important condition in Equation (15) is that the result of (s + 1)-th search is shifted (circularly) back by the number of padded zeroes NZ. It is indicated by symbol “D” in Figure 8 and by circshift in Equation (15).

PCS modified SBZP PCM algorithm
FIGURE 8

PCS modified SBZP PCM algorithm

Each of the two searches is again modeled by a separate rectangular W’-function (W’1, W’2). It is illustrated in Figure 9 for an example of code phase equal to 1/2[T/M]. The sum of these functions using Equation (11) is equal to one shown in Equation (16). Therefore, the partial correlation loss is equal to zero. The resulting total loss of all considered methods is summarized in Table 1. The “M1xxx” is the type of non-coherent combining using only one block from a subset of M, which is presented in Fortin et al. (2015). The “Ideal PCS without zero-padding” is used as an ideal theoretical model of the straightforward solution for comparison only. Its real utilization is not possible due to its sensitivity to the SC bit transition problem.

Modified SBZP combining results of two searches s and s+1 of the partial correlation method
FIGURE 9

Modified SBZP combining results of two searches s and s+1 of the partial correlation method

View this table:
TABLE 1

Total loss of different PCM approaches

15 15

16 16

The one full and two partial correlations appear in three neighboring searches from a total M similar to Figure 2. The estimated code phase is searched in parallel; however, this search is done M times.

The algorithmic complexity of the proposed algorithm is derived here. It is measured in multiply-and-add operations (MACs), or (for the PCS algorithm) in the number of FFT butterflies, which corresponds to two MACs. Let the number of samples in one primary code period be T. In general, the sequential search in the primary code phase [6, 4, 5, 2] leads to asymptotic O(T2) complexity.

One PCS operation comprises three (I) FFT operations, conjugation, and a Hadamard product. An N-point FFT has the complexity Nlog2N. Then, PCS-based algorithms have 3Tlog2(T) complexity. The PCS operation is a one PCM sub-result calculation (one block from M, RPC in Equation (6)),

With PCM methods, the T samples are divided into M blocks. An FFT of M/T points has the complexity of (T/M) log2(T/M). The complexity of one PCM sub-result calculation is then 3(T/M) log2(T/M). Consequently, the complexity of one search, consisting of the calculation of M sub-results, is 3Tlog2(T/M). Thus, the algorithmic complexity of searching in the entire primary code space is 3MTlog2(T/M), requiring to carry out the search M-times with a shifted replica (Fortin et al., 2015). Finally, for a proposed final modified SBZP PCM algorithm, the overall algorithmic complexity is 6MTlog2(T/M). The reason for the twofold increase is the proposed combining of two searches together. Asymptotically, this overall algorithmic complexity is still lower than quadratic. The comparison of algorithmic complexity of used methods is in Table 2.

View this table:
TABLE 2

The algorithmic complexity of different PCM approaches

The other parameters are in Table 2. It is the number of PCS operation, the FFT length NFFT, and the required maximal latency (normalized to the sampling period) of each FFT block.

4.1 The SC bit transition removal schema for the PCS mSBZP PCM algorithm

The resulting correlations using conventional PCS per the primary code period are also affected by the SC transition, and their further coherent combining according to the SC bit transition hypothesis to extend PIT does not lead to useful results (Svatoň & Vejražka, 2018).

The effects of the SC bit transition and PCM can be modeled by rectangular functions. Therefore, both could be eliminated in the same way.

The realization is based on the same principle as the proposed mSBZP. Two partial correlations are coherently combined in two searches per block shifted replica to one full correlation. The difference is only in the requirement to specify the sign of the combined block according to the present SC transition hypothesis

The ability to apply the SC bit transition hypothesis is essential. However, a specific way of obtaining it is out of the scope of this paper. The SC bit hypothesis claims that the PIT starts with the sign of n-th bit of SC. Then, the partial SC bit hypothesis claims whether the SC bit sign transition occurs in the m-th block and s-th search of PCM relative to the previous part of PIT.

The SC bit transition effect in the PCS mSBZP PCM algorithm could be eliminated by application of the SC bit transition removal schema. The partial correlation sub-results are coherently combined multiplied by ±1, according to the partial SC bit transition hypothesis SC[m,s,n] in each m-th sub-result and s-th search in n-th bit of SC (17). The algorithm of how to obtain partial SC[m,s,n] hypothesis is the following.

  1. Let’s have a sequence of SC using ±1 with the Nsc length.

  2. Resample the sequence M-times to M. Nsc length.

  3. To obtain the partial SC[m,s,n] hypothesis, choose the bit with index nM+s+m of the resampled sequence.

    17 17

where: Graphic

The schema is illustrated in Figure 10. The three-bits-long SC code is used. Shadowed blocks indicate the bit transition removal according to the above-described hypothesis SC[m,s,n] in the m-th sub-result and s-th search in the n-th bit of SC. The removal is carried out by combining corresponding shadowed PCM sub-results with an inverted sign to form the search.

Handling bit transition by removal schema in mSBZP PCM algorithm
FIGURE 10

Handling bit transition by removal schema in mSBZP PCM algorithm

Rectangular functions are used for an explanation in Figure 10. Arrows indicate the bit transition and corresponding change of the W’-function sign to sum it with proper polarity without a negative consequence to the CAF. In combination with the previously introduced PCS mSBZP for the PCM algorithm, the loss caused by SC bit transition and the partial correlation loss is eliminated, like that shown in Equation (16) using a similar model with two rectangular functions.

The schema in Figure 10 and Equation (17) could be redrawn to block schema in Figure 11. The symbol “D” in the schema indicates a circular shift back by the number of padded zeroes NZ shown in Equation (17). The schema searches SC bits sequentially using the chosen PIT to construct a joint primary and secondary code phase estimator. The simulation results are in the following Section 5, using the most common Galileo E1C signal.

Handling a signal with an SC bit transition hypothesis in PCM using mSBZP algorithm
FIGURE 11

Handling a signal with an SC bit transition hypothesis in PCM using mSBZP algorithm

This knowledge is obtained from a sequential search in SC phase/bits. Another similar choice for SC search is the approach in Borio (2011) and Corazza et al. (2007) using multi-hypothesis secondary code bit transition removal with the evolutionary tree or Walsh-Hadamard transform.

Another important reason for a classical sequential search in SC is its easier application to some tiered signals with the navigation message above the primary and secondary code (e.g., BeiDou B1 signal from IGSO and MEO orbits) in comparison with approaches presented in Tawk et al. (2011) and Borio (2011).

The required width and, therefore, the number of Doppler frequency shift bins depends on the chosen PIT. The width is equal to 1/(2PIT). To keep the number of Doppler frequency bins small enough, the PIT should be extended not over an entire SC length, but over a shorter part of SC sequence. The PIT should not exceed a few tens of milliseconds (Corazza et al., 2007).

The complexity of a search in SC is considered briefly here. Let the number of SC bits be NSC. Then, the complexity of sequential search in the secondary code phase is equal to NSC2 in general. The approaches (Borio, 2011; Corazza et al., 2007) presenting enhanced search in the SC phase have complexity approximately equal to NSClog2(NSC). The same complexity has the approach (Tawk et al., 2011) with a PCS search in the SC phase. The specific type of SC search is out of the scope of this paper.

The proposed PCS mSBZP PCM algorithm offers a parallel search in the primary code phase with 6MTlog2(T/M) complexity, unlike T2 in the sequential case (Borio, 2011; Corazza et al., 2007). Then, the overall complexity of the proposed PCS mSBZP PCM algorithm with the SC bit transition removal schema is 6MTlog2(T/M)NSC2 using the sequential SC search, or 6MTlog2(T/M)NSClog2(NSC), using the enhanced search with the evolutionary tree (Corazza et al., 2007). It is lower than T2NSC2 or T2 NSClog2(NSC) in Borio (2011), Corazza et al. (2007), and Tawk et al. (2011), which use the sequential search.

5 EXPERIMENTAL RESULTS

In this section, the proposed PCS mSBZP algorithm for PCM and its SC bit removal schema for utilization on a tiered signal is evaluated using Matlab simulations. The algorithm performance will be compared and discussed with different types of the possible combining of M partial correlation sub-results, conventional coherent and non-coherent combining (proposed and presented in Fortin et al., 2015).

At first, the PNR, FSPR metrics are used to compare the resulting and derived performance in Section 5.1. Then, the detection probability is investigated using the Monte-Carlo simulation in Section 5.2. At last, the mSBZP for PCM algorithm with bit removal schema is evaluated as a part of a joint primary and secondary code phase estimator for the Galileo E1C signal in Section 5.3.

The compared algorithms are:

  • The non-coherent PCM combining (M4 non-coherent) shown in Equation (12) as “1234″ from Fortin et al. (2015).

  • The non-coherent PCM combining of single sub-result out of M (M1xxx non-coherent). See 2015) method “1XXX” for an example of M = 4.

  • The coherent PCM combining (M4 coherent) shown in Equation (6).

  • The coherent PCS mSBZP algorithm for PCM (M4 mSBZP) shown in Equation (15).

  • The coherent PCS mSBZP for PCM combined with the SC bit transition removal schema (M4 mSBZP bit removal) shown in Equation (17) (Section 4).

Two metrics suitable for detection of the signal have been chosen to compare the algorithms: the Peak-to-Noise floor-Ratio (PNR) shown in Equation (18) and the First-to-Second Peak-Ratio (FSPR) shown in Equation (19) (Fortin et al., 2015; Molino et al., 2008).

18 18

19 19

5.1 The mSBZP PCM algorithm evaluation – PNR and FSPR results

This simulation has been chosen to demonstrate differences in the combining effects by their CAFs, PNR, and FSPR metrics. The results of the above-proposed algorithms are illustrated using three different examples (M = 4, M = 2, and M = 10) by the Matlab simulation here. Each of them is suitable for a real GNSS signal (Galileo E1C, GPS L1C-P). The bandwidth is single-sided; the two-sided is twice as large:

  • M = 4 (M4) (for Galileo E1 signal using the 4 MHz bandwidth),

  • M = 10 (M10) (for future GPS L1C signal using the 4 MHz bandwidth),

  • M = 2 (M2) for Galileo E1 (using the 2 MHz bandwidth for comparison with M4).

Each simulation uses a signal of one primary code period length with phase equal to the worst-case (maximum of the partial correlation loss, equal to 3 dB) τ = (1/2) [T/M] with no bit transition (except SC bit removal schema simulation) and high C/N0 (> 100 dB-Hz). Hence, a single simulation run is sufficient. The Doppler shift range is ±5 kHz.

The input baseband signal with the 4 ms primary code period for Galileo E1C or 10 ms period in case of GPS L1C-P signal is divided into four, two (for M = 4 and M = 2) or ten (for M = 10) 1 ms length blocks of 4 000 samples. After that, each block is zero-padded with 96 zeroes and is PCM-correlated with the corresponding block of replica using any PCM PCS algorithm based on 4 K FFT. This search is performed four, two, or ten times for the replica shifted by one block to each other to search the entire code phase space.

The PIT corresponds to the type of combing. The non-coherent combing has PIT equal to the length of one block (M4 – 1 ms, M2 – 2 ms, M10 – 1 ms); the coherent combing is equal to the sum of lengths of all blocks (M4, M2 – 4 ms, M10 – 10 ms). The resulting PNR and FSPR in dB for different combining algorithms are summarized in Table 3, Table 4, and Table 5. The corresponding CAFs follow.

View this table:
TABLE 3

Method M4 Results in [dB]

View this table:
TABLE 4

Method M2 Results in [dB]

View this table:
TABLE 5

Method M10 Results in [dB]

These results correspond with theoretical presumptions derived in Section 4. In simple non-coherent combining (the first two columns of Table 3 to Table 5), there is no difference between combining all M (e.g., M4 non-coherent) or just one (e.g., M1XXX) from the M sub-results of PCM. There is only a difference in the amplitude of the correlation function peak, but no difference in PNR and FSPR ratios; see Figure 12 and Figure 13 from Matlab simulation. The difference between M4 and M2 is caused only by different coherent integration time (1 ms versus 2 ms). These results match the results presented in Fortin et al. (2015).

M4 non-coherent combining of four partial correlations (M4 non-coherent)
FIGURE 12

M4 non-coherent combining of four partial correlations (M4 non-coherent)

M4 non-coherent using just one partial correlation (M1XXX coherent/non-coherent)
FIGURE 13

M4 non-coherent using just one partial correlation (M1XXX coherent/non-coherent)

The coherent combining of M partial correlations (the third column of Table 3 to Table 5) has the expected gain in PNR against the non-coherent case due to its zero non-coherent combining loss. (The PIT equals to the number of coherently combined blocks, M.) Consequently, PNR of all types of combining is a function of τ by Equation (11) and has a maximal partial correlation loss of 3 dB in the case τ = 1/2 [T/M].

A significant problem of coherent combining in PCM is a dramatic reduction of FSPR, see the third column of Table 3 to Table 5 and Figure 14. It is caused by a violation of the cyclic correlation function. It is described in Figure 7 and in Equation (10) by parasitic side lobes, using the model with W’-function. Hence, it is not usable for a practical use. However, it is well suited for this comparison. It is also probably another reason why coherent combining has not been considered in Fortin et al. (2015).

M4 coherent combining of four partial correlations (M4 coherent)
FIGURE 14

M4 coherent combining of four partial correlations (M4 coherent)

The result using the proposed coherent PCS mSBZP PCM algorithm is presented in the fourth column of Table 3 to Table 4 (mSBZP) and Figure 15. This modification of coherent combining suppresses side lobes in the coherent PCM CAF. Therefore, the FSPR is not reduced. Its PNR has an expected gain against previous non-coherent combining equal to Equation (13) because both the non-coherent combining loss and the partial correlation loss are suppressed. In conclusion, the proposed PCS mSBZP PCM algorithm works. These PNR values in Table 3 to Table 5 are consistent with the analysis in Section 3.1 and the resulting total losses in Table 1.

M4 using mSBZP algorithm (M4 mSBZP for PCM)
FIGURE 15

M4 using mSBZP algorithm (M4 mSBZP for PCM)

The effect of the SC bit transition to mSBZP PCM CAF is illustrated in Figure 16. The SC bit transition occurs in the middle of the [T/M] block. The CAF of the proposed algorithm with the SC bit transition removal schema that is described in Section 4.1 is in Figure 17. The bit transition effect was removed. Hence, the CAF, PNR, and FSPR values are similar to the ideal case without the presence of bit transition. The result is also in the last column of Table 3 to Table 5. Thus, the bit transition removal schema works.

M4 using mSBZP algorithm (M4 mSBZP for PCM) with bit transition in the middle of the block
FIGURE 16

M4 using mSBZP algorithm (M4 mSBZP for PCM) with bit transition in the middle of the block

M4 using mSBZP algorithm (M4 mSBZP) with bit transition in the middle of the block using the SC bit transition removal schema
FIGURE 17

M4 using mSBZP algorithm (M4 mSBZP) with bit transition in the middle of the block using the SC bit transition removal schema

5.2 The mSBZP PCM algorithm detection probability results

The detection probability has been examined by Monte-Carlo simulation. The aim is to demonstrate that the proposed PCS mSBZP PCM algorithm leads to better performance according to signal detection probability.

The Monte-Carlo simulation uses the CFAR (Constant False Alarm Rate) signal detection and a model of Galileo E1C signal with SC (except M4 coherent). Each point on the C/N0 axis is simulated with τ uniformly covering the range of one primary code period and Doppler shift fd in the range ±5 kHz, also uniform. These signals are processed according to the mentioned types of combing algorithms, using M = 4. For each algorithm, there are up to 1,500 simulation runs.

The coherent time has been chosen to 100 ms for simulation only because it is equal to Galileo E1C secondary code length. However, practical utilization requires considerably shorter times up to 20 ms.

The non-coherent combining is insensitive to the SC bit transition. Therefore, its results are suitable for comparison as an example of a low sensitivity acquisition approach (Fortin et al., 2015). The ordinary coherent combining (M4 coherent) is used for comparison too. However, it uses a signal without SC in this simulation. It is for a comparison purpose only, because the M4 coherent is bit transition sensitive and could not work in practice with SC present. No SC bit removal schema can be used with it. It is used for a demonstration of M4 coherent PCM loss in comparison with the proposed no-loss mSBZP PCM algorithm only.

The detection probability statistics, depending on the carrier-to-noise ratio (C/N0 [dB-Hz]) of signal for different types of combining, are in Figure 18. The proposed modified method mSBZP outperforms others. Its processing gain is up to 9 dB in comparison with the previous M4 non-coherent (Fortin et al., 2015). It is due to the proposed reduction of the non-coherent combining loss, PCM loss, and presented better results of PNR and FSPR, unlike the previous PCM methods from Fortin et al. (2015). These results are also consistent with Table 1.

PCM for M = 4 using different types of combining – detection probability statistics, for 100 ms coherent time
FIGURE 18

PCM for M = 4 using different types of combining – detection probability statistics, for 100 ms coherent time

5.3 The joint primary and secondary code phase PCS mSBZP PCM-based estimator evaluation

The proposed PCS mSBZP PCM algorithm with the SC bit removal schema and any search in the SC bit phase is introduced in Figure 11 of Section 4.1, and its behavior is analyzed here.

The sequential acquisition/synchronization of SC is chosen here, unlike to Borio (2011) and Corazza et al. (2007) for simplification. Results of application of this processing on Galileo E1C signal using CS251 secondary code and mSBZP with M = 4 are presented by the same Monte-Carlo detection probability statistic, but using different longer coherent time (PIT) in Figure 19.

M4 using mSBZP algorithm for PCM – detection statistics for a different coherent time using Galileo E1C signal with CS251 secondary code
FIGURE 19

M4 using mSBZP algorithm for PCM – detection statistics for a different coherent time using Galileo E1C signal with CS251 secondary code

The PNR and FSPR metrics over an entire 25 bit long SC period are in Figure 20 and Figure 21. The testing E1C signal with SC (except M4 coherent), zero fd, τ = 0…NT and high C/N0 (> 100 dB-Hz) is used for this single run simulation. The right sides of both figures are details of algorithm behavior in the first two SC bits. These metrics are presented together with the ordinary coherent PCM combining to demonstrate its SC bit transition sensitivity.

Modified SBZP algorithm with bit transition removal schema used for CS251 secondary code synchronization – PNR metric
FIGURE 20

Modified SBZP algorithm with bit transition removal schema used for CS251 secondary code synchronization – PNR metric

Modified SBZP algorithm with bit transition removal schema used for CS251 secondary code synchronization – FSPR metric
FIGURE 21

Modified SBZP algorithm with bit transition removal schema used for CS251 secondary code synchronization – FSPR metric

The PNR and FSPR metrics of the PCS mSBZP PCM algorithm with the SC bit transition removal schema have a maximum in the interval of one proper SC bit, which is similar to the SC autocorrelation function in Figure 22. Both metrics are almost constant; they are not a function of the primary code phase in this proper SC bit interval. It is beneficial because, while the proper SC bit is searched for sequentially, the code phase of primary code is searched concurrently in a parallel way, and the peak amplitude is dependent only on SC, not on τ. The value does not rely on position of SC bit transition (bit edge), which is a priori not known. The results confirm algorithm usability as a joint primary (parallel in code search) and secondary (sequential search) code phase acquisition estimator.

Auto-correlation function of CS251 secondary code for linear (left) and cyclic case (right)
FIGURE 22

Auto-correlation function of CS251 secondary code for linear (left) and cyclic case (right)

6 SUMMARY AND CONCLUSION

The presented text addresses acquisition of GNSS tiered signals using the Parallel Code Search (PCS) algorithm and coherent processing of the secondary code (SC) component to achieve high acquisition sensitivity. Two fundamental problems are discussed here. First, the acquisition of modern GNSS signals with limited length of available FFT for a PCS algorithm by partial correlation method (PCM). Second, the PCS algorithm sensitivity to PCM processing, SC bit transition, and its utilization for PIT extension over SC bits.

The chosen approach uses a previously presented PCS algorithm with the Single Block Zero-Padding (SBZP) and processing of primary code period in blocks using the PCM (Fortin et al., 2015). The algorithm is constructed as follows:

  • The specifics of the PCM processing are considered as cyclic correlation effects on the resulting Cross-Ambiguity-Function (CAF), and two sources of loss are identified and derived: the non-coherent combining loss and the PCM loss.

  • These losses are then eliminated, unlike the original approach (Fortin et al., 2015). The non-coherent combining loss is eliminated using coherent combining. Then, the PCM loss is eliminated using the coherent combining of CAF for two consecutive circular shifts of replica.

  • Consequently, the result of this modified SBZP PCM (mSBZP PCM) PCS-based algorithm is not dependent on the a priori unknown position of SC bit transition edge. The knowledge about its presence suffices.

Such a processing allows us to extend coherent pre-detection time (PIT) by the application of the proposed SC bit removal schema to the PCS algorithm. In combination with a sequential SC search, the proposed algorithm can work as a joint primary and secondary code phase acquisition estimator for acquisition in extremely weak signal conditions.

In conclusion, the algorithm has the following characteristics:

  • The algorithm allows processing of GNSS signals with a long period code by PCS algorithm with a shorter FFT length using partial correlation. The algorithm eliminates losses and can process the bit transition.

  • The algorithm leads to considerable acceleration of search in the primary code phase, because it allows using the PCS. It differs from relevant approaches in Borio (2011) and Corazza et al. (2007), and Tawk et al. (2011) that also apply SC, but uses sequential search only. Thus, asymptotic complexity of the primary code search can be decreased from N2 to Nlog2N.

  • The algorithm has no non-coherent and PCM loss. It can obtain up to a 9 dB gain in comparison with the previous non-coherent PCM approach (using the same M = 4 and correlation time) (Fortin et al., 2015) for the Galileo E1C signal.

HOW TO CITE THIS ARTICLE

Svatoň J, Vejražka F, Kubalík P, Schmidt J, Borecký J. Novel partial correlation method algorithm for acquisition of GNSS tiered signals. NAVIGATION. 2020;67:745–762. https://doi.org/10.1002/navi.390

ACKNOWLEDGMENT

The submitted paper has arisen during the work on a project, which has been financially supported by the Technology Agency of the Czech Republic under grant No. TE01020186. This work was also supported by the Student Grant Agency of the Czech Technical University in Prague, grant No. SGS20/129/OHK3/2T/13.

Footnotes

  • Funding information

    Technology Agency of the Czech Republic, Grant/Award Number: TE01020186; Czech Technical University in Prague, Grant/Award Number: SGS20/129/OHK3/2T/13

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

REFERENCES

  1. ↵
    Abu-Rgheff, M. A. (2007). Introduction to CDMA wireless communications. Cambridge, MA: Academic Press.
    Google Scholar
  2. ↵
    Ahamed, S. F., Laveti, G., Goswami, R., & Rao, G. S. (2016, February). Fast acquisition of GPS signal using Radix-2 and Radix-4 FFT algorithms. Proceedings of the 2016 IEEE 6th International Conference on Advanced Computing (IACC), Bhimavaram, India, 674–678. https://doi.org/10.1109/IACC.2016.130
    Google Scholar
  3. ↵
    Borio, D. (2011). M-sequence and secondary code constraints for GNSS signal acquisition. IEEE Transactions on Aerospace and Electronic Systems, 47(2), 928–945. https://doi.org/10.1109/TAES.2011.5751235
    Google Scholar
  4. ↵
    Corazza, G. E., Palestini, C., Pedone, R., & Villanti, M. (2007, September). Galileo primary code acquisition based on multi-hypothesis secondary code ambiguity elimination. Proceedings of the 20th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2007), Fort Worth, TX, 2459–2465.
    Google Scholar
  5. ↵
    Fortin, M.-A., Bourdeau, F., & Landry, R. Jr. (2015). Implementation strategies for a software-compensated FFT-based generic acquisition architecture with minimal FPGA resources. NAVIGATION, 62(3), 171–188. https://doi.org/10.1002/navi.110
    Google Scholar
  6. ↵
    Foucras, M., Julien, O., Macabiau, C., & Ekambi, B. (2012, September). A novel computationally efficient Galileo E1 OS acquisition method for GNSS software receiver. Proceedings of the 25th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2012), Nashville, TN, 365–383. https://doi.org/10.13140/RG.2.1.1329.2640
    Google Scholar
  7. ↵
    Garrido, M., Acevedo, M., Ehliar, A., & Gustafsson, O. (2014, December). Challenging the limits of FFT performance on FPGAs. Proceedings of the 2014 International Symposium on Integrated Circuits (ISIC), Downtown Core, Singapore, 172–175. https://doi.org/10.1109/ISICIR.2014.7029571
    Google Scholar
  8. ↵
    Kaplan, E., & Hegarty, C. (2006). Understanding GPS: Principles and applications (2nd ed.) (pp. 67-489). Norwood, MA: Artech House.
    Google Scholar
  9. ↵
    Leclère, J., Botteron, C., & Farine, P.-A. (2012, September). Improving the performance of the FFT-based parallel code-phase search acquisition of GNSS signals by decomposition of the circular correlation. Proceedings of the 25th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2012), Nashville, TN, 1406–1416.
    Google Scholar
  10. ↵
    Leclère, J., Botteron, C., & Farine, P. A. (2013a). Comparison framework of FPGA-based GNSS signals acquisition architectures. IEEE Transactions on Aerospace and Electronic Systems, 49(3), 1497–1518. https://doi.org/10.1109/TAES.2013.6558001
    Google Scholar
  11. ↵
    Leclère, J., Botteron, C., & Farine, P. A. (2013b, June). Modified parallel code-phase search for acquisition in presence of sign transition. Proceedings of the International Conference on Localization and GNSS (ICL-GNSS), Turin, Italy, 1–6. https://doi.org/10.1109/ICL-GNSS.2013.6577261
    Google Scholar
  12. ↵
    Leclère, J., Botteron, C., & Farine, P. A. (2014). Acquisition of modern GNSS signals using a modified parallel code-phase search architecture. Signal Processing, 95, 177–191. https://doi.org/10.1016/j.sigpro.2013.08.004
    Google Scholar
  13. ↵
    Leclère, J., Botteron, C., & Farine, P. A. (2017). High sensitivity acquisition of GNSS signals with secondary code on FPGAs. IEEE Aerospace and Electronic Systems Magazine, 32(8), 46–63. https://doi.org/10.1109/MAES.2017.160176
    Google Scholar
  14. ↵
    Leclère, J., Botteron, C., Landry, R. Jr, & Farine, P. A. (2015). FFT splitting for improved FPGA-based acquisition of GNSS signals. International Journal of Navigation and Observation. https://doi.org/10.1155/2015/765898
    Google Scholar
  15. ↵
    Leibovich, P. E., Díaz, J. G., García, J. G., & Roncagliolo, P. A. (2015, February). Dedicated hardware for FFT based fast acquisition of GNSS signals. Proceedings of the 2015 IEEE 6th Latin American Symposium on Circuits & Systems (LASCAS), Montevideo, Uruguay, 1–4. https://doi.org/10.1109/LASCAS.2015.7250424
    Google Scholar
  16. ↵
    Lin, D. M., & Tsui, J. B. Y. (2003). US Patent No. 6,567,042. Washington, DC: US Patent and Trademark Office.
    Google Scholar
  17. ↵
    Molino, A., Girau, G., Nicola, M., Fantino, M., & Pini, M. (2008, August). Evaluation of a FFT-based acquisition in real time hardware and software GNSS receivers. Proceedings of the 2008 IEEE 10th International Symposium on Spread Spectrum Techniques and Applications, Bologna, Italy, 37–41. https://doi.org/10.1109/ISSSTA.2008.13
    Google Scholar
  18. ↵
    Mollaiyan, K., Santerre, R., & Landry, R., Jr. (2013). Acquisition of weak signals in multi-constellation frequency domain receivers. Positioning, 4(2), 144–152. https://doi.org/10.4236/pos.2013.42014
    Google Scholar
  19. ↵
    Mongrédien, C., Lachapelle, G., & Cannon, M. E. (2006, September). Testing GPS L5 acquisition and tracking algorithms using a hardware simulator. Proceedings of the 19th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2006), Fort Worth, TX, 2901–2913.
    Google Scholar
  20. ↵
    Pang, J., & Starzyk, J. (2003). Fast direct GPS signal acquisition using FPGA. Athens, OH: Ohio University.
    Google Scholar
  21. Pang, J., Van Graas, F., Starzyk, J., & Zhu, Z. (2003). Fast direct GPS P-code acquisition. GPS Solutions, 7(3), 168–175. https://doi.org/10.1007/s10291-003-0070-6
    Google Scholar
  22. ↵
    Presti, L. L., Zhu, X., Fantino, M., & Mulassano, P. (2009). GNSS signal acquisition in the presence of sign transition. IEEE Journal of Selected Topics in Signal Processing, 3(4), 557–570. https://doi.org/10.1109/JSTSP.2009.2024592
    Google Scholar
  23. ↵
    Romero-Aguirre, E., Parra-Michel, R., Longoria-Gandara, O., & Aguirre-Hernandez, M. (2010, December). A hardware-efficient frequency domain correlator architecture for acquisition stage in GPS. Proceedings of the International Conference on Reconfigurable Computing and FPGAs, Quintana Roo, Mexico, 412-417. https://doi.org/10.1109/ReConFig.2010.47
    Google Scholar
  24. ↵
    Sharma, J. V., & Chakradhar Naidu, S. (2018). FPGA implementation of averaging correlation for C/A code acquisition of GPS signal in software receivers. International Journal of Current Engineering and Scientific Research, 5(4), 328–333. Retrieved from http://troindia.in/journal/ijcesr/vol5iss4/328-333.pdf
    Google Scholar
  25. ↵
    Starzyk, J. A., & Zhu, Z. (2001, August). Averaging correlation for C/A code acquisition and tracking in frequency domain. Proceedings of the 44th IEEE Midwest Symposium on Circuits and Systems, Dayton, OH, 905–908. https://doi.org/10.1109/MWSCAS.2001.986334
    Google Scholar
  26. ↵
    Strässle, C., Megnet, D., Mathis, H., & Bürgi, C. (2007, September). The squaring-loss paradox. Proceedings of the 20th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2007), Fort Worth, TX, 2715-2722.
    Google Scholar
  27. ↵
    Svatoň, J., & Vejražka, F. (2018, April). Pre-and post-correlation method for acquisition of new GNSS signals with secondary code. Proceedings of the Position, Location and Navigation Symposium (PLANS), Monterey, CA, 1422–1427. https://doi.org/10.1109/PLANS.2018.8373535
    Google Scholar
  28. ↵
    Tawk, Y., Jovanovic, A., Leclere, J., Botteron, C., & Farine, P. A. (2011, September). A new FFT-based algorithm for secondary code acquisition for Galileo signals. Proceedings of the Vehicular Technology Conference (VTC Fall), San Francisco, CA, 1–6. https://doi.org/10.1109/VETECF.2011.6093107
    Google Scholar
  29. ↵
    Van Nee, D. J. R., & Coenen, A. J. R. M. (1991). New fast GPS code-acquisition technique using FFT. Electronics Letters, 27, 158–160. https://doi.org/10.1049/el:19910102
    Google Scholar
  30. Xilinx. (2011). LogiCORE IP fast Fourier transform v7.1. Product specification DS260.
    Google Scholar
  31. ↵
    Yang, C. (2001, September). FFT acquisition of periodic, aperiodic, puncture, and overlaid code sequences in GPS. Proceedings of the 14th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 2001), Salt Lake City, UT, 137–147.
    Google Scholar
  32. ↵
    Zeng, Q., Qiu, W., Zhang, P., Zhu, X., & Pei, L. (2018). A Fast acquisition algorithm based on division of GNSS signals. The Journal of Navigation, 71(4), 933–954. https://doi.org/10.1017/S0373463317000984
    Google Scholar
  33. ↵
    Ziedan, N. I. (2006). GNSS receivers for weak signals. Norwood, MA: Artech House.
    Google Scholar
  34. ↵
    Ziedan, N. I., & Garrison, J. L. (2004, April). Unaided acquisition of weak GPS signals using circular correlation or double-block zero padding. Proceedings of the PLANS 2004: Position Location and Navigation Symposium (IEEE Cat. No.04CH37556), Monterey, CA, 461–470. https://doi.org/10.1109/PLANS.2004.1309030
    Google Scholar
Loading
Loading
Loading
Loading
Back to top
In this Issue
NAVIGATION: Journal of the Institute of Navigation
NAVIGATION: Journal of the Institute of Navigation

Vol. 67, Issue 4

Winter 2020

Table of Contents Index by author
Jump to section

Keywords

Parallel code search, Partial correlation, Single block zero-padding, Secondary code