Method and apparatus for adaptively processing GPS signals in a GPS receiver

• US 6,133,873 A
• Filed: 06/03/1998
• Issued: 10/17/2000
• Est. Priority Date: 06/03/1998
• Status: Expired due to Term

• Current Assignee: Snaptrack Incorporated (Qualcomm, Inc.)
• Original Assignee: Snaptrack Incorporated (Qualcomm, Inc.)
• Inventors: Krasner, Norman F.
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Mull, Fred H.
• Application Number:
  US09/089,924
• Time in Patent Office: 867 Days
• Field of Search: 342/357.12
• US Class Current: 342/357.59
• CPC Class Codes: G01S 19/235 Calibration of receiver components
• CPC Class Codes: G01S 19/28 Satellite selection
• CPC Class Codes: G01S 19/34 Power consumption
• CPC Class Codes: G01S 5/0027 of actual mobile position, i.e. position determined on mobile
• CPC Class Codes: G01S 5/0036 of measured values, i.e. measurement on mobile and position calculation on base station
• CPC Class Codes: H04L 2027/0034 using hypothesis testing

Abstract

A method and apparatus is disclosed for adaptively processing Global Positioning System (GPS) signals in a GPS receiver. An adaptive method of processing GPS signals optimizes the initial acquisition of GPS signals by performing the search using three separate parameters. These parameters include satellite number, Doppler information, and integration time. A block processing method of GPS signal processing is performed for particular in-view satellites over particular time intervals and for each of a set of hypothesized Doppler frequencies. Each parameter is optimized such that the GPS signal acquisition operation for a location fix is performed in a short period of time.

Claims

1. A method of determining pseudoranges in a global positioning system (GPS) receiver, said method comprising the steps of:

receiving a plurality of signals from a plurality of in-view GPS satellites;

storing said plurality of signals in a digital snapshot memory to produce stored data;

selecting a first satellite for processing from said plurality of in-view satellites based on a position of said first satellite relative to other satellites of said plurality of in-view GPS satellites;

selecting a first integration time period that determines a portion of said stored data to process;

selecting a first Doppler frequency offset with which to process said portion of said stored data to determine a pseudorange for said first satellite; and

processing said portion of said stored data from said first satellite for said Doppler frequency offset.

2. The method of claim 1 wherein said first satellite is positioned more directly above said GPS receiver than said other satellites of said plurality of in-view satellites.

3. The method of claim 1 further comprising the steps of:

processing said stored data in a digital signal processor by,

breaking said stored data into a series of contiguous blocks whose durations are equal to a multiple of the frame period of pseudorandom (PN) codes contained within said signal;

for each block, creating a compressed block of data with length equal to the duration of a pseudorandom code period by coherently adding together successive subblocks of data, said subblocks having a duration equal to one PN frame; and

for each compressed block, performing a matched filtering operation to determine relative timing between the received PN code contained within the block of data and a locally generated PN reference signal, said matched filtering operation utilizing fast convolution techniques, and said matched filtering operation producing an output.

4. The method of claim 3 wherein said successive subblocks of data are coherently adding together during said first integration time period.

5. The method of claim 4 further comprising the steps of:

selecting said first Doppler frequency offset from a plurality of Doppler frequency offsets within a range of Doppler frequency offsets;

comparing said output of said matched filtering operation with a noise threshold;

processing said portion of said stored data from said first satellite for one or more additional Doppler frequency offsets within said range of Doppler frequency offsets if said output exceeds said noise threshold; and

comparing the signal strength of said output with the signal strength of outputs produced by processing said portion of said stored data for said one or more additional Doppler frequency offsets.

6. The method of claim 5 further comprising the step of terminating said method for said satellite if said signal strength for said output exceeds said signal strength of said outputs produced by said one or more additional Doppler frequency offsets, and if said signal strength for said output exceeds a predetermined threshold level.

7. The method of claim 6 further comprising the step of determining said pseudorange by performing a detection operation on the products created from said matched filtering operation and combining said detected data for all blocks into a single block of data by adding together said blocks of detected data to produce a peak, the location of said peak being determined using digital interpolation methods and corresponding to said pseudorange.

8. The method of claim 7 wherein said matched filtering operation comprises the step of performing a convolution of the compressed block'"'"'s data against the pseudorandom sequence (PRS) of said satellite, said convolution being performed using said fast convolution algorithms to produce a product of the convolution.

