Acquisition (GPS and Galileo Receiver) Part 1

The present and the following topics are based on signals recorded according to parameters described in Section 4.3. The theory can be applied similarly to records with a different selection of parameters.

Motivation

The purpose of acquisition is to determine visible satellites and coarse values of carrier frequency and code phase of the satellite signals.

The satellites are differentiated by the 32 different PRN sequences. The second parameter, code phase, is the time alignment of the PRN code in the current block of data. It is necessary to know the code phase in order to generate a local PRN code that is perfectly aligned with the incoming code. Only when this is the case, the incoming code can be removed from the signal. PRN codes have high correlation only for zero lag. That is, the two signals must be perfectly aligned to remove the incoming code. The third parameter is the carrier frequency, which in case of down conversion corresponds to the IF. The IF should be known from the L1 carrier frequency of 1575.42MHz and from the mixers in the down converter. However, the frequency can deviate from the expected value. The line-of-sight velocity of the satellite (with respect to the receiver) causes a Doppler effect resulting in a higher or lower frequency. In the worst case, the frequency can deviate up to ±10 kHz. It is important to know the frequency of the signal to be able to generate a local carrier signal. This signal is used to remove the incoming carrier from the signal. In most cases it is sufficient to search the frequencies such that the maximum error will be less than or equal to 500 Hz.


Block diagram of the serial search algorithm.

FIGURE 6.1. Block diagram of the serial search algorithm.

In an ordinary receiver, the acquisition is usually performed in an application-specific integrated circuit (ASIC). In a software receiver, it is implemented in software. The following sections describe the theory behind three standard methods of acquisition to demonstrate the possibility of implementing an efficient method in a software receiver.

Serial Search Acquisition

Serial search acquisition is an often-used method for acquisition in code-division multiple access systems (CDMA). GPS is a CDMA system. Figure 6.1 is a block diagram of the serial search algorithm.

As seen in Figure 6.1, the algorithm is based on multiplication of locally generated PRN code sequences and locally generated carrier signals. The PRN generator generates a PRN sequence corresponding to a specific satellite. The generated sequence has a certain code phase, from 0 to 1022 chips. The incoming signal is initially multiplied by this locally generated PRN sequence. After multiplication with the PRN sequence, the signal is multiplied by a locally generated carrier signal. Multiplication with the locally generated carrier signal generates the in-phase signal I, and multiplication with a 90° phase-shifted version of the locally generated carrier signal generates the quadrature signal Q.

The I and Q signals are integrated over 1 ms, corresponding to the length of one C/A code, and finally squared and added. Ideally, the signal power should be located in the I part of the signal, as the C/A code is only modulated onto that. However, in this case the I signal generated at the satellite does not necessarily correspond to the demodulated I . This is because the phase of the received signal is unknown. So to be certain that the signal is detected, it is necessary to investigate both the I and the Q signal. The output is a value of correlation between the incoming signal and the locally generated signal. If a predefined threshold is exceeded, the frequency and code phase parameters are correct, and the parameters can be passed on to the tracking algorithms.

The serial search algorithm performs two different sweeps: a frequency sweep over all possible carrier frequencies of IF ±10 kHz in steps of 500 Hz and a code phase sweep over all 1023 different code phases. All in all, this sums up to a total of

tmp2D798_thumb

Obviously, this is a very large number of combinations. This exhausting search routine also tends to be the main weakness of the serial search acquisition.

The implementation of the serial search acquisition method is very straightforward. The algorithm can be implemented directly based on the block diagram of the method as shown in Figure 6.1.

PRN Sequence Generation

Figure 6.1 shows that the first task in the serial search acquisition method is to multiply the incoming signal with the locally generated PRN sequence. This of course involves the generation of this PRN sequence. Instead of generating PRN sequences every time the algorithm is executed, all possible PRN sequences are generated offline. The 32 different PRN sequences are generated by the PRN generator implemented according to Figure 2.5.

The PRN code generator is implemented using the binary values 0 and 1. However, in the signal processing algorithms it is more convenient to represent the codes with a polar non-return-to-zero representation.

