FFT based acquisition techniques for satellite based navigation systems

• US 8,384,592 B1
• Filed: 09/30/2009
• Issued: 02/26/2013
• Est. Priority Date: 09/30/2009
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Crary, Philip, Sun, Qinfang
• Primary Examiner(s): GALT, CASSI J
• Application Number:
  US12/570,942
• Time in Patent Office: 1,245 Days
• Field of Search: 342/357.63, 34235767-35769, 34235775-35777
• US Class Current: 342/357.69
• CPC Class Codes: G01S 19/24 Acquisition or tracking or demodulation of signals transmitted by the system synchronisation aspects of direct sequence spread spectrum modulation H04B1/7073
• CPC Class Codes: G01S 19/30 code related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/37 Hardware or software details of the signal processing chain

Abstract

A satellite navigation receiver receives a combination of radio frequency signals from satellites in satellite navigation systems and process the radio frequency signals to calculate an approximate current location of the satellite navigation receiver. Satellite acquisition plays an important part in identifying the current location of the satellite navigation receiver. Acquisition involves identifying the satellites in the satellite navigation that can be used to provide navigation information. Fast Fourier transform based acquisition involves using FFT and subsequently inverse FFT (IFFT) to correlate a coarse acquisition (C/A) code transmitted by a satellite with a C/A code locally generated on the GPS receiver to identify and acquire a transmitting satellite.

Claims

1. A method comprising:

receiving, using a satellite navigation receiver, input samples of an RF signal from one or more satellites of a plurality of satellites in a satellite navigation system, wherein the RF signal is a combination of signals from the one or more satellites of the satellite navigation system;

compensating, using the satellite navigation receiver, for Doppler shift in a first set of the input samples to yield a compensated first set of samples, wherein the first set of the input samples correspond to the input samples received within a first time interval;

calculating, using the satellite navigation receiver, a frequency domain representation of the compensated first set of samples;

generating, using the satellite navigation receiver, a coarse acquisition code associated with at least one of the plurality of satellites in the satellite navigation system;

inserting, using the satellite navigation receiver, a first zero into the coarse acquisition code as a center bit and inserting a second zero into the coarse acquisition code as an end bit such that a length of the coarse acquisition code equals a pre-defined length;

calculating, using the satellite navigation receiver, a frequency domain representation of the coarse acquisition code of the pre-defined length for determining whether the RF signal was transmitted by the at least one of the plurality of satellites;

determining, using the satellite navigation receiver, a time domain representation of a result of multiplying the frequency domain representation of the compensated first set of samples and the frequency domain representation of the coarse acquisition code;

identifying, using the satellite navigation receiver, a peak correlation value from the time domain representation; and

determining, using the satellite navigation receiver, information about the at least one of the plurality of satellites based on the peak correlation value.

2. The method of claim 1, wherein the pre-defined length is a length of the compensated first set of samples.

3. The method of claim 1, wherein the pre-defined length is a power of 2.

4. The method of claim 1, wherein said inserting the first zero into the coarse acquisition code as the center bit and inserting the second zero into the coarse acquisition code as the end bit comprises inserting the first zero and the second zero into the coarse acquisition code such that a spacing between the first inserted zero and the second inserted zero is a predetermined number of samples.

5. The method of claim 4, wherein the spacing between the first inserted zero and the second inserted zero is 1024 samples.

6. The method of claim 1, wherein said calculating the frequency domain representation of the compensated first set of samples further comprises inserting zeros into the compensated first set of samples such that a length of the compensated first set of samples equals a pre-defined length.

7. The method of claim 6, wherein the pre-defined length is a power of 2.

8. The method of claim 1, further comprising:

calculating a frequency domain representation of a coarse acquisition code of a second of the plurality of satellites for determining whether the RF signal was transmitted by at least the second of the plurality of satellites;

determining a second time domain representation of a result of multiplying the frequency domain representation of the compensated first set of samples and the frequency domain representation of the coarse acquisition code of the second of the plurality of satellites;

identifying a second peak correlation value from the second time domain representation; and

determining information about the second of the plurality of satellites based on the second peak correlation value.

9. The method of claim 1, further comprising:

compensating for the Doppler shift in a second set of the input samples to yield a compensated second set of samples, wherein the second set of the input samples correspond to the input samples received within a second time interval;