9. The method of claim 8 wherein said fast convolution algorithm is a Fast Fourier Transform and the product of said convolution is produced by computing the forward transform of said compressed block and multiplying the forward transform of said compressed block by a restored representation of the forward transform of the PRS to produce a first result and then performing an inverse transformation of said first result to recover said product.

10. A method of determining pseudoranges in a global positioning system (GPS) receiver, said method comprising the steps of:

receiving a plurality of GPS signals from a plurality of in-view GPS satellites;

storing said plurality of GPS signals in a memory;

selecting for processing a first satellite from said plurality of in-view satellites based on a position of said first satellite relative to other satellites of said plurality of in-view GPS satellites, said GPS signals comprising pseudorandom sequences;

selecting a first integration time period that determines a portion of data in said memory to process;

selecting a first Doppler frequency offset with which to process said portion of data to determine a pseudorange for said first satellite; and

computing a pseudorange for said first satellite by performing a plurality of fast convolutions on a corresponding plurality of blocks of data within said portion of data to provide a plurality of corresponding results of each fast convolution and summing a plurality of mathematical representations of said plurality of corresponding results to obtain a first position information.

11. The method of claim 10 further comprising the steps of:

selecting said first Doppler frequency offset from a plurality of Doppler frequency offsets within a range of Doppler frequency offsets; and

performing said step of computing a pseudorange by processing a signal from said first satellite within said portion of data for said first Doppler frequency offset.

12. The method of claim 11 further comprising performing said step of computing a pseudorange by processing said signal from said first satellite within said portion of data for each remaining Doppler frequency offset of said plurality of Doppler frequency offsets within said range of Doppler frequency offsets, each processing operation for said each remaining Doppler frequency offset producing a corresponding output signal.

13. The method of claim 12 further comprising the steps of:

comparing each said corresponding output signal with a noise threshold level to produce one or more intermediate outputs;

comparing each intermediate output with other intermediate outputs of said one or more intermediate outputs to determine a maximum intermediate output; and

comparing said maximum intermediate output with an output threshold value.

14. The method of claim 13 further comprising the steps of:

increasing said first integration time period to a second integration time period that corresponds to a larger portion of data in said memory if said maximum intermediate output does not exceed said output threshold value; and

performing said step of computing pseudoranges by processing said signals from said first satellite over said larger portion of data and for said first Doppler frequency offset.

15. The method of claim 13 further comprising the step of terminating said processing operation for said first satellite if said maximum intermediate output exceeds said output threshold value.

16. The method of claim 15 further comprising the steps of:

processing a GPS signal from a second satellite of said plurality of in-view GPS satellites, said second satellite selected from said plurality of in-view satellites based on a position of said second satellite relative to other satellites of said plurality of in-view GPS satellites; and

computing a pseudorange by processing said GPS signal from said second satellite over said portion of data and for a Doppler frequency offset derived from said maximum intermediate output.

17. The method of claim 13 wherein said first satellite is positioned more directly above said GPS receiver than said other satellites of said plurality of in-view satellites.

18. The method of claim 13 wherein said step of performing said plurality of fast convolutions on said corresponding plurality of blocks of data representing said GPS signals is performed using Fast Fourier Transform processes.

19. A method of determining pseudoranges in a global positioning system (GPS) receiver, said method comprising the steps of:

receiving GPS signals from a plurality of in-view GPS satellites, said GPS signals comprising pseudorandom sequences;

storing said GPS signals in a memory;

selecting for processing a first satellite from said plurality of GPS satellites;

selecting an integration time period that determines a portion of data in said memory to process;

selecting a first Doppler frequency offset with which to process said signals to determine a pseudorange for said first satellite; and

computing pseudoranges for said GPS satellites by performing a plurality of fast convolutions on a corresponding plurality of blocks of data within said portion of data to provide a plurality of corresponding results of each fast convolution and summing a plurality of mathematical representations of said plurality of corresponding results to obtain a first position information.

20. The method of claim 19 further comprising the steps of:

selecting said first Doppler frequency offset from a plurality of Doppler frequency offsets within a range of Doppler frequency offsets; and

performing said step of computing pseudoranges by processing said signal from said first satellite over said portion of data and for said first Doppler frequency offset.

21. The method of claim 20 further comprising performing said step of computing pseudoranges by processing said signal from said first satellite over said portion of data for each remaining Doppler frequency offset of said plurality of Doppler frequency offsets within said range of Doppler frequency offsets, each processing operation for said each remaining Doppler frequency offset producing a corresponding output signal.