With 32 generated PRN sequences, all possible sequences originating from GPS satellites are created. However, as mentioned in the theory of serial search acquisition, the method involves multiplication with all possible shifted versions of the PRN codes. That is, besides saving the 32 possible PRN codes all possible shifted versions should also be saved. This sums up to a total of 32,736 different PRN codes. To make the multiplication between one of the generated PRN codes and the incoming signal possible, the code has to be sampled with 38.192MHz, like the received signal. This sampling converts the length of a PRN sequence from 1023 to 38,192.

Carrier Generation

The second step is multiplication with a locally generated carrier wave. The carrier generator must generate two carrier signals with a phase difference of 90°, corresponding to a cosine and a sine wave. The carrier must have a frequency corresponding to the IF ± the frequency step according to the examined frequency area. It must be sampled with the sampling frequency of 38.192MHz and have a length of1 ms. A complex signal is generated using the natural exponential functiontmp2D799_thumb

Locally generated cosine (a) and sine (b) waves.

FIGURE 6.2. Locally generated cosine (a) and sine (b) waves.

In MATLAB the 38,192 sample-long sequence, corresponding to 1 ms, is generated astmp2D802_thumbwhere fc is the IF plus current frequency offset, ts is the sampling periodtmp2D803_thumband nn is an array with numbers from 0 to 38,191. Now the sine and cosine waves are generated as cosine = real(carrier); and sine = imag(carrier);.

Figure 6.2 shows the first 20 samples of the resulting cosine and sine waves when using a sampling frequencytmp2D804_thumband lettingtmp2D805_thumb

Integration and Squaring

The last parts of the serial search algorithm involve an integration and a squaring of the two results of the multiplications with the cosine and sine signals, respectively. The squaring is introduced to obtain the signal power. The integration is simply a summation of all 38,192 points corresponding to the length of the processed data. The squaring is then performed on the result of the summation. The final step is to add the two values from the I arm and the Q arm. If the locally generated code is well aligned with the code in the incoming signal, and the frequency of the locally generated carrier matches the frequency of the incoming signal, the output will be significantly higher than if any of these criteria were not fulfilled. Figure 6.3 shows the output from the serial search acquisition method. Figure 6.3a is the output when performing the acquisition on a satellite that is not visible and Figure 6.3b when performing the acquisition on a satellite that is visible. PRN 19 is arbitrarily chosen as a nonvisible satellite.

Parallel Frequency Space Search Acquisition

The serial search acquisition method showed that it is a very time-consuming procedure to search sequentially through all possible values of the two parameters frequency and code phase. If any of the two parameters could be eliminated from the search procedure or if possible implemented in parallel, the performance of the procedure would increase significantly.

Output from serial search acquisition. (a) PRN 19 is not visible so no peak is present. (b) PRN 21 is visible so a significant peak is present. The peak occurs at C/A code phase = 359 chips and frequency = 9.5475 MHz.

FIGURE 6.3. Output from serial search acquisition. (a) PRN 19 is not visible so no peak is present. (b) PRN 21 is visible so a significant peak is present. The peak occurs at C/A code phase = 359 chips and frequency = 9.5475 MHz.

As the name parallel frequency space search acquisition implies, this second method of acquisition parallelizes the search for the one parameter. This method utilizes the Fourier transform to perform a transformation from the time domain into the frequency domain. Figure 6.4 is a block diagram of the parallel frequency space search algorithm.

The incoming signal is multiplied by a locally generated PRN sequence, with a code corresponding to a specific satellite and a code phase between 0 and 1022 chips. The resulting signal is transformed into the frequency domain by a Fourier transform. The Fourier transform could be implemented as a discrete Fourier transform (DFT) or a fast Fourier transform (FFT). The FFT is the faster of the two; but it requires an input sequence with a radix-2 length, that is, 2n, where n takes positive integer value.

Figure 6.5 illustrates the result of multiplying the incoming signal with a perfectly aligned locally generated PRN sequence. The result is a continuous wave signal. Of course, this only happens when the locally generated PRN code is perfectly aligned with the code in the incoming signal. If the incoming signal contains signal components from other satellites, these components will be minimized as a result of the cross-correlation properties of the PRN sequences.

