Fast FFT based GPS satellite acquisition methods

A Global Positioning System (GPS) receiver uses satellite signals to determine position, velocity, and timing information. Measurements are obtained by synchronising the locally generated signal in the receiver with the signals received. A synchronisation procedure called acquisition adjusts the code phases of the incoming signal and the locally generated pseudo-random replica sequence of the corresponding satellite to a small timing offset and finds the residual frequency modulation after carrier wipe-off. New fast techniques for acquiring signals indoors in conditions that require a significant number of computations are presented. In this work many arithmetic operations are shared when exploring different search options by using fast Fourier transform (FFT) and a technique based on the frequency domain replica shifting. It is shown that FFT can be used for the joint processing of multiple (code-phase/frequency) search options in both dimensions at once. With a slight degradation in performance, the algorithm has a modified version that implements the technique using two-dimensional FFT. Several possible processing schemes are presented. Moreover, the presented shifting replica approach in the frequency domain can significantly reduce computational complexity by jointly acquiring different satellites.