GPS receivers spend much of their time on acquisition and tracking. Slow acquisition is due to the large computation time of the correlation function. The correlation function searches for the code phase between the GPS receiver signal arrival time and the GPS satellite's signal transmission time. The computation of the correlation function in frequency domain is speed up N/logN times compared with the time domain implementation.
The long computation time for the correlation function is due to the computation of the FFT functions. One possible solution to speed up the calculations of the correlation function is by replacing the FFTs with simpler transforms. Two transforms were studied in this work. A real transform called the Fermat number transform (FNT) was presented. The FNT-based convolution algorithm was shown. However, the FNT-based convolution has a sequence length restriction that makes it not applicable to the GPS case. A binary transform called the Walsh Hadamard transform (WHT) was also investigated. The WHT-based correlation algorithm was presented and verified. This method shows a significant reduction in the computing time of the correlation function by approximately 20 times compared to the FFT method. The Walsh Hadamard method is not directly applicable to the GPS C/A code, so was not used for GPS signal acquisition.
This dissertation also illustrates a realistic solution to the slow acquisition of the GPS receivers. It uses the FPGA technology along with an averaging method to speed up the calculations of the FFT-based correlation function and to reduce the hardware requirements. The developed method approximated the correlation function by using a modified version of the C/A code. This approximation was accurate enough to use in the acquisition process while maintaining an acceptable level of signal power. This algorithm was used to guide three serial correlators to zoom-in around the correlation peak and provide refined versions of the acquisition estimates. This unique algorithm was implemented and then successfully acquired a GPS signal in less than 1-ms.