In parallel frequency space search acquisition, the upper signal in Figure 6.5 is the input to the Fourier transform function. With a perfectly aligned PRN code, the output of the Fourier transform will show a distinct peak in magnitude. The peak will be located at the frequency index corresponding to the frequency of the continuous-wave signal and thereby the frequency of the carrier wave signal.

Block diagram of the parallel frequency space search algorithm.

FIGURE 6.4. Block diagram of the parallel frequency space search algorithm.

 PRN code demodulation. At the top the PRN code is modulated onto the carrier wave. In the middle is a perfectly aligned PRN sequence. At the bottom we recover the continuous wave after multiplying the incoming signal with the perfectly aligned PRN sequence.

FIGURE 6.5. PRN code demodulation. At the top the PRN code is modulated onto the carrier wave. In the middle is a perfectly aligned PRN sequence. At the bottom we recover the continuous wave after multiplying the incoming signal with the perfectly aligned PRN sequence.

The accuracy of the determined frequency depends on the length of the DFT. The length corresponds to the number of samples in the analyzed data. If 1 ms of data is analyzed, the number of samples can be found as 1/1000 of the sampling frequency. That is, if the sampling frequency istmp2D813_thumbthe number of samples is N = 10,000.

With a DFT length of 10,000, the first N/2 output samples represent the frequencies fromtmp2D814_thumbThat is, the frequency resolution of the output is

tmp2D817_thumb

With a sampling frequency of tmp2D818_thumb the resulting frequency resolution is

tmp2D819_thumb

In this case, the accuracy of the estimated carrier frequency is 1 kHz compared to the accuracy of 500 Hz in serial search acquisition.

Figure 6.6 shows the output as two power spectral density (PSD) plots. The PSD algorithm is using FFT for the acquisition. Figure 6.6a is the output of the Fourier transform with a perfectly aligned code phase. This can be noticed from the peak in the plot. Figure 6.6b shows the PSD plot for a not aligned code phase. Note the absence of a peak in the plot.

Where the serial search acquisition method steps through possible code phases and carrier frequencies, the parallel frequency space search acquisition only steps through the 1023 different code phases. This comes with the cost of a frequency domain transformation with each code phase. Depending on the implementation of the frequency domain transformation, it should be possible to make a faster implementation of this method compared to the serial search acquisition method.

PSD plot of the incoming signal multiplied by a locally generated PRN code sequence. (a) When multiplying with a perfectly aligned PRN code, the output will show a peak at the carrier frequency. (b) When multiplying with a nonaligned code, the output will not show any peaks. The IF is 9.548 MHz. The Doppler frequency is the same on IF and RF, and thus also the difference between the IF and the peak frequency.

FIGURE 6.6. PSD plot of the incoming signal multiplied by a locally generated PRN code sequence. (a) When multiplying with a perfectly aligned PRN code, the output will show a peak at the carrier frequency. (b) When multiplying with a nonaligned code, the output will not show any peaks. The IF is 9.548 MHz. The Doppler frequency is the same on IF and RF, and thus also the difference between the IF and the peak frequency.

Like the serial search acquisition method, the implementation of the parallel frequency space search method is straightforward. The algorithm can be implemented directly based on the block diagram of the method shown in Figure 6.4.

The first part of this method is identical to the first part of the serial search method. That is, a locally generated PRN code must be multiplied with the incoming signal. After the code multiplication, the signal is transformed into the frequency domain through Fourier transform. An efficient tool for that is the fast Fourier transform (FFT). See Oppenheim & Schafer (1999) for details on the FFT.

After transforming the signal into the frequency domain by means of the FFT algorithm, it becomes a complex signal. If the locally generated code is well aligned with the code in the incoming signal, the output from the FFT will have a peak at the IF plus Doppler offset frequency. To find the possible peak frequency the absolute value of all components are calculated. Figure 6.7 shows the output from the parallel frequency space search method.

Next post:

Previous post: