Communications: directive radio wave systems and devices (e.g. – Directive – Including a satellite
Reexamination Certificate
2002-04-19
2004-12-28
Issing, Gregory C. (Department: 3662)
Communications: directive radio wave systems and devices (e.g.,
Directive
Including a satellite
Reexamination Certificate
active
06836241
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to signal processing under Global Positioning System (GPS). In particular, the present invention relates to optimal scheduling for satellite acquisition under GPS, relative to certain search performance criteria.
DISCUSSION OF THE RELATED ART
Location determination using GPS is achieved in a receiver by processing signals received from multiple GPS satellites. The time difference between signal transmission at a GPS satellite and the same signal being received at the receiver provides a range measurement (“pseudo-range”) representative of the distance between the satellite and the receiver. To allow the signal of each GPS satellite to be distinguished from the signals of other GPS satellites, each GPS satellite modulates the carrier signal (1575.42 MHz) with a 1024-chip pseudo-random code (PRN) assigned to that GPS satellite. The PRN has a 1-millisecond period. In theory, the PRNs of the GPS satellites are mutually orthogonal to allow them to be individually recovered at the receiver. Because the position of each satellite at signal transmission time is relatively accurately known, the position of the receiver can be determined in theory using four or more pseudo-ranges from multiple GPS satellites.
The time difference between signal transmission and the signal reaching the receiver is often represented by the quantity “code phase,” which is the time difference modulo the period of the PRN. To obtain a pseudo-range, the receiver processes the signal received, taking into consideration signal and receiver parameters, some of which values are not accurately known a priori. For example, the motion of the satellite relative to the receiver and the imperfection in the receiver clock lead to frequency shifts (“Doppler effects”) in the received signal, known respectively as “satellite Doppler” and “clock Doppler.” The receiver's own motion also contributes a Doppler effect in the received signal. In practice, with a receiver clock accuracy of 1 part per million, the clock Doppler introduces an uncertainty of in the order of 1575 Hz. Because the GPS carrier wavelength is 19 cm., a 1/0.19 Hz uncertainty is introduced per meter per second of receiver velocity; thus a +/−200 Hz uncertainty is introduced for a receiver traveling at a velocity of 85 mph.
To acquire a satellite (i.e., to determine sufficiently accurately the code phase and the Doppler effects as to provide a pseudo-range down to the nano-second range), a receiver may search the code phase and Doppler uncertainty ranges for the code phase and Doppler values that match best with the received signal. In such a search, the present invention provides a search schedule that maximizes certain specified performance criteria (e.g., maximizes the probability for acquiring a satellite within a specified processing time of a digital signal processor).
SUMMARY OF THE INVENTION
The present invention provides, in a location determination apparatus, a method for scheduling a search of a parameter space. The method includes (a) dividing the parameter space into search regions, (b) computing a figure of merit associated with each search region, and (c) scheduling a search of the search regions according to optimizing a function of the figure of merit.
In one embodiment of the present invention, a method is provided in a Global Positioning System (GPS) receiver that achieves enhanced performance by scheduling searches in the Doppler search space according to a cost function. In that embodiment, the cost function relates to both the cost of constructing a 3-dimensional correlation grid associated with each GPS satellite, code phase and Doppler range (“grid building cost”) and the cost of probing the correlation grid for a maximum correlation value (“search cost”). In one implementation, the correlation grid is constructed by creating a table of correlation values for various hypothesized code phase values, integrated over various integration time intervals. The integration can be performed using a fast fourier transform (FFT). Probing this correlation grid is achieved by searching for the integration time, code phase and Doppler values that maximize an “ambiguity function”(i.e., the modulus of the complex correlation function resulting from the FFT). (Additional search parameters may include acceleration and the size of coherent blocks in non-coherent combinations). In that implementation, extending integration time intervals—which enhances the signal-to-noise ration (SNR)—can be achieved by processing incrementally, while changing the range of Doppler values requires recalculating the correlation values.
In addition to a cost function, a method of the present invention includes a reward or value function for each search region. In one instance, the reward function relates to a probability of acquiring a satellite signal in the cells of search region. (A cell is the smallest unit of space within a search region.) By scheduling search of cells having high ratio of reward vis-à-vis cost (i.e., the figure of merit being representative of a constraint maximization), the probability of acquiring satellite is maximized per unit cost. In one instance, the reward function is independent of the Doppler search range and the integration times. In an embodiment described above, the scheduler extends integration time intervals before changing Doppler search ranges, thus optimizes searching of each cell in the grid over various integration times, while rebuilding the grid only when necessary. Cost savings are thus achieved through reduction of grid construction cost.
In one embodiment, after the clock Doppler has been determined upon acquiring one satellite, the Doppler search range associated with a cell in the grid is dominated by the receiver's own motion. In one embodiment of the present invention, the scheduler schedules searching the Doppler search space using search ranges determined empirically by the expected receiver velocity. In particular, when the receiver experiences a weak signal condition, the scheduling takes advantage of the fact that such a condition also suggests a low receiver velocity. Under such a condition, a tighter Doppler search range is scheduled to decrease search cost, without significantly reducing the probability of signal acquisition.
In one embodiment, an ultra-stacked technique is used.
In one embodiment, the Doppler search expands from a minimum Doppler search range, which is selected for low cost, to a maximum Doppler search range covering substantially all the possible Doppler values. In one implementation, the Doppler search range increases by a factor of 4 to reduce the total cost of rebuilding grid throughout the search. In one implementation, certain search regions having prohibitive costs are not searched.
The present invention is better understood upon consideration of the detailed description below and the accompanying drawings.
REFERENCES:
patent: 4928107 (1990-05-01), Kuroda et al.
patent: 6052082 (2000-04-01), Hassan et al.
patent: 6181274 (2001-01-01), Pratt et al.
patent: 6256583 (2001-07-01), Sutton
patent: 6259398 (2001-07-01), Riley
patent: 6384778 (2002-05-01), Campbell
patent: 2001/0051936 (2001-12-01), Michalewicz
patent: 2003/0050902 (2003-03-01), Buczak et al.
patent: 0 635 728 (1995-01-01), None
patent: WO 01/71375 (2001-09-01), None
Seybold, John S.; Belkerdid Madjid A. “Performance Analysis of An Expanding-Search Algorithm For Coarse Acquisition of Dess Signals,” 1996 IEEE, pp. 148-155.
Ward, Phillip W., “GPS Receiver Search Techniques,” 1996 IEEE, pp. 604-611.
Chou Andrew
Mann Wallace
Stone Jesse
Issing Gregory C.
Kwok Edward C.
MacPherson Kwok & Chen & Heid LLP
SiRF Technology Inc.
LandOfFree
Method for optimal search scheduling in satellite acquisition does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for optimal search scheduling in satellite acquisition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimal search scheduling in satellite acquisition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3324726