Acquisition

The role of an Acquisition block is the detection of presence/absence of signals coming from a given GNSS satellite. In case of a positive detection, it should provide coarse estimations of the code phase and the Doppler shift , yet accurate enough to initialize the delay and phase tracking loops.

By exploiting the concepts and methodology of estimation theory, it is possible to show that the maximum likelihood (ML) estimates of and can be obtained by maximizing the function

where

is a complex vector containing I&Q samples of the received signal, is the sampling period, is the code phase of the received signal with respect to a local reference, is the Doppler shift, is the number of samples in a spreading code (4 ms for Galileo E1, 1 ms for GPS L1), and is a locally generated reference. The maximization in the equation above requires a two-dimensional search in a function which output results from a multiplication-and-sum of complex samples, becoming the computational bottleneck of the whole process. A usual method to alleviate this issue is to resort to the FFT-based circular convolution, which exchanges the expensive multiplication-and-sum operation by a discrete Fourier transform, a vector product and an inverse transform, taking advantage of the efficient implementations available for such operations1.

The magnitude of , also known as cross-ambiguity function, is also used to decide whether the satellite corresponding to the local replica is in view or it is not. Resorting to signal detection theory, it is possible to define tests statistics with desirable properties. A criterion commonly used for a detection problem is the maximization of the detection probability () subject to a given false alarm probability (). It is well-known in the literature that the optimum solution to that problem can be found by applying the Neyman-Pearson (NP) approach, which requires perfect knowledge of the signal parameters and constitutes the uniformly most powerful test. Assuming additive white Gaussian noise and replacing the true synchronization parameters by their ML estimators in the NP detector, one obtains the Generalized Likelihood Ratio Test (GLRT) function, that can be written as:

where is an estimation of the input signal power. It can be shown that this acquisition test statistic is a Constant False Alarm Rate (CFAR) detector because does not depend on the noise power.

CAF

GLRT statistic for Parallel Code Phase Search acquisition algoritm for a configuration of Msps, a frequency span of kHz with steps of Hz, and using the E1B sinBOC local replica for Galileo’s IOV satellite PRN 112.

GPS L1 C/A signal acquisition

Implementation: GPS_L1_CA_PCPS_Acquisition

The Parallel Code Phase Search (PCPS) algorithm is described as follows:

  • Require: Input signal buffer of complex samples, provided by the Signal Conditioner; on-memory FFT of the local replica, ; acquisition threshold ; freq. span ; freq. step .
  • Ensure: Decision positive or negative signal acquisition. In case of positive detection, it provides coarse estimations of code phase and Doppler shift to the Tracking block.
  1. Compute input signal power estimation: .

  2. for to in steps:
    • Carrier wipe-off: , for .
    • Compute .
    • Compute , for .
    • Compute .
  3. end for

  4. Search maximum and its indices in the search grid:

  5. Compute the GLRT function with normalized variance:

  6. if
    • Declare positive acquisition and provide and .
  7. else
    • Declare negative acquisition.
  8. endif

The computation of the Fast Fourier Transform and its inverse (second and fourth steps inside the for loop) are performed by means of GNU Radio wrappers of the FFTW library, an efficient implementation for computing the discrete Fourier transform, whereas the products (first and third steps in the for loop) are implemented with the Vector-Optimized Library of Kernels (VOLK), which generates processor-specific Single-Input Multiple-Data (SIMD) assembly instructions that take advantage of parallel computing techniques and allow writing efficient and portable code.

This implementation accepts the following parameters:

Global Parameter Description Required
GNSS-SDR.internal_fs_hz Input sample rate to the processing channels, in samples per second. Mandatory
Parameter Description Required
implementation GPS_L1_CA_PCPS_Acquisition Mandatory
item_type [gr_complex, cshort, cbyte]: Set the sample data type expected at the block input. It defaults to gr_complex. Optional
if Intermediate frequency of the incoming signal, in Hz. It defaults to (i.e., complex baseband signal). Optional
doppler_max Maximum Doppler value in the search grid, in Hz. It defaults to 5000 Hz. Optional
doppler_step Frequency step in the search grid, in Hz. It defaults to 500 Hz. Optional
threshold Decision threshold from which a signal will be considered present. It defaults to (i.e., all signals are declared present), Optional
pfa If defined, it supersedes the threshold value and computes a new threshold based on the Probability of False Alarm. It defaults to (i.e., not set). Optional
use_CFAR_algorithm [true, false]: If set to true, applies a normalization to the computed peak value on the search grid. It defaults to true. Optional
coherent_integration_time_ms Set the integration time , in ms. It defaults to 1 ms. Optional
bit_transition_flag [true, false]: If set to true, it takes into account the possible presence of a bit transition, so the effective integration time is doubled. When set, it invalidates the value of max_dwells. It defaults to false. Optional
max_dwells Set the maximum number of dwells to declare a signal present. It defaults to 1. Optional
repeat_satellite [true, false]: If set to true, the block will search again for the same satellite once its presence has been discarded. Useful for testing. It defaults to false. Optional
blocking [true, false]: If set to false, the acquisition workload is executed in a separate thread, outside the GNU Radio scheduler that manages the flow graph, and the block skips over samples that arrive while the processing thread is busy. This is specially useful in real-time operation using radio frequency front-ends, overcoming the processing bottleneck for medium and high sampling rates. However, this breaks the determinism provided by the GNU Radio scheduler, and different processing results can be obtained in different machines. Do not use this option for file processing. ONLY AVAILABLE IN THE next BRANCH. It defaults to true. Optional
dump [true, false]: If set to true, it enables the Acquisition internal binary data file logging. It defaults to false. Optional
dump_filename If dump is set to true, name of the file in which internal data will be stored. It defaults to ./acquisition.dat Optional

Acquisition implementation: GPS_L1_CA_PCPS_Acquisition.

Example:

;######### ACQUISITION GLOBAL CONFIG ############
Acquisition_1C.implementation=GPS_L1_CA_PCPS_Acquisition
Acquisition_1C.doppler_max=8000
Acquisition_1C.doppler_step=250
Acquisition_1C.pfa=0.0001

Implementation: GPS_L1_CA_PCPS_Fine_Doppler_Acquisition

This implementation accepts the following parameters:

Global Parameter Description Required
GNSS-SDR.internal_fs_hz Input sample rate to the processing channels, in samples per second. Mandatory
Parameter Description Required
implementation GPS_L1_CA_PCPS_Fine_Doppler_Acquisition Mandatory
item_type [gr_complex]: Set the sample data type expected at the block input. Only gr_complex is defined in this version. It defaults to gr_complex. Optional
if Intermediate frequency of the incoming signal, in Hz. It defaults to (i.e., complex baseband signal). Optional
doppler_max Maximum Doppler value in the search grid, in Hz. It defaults to Hz. Optional
doppler_min Minimum Doppler value in the search grid, in Hz. It defaults to Hz. Optional
doppler_step Frequency step in the search grid, in Hz. It defaults to 500 Hz. Optional
threshold Decision threshold from which a signal will be considered present. It defaults to (i.e., all signals are declared present), Optional
coherent_integration_time_ms Set the integration time , in ms. It defaults to 1 ms. Optional
max_dwells Set the maximum number of dwells to declare a signal present. It defaults to 1. Optional
repeat_satellite [true, false]: If set to true, the block will search again for the same satellite once its presence has been discarded. Useful for testing. It defaults to false. Optional
dump [true, false]: If set to true, it enables the Acquisition internal binary data file logging. It defaults to false. Optional
dump_filename If dump is set to true, name of the file in which internal data will be stored. It defaults to ./acquisition.dat Optional

Acquisition implementation: GPS_L1_CA_PCPS_Fine_Doppler_Acquisition.

Example:

Acquisition_1C.implementation=GPS_L1_CA_PCPS_Acquisition_Fine_Doppler
Acquisition_1C.threshold=0.007
Acquisition_1C.doppler_max=10000
Acquisition_1C.doppler_min=-10000
Acquisition_1C.doppler_step=500
Acquisition_1C.max_dwells=10