summing the compensated first set of samples with the compensated second set of samples to yield a pre-summed set of samples and to improve signal to noise ratio of the pre-summed set of samples;

calculating a frequency domain representation of the pre-summed set of samples;

determining a second time domain representation of a result of multiplying the frequency domain representation of the pre-summed set of samples and the frequency domain representation of the coarse acquisition code;

identifying a second peak correlation value from the second time domain representation; and

determining the information about the at least one of the plurality of satellites based on the second peak correlation value.

10. The method of claim 1, wherein the compensating for the Doppler shift in the first set of the input samples further comprises:

calculating an estimated value of the Doppler shift; and

compensating for the Doppler shift by shifting the first set of the input samples by the estimated value of the Doppler shift.

11. The method of claim 10, further comprising:

calculating, after searching through code space of the plurality of satellites in the satellite navigation system using the first set of the input samples shifted by the estimated value of the first Doppler shift, an estimated value of a second Doppler shift;

compensating for the second Doppler shift by shifting the first set of the input samples by the estimated value of the second Doppler shift; and

searching through code space of the plurality of satellites in the satellite navigation system using the first set of the input samples shifted by the estimated value of the second Doppler shift.

12. The method of claim 1, further comprising determining whether the first set of the input samples is available for processing by determining whether a signal to noise ratio of the first set of the input samples is greater than a threshold signal to noise ratio.

13. The method of claim 1, further comprising:

calculating a second time domain representation of a result of multiplying the frequency domain representation of a compensated second set of samples and the frequency domain representation of the coarse acquisition code associated with the at least one of the plurality of satellites, wherein the compensated second set of samples correspond to the input samples received within a second time interval and compensated for the Doppler shift;

accumulating the first time domain representation with the second time domain representation to improve a signal to noise ratio and generate a significant peak correlation value; and

identifying the peak correlation value from said accumulating the first time domain representation with the second time domain representation.

14. The method of claim 1, further comprising:

compensating each of a plurality of instances of the first set of the input samples by a distinct Doppler shift; and

correlating the plurality of instances of the first set of the input samples and the coarse acquisition code associated with the at least one of the plurality of satellites to determine information about the at least one of the plurality of satellites.

15. A method comprising:

receiving, using a satellite navigation receiver, input samples of an RF signal from one or more satellites of a plurality of satellites in a satellite navigation system, wherein the RF signal is a combination of signals from the one or more satellites of the satellite navigation system;

generating, using the satellite navigation receiver, a coarse acquisition code associated with a first of the plurality of satellites in the satellite navigation system;

inserting, using the satellite navigation receiver, a first zero into the coarse acquisition code as a center bit and inserting a second zero into the coarse acquisition code as an end bit to generate a compensated coarse acquisition code such that a length of the coarse acquisition code equals a pre-defined length; and

correlating, using the satellite navigation receiver, a first set of input samples, which correspond to the input samples received within a first time interval, and the compensated coarse acquisition code to determine information about the first of the plurality of satellites.

16. The method of claim 15, further comprising inserting zeros into the first set of the input samples such that a length of the first set of the input samples equals the pre-defined length.

17. The method of claim 16, wherein the pre-defined length associated with the first set of the input samples and the compensated coarse acquisition code is a power of 2.

18. The method of claim 15, wherein said inserting the first zero into the coarse acquisition code as the center bit and inserting the second zero into the coarse acquisition code as the end bit comprises inserting the first zero and the second zero into the coarse acquisition code such that a spacing between the first inserted zero and the second inserted zero is a predetermined number of samples.

19. The method of claim 15, wherein said correlating the first set of input samples and the compensated coarse acquisition code to determine information about the first of the plurality of satellites further comprises:

calculating a frequency domain representation of the first set of the input samples;

calculating a frequency domain representation of the compensated coarse acquisition code for determining whether the RF signal was transmitted by at least the first of the plurality of satellites;

determining a time domain representation of a result of multiplying the frequency domain representation of the first set of the input samples and the frequency domain representation of the compensated coarse acquisition code;

identifying a peak correlation value from the time domain representation; and

determine information about the first of the plurality of satellites based on the peak correlation value.

20. The method of claim 15, wherein said determining information about the first of the plurality of the satellites based on the peak correlation value comprises determining at least one of a current Doppler frequency, a code phase of the first of the plurality of satellites, a position of the first of the plurality of satellites, and timing information about the first of the plurality of satellites.

21. A satellite navigation receiver comprising:

a pre-FFT unit operable to;

receive input samples of an RF signal from one or more satellites of a plurality of satellites in a satellite navigation system, wherein the RF signal is a combination of signals from the one or more satellites of the satellite navigation system;

compensate for Doppler shift in a first set of the input samples to yield a compensated first set of samples, wherein the first set of the input samples correspond to the input samples received within a first time interval;

an FFT engine operable to;

calculate a frequency domain representation of the compensated first set of samples;

a coarse acquisition code generator operable to;

generate a coarse acquisition code associated with at least one of the plurality of satellites in the satellite navigation system;

a coarse acquisition code processing unit operable to;

insert a first zero into the coarse acquisition code as a center bit and a second zero into the coarse acquisition code as an end bit such that a spacing between the first zero and the second zero is a predetermined number of samples and a length of the coarse acquisition code equals a pre-defined length;

calculate a frequency domain representation of the coarse acquisition code of the pre-defined length for determining whether the RF signal was transmitted by the at least one of the plurality of satellites;

an IFFT processing unit operable to;

determine a time domain representation of a result of multiplying the frequency domain representation of the compensated first set of samples and the frequency domain representation of the coarse acquisition code; and

a peak detection unit operable to;

identify a peak correlation value from the time domain representation; and

determine information about the at least one of the plurality of satellites based on the peak correlation value.

22. The satellite navigation receiver of claim 21, wherein the FFT engine operable to calculate the frequency domain representation of the compensated first set of samples further comprises the FFT engine operable to:

insert zeros into the compensated first set of samples such that a length of the compensated first set of samples equals the pre-defined length associated with the coarse acquisition code; and

calculate the frequency domain representation of the compensated first set of samples of the pre-defined length.

23. The satellite navigation receiver of claim 21, further comprising:

the coarse acquisition code processing unit operable to calculate a frequency domain representation of a coarse acquisition code of a second of the plurality of satellites for determining whether the RF signal was transmitted by at least the second of the plurality of satellites;

the IFFT processing unit operable to;

determine a second time domain representation of a result of multiplying the frequency domain representation of the compensated first set of samples and the frequency domain representation of the coarse acquisition code of the second of the plurality of satellites; and

the peak detection unit operable to;

identify a second peak correlation value from the second time domain representation; and

determine information about the second of the plurality of satellites based on the second peak correlation value.

24. The satellite navigation receiver of claim 21, further comprising:

the pre-FFT unit operable to;

compensate for the Doppler shift in a second set of the input samples to yield a compensated second set of samples, wherein the second set of the input samples correspond to the input samples received within a second time interval;

sum the compensated first set of samples with the compensated second set of samples to yield a pre-summed set of samples and to improve signal to noise ratio of the pre-summed set of samples;

the FFT engine operable to;

calculate a frequency domain representation of the pre-summed set of samples;

the IFFT processing unit operable to;

determine a second time domain representation of a result of multiplying the frequency domain representation of the pre-summed set of samples and the frequency domain representation of the coarse acquisition code;

the peak search module operable to;

identify a second peak correlation value from the second time domain representation; and

determine the information about the at least one of the plurality of satellites based on the second peak correlation value.

25. The satellite navigation receiver of claim 21, wherein the pre-FFT unit operable to compensate for the Doppler shift in the first set of the input samples further comprises the pre-FFT unit operable to:

calculate an estimated value of the Doppler shift; and

compensate for the Doppler shift by shifting the first set of the input samples by the estimated value of the Doppler shift.

26. The satellite navigation receiver of claim 21, further comprising:

the IFFT processing unit operable to;

calculate a second time domain representation of a result of multiplying the frequency domain representation of a compensated second set of samples and the frequency domain representation of the coarse acquisition code associated with the at least one of the plurality of satellites, wherein the compensated second set of samples correspond to the input samples received within a second time interval and compensated for the Doppler shift;

accumulate the first time domain representation with the second time domain representation to improve a signal to noise ratio and generate a significant peak correlation value; and

the peak detection unit operable to;

identify the peak correlation value in response to the inverse fast Fourier transform processing unit accumulating the first time domain representation with the second time domain representation.

