Rapid acquisition methods and apparatus for GPS signals

• US 7,702,002 B2
• Filed: 09/07/2004
• Issued: 04/20/2010
• Est. Priority Date: 01/28/2004
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Krasner, Norman F.
• Primary Examiner(s): Liu; Shuwang
• Assistant Examiner(s): HUANG, DAVID S
• Application Number:
  US10/936,177
• Publication Number:
  US 20050163201A1
• Time in Patent Office: 2,051 Days
• Field of Search: 375/150, 701/200, 701/213, 701/214
• US Class Current: 375/150
• CPC Class Codes: G01S 19/09 providing processing capability normally carried out by the receiver
• CPC Class Codes: G01S 19/25 involving aiding data received from a cooperating element, e.g. assisted GPS
• CPC Class Codes: G01S 19/29 carrier including Doppler, related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/30 code related G01S19/246 takes precedence
• CPC Class Codes: H04B 1/707 using direct sequence modulation
• CPC Class Codes: H04B 2201/70715 with application-specific features

Abstract

A method and apparatus for receiving a signal from transmitters such as GPS satellites, for fixing the location of the receiver. Each of the transmitted signals includes a unique periodically-repeating sequence. A received signal is stored by the receiver for at least two repetitions of the periodically-repeating sequence. FFT operations are performed, and the resulting data frequency samples are pruned responsive to a hypothesized residual frequency, a procedure which significantly reduces the total number of subsequent calculations and therefore significantly reduces processing time. A correlation series is determined from the pruned samples and reference frequency samples corresponding to a hypothesized transmitter. If a match is found in the examination of this series, a code phase offset is determined; if not the process is repeated with another hypothesized residual frequency. Multiple correlation series similarly obtained may also be incoherently combined prior to this examination. The apparatus and method disclosed herein is particularly useful for combined position location and communication systems, especially those that are unsynchronized, such as assisted GPS (“A-GPS”) utilized on GSM and UMTS cellular telephone systems.

Claims

1. A method of receiving a signal with a receiver, said signal transmitted at a predetermined carrier frequency from one of a plurality of transmitters, said signal including a waveform modulated according to a periodically-repeating pseudonoise (PN) sequence that uniquely identifies the transmitter that sent the signal, said signal used in determining a location of the receiver, said method comprising:

at the receiver, receiving electromagnetic energy in the vicinity of said carrier frequency, and digitizing said energy for a predefined period of time;

hypothesizing one of said plurality of transmitters and an associated hypothesized signal and providing a set of reference frequency samples corresponding to said hypothesized signal;

hypothesizing a first residual frequency;

selecting from said digitized energy a first subset of data of length at least equal to two repetitions of said periodically-repeating PN sequence, thereby defining a first data block;

responsive to said first data block, calculating a first set of data frequency samples;

pruning said first set of data frequency samples responsive to said hypothesized first residual frequency to provide a periodically-spaced first subset of said first set of data frequency samples, wherein said periodically-spaced first subset includes a plurality of samples having indices spaced relative to one another by an integer K, wherein K is the number of PN sequences in said first data block;

computing a first correlation series from said periodically-spaced first subset of said first set of data frequency samples and said set of reference frequency samples;

computing a first final correlation series comprising at least said first correlation series; and

examining said first final correlation series to determine whether a matched condition occurs between said transmitted signal and said hypothesized signal.

2. The meted of claim 1 further comprising:

selecting from said digitized energy a second subset of data of length at least equal to two repetitions of said periodically-repeating sequences, thereby defining a second data block;

responsive to said second data block, calculating a second set of data frequency samples;

pruning said second set of data frequency samples responsive to said hypothesized first residual frequency to provide a periodically-spaced second subset of said second set of data frequency samples; and

computing a second correlation series from said second subset of data frequency samples and said set of reference frequency samples;

wherein computing said first final correlation series comprises computing at least said first correlation series and said second correlation series.

3. The method of claim 2 wherein said computing said first final correlation series comprises at least detecting and combining said first and said second correlation series.

4. The method of claim 1 further comprising frequency translating said electromagnetic energy to a lower frequency before digitizing said energy.

5. The method of claim 1 wherein said periodically-spaced first subset comprises a plurality of data frequency samples spaced relative to one another in Hertz by a repetition rate of said periodically-repeating sequence.

6. The method of claim 1 wherein said pruning includes interpolating between said first set of data frequency samples.

7. The method of claim 1 wherein said providing said set of reference frequency samples includes performing a DFT operation upon said PN sequence.

8. The method of claim 1 wherein said computing the first correlation includes multiplying said first subset of said first set of data frequency samples with said set of reference frequency samples, to form a set of weighted frequency samples.

9. The method of claim 8 wherein said computing the first correlation includes performing an inverse DFT upon said set of weighted frequency samples, in order to produce said first correlation series.

10. The method of claim 1 wherein said transmitters comprise a plurality of GPS satellites that transmit GPS signals at a GPS frequency, each GPS satellite transmitting a unique periodically-repeating sequence.

11. The method of claim 1 wherein said examining said first final correlation series comprises searching said first final correlation series to identify the presence of a GPS signal and if the presence of the GPS signal is identified, then determining a PN code phase offset and determining a time of arrival of the GPS signal at said receiver.

12. The method of claim 11 further comprising utilizing said time of arrival information to determine a position of said receiver.

13. The method of claim 1 wherein said first data block has a size that corresponds to an integral number of repetitions of said periodically-repeating sequences.

14. The method of claim 13 wherein said first data block has a size within a range of five to twenty repetitions of said periodically-repeating sequences.

15. The method of claim 1 further comprising:

hypothesizing a second residual frequency;

pruning said first set of data frequency samples responsive to said hypothesized second residual frequency to provide a periodically-spaced second subset of data frequency samples;

computing a second correlation series from said second subset of data frequency samples and said set of reference frequency samples;

computing a second final correlation series comprising at least said second correlation series; and

examining said second final correlation series to determine whether a matched condition occurs between said transmitted signal and said hypothesized signal.

16. A method of processing a signal that has been transmitted at a predetermined carrier frequency from one of a plurality of transmitters and that includes a waveform modulated according to a repeating pseudonoise (PN) sequence that identifies said one transmitter, the method comprising:

receiving electromagnetic energy in a vicinity of said carrier frequency, and digitizing said energy for a predefined period of time;

hypothesizing an identity of one of said transmitters and determining a signal associated therewith;

providing a set of reference frequency samples corresponding to said determined signal;

hypothesizing a first residual frequency of said determined signal;

selecting from said digitized energy a first subset of data of length at least equal to two repetitions of said repeating PN sequence, thereby defining a first data block;

responsive to said first data block, calculating a first set of data frequency samples using said first subset of data;

pruning said first set of data frequency samples using said hypothesized first residual frequency to produce a periodically-spaced first subset of said first set of data frequency samples, wherein said periodically-spaced first subset includes a plurality of samples having indices spaced relative to one another by an integer K, wherein K is the number of PN sequences in said first data block; and

computing a first final correlation series using as an input at least a first correlation series from said periodically-spaced first subset of said first set of data frequency samples and said set of reference frequency samples to produce an indication of whether a matched condition exists between said transmitted signal and said hypothesized signal.

17. The method of claim 16 further comprising:

selecting from said digitized energy a second subset of data of length at least equal to two repetitions of said PN sequence;

calculating a second set of data frequency samples using said second subset of data; and

pruning said second set of data frequency samples responsive to said hypothesized first residual frequency to provide a subset of said second set of data frequency samples;

wherein said computing comprises computing the first final correlation series using as an input at least

said first correlation series computed from said first subset of data frequency samples and said set of reference frequency samples;

a second correlation series computed from said second subset of data frequency samples; and

said set of reference frequency samples;

to produce said indication of whether a matched condition exists between said transmitted signal and said hypothesized signal.

18. The method of claim 17 wherein said computing comprises at least detecting and combining said first and said second correlation series.

19. The method of claim 16 further comprising frequency translating said electromagnetic energy to a lower frequency before digitizing said energy.

20. The method of claim 16 wherein said first subset comprises a plurality of data frequency samples spaced relative to one another in Hertz by a repetition rate of said PN sequence.

21. The method of claim 16 wherein said pruning includes interpolating between said first set of data frequency samples.

22. The method of claim 16 wherein said providing set of reference frequency samples includes performing a DFT operation upon said PN sequence.

23. The method of claim 16 wherein said computing includes multiplying said first subset of said first set of data frequency samples with said set of reference frequency samples, to form a set of weighted frequency samples.

24. The method of claim 23 wherein said computing includes performing an inverse DFT upon said set of weighted frequency samples, in order to produce said first correlation series.

25. The method of claim 16 wherein said transmitters comprise a plurality of GPS satellites that transmit GPS signals at a GPS frequency, each GPS satellite transmitting a unique PN sequence.

26. The method of claim 16 wherein said first final correlation series is searched to identify the presence of a GPS signal, and, if the presence of the GPS signal is identified, then determining a PN code phase offset, and determining a time of arrival of the GPS signal at said receiver.

27. The method of claim 16 further comprising:

hypothesizing a second residual frequency;

pruning said first set of data frequency samples responsive to said hypothesized second residual frequency to provide a second subset of data frequency samples;

computing a second correlation series from said second subset of data frequency samples and said set of reference frequency samples;

computing a second final correlation series comprising at least said second correlation series; and

examining said second final correlation series to determine whether a matched condition occurs between said transmitted signal and said hypothesized signal.

28. The method of claim 27 wherein said first data block has a size within a range of five to twenty repetitions of said PN sequence.

29. The method of claim 16 further comprising utilizing time of arrival information to determine a position of said receiver.

30. A method of receiving at a mobile station a GPS signal transmitted at a GPS frequency from one of a plurality of satellite transmitters in earth orbit, to identify the satellite that transmitted the GPS signal and to determine a time of arrival at said mobile station of the GPS signal, said time of arrival used in determining the location of the mobile station, said GPS signal including a plurality of repetitions of a periodically-repeated PN sequence that uniquely identify the satellite that transmitted the GPS signal, the method comprising:

at the mobile station, observing and digitizing a signal in the vicinity of the GPS frequency for a predefined period of time;

hypothesizing a GPS satellite and providing a set of reference frequency samples corresponding to said hypothesized satellite;

hypothesizing a first residual frequency;

selecting from said digitized signal a first subset of data of length at least equal to two repetitions of said periodically-repeating PN sequence, thereby defining a first data block;

responsive to said first data block, calculating a first set of data frequency samples;

pruning said first set of data frequency samples responsive to said hypothesized first residual frequency to define a periodically-spaced first subset of said first set of data frequency samples wherein said periodically-spaced first subset includes a plurality of samples having indices spaced relative to one another by an integer K, wherein K is the number of repetitions of said PN sequence in said first data block;

computing a first correlation series from said periodically-spaced first subset of said first set of data frequency samples and said set of reference frequency;

selecting from said digitized signal a second subset of data of length at least equal to two repetitions of said periodically-repeating PN sequence, thereby defining a second data block;

responsive to said second data block, calculating a second set of data frequency samples;

pruning said second set of data frequency samples responsive to said hypothesized first residual frequency to define a periodically-spaced second subset of said second set of data frequency samples wherein said periodically-spaced second subset includes a plurality of samples having indices spaced relative to one another by an integer K, wherein K is the number of repetitions of said PN sequence in said second data block;

computing a second correlation series from said periodically-spaced second subset of said second set of data frequency samples and said set of reference frequency samples;

forming a final correlation series comprising at least a detecting and combining of said first correlation series and said second correlation series; and

searching said final correlation data set to identify the presence of the GPS signal and if the presence of the GPS signal is identified, then determining a PN code phase offset.

31. The method of claim 30 wherein said providing said set of reference frequency samples includes performing a DFT operation upon at least one repetition of said periodically-repeated PN sequence.

32. The method of claim 30 wherein said computing the first correlation series further comprises multiplying said first subset of said first set of data frequency samples with said set of reference frequency samples, to form a set of weighted frequency samples, and performing an inverse DFT upon said set of weighted frequency samples.

33. The method of claim 30 further comprising utilizing said determined PN code phase offset to compute a position of said mobile station.

34. The method of claim 30 wherein said first data block has a size that corresponds to an integral number of repetitions of said periodically-repeating sequences.

35. The method of claim 34 wherein said first data block has a size within a range of five to twenty repetitions of said periodically-repeating sequences.

36. A method of processing a signal that has been transmitted from one of a plurality of transmitters, said signal containing a waveform modulated by a repeating PN sequence, the method comprising:

hypothesizing a signal associated with one of said transmitters and a carrier frequency thereof;

hypothesizing a residual frequency;

extracting a first subset of data of length at least equal to two repetitions of said repeating PN sequence from electromagnetic energy received in a vicinity of a carrier frequency of said signal to be processed;

pruning a first set of data frequency samples, computed from said first subset of data, in response to said hypothesized residual frequency, to produce a subset of said first set of data frequency samples, wherein said subset of said first set of data frequency samples comprises a plurality of samples having indices spaced relative to one another by an integer K, wherein K is the number of repetitions of said repeating PN sequence in said extracted first subset of data;

computing a final correlation series using as inputs at least a correlation series determined from said subset of said first set of data frequency samples and a set of reference frequency samples corresponding to said hypothesized signal; and

examining said final correlation series to determine whether a matched condition exists between said transmitted signal and said hypothesized signal.

37. A mobile station that includes a position location system that receives a signal transmitted at a predetermined frequency from one of a plurality of transmitters, said transmitted signal including a periodically-repeating sequence that uniquely identifies the transmitter that sent the signal, the method comprising:

means for observing and digitizing electromagnetic energy at the predetermined frequency for a predefined period of time;

means for hypothesizing one of said plurality of transmitters and providing a set of reference frequency samples corresponding to a hypothesized signal transmitted from said hypothesized transmitter;

means for hypothesizing a residual frequency;

means for selecting a first portion of said digitized electromagnetic energy of length at least equal to two repetitions of said periodically-repeating sequences, thereby defining a first data block;

means, responsive to said first data block, for calculating a first set of data frequency samples;

means for pruning said first set of data frequency samples responsive to said hypothesized residual frequency to provide a periodically-spaced subset of said first set of data frequency samples, wherein said periodically-spaced subset comprises a plurality of samples having indices spaced relative to one another by an integer K, wherein K is the number of repetitions of said periodically-repeating sequence in said first data block;

means for computing a first correlation series from said periodically-spaced subset of said first set of data frequency samples and said sat of reference frequency samples;

means for computing a final correlation series comprising at least said first correlation series; and

means for searching said final correlation series to identify whether a signal match condition occurs between said hypothesized signal and said received signal and if a matched condition is found between said hypothesized signal and said received signal, then determining timing information.

38. The mobile station of claim 37 wherein said periodically-spaced subset comprises a plurality of samples having adjacent samples spaced relative to one another in Hertz by a repetition rate of said periodically-repeating sequence.

39. The mobile station of claim 37 wherein said pruning means includes means for interpolating between said first set of data frequency samples.

40. The mobile station of claim 37 wherein said mobile station comprises memory for storing said set of reference frequency samples.

41. The mobile station of claim 37 wherein said means for computing the final correlation series includes means for incoherently combining said first correlation series with a second correlation series computed from a second portion of said digitized electromagnetic energy, distinct from said first portion.

42. The mobile station of claim 37 wherein said computing the first correlation series includes means for multiplying said first subset of said first set of data frequency samples with said set of reference frequency samples, to form a set of weighted frequency samples and means for performing an inverse DFT upon said set of weighted frequency samples, in order to produce said first correlation series.

43. The mobile station of claim 37 wherein said transmitters comprise a plurality of GPS satellites that transmit GPS signals at a GPS frequency, each GPS satellite transmitting a unique periodically-repeating sequence.

44. The mobile station of claim 37 wherein said first data block has a size that corresponds to an integral number of repetitions of said periodically-repeating sequences.

45. The method of claim 37 further comprising a GPS location system for utilizing said timing information to determine a position of said mobile station.