Implementation: GPS_L1_CA_PCPS_Tong_Acquisition

On top of the PCPS Algorithm (or any other providing the same outputs), we could integrate results from more than one consecutive code periods in order to enhance the acquisition sensitivity, understood as the minimum signal power at which a receiver can correctly identify the presence of a particular satellite signal in the incoming RF signal within a given time-out interval.

This is the case of the Tong detector3, a sequential variable dwell time detector with a reasonable computation burden and proves good for acquiring signals with low levels. During the signal search, the up/down counter is incremented by one if the correlation peak value exceeds the threshold, otherwise it is decremented by one. If the counter has reached maximum count value , the signal is declared ‘present’ and the search is terminated. Similarly if the counter contents reach zero, the signal is declared ‘absent’ and the search is terminated. So that the Tong detector is not trapped into an extended dwell in the same cell, under certain poor signal conditions, another counter () sets the limit on maximum number of dwells.

This implementation accepts the following parameters:

Global Parameter Description Required
GNSS-SDR.internal_fs_hz Input sample rate to the processing channels, in samples per second. Mandatory
Parameter Description Required
implementation GPS_L1_CA_Tong_PCPS_Acquisition Mandatory
item_type [gr_complex]: Set the sample data type expected at the block input. It defaults to gr_complex. Optional
if Intermediate frequency of the incoming signal, in Hz. It defaults to (i.e., complex baseband signal). Optional
doppler_max Maximum Doppler value in the search grid, in Hz. It defaults to 5000 Hz. Optional
doppler_step Frequency step in the search grid, in Hz. It defaults to 500 Hz. Optional
threshold Decision threshold from which a signal will be considered present. It defaults to (i.e., all signals are declared present), Optional
pfa If defined, it supersedes the threshold value and computes a new threshold based on the Probability of False Alarm. It defaults to (i.e., not set). Optional
coherent_integration_time_ms Set the integration time , in ms. It defaults to 1 ms. Optional
tong_init_val Initial value of the Tong counter . It defaults to 1. Optional
tong_max_val Count value that, if reached by counter , declares a signal as present. It defaults to 2. Optional
tong_max_dwells Maximum number of dwells in a search . It defaults to tong_max_val . Optional
repeat_satellite [true, false]: If set to true, the block will search again for the same satellite once its presence has been discarded. Useful for testing. It defaults to false. Optional
dump [true, false]: If set to true, it enables the Acquisition internal binary data file logging. It defaults to false. Optional
dump_filename If dump is set to true, name of the file in which internal data will be stored. It defaults to ./acquisition.dat Optional

Acquisition implementation: GPS_L1_CA_PCPS_Tong_Acquisition.

Example:

;######### ACQUISITION GLOBAL CONFIG ############
Acquisition_1C.implementation=GPS_L1_CA_PCPS_Tong_Acquisition
Acquisition_1C.pfa=0.0001
Acquisition_1C.doppler_max=10000
Acquisition_1C.doppler_step=250
Acquisition_1C.tong_init_val=2
Acquisition_1C.tong_max_val=10
Acquisition_1C.tong_max_dwells=20

GPS L2CM signal acquisition

Implementation: GPS_L2_M_PCPS_Acquisition

This implementation accepts the following parameters:

Global Parameter Description Required
GNSS-SDR.internal_fs_hz Input sample rate to the processing channels, in samples per second. Mandatory
Parameter Description Required
implementation GPS_L2_M_PCPS_Acquisition Mandatory
item_type [gr_complex, cshort, cbyte]: Set the sample data type expected at the block input. It defaults to gr_complex. Optional
if Intermediate frequency of the incoming signal, in Hz. It defaults to (i.e., complex baseband signal). Optional
doppler_max Maximum Doppler value in the search grid, in Hz. It defaults to 5000 Hz. Optional
doppler_step Frequency step in the search grid, in Hz. It defaults to 500 Hz. Optional
threshold Decision threshold from which a signal will be considered present. It defaults to (i.e., all signals are declared present), Optional
pfa If defined, it supersedes the threshold value and computes a new threshold based on the Probability of False Alarm. It defaults to (i.e., not set). Optional
use_CFAR_algorithm [true, false]: If set to true, applies a normalization to the computed peak value on the search grid. It defaults to true. Optional
coherent_integration_time_ms Set the integration time , in ms. It defaults to 1 ms. Optional
bit_transition_flag [true, false]: If set to true, it takes into account the possible presence of a bit transition, so the effective integration time is doubled. When set, it invalidates the value of max_dwells. It defaults to false. Optional
max_dwells Set the maximum number of dwells to declare a signal present. It defaults to 1. Optional
repeat_satellite [true, false]: If set to true, the block will search again for the same satellite once its presence has been discarded. Useful for testing. It defaults to false. Optional
blocking [true, false]: If set to false, the acquisition workload is executed in a separate thread, outside the GNU Radio scheduler that manages the flow graph, and the block skips over samples that arrive while the processing thread is busy. This is specially useful in real-time operation using radio frequency front-ends, overcoming the processing bottleneck for medium and high sampling rates. However, this breaks the determinism provided by the GNU Radio scheduler, and different processing results can be obtained in different machines. Do not use this option for file processing. ONLY AVAILABLE IN THE next BRANCH. It defaults to true. Optional
dump [true, false]: If set to true, it enables the Acquisition internal binary data file logging. It defaults to false. Optional
dump_filename If dump is set to true, name of the file in which internal data will be stored. It defaults to ./acquisition.dat Optional

Acquisition implementation: GPS_L2_M_PCPS_Acquisition.

Example:

Acquisition_2S.implementation=GPS_L2_M_PCPS_Acquisition
Acquisition_2S.item_type=cshort
Acquisition_2S.threshold=0.0015
Acquisition_2S.doppler_max=6000
Acquisition_2S.doppler_step=60
Acquisition_2S.max_dwells=2

Galileo E1B signal acquisition

Implementation: Galileo_E1_PCPS_Ambiguous_Acquisition

The user can also configure the shape of , allowing simplifications that reduce the computational load. As shown in Figure [fig:Rxd], in narrowband receivers the CBOC waveform can be substituted by a sinBOC modulation with very small performance penalty4. For the E1B signal component, the reference signals available in our implementation are:

while for E1C, users can choose among:

where the subcarriers are defined as and , with MHz and MHz.

Rxd

Normalized for different sampling rates and local reference waveforms2.

This implementation accepts the following parameters:

Global Parameter Description Required
GNSS-SDR.internal_fs_hz Input sample rate to the processing channels, in samples per second. Mandatory
Parameter Description Required
implementation Galileo_E1_PCPS_Ambiguous_Acquisition Mandatory
item_type [gr_complex, cshort, cbyte]: Set the sample data type expected at the block input. It defaults to gr_complex. Optional
if Intermediate frequency of the incoming signal, in Hz. It defaults to (i.e., complex baseband signal). Optional
doppler_max Maximum Doppler value in the search grid, in Hz. It defaults to 5000 Hz. Optional
doppler_step Frequency step in the search grid, in Hz. It defaults to 500 Hz. Optional
threshold Decision threshold from which a signal will be considered present. It defaults to (i.e., all signals are declared present), Optional
pfa If defined, it supersedes the threshold value and computes a new threshold based on the Probability of False Alarm. It defaults to (i.e., not set). Optional
cboc [true, false]: If set to true the algorithm uses the CBOC waveform , if set to false a simpler sinBOC waveform is used. It defaults to false. Optional
coherent_integration_time_ms Set the integration time , in ms. Should be a multiple of 4 ms. It defaults to 4 ms. Optional
bit_transition_flag [true, false]: If set to true, it takes into account the possible presence of a bit transition, so the effective integration time is doubled. When set, it invalidates the value of max_dwells. It defaults to false. Optional
max_dwells Set the maximum number of dwells to declare a signal present. It defaults to 1. Optional
repeat_satellite [true, false]: If set to true, the block will search again for the same satellite once its presence has been discarded. Useful for testing. It defaults to false. Optional
blocking [true, false]: If set to false, the acquisition workload is executed in a separate thread, outside the GNU Radio scheduler that manages the flow graph, and the block skips over samples that arrive while the processing thread is busy. This is specially useful in real-time operation using radio frequency front-ends, overcoming the processing bottleneck for medium and high sampling rates. However, this breaks the determinism provided by the GNU Radio scheduler, and different processing results can be obtained in different machines. Do not use this option for file processing. ONLY AVAILABLE IN THE next BRANCH. It defaults to true. Optional
dump [true, false]: If set to true, it enables the Acquisition internal binary data file logging. It defaults to false. Optional
dump_filename If dump is set to true, name of the file in which internal data will be stored. It defaults to ./acquisition.dat Optional

Acquisition implementation: Galileo_E1_PCPS_Ambiguous_Acquisition.

Example:

;######### ACQUISITION GLOBAL CONFIG ############
Acquisition_1B.implementation=Galileo_E1_PCPS_Ambiguous_Acquisition
Acquisition_1B.pfa=0.000008
Acquisition_1B.doppler_max=6000
Acquisition_1B.doppler_step=250

Implementation: Galileo_E1_PCPS_Tong_Ambiguous_Acquisition

The Tong detector3 is a sequential variable dwell time detector with a reasonable computation burden that proves good for acquiring signals with low levels. During the signal search, the up/down counter is incremented by one if the correlation peak value exceeds the threshold, otherwise it is decremented by one. If the counter has reached maximum count value , the signal is declared ‘present’ and the search is terminated. Similarly if the counter contents reach zero, the signal is declared ‘absent’ and the search is terminated. So that the Tong detector is not trapped into an extended dwell in the same cell, under certain poor signal conditions, another counter () sets the limit on maximum number of dwells.

This implementation accepts the following parameters:

Global Parameter Description Required
GNSS-SDR.internal_fs_hz Input sample rate to the processing channels, in samples per second. Mandatory
Parameter Description Required
implementation Galileo_E1_PCPS_Tong_Ambiguous_Acquisition Mandatory
item_type [gr_complex]: Set the sample data type expected at the block input. It defaults to gr_complex. Optional
if Intermediate frequency of the incoming signal, in Hz. It defaults to (i.e., complex baseband signal). Optional
doppler_max Maximum Doppler value in the search grid, in Hz. It defaults to 5000 Hz. Optional
doppler_step Frequency step in the search grid, in Hz. It defaults to 500 Hz. Optional
threshold Decision threshold from which a signal will be considered present. It defaults to (i.e., all signals are declared present), Optional
pfa If defined, it supersedes the threshold value and computes a new threshold based on the Probability of False Alarm. It defaults to (i.e., not set). Optional
coherent_integration_time_ms Set the integration time , in ms. Should be a multiple of 4 ms. It defaults to 4 ms. Optional
tong_init_val Initial value of the Tong counter . It defaults to 1. Optional
tong_max_val Count value that, if reached by counter , declares a signal as present. It defaults to 2. Optional
tong_max_dwells Maximum number of dwells in a search . It defaults to tong_max_val . Optional
repeat_satellite [true, false]: If set to true, the block will search again for the same satellite once its presence has been discarded. Useful for testing. It defaults to false. Optional
dump [true, false]: If set to true, it enables the Acquisition internal binary data file logging. It defaults to false. Optional
dump_filename If dump is set to true, name of the file in which internal data will be stored. It defaults to ./acquisition.dat Optional

Acquisition implementation: Galileo_E1_PCPS_Tong_Ambiguous_Acquisition.

Example:

;######### ACQUISITION GLOBAL CONFIG ############
Acquisition_1B.implementation=Galileo_E1_PCPS_Tong_Ambiguous_Acquisition
Acquisition_1B.pfa=0.0001
Acquisition_1B.doppler_max=10000
Acquisition_1B.doppler_step=250
Acquisition_1B.tong_init_val=2
Acquisition_1B.tong_max_val=10
Acquisition_1B.tong_max_dwells=20