27. The satellite navigation receiver of claim 21, wherein the peak detection unit operable to determine information about the at least one of the plurality of the satellites based on the peak correlation value comprises the peak detection unit operable to determine at least one of a current Doppler frequency, a code phase of the at least one of the plurality of satellites, a position of the at least one of the plurality of satellites, and timing information about the at least one of the plurality of satellites.

28. The satellite navigation receiver of claim 21, further comprising the pre-FFT unit operable to:

store the input samples of the RF signal in an RF buffer, wherein the input samples are associated with an input data rate;

retrieve the first set of input samples, at an output data rate, from the RF buffer to compensate for the Doppler shift in the first set of the input samples such that the output data rate is greater than the input data rate.

29. The satellite navigation receiver of claim 28, further comprising:

the pre-FFT unit operable to compensate each of a plurality of instances of the first set of input samples by a distinct Doppler shift; and

the peak search module operable to correlate the plurality of instances of the first set of input samples and the coarse acquisition code associated with the at least one of the plurality of satellites to determine information about the at least one of the plurality of satellites.

34. The satellite navigation receiver of claim 21, further comprising:

the pre-FFT unit operable to;

compensate for the Doppler shift in a second set of the input samples to yield a compensated second set of samples, wherein the second set of the input samples correspond to the input samples received within a second time interval;

sum the compensated first set of samples with the compensated second set of samples to yield a pre-summed set of samples and to improve signal to noise ratio of the pre-summed set of samples;

store the pre-summed set of samples in a pre-FFT buffer;

the FFT engine operable to;

obtain the pre-summed set of samples from the pre-FFT buffer;

calculate a frequency domain representation of the pre-summed set of samples;

the IFFT processing unit operable to;

determine a second time domain representation of a result of multiplying the frequency domain representation of the pre-summed set of samples and the frequency domain representation of the coarse acquisition code;

the peak search module operable to;

identify a second peak correlation value from the second time domain representation; and

determine the information about the first of the plurality of satellites based on the second peak correlation value.

30. One or more non-transitory machine-readable storage media, having instructions stored therein, which when executed by one or more processors causes the one or more processors to perform operations that comprise:

receiving input samples of an RF signal from one or more satellites of a plurality of satellites in a satellite navigation system, wherein the RF signal is a combination of signals from the one or more satellites of the satellite navigation system;

compensating for Doppler shift in a first set of the input samples to yield a compensated first set of samples, wherein the first set of the input samples correspond to the input samples received within a first time interval;

calculating a frequency domain representation of the compensated first set of samples;

generating a coarse acquisition code associated with at least one of the plurality of satellites in the satellite navigation system;

inserting a first zero into the coarse acquisition code as a center bit and a second zero into the coarse acquisition code as an end bit such that a spacing between the first zero and the second zero is a predetermined number of samples and a length of the coarse acquisition code equals a pre-defined length;

calculating a frequency domain representation of the coarse acquisition code of the pre-defined length for determining whether the RF signal was transmitted by the at least one of the plurality of satellites;

determining a time domain representation of a result of multiplying the frequency domain representation of the compensated first set of samples and the frequency domain representation of the coarse acquisition code;

identifying a peak correlation value from the time domain representation; and

determining information about the at least one of the plurality of satellites based on the peak correlation value.

31. The machine-readable storage media of claim 30, wherein the pre-defined length is a length of the compensated first set of samples.

32. The machine-readable storage media of claim 30, wherein said operation of determining information about the at least one of the plurality of the satellites based on the peak correlation value comprises determining at least one of a current Doppler frequency, a code phase of the at least one of the plurality of satellites, a position of the at least one of the plurality of satellites, and timing information about the at least one of the plurality of satellites.

33. The machine-readable storage media of claim 30, wherein the operations further comprise:

calculating a frequency domain representation of a coarse acquisition code of a second of the plurality of satellites for determining whether the RF signal was transmitted by at least the second of the plurality of satellites;

determining a second time domain representation of a result of multiplying the frequency domain representation of the compensated first set of samples and the frequency domain representation of the coarse acquisition code of the second of the plurality of satellites;

identifying a second peak correlation value from the second time domain representation; and

determining information about the second of the plurality of satellites based on the second peak correlation value.