22. The method of claim 21 further comprising the steps of:

comparing each said corresponding output signal with a noise threshold level to produce one or more intermediate outputs;

comparing each intermediate output with other intermediate outputs of said one or more intermediate outputs to determine a maximum intermediate output; and

comparing said maximum intermediate output with an output threshold value.

23. The method of claim 22 further comprising the step of terminating said processing operation for said first satellite if said maximum intermediate output exceeds said output threshold value.

24. The method of claim 22 further comprising the steps of:

processing a GPS signal from a second satellite of said plurality of in-view GPS satellites if said maximum intermediate output does not exceed said output threshold value; and

performing said step of computing pseudoranges by processing said signal from said second satellite over said portion of data and for a first Doppler frequency offset of said second second satellite.

25. The method of claim 24 wherein said step of performing said plurality of fast convolutions on said corresponding plurality of blocks of data within said portion of data is performed using Fast Fourier Transform processes.

26. A GPS receiver apparatus comprising:

an antenna for receiving GPS signals at an RF frequency from a plurality of in-view satellites;

a downconverter coupled to said antenna, said downconverter reducing the RF frequency of said received GPS signals to an intermediate frequency (IF) to produce a baseband signal;

a digitizer coupled to said downconverter and receiving said baseband signal, said digitizer sampling said baseband signal at a predetermined rate to produce a sampled baseband signal;

a memory coupled to said digitizer, said memory storing a data record of said sampled baseband signal during a predetermined time period; and

a digital signal processor (DSP) coupled to said memory, said DSP performing fast convolution operations, wherein said DSP processes a portion of said data record to process a signal from a first satellite of said plurality of in-view satellites by performing a plurality of fast convolution operations on a corresponding plurality of blocks of said portion of said data record to provide a plurality of corresponding results of each fast convolution operation and summing a plurality of mathematical representations of said plurality of corresponding results to obtain a position information, and wherein said DSP is further operable to perform said plurality of fast convolution operations for a first Doppler frequency offset, said first Doppler frequency offset being selected from a plurality of Doppler frequency offsets within a range of Doppler frequency offsets.

27. The GPS receiver apparatus of claim 26 wherein said first satellite of said plurality of in-view satellites is selected based on a position of said GPS receiver apparatus relative to other satellites of said plurality of in-view satellites.

28. The GPS receiver apparatus of claim 27 wherein said DSP is further operable to:

perform said plurality of fast convolution operations for each remaining Doppler frequency offset of said plurality of Doppler frequency offsets within said range of Doppler frequency offsets; and

compare the outputs from each of said plurality of fast convolution operations with a noise threshold level.

29. The GPS receiver apparatus of claim 28 further operable to:

increase said portion of data to a larger portion of data if none of said outputs exceeds said noise threshold level; and

perform said plurality of fast convolution operations on a corresponding plurality of blocks within said larger portion of data.

30. The GPS receiver apparatus of claim 28 further operable to:

process a GPS signal from a second satellite of said plurality of in-view GPS satellites if none of said outputs exceeds said noise threshold level; and

perform said plurality of fast convolution operations on a corresponding plurality of blocks within said portion of data and for said first Doppler frequency offset.

31. The GPS receiver apparatus of claim 28 further comprising a communication antenna and a communication receiver coupled to said communication antenna and to said DSP, said communication receiver operable to receive a data signal containing satellite data information over a communication link.

32. The GPS receiver apparatus of claim 31 wherein said position information is transmitted to a basestation over said communication link.

33. A method of determining pseudoranges in a global positioning system (GPS) receiver, said method comprising the steps of:

receiving a plurality of GPS signals from a plurality of in-view GPS satellites;

storing said plurality of GPS signals in a memory;

selecting for processing a first satellite from said plurality of in-view satellites based on a position of said first satellite relative to other satellites of said plurality of in-view GPS satellites, said GPS signal comprising pseudorandom sequences;

selecting a first integration time period that determines a first portion of data in said memory to process;

selecting a first Doppler frequency offset with which to process said first portion of said data to determine a pseudorange for said first satellite;

computing a pseudorange for said first satellite by performing a series of fast convolutions on a corresponding plurality of blocks of data within said first portion of data to provide a plurality of corresponding output values of each fast convolution; and

comparing each output value of said corresponding output values to a pre-defined noise threshold.

34. The method of claim 33 further comprising the steps of:

determining whether an output value of said corresponding output value exceeds said pre-defined noise threshold; and

selecting a second integration time period that determines a second portion of data in said memory to process, if no output values of said corresponding output values exceeds said pre-defined threshold value.

35. The method of claim 34 wherein said second integration time period is longer than said first integration time period.

36. The method of claim 35 further comprising the steps of:

determining whether said second integration time period exceeds a pre-defined maximum time period; and

computing a pseudorange for said first satellite by performing a series of fast convolutions on a corresponding plurality of blocks of data within said second portion of data to provide a plurality of corresponding output values of each fast convolution, if said second integration time period does not exceed said pre-defined maximum time period.

37. The method of claim 33 further comprising the steps of:

determining whether an output value of said corresponding output values exceeds said pre-defined noise threshold; and

selecting a second Doppler frequency offset with which to process said first portion of said data to determine a pseudorange for said first satellite, if at least one output value of said corresponding output values exceeds said pre-defined threshold value.

38. The method of claim 36 wherein said first satellite is positioned more directly above said GPS receiver than said other satellites of said plurality of in-view satellites.

39. The method of claim 38 wherein said step of performing said plurality of fast convolutions on said corresponding blocks of data within said first portion of data is performed using Fast Fourier Transform processes.

40. The method of claim 36 wherein said step of performing said plurality of fast convolutions on said corresponding blocks of data within said second portion of data is performed using Fast Fourier Transform processes.

41. A method of determining pseudoranges in a global positioning system (GPS) receiver, said method comprising:

receiving a plurality of signals from a plurality of in-view GPS satellites;

selecting a first satellite for processing a first signal from said plurality of in-view satellites;

selecting a first integration time period;

selecting a set of Doppler frequency offsets;

processing said first signal over said first integration time period and said set of Doppler frequency offsets to produce a first set of outputs;

comparing said first set of outputs with a first detection threshold in order to form a first set of detected outputs, corresponding to any of said first set of outputs that exceed said first detection threshold;

associating time indices of said first set of detected outputs with a pseudorange of said first signal and associating amplitudes of said first set of detected outputs with a signal strength of said first signal;

selecting a second integration time period, which is longer than the first integration time period, if said first set of detected outputs contains no members;

processing said first signal over said second integration time period and said set of Doppler frequency offsets to a produce a second set of outputs;

comparing said second set of outputs with a second detection threshold in order to form a second set of detected outputs, corresponding to any of said second set of outputs that exceed said second detection threshold;

associating time indices of said second set of detected outputs with a pseudorange of said first signal and associating amplitudes of said second set of detected outputs with the signal strength of said first signal.

42. A method as in claim 41 wherein said processing of said first signal over said first integration time period further comprise storing said plurality of signals in a digital memory to produce stored data.

43. A method of determining pseudoranges in a global positioning system (GPS) receiver said method comprising:

receiving a plurality of signals from a plurality of in-view GPS satellites;

selecting a first integration time period,

selecting a set of at least two in view GPS satellites for processing at least two signals from said plurality of in-view satellites,

for each GPS satellite in said set of at least two in view GPS satellites, performing a first method comprising;

selecting a first set of Doppler frequency offsets;

processing a signal, corresponding to each satellite in said set of at least two in view GPS satellites, over said first integration time and said first set of Doppler frequency offsets to a produce a first set of outputs;

comparing said first set of outputs with a first detection threshold, in order to form a first set of detected outputs, corresponding to any of said first set of outputs that exceed said first detection threshold;

associating time indices of said first set of detected outputs with a pseudorange of said signal and associating amplitudes of said first set of detected outputs with a signal strength of said first signal,

selecting a second integration time period, which is longer than the first integration time period,

for each GPS satellite in said set of at least two in view GPS satellites, for which said first set of detected outputs contained no members, performing a second method comprising;

selecting a second set of Doppler frequency offsets;

processing a signal corresponding to each satellite in said set of at least two in view GPS satellites for which said first set of detected outputs contained no members, over said second integration time and said second set of Doppler frequency offsets to a produce a second set of outputs;

comparing said second set of outputs with a second detection threshold in order to form a second set of detected outputs, corresponding to any of said second set of outputs that exceed said second detection threshold

associating time indices of said second set of detected outputs with a pseudorange of said signal and associating amplitudes of said second set of detected outputs with a signal strength of said signal.

44. A method as in claim 43 wherein said processing of said signal in said first method further comprises storing said plurality of signals in a digital memory to produce stored data.