A Fast Algorithm for Calculating Correlation in FFT Based GPS Receiver with Carrier Frequency Deviation

摘要

Recently, the Global Positioning System (GPS) has been widely used. However, It requires a huge of number of computations for calculating the correlation between PRN codes of the receiving signal and the stored signal in the receiver. Different satellites have the different orthogonal codes. FFT and IFFT are effectively applied to signal processing in GPS in order to save computations. However, a large number of computations are still required. Furthermore, the carrier frequency is slightly changed by the Doppler effect. This deviation should be compensated for. In this paper, a fast algorithm for saving computations required in the FFT and IFFT processing. The carrier frequency deviation is compensated for after FFT by shifting the frequency components. Only a single FFT is required, and the computation is reduced to 10 percent of the conventional. The candidates for the frequency compensation are estimated in the frequency domain based on the Parseval theory. The number of IFFT can be reduced to 5/17 of the original. Totally, computation can be saved, that is 40 persent of the conventional. The proposed method will be useful in a soft-processing based GPS in the near future.