Acquisition of GPS C/A Code Signals - Fundamentals of Global Positioning System Receivers: A Software Approach - page 134

not 2.5 MHz. Therefore, one might calculate only 21 frequency components sep-
arated by 1 kHz using the discrete Fourier transform (DFT) to save calculation
time. This decision depends on the speed of the two operations.
Since the beginning point of the C/A code in the input data is unknown, this
point must be found. In order to find this point, a locally generated C/A code must
be digitized into 5,000 points and multiply the input point by point with the input
data. FFT or DFT is performed on the product to find the frequency. In order to
search for 1 ms of data, the input data and the locally generated one must slide
5,000 times against each other. If the FFT is used, it requires 5,000 operations
and each operation consists of a 5,000-point multiplication and a 5,000-point
FFT. The outputs are 5,000 frames of data and each contains 2,500 frequency
components because only 2,500 frequency components provide information and
the other 2,500 components provide redundant information. There are a total
of 1 . 25 × 10 7 (5 , 000 × 2 , 500) outputs in the frequency domain. The highest
amplitude among these 1 . 25 × 10 7 outputs can be considered as the desired result
if it also crosses the threshold. Searching for the highest component among this
amount of data is also time consuming. Since only 21 frequencies of the FFT
outputs covering the desired 20 kHz are of interest, the total outputs can be
reduced to 105,000 (5 , 000 × 21). From this approach the beginning point of the
C/A code can be found with a time resolution of 200 ns (1/5 MHz) and the
frequency resolution of 1 kHz.
If 10 ms of data are used, it requires 5,000 operations because the signal
only needs to be correlated for 1 ms. Each operation consists of a 50,000-point
multiplication and a 50,000 FFT. There are a total of 1 . 25 × 10 8 (5 , 000 × 25 , 000)
outputs. If only the 201 frequency components covering the desired 20 kHz are
considered, one must sort through 1,005,000 (5 , 000 × 201) outputs. The increase
in operation time from 1 ms to 10 ms is quite significant. The time resolution
for the beginning of the C/A code is still 200 ns but the frequency resolution
improves to 100 Hz.
7.6 TIME DOMAIN CORRELATION
The conventional acquisition in a GPS receiver is accomplished in hardware.
The hardware is basically used to perform the process discussed in the previous
section. Suppose that the input data is digitized at 5 MHz. One possible approach
is to generate a 5,000-point digitized data of the C/A code and multiply them
with the input signal point by point. The 5,000-point multiplication is performed
every 200 ns. Frequency analysis such as a 5,000-point FFT is performed on the
products every 200 ns. Figure 7.2 shows such an arrangement. If the C/A code
and the input data are matched, the FFT output will have a strong component. As
discussed in the previous section, this method will generate 1 . 25 × 10 7 (5 , 000 ×
2 , 500) outputs. However, only the outputs within the proper frequency range of
± 10 kHz will be sorted. This limitation simplifies the sorting processing.
Another way to implement this operation is through DFT. The locally gen-
erated local code is modified to consist of a C/A code and an RF. The RF is