HK1109930A - Method and apparatus for increasing coherent integration length while receiving a positioning signal - Google Patents

Abstract

A receiving method and apparatus for increasing coherent integration length while receiving a positioning signal from transmitters such as GPS satellites. In order to compensate for frequency drifts that may occur in the positioning signal, a hypothesis is made as to the frequency drift, which is inserted into the receiving algorithm. Advantageously, the length of coherent integration can be increased at the expense of reducing the length of incoherent integration while keeping the total integration length the same, the net effect of which is an increase in signal detection sensitivity. The frequency drift hypothesis has any appropriate waveform; for example, approximately linear or exponential. The hypothesized frequency drift can be inserted into the receiver algorithm in any suitable place; for example, the data block may be adjusted for the hypothesized frequency drift, alternatively the reference signal may be adjusted, or the frequency samples of either the data block or the reference signal may be adjusted.

Description

Method and apparatus for increasing coherent integration length when receiving positioning signals

Technical Field

The present invention relates to an apparatus and method for calculating the position of a mobile device by using wireless positioning signals, such as a GPS system.

Background

Position location devices are becoming more and more popular not only for marine vessels or expeditioners in remote areas, but also for anyone who uses a mobile phone in everyday life. The increasing number of cell phones associated with the popularity of personal position location devices has facilitated the development of fast, high-sensitivity methods for acquiring signals used to determine position.

Position location techniques typically utilize wireless location signals that are simultaneously transmitted from known locations. In the GPS system, these positioning signals are transmitted simultaneously from a variety of satellites at known times and at predefined frequencies. On the ground, a GPS receiver acquires positioning signals from each satellite within its view of the sky. The time of arrival of the positioning signal, as well as the exact location of the satellites within view and the exact time that the signal was transmitted from each satellite, are used to triangulate the position of the GPS receiver.

The positioning signals, and in particular the GPS signals, comprise high-rate repetitive signals or "codes," known as pseudo-random (PN) sequences. Codes available for civilian use are referred to as C/a codes and have a binary phase inversion rate or "chipping" rate of 1.023MHz and a repetition period of 1023 chips for a code period of 1 millisecond. The pseudorandom sequence in the GPS system belongs to a group called "gold codes". Each GPS satellite broadcasts a signal simultaneously at its unique gold code with a carrier frequency.

At the receiver, electromagnetic energy at the carrier frequency is observed, and this observed energy is processed to search for the possible presence of signals from any GPS satellite that may be in the field of view. The particular GPS code and phase delay is unknown at the time of observation by the receiver. The purpose of the receiver is to identify GPS codes for the carrier frequency in the observed energy and determine the phase delay of each identified GPS code. However, since the GPS code and phase delay are initially unknown, the following method is generally employed: a first GPS code is assumed and then a number of phase hypotheses are tested in sequence until a GPS signal has been identified or determined to be absent. This process is then repeated for each other GPS satellite that may be in the field of view.

Receiving positioning signals from GPS satellites can be difficult due to a number of factors. For example, GPS signals are transmitted at relatively low power and from a large distance. As GPS signals travel from earth orbit to a receiver, their initial low power has been significantly reduced, making the signals extremely weak at the receiver.

Another problem relates to frequency errors that may affect one or more of the positioning signals. For example, the carrier frequency may shift slightly over time due to the doppler effect. In a receiver, oscillators and other electronics that receive and process signals may introduce errors in frequency (e.g., slight shifts), which may complicate reception. If the frequency shift is constant, then a Fourier transform (e.g., FFT) method may be used; however, further complexity results when this frequency shift varies over time; i.e. when the frequency shift is not constant with the observation time (data block). To deal with the problem of time-varying frequency errors, the length of the data block for coherent processing (coherence length) is typically limited to fractions of a second (e.g., 20 milliseconds); otherwise, the frequency error may significantly degrade the system sensitivity. To increase system sensitivity when there may be a frequency shift, many successive coherent processing operations may be done over many time periods (e.g., five to twenty), and the results added together in a non-coherent fashion to provide an indication of the signal over a period of one or more seconds. This is a significant advantage if there are available systems that can perform a single coherent processing operation in a longer period of time, i.e. if the coherent integration length can be significantly increased.

Disclosure of Invention

A method and apparatus for increasing the coherent integration length for receiving and processing one or more positioning signals transmitted at a predetermined frequency from multiple transmitters, which are used to determine the position of a receiver, is described herein. Each positioning signal includes a periodically repeating sequence that uniquely identifies the transmitter that transmitted the signal.

To compensate for frequency drift that may occur in the positioning signal after observation and processing in the receiver, one or more assumptions are made regarding the frequency drift, which are then combined with the observed data and processed in one embodiment. This allows for longer coherent integration lengths, which may significantly reduce processing time and/or provide more accurate results. In particular, by applying the frequency drift assumption in signal processing, the length of coherent integration can be increased at the expense of reducing the length of incoherent integration while keeping the total integration length constant, the net effect of which is an increase in signal detection sensitivity.

In particular, a method and apparatus are disclosed that utilize a long coherent integration period to receive a positioning signal transmitted from one of a plurality of transmitters at a predetermined carrier frequency. The positioning signal includes a reference signal that uniquely identifies the transmitter that sent the positioning signal. The method comprises the following steps: at a receiver, electromagnetic energy at about the carrier frequency is observed, and data indicative of the observed electromagnetic energy is stored. The data is observed over a predefined period of time to define blocks of data that may be subject to unknown frequency drift. One of the transmitters is assumed, whereby one of the plurality of unique reference signals is assumed. A frequency drift is assumed, and in response to the assumed frequency drift, the receiver searches for a match between the data block and the assumed reference signal over a plurality of phase shifts. If a matching signal is found, the receiver determines the phase delay and timing information, otherwise the receiver repeats the loop of the previous steps until a matching signal is found, or until a predetermined exit criterion has been met.

The assumed frequency drift has any suitable signal form; for example, the hypothesized frequency drift may be approximately linear or approximately exponential, or more complex. The hypothesized frequency drift may be implemented to any suitable location within the receiver algorithm; for example, the method may include processing the data block in response to the hypothesized frequency drift to provide a drift-adjusted data signal; and searching for a match between the drift adjusted data block and the hypothesized reference signal. Alternatively, the method may include processing the hypothesized reference signal in response to the hypothesized frequency drift to provide a drift-adjusted reference signal, and searching for a match between the data block and the hypothesized reference signal.

The receiving method may include calculating frequency samples in response to a data block, calculating frequency samples in response to a reference signal, and searching for a match between the data block and the frequency samples of the reference signal. In this embodiment, the method may further comprise adjusting a vector basis of at least one of the data block frequency samples and the periodically repeating sequence in response to the hypothesized frequency drift.

Advantageously, the disclosed method allows for longer coherent integration periods, thereby using longer data blocks than conventional receiver methods. For example, the data block may have a size that is within a one hundred to five hundred repeat range of the reference signal or within a range of one hundred milliseconds to one second. However, it may be more advantageous to utilize the disclosed method with shorter coherent integration periods (e.g., ten to one hundred milliseconds).

In one embodiment, the transmitter includes a plurality of GPS satellites that transmit GPS signals at GPS frequencies, each GPS satellite transmitting a unique periodically repeating sequence. The code phase offset of the signal at the receiver is found and by using this information from many transmitters, the position of the receiver can be determined using GPS algorithms.

The above-described methods may be implemented in suitable hardware and/or software on a receiver and/or one or more servers in a wireless network. For example, certain functions may be implemented in a receiver and certain functions may be implemented in a Position Determination Entity (PDE).

Drawings

For a more complete understanding of the present invention, reference is now made to the following descriptions of the embodiments illustrated in the accompanying drawings, in which:

FIG. 1 is a perspective view of a communication and position location system including satellites that transmit GPS signals that are received by a GPS receiver in a mobile station that is in communication with a plurality of base stations;

FIG. 2 is a block diagram of one embodiment of a mobile station including a GPS receiver and a cellular communication system;

FIG. 3 is a diagram illustrating the structure and waveform components of a GPS positioning signal;

FIG. 4 is a functional block diagram of a GPS receiver portion that processes and correlates received signals to determine whether a GPS positioning signal is present;

FIG. 5 is a graph of frequency drift versus time illustrating many examples of frequency drift;

FIG. 6 is a flow chart of a method for receiving a positioning signal including adjusting a data block in response to an assumed frequency drift; and

fig. 7 is a flow chart of a method of receiving a positioning signal in response to a hypothesized frequency drift.

Detailed Description

The present invention is described in the following description with reference to the figures, in which like numerals represent the same or similar elements.

The FFT and DFT algorithms discussed herein are used to illustrate examples of algorithms for generating frequency samples. More generally, any suitable algorithm that generates the appropriate frequency samples may be used as an alternative to the FFT and DFT algorithms. For example, frequency samples may be generated using a DFT-like algorithm in which the number and spacing of frequency domain samples is not exactly the number and spacing of frequency domain samples of the DFT; that is, more or fewer frequency samples may be calculated, and the spacing between frequency domain samples may be narrower than the spacing between frequency domain samples of a standard DFT operation. The frequency samples may be generated from digital or analog data, from observed data, or from previously calculated values. The calculated frequency samples are then used for subsequent operations.

Glossary of terms and abbreviations

The following terms and abbreviations are used throughout the detailed description:

A-GPS: aiding GPS. A positioning technique in which a positioning server provides special assistance to a GPS acquisition process, which can reduce acquisition time and improve sensitivity.

Base station or BTS: a base transceiver station. A fixed station for communicating with a mobile station. Including an antenna for transmitting and receiving wireless communication signals.

CDMA: code division multiple access. High capacity digital radio technology, more advanced and commercially available by QUALCOMM^TMAnd (5) company development.

Chip: the symbol, which is also the smallest part of the modulation (e.g., phase reversal) of the pseudo-random (PN) sequence.

Chip rate: the symbol transmission rate.

Code phase: the relative timing between the frame boundary of the received PN sequence contained within the received GPS signal and the frame boundary of the locally generated PN reference sequence. The code phase is typically a number between zero and the duration of one PN frame (i.e., one millisecond in civilian GPS signals). The code phase may be considered as timing information extracted by the receiver for determining the position.

And (3) coherent treatment: techniques that process a block of data as a whole typically do not use non-linear (e.g., detection or combining) operations.

And (3) correlation: a process of comparing the received signal with a reference code. The correlation operations include coherent processing and may also include non-coherent processing. The output of any correlation process (coherent or non-coherent) is referred to as the "correlation output".

And (3) detection: a process that operates on a set of samples by determining the power in each data sample using a non-linear operation, typically a magnitude or magnitude squared operation. For example, if each data sample is represented in an in-phase and quadrature (I-Q) component format or in a "complex" format in which the in-phase component is associated with the real component of the data word and the quadrature component is associated with the imaginary component, the detection process may calculate a magnitude or a magnitude squared. In one case, the magnitude squaring operation is a standard operation associated with complex numbers.

DFT: a discrete fourier transform.

FFT: and (4) performing fast Fourier transform. An efficient technique for computing a DFT for a finite duration sequence. It should be noted that the frequency samples constructed by the DFT or FFT algorithm are the same, and we may use the terms "DFT data" and "FFT data" interchangeably.

GPS: a global positioning system. A technique for determining three-dimensional position, including altitude, using range measurements to GPS satellites. Although the term GPS is commonly used to refer to the United states Global positioning System, the meaning of this term includes other global positioning systems such as the Russian Glonass system and the planned European Galileo system. In some systems, the term Satellite Positioning System (SPS) is used instead of the GPS term. For illustrative purposes, the present invention is described herein in terms of the current U.S. GPS system. However, it should be apparent to those skilled in the art that the present invention may be applied to a variety of SPS systems utilizing similar signaling formats, as well as to future variants of the United states GPS system.

GPS positioning: the end result of the process of measurement and subsequent calculations by which the location of the GPS user is determined.

GSM: global system for mobile, another widely used digital wireless technology.

Non-coherent treatment: for reasons of, for example, improving the signal-to-noise ratio, several adjacent coherently processed data sets are combined by performing a non-linear detection operation followed by a combining operation. For example, non-coherent processing may include detecting and combining (e.g., summing) correlation outputs from multiple neighboring data blocks.

MS: a mobile station, such as a handset having a baseband modem and position location capability for communicating with one or more base stations. The MS referenced in this disclosure typically includes a GPS receiver.

PDE: a location determination entity. System resources (e.g., servers), typically within a CDMA network, working in conjunction with one or more GPS reference receivers, are capable of exchanging information about GPS with the MS. In an MS-assisted A-GPS session, the PDE may send GPS assistance data to the MS to enhance the signal acquisition process. The MS may return information, such as pseudorange measurements, to the PDE, which is then able to compute the position of the MS. In an MS-based A-GPS session, the MS may send the computed position results to the PDE.

And (3) pseudo-range measurement: a process employed by a GPS receiver and based on signal processing techniques to determine a range estimate between the receiver and a selected satellite. The range is measured in terms of signal transit times from SVs to the receiver.

SV: a satellite. One of the main elements of the global positioning system is the set of SVs that orbit the earth and broadcast uniquely identifiable signals.

UMTS: general mobile phone service: a third generation cellular standard utilizing the CDMA form, designed as a successor to GSM.

Overview of GPS System and Mobile station

Reference is now made to fig. 1 and 2. FIG. 1 illustrates a GPS environment that includes a plurality of GPS Satellites (SVs) 11 that transmit GPS positioning signals 12, a plurality of terrestrial-based base stations 10, and a Mobile Station (MS) 14. The base station 10 is connected to a cellular infrastructure network 15, the infrastructure network 15 allowing the base station 10 to communicate with other networks and communication systems (e.g., a telephone system 16, a computer network 17a such as the internet, and other communication systems 17 b). Thus, the base station 10 may comprise a portion of a communication network that may include many additional communication systems in communication with the base station.

The MS 14 is described elsewhere herein (e.g., with reference to fig. 2), but generally includes a GPS receiver and a two-way communication system for communicating with a base station using two-way communication signals 20. It should be appreciated that a GPS receiver may be implemented with a wide variety of mobile stations (other than handsets) in communication with one or more base stations. Further, for ease of description herein, the position location system disclosed herein may be a GPS system; it should be appreciated that the system described herein may be implemented in any satellite-based positioning system.

In fig. 1, a walking user 13 is illustrated holding an MS 14. For example, the user may stand, walk, go in a car, or be in public transportation. It should be appreciated that a mobile station may be located in a wide variety of environments and may be stationary or mobile.

GPS Satellites (SVs) 11 include any group of satellites that broadcast signals for locating GPS receivers. Specifically, the satellites are synchronized to send wireless positioning signals 12 phased to GPS time. These positioning signals are generated at a predetermined frequency and in a predetermined format. In current GPS implementations, each SV transmits civilian-type GPS signals on the L1 band (1575.42MHz) in a format according to the GPS standard. When a conventional GPS receiver in the MS detects a GPS signal, the GPS system attempts to calculate the amount of time that elapses from the transmission of the GPS signal until reception at the MS. In other words, the GPS system calculates the time required for each of the GPS signals to travel from its respective satellite to the GPS receiver. The pseudoranges are defined as: c (T)_user-T_sv)+cT_biasWhere c is the speed of light, T_userIs the GPS time when a signal from a given SV is received, T_svIs the GPS time when the satellite transmits a signal, and T_biasWhich is an error in the local user's clock, is typically present in GPS receivers. Sometimes the pseudoranges are defined with the constant "c" omitted. In general, the receiver needs to solve for four unknowns: x, Y, Z (coordinates of the receiver antenna) and T_bias. For this general case, solving for four unknowns typically requires measurements from four different SVs; in some cases, however, this restriction may be relaxed. For example, if accurate altitude estimates are available, the number of SVs required may be reduced from four to three. In so-called assisted GPS operation, T_svNot necessarily available to the receiver and instead of processing the true pseudoranges, the receiver relies primarily on code phase. In current GPS implementations, the code phase has a one millisecond time uncertainty since the PN code repeats every millisecond. Sometimes data bit boundaries may be determined, thus yielding only 20 ms uncertainty.

The base station 10 comprises any collection of base stations that serve as part of a communication network that communicates with the MS 14 using wireless signals 20. The base stations are connected to a cellular infrastructure network 15, the infrastructure network 15 providing communication services with a plurality of other communication networks such as a public telephone system 16, a computer network 17a such as the internet, a Position Determining Entity (PDE)18 (defined above) and a plurality of other communication systems shown collectively in block 17 b. A GPS reference receiver (or receivers) 19, which may be in the base station 10 or near the base station 10 or at any other suitable location, communicates with the PDE 18 to provide information useful in determining position, such as SV position (ephemeris) information.

The land-based cellular infrastructure network 15 typically provides communication services that allow a handset user to connect to another telephone through the telephone system 16; the base station may also be used for communication with other devices and/or for other communication purposes, such as an internet connection with a handheld Personal Digital Assistant (PDA). In one embodiment, the base station 10 is part of a GSM communication network; however, in other embodiments, other types of synchronous (e.g., CDMA2000) or asynchronous communication networks may be used.

Fig. 2 is a block diagram of one embodiment of the mobile device 14, the mobile device 14 including a communication and position location system. The cellular communication system 22 is connected to an antenna 21, and the antenna 21 communicates using the cellular signal 20. The cellular communication system 22 includes suitable means such as a modem 23, hardware, and software for communicating with and/or detecting signals 20 from base stations and processing the transmitted or received information.

A GPS position location system 27 in the MS is connected to a GPS antenna 28 to receive the location signal 12 transmitted at or near the desired GPS (carrier) frequency. The GPS system 27 comprises a GPS receiver 29 including frequency conversion circuitry and an analog-to-digital converter, a GPS clock, control logic for controlling the required functions of the GPS receiver, and any suitable hardware and software for receiving and processing GPS signals and for performing any calculations necessary to determine position using any suitable position location algorithm. In the illustrated embodiment, the analog-to-digital converter is connected to a buffer memory in the position location system, and the buffer memory is coupled to the DFT circuit to provide and store data during the DFT operation. In some assisted GPS implementations, final position location calculations (e.g., latitude and longitude) are performed at a remote server based on code phases and other information sent from the GPS receiver to the remote server. Some examples of GPS systems are disclosed in U.S. patent nos. 5,841,396, 6,002,363, and 6,421,002 to Norman f.

The GPS clock is intended to maintain accurate GPS time; however, since it is most often the case that accurate time is not available prior to a fix, it is common practice to maintain time in the GPS clock software by its estimate and the uncertainty associated with that value. It may be noted that after an accurate GPS fix, the GPS time will typically be known precisely (within tens of nanoseconds uncertainty in current GPS implementations). However, when the final position location calculation is completed at the remote server, the precise time may only be available at the server.

The mobile device control system 25 is connected to the two-way communication system 22 and the position location system 27. The mobile device control system 25 comprises any suitable structure, such as one or more microprocessors, memory, other hardware, firmware, and software to provide the appropriate control functions for the system to which it is connected. It should be apparent that the process steps described herein may be implemented in any suitable manner using hardware, software, and/or firmware subject to microprocessor control.

The control system 25 is also connected to a user interface 26, the user interface 26 including any suitable components for interfacing with a user, such as a keypad, a microphone/speaker for voice communication services, and a display (e.g., a backlit LCD display). The mobile device control system 25 and user interface 26, which are connected to the position location system 27 and the two-way communication system 22, provide the GPS receiver and the two-way communication system with appropriate input-output functions, such as controlling user inputs and displaying results.

GSP signal description

Referring to fig. 3, it is a diagram representing the structure of an ideal GPS signal described in equation (a 1). The functional form of the GPS signal can be expressed at any time t as follows:

img id="idf0001" file="A20058004623400131.GIF" wi="261" he="20" img-content="drawing" img-format="GIF"/

where A is the signal amplitude, d (t) is a relatively low rate (e.g., 50 baud) data sequence that modulates a carrier (e.g., by bi-phase modulation), P (t) is a waveform consisting of a repeating PN sequence F (t), □ is the carrier phase, and w is_r(t) is the instantaneous received carrier frequency:

w_r(t)＝w_e(t)+w_c (A2)

wherein w_e(t) is the instantaneous frequency error (frequency drift), and w_cIs the nominal carrier frequency.

It may be noted that equation (a1) is a complex representation, which may be useful when processing signals using a quadrature sampling method; of course other representations may be used as desired. In a real situation it should be realized that the individual parameters are not completely stable.

As shown in fig. 3, the GPS signal comprises a series of PN frames shown at 35, each frame containing a waveform f (t)36 bi-phase modulated according to a particular pseudo-noise (or "PN") sequence and a carrier frequency 37. The individual repetitions of f (t) are referred to as "PN frames". Each PN frame has a predetermined period T_r. At 38The data transitions of the data sequence d (t) are shown as occurring at the beginning of one of the illustrated PN frames; however, because the data sequence d (t) has a relatively low rate, the data transition 38 will occur only once every 20 PN frames, and thus the data transition may or may not occur at the beginning of the optional PN frame.

Each GPS Satellite (SV) transmits a unique PN waveform f (t), shown at 36, which is a series of symbols (chips) transmitted at a predetermined rate. The PN waveforms are distinguished from each other by a specific PN sequence for bi-phase modulating the carrier wave. For example, these sequences are selected from a set of gold codes in the C/A waveform of the U.S. GPS system. In the following description, the term "PN sequence" may be used for f (t), which is not strictly correct, since the PN sequence is actually a digital sequence used to construct the modulation signal of the carrier and thus produce the waveform f (t). However, it will be appreciated from the context that "PN sequence" as used in this manner means a waveform modulated by a PN sequence.

In one example, the chip rate is 1.023MHz, and thus the PN frame rate will be 1 kHz. This waveform F (t) repeats continuously; e.g. from a first satellite SV₁Of the first code repeat-emitting a unique sequence F₁(t)，SV₂Repeatedly transmitting a unique PN sequence F₂₍t), and so on. The GPS receiver is programmed with a unique PN sequence for all GPS satellites that may be in the field of view.

These PN sequences are used in an algorithm to identify a particular satellite; in particular, when satellite signals are received in a GPS receiver, the PN sequence is used to identify the satellite transmitting the received signal. Initially, however, the GPS receiver does not know the actual received code phase epoch, which as noted above may be within a full PN frame (e.g., one millisecond or 1023 chip period). Therefore, the receiver must search (in serial or parallel fashion) within the epoch uncertainty region to attempt to align the epoch of the received GPS frame with the epoch of the locally generated reference frame.

Receiver for GPS positioning signal

Referring now to fig. 4, fig. 4 is a functional diagram of a portion of a GPS receiver that processes and correlates received signals to determine whether a GPS signal is present.

The observed data is shown at 40. It should first be noted that in an actual GPS environment, the GPS receiver simultaneously receives multiple signals similar to the theoretical signal specified in equation (a1), each signal having a unique PN sequence f (t). For example, in a typical scenario, a GPS receiver typically receives eight to twelve signals from satellites in a variety of fields of view at any time, and the various parameters differ from one another due to, for example, different path lengths, directions of arrival, and doppler shifts. The "observed data" may therefore contain information from satellites in all fields of view. For purposes of illustration, the following disclosure discusses processing observed data to search for signals from selected satellites; it will be appreciated that processing observed data for other satellites that may be in the field of view will proceed in a similar manner.

The observed data is then processed at 41, for example by a suitable frequency conversion system, to take the observed data and convert it to the appropriate frequency, for example by down conversion. If desired, the frequency converted output may be converted to digital form for subsequent processing using an analog/digital converter 42. Of course, if the signal has been converted to digital format, then this A/D converter 42 would not be needed. The signal from the a/D converter 42 is then applied to a processing box 43 where it is combined with a waveform of the frequency drift hypothesis, for example by multiplication.

After the GPS signal arrives at the receiver and has been subjected to processing in the receiver, the frequency may have drifted from its original value. Due to doppler effects from SV motion and MS motion, frequency drift may result even before the signal reaches the receiver. Also, small errors in the MS local oscillator, for example caused by temperature changes, can cause the carrier frequency to vary from its ideal frequency. This frequency drift may vary over time; that is, the frequency drift may change during the time data is being observed. Typically, the amount of frequency drift is unknown to the receiver.

To compensate for the unknown frequency drift, a frequency drift assumption is made at 44. The predicted frequency drift due to radial acceleration of the transmitter/satellite (i.e., the predicted satellite doppler change) may or may not be included in the frequency drift hypothesis. The assumed frequency drift generally follows the form:

assumed frequency drift w_h (A3)

Referring now to fig. 5, fig. 5 is a graph of frequency drift versus time showing many examples of frequency drift. It should be appreciated that the assumptions illustrated are merely examples, and that the assumed frequency drift may have a variety of forms. One example is a constant frequency drift shown at 51. Another example is a negative linear rate of change of frequency drift (e.g., -2 Hz/sec) shown at 52. Another example is the exponential rate of change of frequency drift shown at 53. Still other examples are positive linear rates of change of frequency drift (e.g., 1 Hz/sec and 2 Hz/sec) shown at 54 and 55. Other examples are the curves shown at 56 and 57. It should be appreciated that an infinite number of functions may be used for the frequency drift hypothesis; however simple assumptions such as a linear rate of change (positive or negative) may be simpler to implement. Also, typically the rate of frequency drift of the actual signal is gradual (e.g., less than 3 Hz/sec), and thus a frequency drift assumption within that range will likely improve reception. It should be noted that the predicted frequency drift due to radial acceleration of the transmitter/satellite (i.e., the predicted satellite doppler change) may or may not be included in the frequency drift hypothesis. If the satellite Doppler changes are not included in the frequency drift hypothesis, they can be compensated for separately.

The frequency hypotheses may be stored in any suitable form. For example, the frequency hypotheses may be stored in memory in digital form as waveforms. Alternatively, it may be stored in analog form.

Referring again to fig. 4, the frequency hypothesis at 44 is applied to a/D converter 45 (as needed), and then combined with the data from a/D converter 42 by appropriate methods to provide a drift-adjusted signal. For many purposes, a multiplication operation will be suitable for combining two signals. In some embodiments, the hypothesized frequency drift may be implemented in other parts of the position location system; for example, the hypothesized frequency drift may be used to adjust the reference code instead of the collected data. Since the reference code and data are used together coherently, the net effect of adjusting the reference code will be similar to the effect of adjusting the data described herein. In yet another embodiment, the hypothesized frequency drift may be used to adjust the vector basis of subsequent FFT operations, or to modify the input or output, or both, of the FFT operation. The predicted frequency drift due to the motion of the transmitter/satellite (i.e., the predicted satellite doppler change) may be included in the hypothesized frequency drift, or it may be applied separately. In the latter case, adjustments for satellite doppler may be inserted in the algorithm at the same location as adjustments for other frequency drifts or at some other location.

The drift adjusted signal is then applied to a correlation system 46, which correlation system 46 searches for a match with the selected positioning signal and phase delay in response to the drift adjusted signal. The particular correlation system 46 shown in fig. 4 is provided for purposes of illustration, other embodiments may employ other correlation systems as appropriate and/or available. In particular, in FIG. 4, correlation system 46 includes a number of processing branches that operate in parallel to achieve faster processing times. In practice, however, the cost of branches for all possible PR shifts is generally not justified by the time savings, and operations are typically performed in a serial fashion as in a loop.

Correlation system

Typically, to receive positioning signals from GPS satellites, the observed signals are correlated with a reference code of a particular GPS code and phase. For example, a correlation receiver may multiply a received signal by a locally generated reference code containing a stored replica of the appropriate gold code contained within its local memory, and then integrate (e.g., low pass filter) the product in order to obtain an indication of the presence of the signal. This process is referred to as coherent processing.

In fig. 4, correlation system 46 includes a first correlator 47a that receives both the drift-adjusted signal and a first Pilot Reference (PR) signal. The correlated signals are applied to a fourier transform block 48 and then a detection operation 49 is performed to provide comparable magnitudes. The second correlator 47b also receives the drift-adjusted signal, but receives a second PR signal that has been shifted in phase from the first PR signal. An FFT is performed at 48b and a detection operation is performed at 49b so that the magnitude is now available. Also, correlation is performed for the third, fourth, fifth PR signal, etc. to obtain all possible phase shifts. Then, a maximum value is selected from these results, and if this maximum value is sufficiently greater than the other results (as determined by a predetermined criterion), it may be selected as a match and the phase delay is indicated (i.e., in customary terminology, it would indicate □ □.)

In some correlation systems, the results of multiple successive coherent processing operations are detected (e.g., their magnitudes determined) and combined to provide a correlation output with higher fidelity. The initial correlation operation is referred to as "coherent processing" and the subsequent combining step is referred to as "incoherent" or "incoherent" processing. With the long coherent processing times contemplated by the systems defined herein, it may not be necessary to perform incoherent processing, but incoherent processing may be useful or desirable in certain circumstances. Advantageously, the longer coherence length provided by the systems disclosed herein may reduce the number of non-coherent integrations required to achieve a desired sensitivity. At 50, an optional system is implemented to "chop"; that is, the result of the correlation is chopped, and the chopped slices (time periods) are entered into the FFT system. In this case, the detection operation at 49a includes squaring and non-coherently summing the FFT results over a time period.

Overview of the related System

By re-adjusting the relative timing of this stored replica in order with respect to the received signal and observing the correlation output, the receiver can determine the time delay between the received signal and the local clock. This time delay modulo the code period (e.g., 1 millisecond) is referred to as the "code phase". The initial determination of the presence of this output is referred to as "acquisition". In some GPS receivers, once acquisition occurs, the process enters a "tracking" phase in which the timing of the local reference is adjusted by a small amount in order to maintain a high correlation output. The correlation output during the tracking phase may be considered as a GPS signal with the pseudorandom code removed, or expressed in general terms as "despreading". This signal is narrowband, with a bandwidth equivalent to a 50 bit per second (bps) binary phase shift keyed data signal superimposed on the GPS waveform.

Method

Fig. 6 is a flow chart showing a series of steps performed in a mobile station aimed at processing a positioning signal to identify whether it matches the assumption of selecting a frequency drift, identifying a transmitter's repetition code and carrier frequency offset. As will be described, the algorithm makes a frequency drift assumption, it selects the transmitter (e.g., a GPS satellite or base station) and it can check all possible code phase offsets (e.g., 1023 offsets for GPS) to attempt to find a code phase offset match for the selected GPS code. The dry processing algorithm is then repeated for many frequency drift hypotheses and then again for each GPS code viewable by the mobile station.

Observed data (61)

At 61 in fig. 6, an operation is indicated to observe Electromagnetic (EM) energy at about the carrier frequency of the GPS positioning signal. At least during the block period T_cThe GPS signal (if present) is continuously observed for as long a period of time. Forms of GPS signals are discussed elsewhere herein (e.g., with reference to fig. 6).

Processing the observed data (62)

Referring again to fig. 6, at 62,the observed data is processed as necessary. Processing may be done "in real time" by processing the data as it is received, e.g., on a chip-by-chip basis, or the data may be buffered and then processed together as a set. Processing may include removing the carrier frequency from the GPS signal by suitable frequency translation circuitry, leaving a residual frequency f_e. To remove the carrier frequency, the GPS signal is typically first converted to an Intermediate Frequency (IF) by a mixer. The converted GPS signals are then processed to reduce the remaining IF components to approximately zero by any suitable analog or digital technique; for example, the IF frequency may be approximately removed by another mixer, or after converting GPS to a digital signal in an analog-to-digital converter, digital processing mixing techniques may be used. This can be accomplished in a manner well known in the art, for example, with conventional local oscillators and mixers. Additionally, while the carrier frequency may be removed prior to digitization, it is possible that only a majority of the carrier frequency may be removed and the signal is at a transition to a low IF frequency (e.g., f) prior to digitization_IF+f_e) Of (c) is detected. After the digitizing operation, the IF frequency f is removed, usually by means of digital signal processing methods_IF. Other variations on the signal processing will be apparent to those skilled in the art.

In an assisted GPS system, predicted doppler corrections for all GPS signals may be transmitted (in one form or another) from the PDE to the GPS receiver, and also a list of GPS satellites that may be in view is sent to the receiver so that the GPS receiver can more efficiently search for satellite signals. The predicted data stream may also be provided by the PDE.

At 62, the data sequence is removed as needed. Although optional, it may be very useful to remove the data sequence d (t) prior to processing. To assist in data sequence removal, in some assisted GPS systems, the predicted data sequence d (t) is sent (e.g., from a server) to the GPS receiver along with some approximate time of arrival of the GPS signal. In these cases, the GPS receiver may remove the data sequence d (t), and thus the pseudo-random polarity inversion that may occur every twenty milliseconds in the signal of equation (a1) due to the data sequence d (t). By removing random polarity inversion (i.e., by removing d (t)), the coherent processing time may be increased to longer time intervals, e.g., greater than 100 milliseconds, which may improve the sensitivity of the GPS acquisition process. As indicated previously, some future modes of GPS may contain signaling components that do not contain data.

Also at 62, the processed GPS signal is digitized (i.e., sampled) in an analog-to-digital converter for a predetermined period of time (if it was not previously converted) and then stored in a buffer memory in the GPS receiver. There is theoretically no limit to the size of the data set or the sampling rate of the data, but a power of 2 data set size is sometimes beneficial.

Providing a data block (33)

At 63, by selecting a value corresponding to a predetermined coherent processing period T_cA sampling time period T of a portion of internal digital data (e.g., raw or processed data)_cTo define blocks of data for coherent processing. The time period for combining the data for coherent processing is typically selected to contain a large integer number of PN frames (e.g., 100 PN frames); advantageously, the length of the time period (coherence length) can be made longer than in conventional systems due to the assumed frequency drift. However, the coherent processing block should not be chosen to be too long; in particular, it may be disadvantageous to attempt coherent processing of very large blocks (e.g., 2-second or 3-second blocks) because unpredictable frequency variations over the longer time period may limit or prevent any performance improvement.

Referring briefly to FIG. 3, at time T_cAn intra-observation positioning signal, which defines a data block, such as the first data block 39a or the second data block 39b, and a time T_cIs selected such that the data block has an integer number of PN frames 35. It may be noted that the beginning and end of a data block may be located anywhere within the PN frame boundary because the actual data block is received without previously knowing when the PN frame begins; for example, the data block may be uniformly from the first PN frameThe start extends to the end of the last PN frame as shown at 39a (code phase offset 0), but more likely the data block will extend arbitrarily from somewhere in the middle of the first PN frame to somewhere in the middle of the frame after the last full PN frame (as shown at 39 b) so that the code phase offset is not equal to zero.

Suppose frequency drift (64)

At 64, assumptions are made regarding frequency drift (examples of which are discussed with reference to FIG. 5) by any suitable method, either randomly or based on prior information. For example, an algorithm may be used to select the most likely frequency drift hypothesis, e.g., 2 Hz/sec is linear. Alternatively, the selection of the most likely frequency drift may be based on the most recent successful frequency drift, or based on the most common frequency drift, or any other suitable algorithm.

Processing the data block (65) in response to the hypothesized frequency drift

At 65, the data block and the hypothesized frequency drift are processed, for example by a multiplication operation, to provide a drift-adjusted data signal, which is the data block adjusted for the hypothesized frequency drift. It may be noted that in other embodiments, the hypothesized frequency drift may be used elsewhere in the algorithm to adjust other amounts; for example, the assumed frequency drift may be used to adjust the reference code instead of the data. Since the reference code and data are used together coherently, the net effect of adjusting the reference code will be similar to the effect of adjusting the data described herein. In yet another embodiment, the hypothesized frequency drift may be used to adjust the vector basis of subsequent FFT operations, or to modify the input or output, or both, of the FFT operation. The predicted frequency drift due to the motion of the transmitter/satellite (i.e., satellite doppler) may be included in the hypothesized frequency drift, or it may be applied separately. In the latter case, adjustments for satellite doppler may be inserted in the algorithm at the same location as adjustments for other frequency drifts or at some other location.

Selecting transmitters likely to be in the field of view, providing a reference code (66)

At 66, a transmitter (e.g., a GPS satellite) is selected or determined by any suitable method. The selection of any particular satellite may be random or, preferably, may be based on any suitable information, such as history or a list provided by the PDE.

Based on this satellite selection, a reference code indicative of a signal transmitted from the satellite is supplied. The reference code may be generated locally or pre-computed and stored. The reference code may be in any suitable form, for example it may be a time domain signal; or it may be stored as an FFT. These codes are well known and it is feasible and practical to pre-calculate and store the value of each GPS code in the GPS receiver.

It should be noted that a GPS receiver receives multiple signals simultaneously, for example, in a typical scenario, a GPS receiver typically receives eight to twelve signals from satellites in multiple fields of view at any time, but many of those signals may be too weak to detect. Thus, there is uncertainty as to which satellites are providing receivable signals, and in addition, the code phase offset of the determined time of arrival of any receivable signal is unknown, even if detectable.

As will be discussed, the PN codes for a selected satellite will be tested in all frequency hypotheses, at least until a match is found or all hypotheses have been exhausted, and then the next satellite is selected and tested in all frequency hypotheses, and so on, until all candidate satellites have been selected, or until enough satellites have been found to complete a position fix.

Assume initial PR shift (67)

At 67, an initial assumption is made regarding PR shifting. If sufficient information is available to the GPS receiver, (e.g., previous position fixes or code phase predictions are available), then this initial and subsequent assumptions can be made based on this information. If no information is available, a best guess can be made and a search will begin.

Correlating (68) the drift-adjusted signal with a reference code

At 68, an operation is performed to correlate the drift-adjusted signal with a reference code by any suitable method. The result is a relevant data set.

For purposes of explanation, the method disclosed above corresponds to processing one block of data in a coherent manner, which is a type of correlation referred to herein as "coherent integration". To improve sensitivity, the magnitudes of the correlation outputs from many coherent correlation processes may be detected and combined in many (e.g., 2 to 2000 blocks, typically 5 to 200 blocks) adjacent time intervals to provide correlation results. This process is referred to as "non-coherent integration".

Performing a Fourier transform on the data block (69)

At 69, the correlation data set is transformed to the frequency domain using a fourier transform process, for example, to produce a set of frequency samples. This step may be referred to as a "forward transform" process and may be performed in a variety of ways, such as a Fast Fourier Transform (FFT). One well-known method is "time decimation"; another method is frequency decimation. Other suitable or available fast algorithms may be employed, such as chirp z-transform (chirp z-transform) or number theory transform (numberregenerative transform).

The FFT of an arbitrary signal consists of a series of data frequency samples separated in frequency by the inverse of the duration of the data block being processed. For example, if the block duration (T)_c) Is 80 milliseconds, then the frequency samples are spaced 12.5Hz apart. Each data frequency sample may be identified by its frequency (in Hz) or, more conveniently, by its frequency index. Specifically, each data frequency sample of the DFT may be assigned an integer (frequency index), which may, for example, start at zero index of zero frequency. For an N-point FFT, the frequency index N/2 corresponds to a frequency of one-half the sampling rate (in Hz), i.e., S/2. The frequency samples with indices N/2+1, N/2+2, etc. correspond to a value equal to-S/2 +1/T_c、-S/2+2/T_cEtc. (in Hz); that is, it represents data corresponding to a negative frequency.

Searching for FFT correlation results for matching (70)

At 70, the FFT correlation results from step 69 are analyzed to determine if a match has been found. This operation may be performed, for example, by any of a number of suitable algorithms described below. Specifically, the FFT result is a series of equally spaced lines at different frequencies. To determine whether a match has been found, any suitable search algorithm may be employed. Typically, the magnitude of each line is calculated (detected). A match may be found if the magnitude of the line of FFT frequency indices and a particular hypothetical code phase is the largest of all the lines and its magnitude meets or exceeds a predetermined threshold.

At 71, a test is performed. If a match has not been identified, operation moves to decision step 72. At 72, if there are more PR shifts to search for, another PR shift assumption is made at step 73, and then operation continues in a "phase loop" including steps 68-71. However, if there are no more PR shifts to be searched, then the operation moves out of the phase loop, from 72 to decision step 74, which determines whether more frequency drift hypotheses need to be tested, decision step 74.

From decision step 74, if more frequency drift hypotheses need to be tested, then operation continues in a "frequency drift loop" including steps 64-72 to assume another frequency drift for the same transmitter. If no more frequency drift hypotheses need to be tested, then operation moves to decision step 76, discussed below, where decision step 76 determines whether there are more satellites/transmitters to search for.

Returning to the decision at step 71, if a match has been found, then operation moves to step 75 where the code phase offset is determined at step 75.

Determining a code phase offset (75)

As discussed above, when sampling data, the code phase is unknown; that is, the start and end of the PN frame period are not yet determined. In particular, although a data block has an integer number of PN frames, the starting position of the data block is unknown, and thus the start and end of the data block may be located anywhere within the PN frame. For example, as shown in fig. 3, the data block may extend uniformly from the beginning of the first PN frame to the end of the last PN frame, as shown at 39a (code phase offset ≠ 0), but more likely the data block will extend from any point within the first PN frame (as shown at 69 b) to the same point within the frame following the last full PN frame (code phase offset ≠ 0).

At 75, after a positive search result (i.e., after a match is found in step 71), the code phase offset is determined from the hypothetical PR shift used at 68, while the average frequency offset is determined from the FFT correlation results of step 69. The exact code phase offset is usually interpolated from correlation results corresponding to several PR shifts around the peak found in the search. This interpolation is possible if successive PR shifts are assumed to be separated by only one-half PN chip.

At 76, a determination is made as to whether additional transmitters/satellites will be searched. Making this determination according to any suitable criteria; for example, if enough satellites have been found to make a position fix, or if the list of possible in-view satellites is exhausted, a decision may be made to stop the search, and thus the acquisition operation is complete as indicated at 77. However, if more satellites are to be searched, operation returns to step 66 and a transmitter loop is performed to select the next satellite, assuming another PR shift, and steps 66-76 are performed with the new assumption.

Overview and additional discussion

The method of fig. 6 corresponds to processing a block of data in a coherent manner, which is a type of correlation referred to herein as "coherent integration". However, in actual practice, coherent integration may not yield sufficient sensitivity to detect weak GPS signals and measure their code phase, because the length of the coherent integration period is limited by various frequency errors. To improve sensitivity, the magnitude of the correlation output from many coherent correlation processes can be detected and combined, which is referred to as "non-coherent integration". In particular, the coherence process can repeat one or more additional adjacent time intervals (e.g., 2-2000 blocks, typically 5-200 blocks), and then detect (e.g., calculate their magnitudes or magnitude squares) and combine the results. The summation of these detected blocks of correlated samples is referred to as non-coherent or incoherent processing. Non-coherent processing provides lower sensitivity than coherent processing for the same total integration length. By applying the frequency drift assumption during signal processing, the length of coherent integration can be increased at the expense of reducing the length of incoherent integration while keeping the total integration length constant, the net effect of which is an increase in signal detection sensitivity.

Based on these teachings, one skilled in the art will appreciate that alternative embodiments may be implemented without departing from the spirit or scope of the present invention.

Fig. 7 is a flow chart including an alternative embodiment for receiving a positioning signal. Specifically, the steps in blocks 61-64, 66, 67, and 71-77 correspond to those described above with reference to FIG. 6.

At 78, an operation is shown to search for a match between the data block and the hypothesized reference signal in response to the hypothesized PR shift and the hypothesized frequency drift. The operations at 78 may include the system described above with reference to fig. 6, where a data block is processed in response to an assumed frequency drift to provide a drift-adjusted data signal, followed by a search for a match between the drift-adjusted data block and the assumed reference signal.

Alternatively, operating at 78 may include processing a hypothesized reference signal in response to the hypothesized frequency drift to provide a drift-adjusted reference signal, and searching for a match between the data block and the hypothesized reference signal.

In general, the operations at 78 may be performed using any suitable sequence assuming frequency drift, frequency, and phase shift. Many alternatives are suitable; for example, multiple frequency drift hypotheses may be tested in parallel, or a single phase drift hypothesis may be tested for multiple frequency drift hypotheses, or many different types of different hypotheses may be tested in parallel.

In yet another alternative, the operations at 78 may include calculating frequency samples in response to a data block, calculating frequency samples in response to the reference signal; and searching for a match between the data block and the reference signal frequency sample. A vector basis of at least one of the fourier transformed data block and the periodically repeating sequence may be adjusted in response to the hypothesized frequency drift.

The invention is to be defined solely by the appended claims, which include all such embodiments and modifications when viewed in conjunction with the above specification and accompanying drawings.

Claims (30)

1. A method of receiving a positioning signal transmitted from one of a plurality of transmitters at a predetermined carrier frequency using a long coherent integration period, the positioning signal including a reference signal that uniquely identifies the transmitter sending the positioning signal, the method comprising:

a) at a receiver, observing electromagnetic energy at about the carrier frequency and providing data in response to the observed electromagnetic energy;

b) assuming one of the transmitters, thereby assuming one of the plurality of unique reference signals;

c) assuming a frequency drift;

d) processing the data in response to the hypothesized frequency drift;

e) defining a data block of the data;

f) searching for a match between the data block and the hypothesized reference signal; and

g) if a matching signal is found, phase delay and timing information is determined, otherwise the steps b to f are cycled through until a matching signal is found, or until a predetermined exit criterion has been met.

2. The method of claim 1, wherein the hypothesized frequency drift is approximately linear.

3. The method of claim 1, wherein the hypothesized frequency drift is approximately exponential.

4. The method of claim 1, wherein the step f comprises:

processing the data block in response to the hypothesized frequency drift to provide a drift-adjusted data signal; and

searching for a match between the drift-adjusted data block and the hypothesized reference signal over a plurality of phase shifts.

5. The method of claim 1, wherein the step f comprises:

processing the hypothesized reference signal in response to the hypothesized frequency drift to provide a drift-adjusted signal; and

searching for a match between the data block and the hypothesized reference signal over a plurality of phase shifts.

6. The method of claim 1, wherein the step f comprises:

calculating frequency samples in response to the data block;

calculating frequency samples in response to the reference signal; and

searching for a match between the data block frequency samples and the reference signal frequency samples.

7. The method of claim 6, wherein the step f further comprises: adjusting the data block frequency samples and the vector basis of the periodically repeating sequence in response to the hypothesized frequency drift.

8. The method of claim 1, wherein the transmitter comprises a plurality of GPS satellites that transmit GPS signals at GPS frequencies, each GPS satellite transmitting a unique reference signal.

9. The method of claim 1, wherein the data block has a size corresponding to an integer number of repetitions of the reference signal.

10. The method of claim 1, wherein the data block has a size in a range of one hundred to five hundred repetitions of the reference signal.

11. A method of receiving a positioning signal transmitted from one of a plurality of transmitters at a predetermined carrier frequency using a long coherent integration period, the positioning signal including a periodically repeating sequence that uniquely identifies the transmitter sending the positioning signal, the method comprising:

a) observing, at a receiver, electromagnetic energy at about the carrier frequency and storing data indicative of the observed electromagnetic energy;

b) defining blocks of data that may be subject to unknown frequency drift;

c) assuming a frequency drift on the data block;

d) processing the data in response to the hypothesized frequency drift to provide a drift-adjusted signal;

e) applying the drift-adjusted signal to a correlation system and searching for a match between the drift-adjusted signal and at least one of the plurality of transmitters; and

f) if a matching signal is found, phase delay and timing information is determined, otherwise the steps c to e are cycled through until a matching signal is found, or until a predetermined exit criterion has been met.

12. The method of claim 11, wherein the hypothesized frequency drift is approximately linear.

13. The method of claim 11, wherein the hypothesized frequency drift is approximately exponential.

14. The method of claim 11, wherein the step e comprises:

assuming one of the plurality of transmitters and providing a reference code corresponding to the assumed transmitter;

assuming a PR shift;

correlating the drift adjusted signal with the reference code in response to the PR shifting, thereby providing a correlated data set; and

the correlated data sets are searched to identify signal matches.

15. The method of claim 14, wherein the reference code comprises a time domain signal.

16. The method of claim 11, wherein the transmitter comprises a plurality of GPS satellites that transmit GPS signals at GPS frequencies, each GPS satellite transmitting a unique periodically-repeating sequence.

17. The method of claim 11, wherein the data block has a size corresponding to an integer number of repetitions of the periodically-repeating sequence.

18. The method of claim 11, wherein the data block has a size in a range of one hundred to five hundred repetitions of the periodically repeating sequence.

19. The method of claim 11, further comprising utilizing the timing information to determine a location of the mobile station.

20. The method of claim 11, wherein the block of data corresponds to a time period between ten milliseconds and 1 second.

21. A receiver that uses a long coherent integration period to receive a positioning signal transmitted from one of a plurality of transmitters at a predetermined carrier frequency, the positioning signal including a reference signal that uniquely identifies the transmitter that sent the positioning signal, the method comprising:

means for observing electromagnetic energy at about the carrier frequency, including an antenna;

means for storing data indicative of said observed electromagnetic energy over a predefined period of time;

means for assuming that one of the transmitters thereby assumes one of the plurality of unique reference signals;

means for assuming a frequency drift;

means for defining a data block in response to the data and searching for a match between the data block and the hypothesized reference signal over a plurality of phase shifts in response to the hypothesized frequency drift;

means for determining phase delay and timing information; and

control means for determining whether a matching signal has been found.

22. The receiver of claim 21, wherein the hypothesized frequency drift is approximately linear.

23. The receiver of claim 21, wherein the hypothesized frequency drift is approximately exponential.

24. The receiver of claim 21, further comprising:

means for processing the data block in response to the hypothesized frequency drift to provide a drift-adjusted data signal; and

means for searching for a match between the drift adjusted data block and the hypothesized reference signal.

25. The receiver of claim 21, further comprising:

means for processing the hypothesized reference signal in response to the hypothesized frequency drift to provide a drift-adjusted reference signal; and

means for searching for a match between the data block and the hypothesized reference signal.

26. The receiver of claim 21, further comprising:

means for calculating frequency samples in response to the data block;

means for calculating frequency samples in response to the reference signal; and

means for searching for a match between the Fourier transformed data block and the Fourier transformed reference signal.

27. The receiver of claim 26, further comprising: means for adjusting the data block frequency samples and the vector basis of the periodically repeating sequence in response to the hypothesized frequency drift.

28. The receiver of claim 21, wherein the transmitter comprises a plurality of GPS satellites that transmit GPS signals at GPS frequencies, each GPS satellite transmitting a unique reference signal.

29. The receiver of claim 21, wherein the data block has a size corresponding to an integer number of repetitions of the reference signal.

30. The receiver of claim 21, wherein the block of data corresponds to a time period between ten milliseconds and 1 second.