Galileo E5a signal acquisition

Implementation: Galileo_E5a_Noncoherent_IQ_Acquisition_CAF

This implementation accepts the following parameters:

Global Parameter Description Required
GNSS-SDR.internal_fs_hz Input sample rate to the processing channels, in samples per second. Mandatory
Parameter Description Required
implementation Galileo_E5a_Noncoherent_IQ_Acquisition_CAF Mandatory
item_type [gr_complex]: Set the sample data type expected at the block input. It defaults to gr_complex. Optional
if Intermediate frequency of the incoming signal, in Hz. It defaults to (i.e., complex baseband signal). Optional
doppler_max Maximum Doppler value in the search grid, in Hz. It defaults to 5000 Hz. Optional
doppler_step Frequency step in the search grid, in Hz. It defaults to 500 Hz. Optional
CAF_window_hz Resolves Doppler ambiguity by veraging the specified bandwidth (in Hz) in the winner code delay. If set to , the CAF filter is deactivated. Recommended value: Hz. It defaults to 0 Hz. Optional
Zero_padding If set to a , it avoids power loss and doppler ambiguity in bit transitions by correlating one code with twice the input data length, ensuring that at least one full code is present without transitions. It defaults to (i.e., deactivated). Optional
threshold Decision threshold from which a signal will be considered present. It defaults to (i.e., all signals are declared present), Optional
pfa If defined, it supersedes the threshold value and computes a new threshold based on the Probability of False Alarm. It defaults to (i.e., not set). Optional
coherent_integration_time_ms Set the integration time , in ms. Should be a 3 ms or less. It defaults to 1 ms. Optional
bit_transition_flag [true, false]: If set to true, it takes into account the possible presence of a bit transition, so the effective integration time is doubled. When set, it invalidates the value of max_dwells. It defaults to false. Optional
max_dwells Set the maximum number of dwells to declare a signal present. It defaults to 1. Optional
repeat_satellite [true, false]: If set to true, the block will search again for the same satellite once its presence has been discarded. Useful for testing. It defaults to false. Optional
dump [true, false]: If set to true, it enables the Acquisition internal binary data file logging. It defaults to false. Optional
dump_filename If dump is set to true, name of the file in which internal data will be stored. It defaults to ./acquisition.dat Optional

Acquisition implementation: Galileo_E5a_Noncoherent_IQ_Acquisition_CAF.

Example:

;######### ACQUISITION GLOBAL CONFIG ############
Acquisition_5X.implementation=Galileo_E5a_Noncoherent_IQ_Acquisition_CAF
Acquisition_5X.threshold=0.002
Acquisition_5X.doppler_max=10000
Acquisition_5X.doppler_step=250

References

  1. K. Borre, D. M. Akos, N. Bertelsen, P. Rinder, S. H. Jensen, A Software-Defined GPS and Galileo Receiver. A Single-Frequency Approach, 1st edition, Boston: Birkhäuser, November 2006. 

  2. C. Fernández-Prades, J. Arribas, L. Esteve-Elfau, D. Pubill, P. Closas, An Open Source Galileo E1 Software Receiver, in Proceedings of the 6th ESA Workshop on Satellite Navigation Technologies (NAVITEC 2012), 5-7 December 2012, ESTEC, Noordwijk (The Netherlands).  2

  3. P. S. Tong, A Suboptimum Synchronization Procedure for Pseudo Noise Communication Systems, in Proc. of National Telecommunications Conference, 1973, pp. 26D1-26D5.  2

  4. J. Zhang, E. S. Lohan, Galileo E1 and E5a Link-Level Performances in Single and Multipath Channels. In G. Giambene, C. Sacchi, Eds., Personal Satellite Services, Third International ICST Conference PSATS 2011, Malaga, Spain, February 2011. 

Updated:

Leave a Comment