HK1151859A - Satellite time determination for sps receiver - Google Patents

Description

Satellite time determination for SPS receiver

Cross Reference to Related Applications

This application claims the benefit of U.S. provisional application No.61/032,852, entitled "IMPLIED TIME SETTINGFOR GPS RECEIVER (implicit time setting for GPS receiver)" filed on 29.2.2008, which is incorporated herein by reference in its entirety.

Background

Many wireless communication systems utilize direct sequence spread spectrum to communicate information. The code used to spread the signal is typically a pseudorandom code. The receiver typically recovers the underlying information by correlating the spreading code with a locally generated code.

The receiver may sometimes utilize the time offsets associated with these codes to establish a timing reference that may be used to perform position location. Position determination based on time bases established from pseudo-randomly spread signals is performed in various positioning systems.

A Global Positioning System (GPS) navigation system is an example of a Satellite Positioning System (SPS) that employs satellites located in earth-orbiting motion. Any user of GPS, wherever they are on the earth, can derive accurate navigation information including three-dimensional position, three-dimensional velocity, and time. The GPS system comprises up to 32 satellites deployed in circular orbits of radius 26,600 kilometers in six planes inclined 55 ° with respect to the equator and 120 ° apart from each other. Typically, there are 4 to 6 satellites evenly spaced in each of the six orbital planes. Position measurements using GPS are based on measurements of the propagation delay time of GPS signals broadcast from these orbiting satellites to a GPS receiver. Normally, accurate position determination in 4 dimensions (latitude, longitude, altitude and time) requires reception of signals from 4 satellites. Once the receiver has measured the respective signal propagation delays, the distance to each satellite is calculated by multiplying each delay by the speed of light. The position and time are then found by solving a system of four-way equations with four unknowns that incorporates the measured distances and the known positions of the satellites. The precise capabilities of the GPS system are maintained by means of an onboard atomic clock for each satellite and by a ground tracking station that continuously monitors and corrects the satellite clock and orbital parameters.

Each GPS satellite transmits at least two direct sequence encoded spread spectrum signals in the L-band. I.e., the L1 signal at the 1.57542GHz carrier frequency and the L2 signal at 1.2276 GHz. The L1 signal is composed of two Phase Shift Keying (PSK) spread spectrum signals modulated in phase quadrature. Namely a P-code signal (P for precision) and a C/a code signal (C/a for coarse/acquisition). The L2 signal contains only the P-code signal. The P-code and C/a-code are repetitive pseudorandom bit (also referred to as "chips") sequences modulated onto a carrier wave. The clock-like nature of these codes is exploited by the receiver in making time delay measurements. The codes of each satellite are unique, allowing the receiver to distinguish which satellite transmitted a given code even though the codes are all at the same frequency. Also modulated onto each carrier is a 50 bit/second data stream containing information about the system state and satellite orbit parameters required for the navigation algorithm. The P-code signal is encrypted and is not generally available to commercial and private users. The C/a signal is available to all users.

The operations performed in a GPS receiver are for the most part typical of those performed in any direct sequence spread spectrum receiver. The spreading effect of pseudo-random code modulation must be removed from each signal by multiplying it by a locally generated replica of the time-aligned code in a process called despreading. Since the appropriate time alignment or code delay is unlikely to be known at receiver start-up, it must be determined by searching during the initial "acquisition" phase of GPS receiver operation. Once determined, proper code time alignment is maintained during the "tracking" phase of GPS receiver operation.

Once the received signals are despread, each signal consists of a 50 bit/sec PSK signal at the intermediate frequency carrier frequency. The exact frequency of this signal is uncertain due to doppler effects caused by relative motion between the satellites and the terminal unit and local receiver GPS clock reference errors. This doppler frequency must also be searched during initial signal acquisition because it is typically unknown prior to acquisition. Once the doppler frequency is properly determined, carrier demodulation follows.

After carrier demodulation, the data bit timing is derived by a bit synchronization loop and the data stream is finally detected. Once the signals from 4 satellites have been acquired and locked to, the necessary time delays and doppler measurements have been made, and a sufficient number of data bits (sufficient to determine GPS time reference and orbit parameters) have been received, the navigation algorithm can proceed.

One disadvantage of GPS systems, and in general most SPS systems, used for position determination is that the initial signal acquisition phase takes a long time. As mentioned above, before 4 satellite signals can be tracked, the 4 satellite signals must first be searched in a two-dimensional search "space" whose dimensions are code phase delay and doppler shift. Typically, if there is no a priori knowledge of the location of the signal within this search space, as would be the case after a "cold start" of the receiver, then a large number of code delays (about 2000) and doppler frequencies (perhaps 15 or more) must be searched for each satellite to be acquired and tracked. Thus, for each signal, up to 30,000 or more locations in the search space must be examined. Typically, the locations are checked sequentially one at a time, a process that can take minutes. The acquisition time is further extended if the identities (i.e., PN codes) of the 4 satellites falling within the field of view of the receiving antennas are unknown.

In the case where the SPS receiver has acquired satellite signals and is subsequently in a tracking mode, the position determination process may typically be performed in a time frame much smaller than that required for initial acquisition. However, in routine use of the wireless terminal, the user turns on the power and starts operating quickly. This may be the case when emergency communication is intended. In such circumstances, the time delay associated with a few minutes SPS satellite signal acquisition cold start by the SPS/wireless terminal unit before a position fix can be obtained limits the response time of the system.

Accordingly, there remains a need for systems and methods for improving the ability to determine the time associated with SPS satellite signals and to submit a position fix in an SPS/wireless terminal unit.

SUMMARY

Methods and apparatus for improving SPS positioning performance. The methods and apparatus described herein may be used to improve the fix time for a position determined by an SPS and contribute to the ability to determine a position fix in faint, dim, or otherwise challenging coverage areas. An SPS receiver is able to solve for position location in situations where 2 to 4 or more satellite signals can be received, but only one satellite time can be successfully demodulated. The receiver can utilize the successfully decoded time reference to determine the time associated with the bit edge transition of the signal from the satellite. The receiver uses bit edge transitions from satellites having known times to time at least one bit edge transition of signals from other satellites whose times are not demodulated. The receiver sets the time to a bit edge transition that occurs within a predetermined window that includes bit edge transitions having known times. Based on the time, a location may be determined. Following the invalid position solution hypotheses, the non-demodulated satellite times and window placements may be modified.

Aspects of the invention include a method of positioning in a wireless device. The method includes receiving a pseudo-noise code spread signal from each of at least two satellite vehicles, determining a bit transition edge timing of each pseudo-noise code spread signal, determining a time reference for at least one of the pseudo-noise code spread signals, and determining a positioning solution for the wireless device based on the time reference and the bit transition edge timing of the pseudo-noise code spread signal from each of the at least two satellite vehicles.

Aspects of the invention include a method of positioning in a wireless device. The method includes receiving a pseudo-noise code spread signal from each of at least two Satellite Positioning System (SPS) satellite vehicles, determining a bit transition edge timing for each pseudo-noise code spread signal, determining a time reference for a first pseudo-noise code spread signal, determining a time associated with a first bit transition of the first pseudo-noise code spread signal, configuring a time window that captures the first bit transition of the first pseudo-noise code spread signal and at least one bit transition of a second pseudo-noise code spread signal from which the time reference is unknown, generating a time hypothesis for the at least one bit transition from the second pseudo-noise code spread signal, determining a positioning solution for the wireless device based on the time associated with the first bit and the time hypothesis for the at least one bit transition from the second pseudo-noise code spread signal, and verifying the positioning solution.

Aspects of the invention include a method of positioning in a wireless device. The method includes determining a timing of a bit edge transition for each of a plurality of SPS signals, determining a time reference for at least one bit edge transition, generating a time hypothesis for the plurality of bit edge transitions based on the time hypothesis and the time reference, and determining a positioning solution based on the time hypothesis.

Aspects of the present invention include a positioning apparatus within a wireless device. The apparatus includes a receiver configured to receive a plurality of pseudo noise code spread signals from a plurality of SPS satellite vehicles, a correlator configured to determine a time base of bit edge transitions from each of the plurality of pseudo noise code spread signals, a time base message decoder configured to determine a time reference for at least one of the pseudo noise code spread signals, a hypothesis selector configured to determine a time for a bit edge from each of the plurality of pseudo noise code spread signals, and a position solution module configured to determine a position solution based on the time reference and the time hypothesis for the bit edge from each of the plurality of pseudo noise code spread signals.

Brief Description of Drawings

The features, objects, and advantages of embodiments of the disclosure will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like elements have like reference numerals.

FIG. 1 is a simplified system diagram of an embodiment of a positioning system.

Fig. 2 is a simplified functional block diagram of an embodiment of a positioning receiver.

FIG. 3 is a simplified functional block diagram of an embodiment of an authentication module.

Fig. 4 is a simplified flow diagram of an embodiment of a method for position location using hypothesis time settings.

Fig. 5 is a simplified flow diagram of an embodiment of a location de-validation method.

Fig. 6 is a simplified timing diagram of an example of position resolution using an assumed time setting.

Fig. 7 is a simplified timing diagram of an example of position resolution using the hypothesis time setting.

Detailed description of embodiments of the invention

Methods and apparatus for determining a Satellite Positioning System (SPS) position solution based on at least one time reference to acquire a pseudonoise code spread signal of a satellite vehicle are described herein. The SPS receiver may receive two or more pseudo-noise code spread signals from satellite vehicles and may correlate the signals with a locally generated pseudo-noise code sequence to determine the identity of the satellite vehicles and determine the relative bit edge transition timing of each of the signals. The receiver may demodulate at least one of the satellite signals to determine a time reference from which the associated timing of the bit edge transitions may be determined.

Although the GPS system is used herein for purposes of discussion, it will be appreciated that the SPS may include other satellite positioning systems, such as the GLONASS system operated by Russia, the Galileo system being developed by the European Union, and global satellite navigation projects such as the COMPASS system scheduled for future deployment by China.

Additionally, an SPS may include a regional navigation satellite system that services a particular geographic region ("coverage area") defined by the orbits of its particular satellites. For example, the RNSS may include a Wide Area Augmentation System (WAAS) covering the united states, a European Geostationary Navigation Overlay Service (EGNOS) covering europe and surrounding areas, an MTSAT satellite-based augmentation system (MSAS) serving japan, and a quasi-zenith satellite system (QZSS). It will be appreciated that the RNSS may also include other regional satellite systems such as the GPS Assisted Geo Augmented Navigation (GAGAN) and Indian Regional Navigation Satellite System (IRNSS) system being developed by india and other similar systems. Where the methods and apparatus described herein rely on or otherwise utilize signals from SPS satellite vehicles, SPS satellite vehicle signals may originate from a single SPS or a combination of SVs from multiple SPSs.

A receiver having knowledge of the timing of the bit edge transitions of one satellite and the relative timing of the bit edge transitions of the other satellites can configure a time window having a predetermined duration and place the time window to include at least one bit edge transition having a known timing. The receiver may check for an assumption in which the time of the bit edge transition in the time window is set based on this bit edge transition having a known time base.

The receiver may attempt a position fix with the time setting of the hypothesis and verify the position solution. The position solution and the parameters associated with the position solution may be validated by checking the solution against one or more predetermined constraints. A position solution that satisfies all constraints is considered a valid position solution.

A location solution that fails to satisfy some predetermined number of constraints may be considered an invalid location solution. The receiver may relocate the time window and update the timing hypotheses in response to the invalid position solution. The location solution is tried again and verified. The receiver may repeat this process of relocating the time window, updating the timing hypotheses, and attempting the position solution until a valid position solution is generated or all of the disparate time window configurations and timing hypotheses have been attempted.

The ability to demodulate more than one time reference from an associated satellite signal reduces the number of distinct time window configurations and thereby reduces the total number of timing hypotheses that need to be tested before a valid solution is determined or all possibilities exhausted.

In a general case, when the receiver is configured to determine a three-dimensional position fix based solely on signals from SPS satellite vehicles, the receiver requires signals from at least four distinct SPS satellite vehicles. Under more limited conditions than this general case, the receiver may be able to determine a position fix using signals from fewer than four distinct SPS satellite vehicles.

With additional knowledge about position or system time base, the receiver can use signals from as few as three distinct SPS satellite vehicles to determine a position fix. For example, if the receiver has knowledge of altitude, assumes altitude, or for other reasons only needs to determine a two-dimensional position fix, the receiver may only need signals from three distinct SPS satellite vehicles. Additionally, where the receiver does not have knowledge of the initial position, but has knowledge of the SPS system time, the receiver may use signals from as few as three distinct SPS satellite vehicles to determine the position. The receiver may have knowledge of the SPS system time, for example, by previous time resolution determined in previous position fixes, using a local clock locked to the system time, by receiving system time information from an external source, and the like, or some combination thereof.

In the case where the receiver has knowledge of altitude or otherwise assumes altitude, the receiver may be able to determine a position fix using signals from as few as two distinct SPS satellite vehicles in combination with knowledge of pseudoranges and doppler for the two satellite vehicles for position calculation.

In general, the receiver needs to obtain information sufficient to solve for the three-dimensional position unknowns (x, y, and z in a cartesian coordinate system) and system time. Where one or more of the three-dimensional position or system time is known or can be independently determined for other reasons, the receiver may reduce the number of distinct SPS satellite vehicle signals needed to determine the position solution.

In each of the above circumstances, the receiver need only determine or otherwise derive the timing of the bit edge transitions of one satellite vehicle to determine an effective three-dimensional position fix. The timing of the bit edge transitions of the signals from the one or more additional satellites may be determined based on hypothesis testing in combination with any additional location-related information or parameters, such as altitude, pseudorange, and doppler, or some other parameter.

The functionality of the SPS receiver is improved due to the ability to determine an effective position fix in the presence of only one satellite vehicle signal having sufficient signal quality to demodulate the time reference. The remaining satellite signals required for position fix may be relatively weak signals where only the ability to determine a bit edge transition is required. The ability to determine a successful position solution remains valid despite any initial position uncertainty. Thus, the methods and apparatus may be implemented in a global roaming device where initial position uncertainty may be large or otherwise unknown, but satellite ephemeris data may be readily received or determined. The ability to utilize signals from weak satellite vehicles improves the time to first fix, yield, and accuracy of the SPS receiver. The ability to determine a successful location solution can be particularly helpful in situations where assistance data or initial assumptions are inaccurate, such as information received in the form of a country-based assistance table.

Further, the ease of obtaining a location solution permits the disclosed methods and apparatus to be used as a verification of location determinations made by other location technologies. The methods and apparatus may be performed in a standalone SPS receiver, such as a personal navigation device, and do not require receipt of assistance data.

Fig. 1 is a simplified system diagram of an embodiment of a positioning system 100. The positioning system 100 includes a plurality of satellites 130. The positioning system 100 may also include one or more terrestrial beacons 120, pseudolites, or other signal transmitters. In the embodiment of fig. 1, terrestrial beacon 120 is depicted as a base station, such as a base station of a wireless communication system. The base station may, for example, provide timing signals that may be used in a hybrid positioning system such as hybrid GPS. Alternatively or additionally, the base station may be a source of initial position fixes to reduce position uncertainty and may be configured to provide assistance data such as GPS assistance data. The assistance data may include, but is not limited to, the identity of the satellites above the horizon, suggested code phase search starting points and/or ranges, GPS almanac data, satellite ephemeris data, and the like, or some combination thereof.

If wireless device 110 receives two dissimilar timing signals, wireless device 110 may determine its location. Although the present discussion focuses on location determination based solely on satellite vehicle signals, some positioning systems or variations of positioning systems (such as hybrid GPS) may use signals from terrestrial beacons 120 as part of location determination.

The wireless device 110 may receive a pseudo-random code spread signal from each of at least two satellite vehicles (e.g., 130-1 and 130-n) that are part of a satellite constellation such as a GPS satellite constellation. The number of distinct satellite signals required for wireless device 110 to obtain an effective position fix is based on the amount of additional position-related information available to wireless device 110. As described above, where the wireless device 110 determines a three-dimensional position fix based solely on signals from satellite vehicles, the wireless device 100 requires signals from at least four distinct satellite vehicles 130-1, 130-2, 130-3, and 130-n. Where the wireless device 110 has knowledge of, or is otherwise able to determine, additional location-related information, the wireless device 110 may require signals from as few as two distinct satellite vehicles (e.g., 130-1 and 130-n).

Wireless device 110 may correlate the received signal against a locally generated version of the pseudonoise code sequence, which may be frequency shifted to account for doppler shift. Wireless device 110 may identify a satellite based on the correlation results.

The wireless device 110 may also determine the relative bit edge transitions of each of these satellite signals. The bit edge transition occurs at a transition of the hidden information modulated onto the satellite signal. The hidden information may include, for example, navigation messages, almanac data, satellite ephemeris data, and time reference or timestamp information. Wireless devices are typically able to accurately determine bit edge transitions and are able to increase the sensitivity of bit edge transition determination by increasing the integration time of the received signal. In GPS satellite signals as well as GLONASS satellite signals, the latent data occurs at a rate of 50Hz, so bit edge transitions can occur every 20 milliseconds. In the proposed Galileo satellite system, the bit durations occur at 4 millisecond intervals.

The wireless device 110 may attempt to demodulate the latent message and decode the time message from each of these satellites 130. The time message in the GPS pseudorandom code spread signal repeats every six seconds. Thus, the opportunity to decode out the time message occurs only once in each six second interval. However, the wireless device 110 may not be able to successfully decode the time message information from all of these satellites 130, for example, due to weak satellite signals. If the wireless device 110 is capable of decoding at least one time message in addition to identifying the relative bit edge transition timing of at least one other satellite vehicle, the wireless device 110 is able to make an accurate position determination.

Assume that the wireless device 110 is able to successfully decode the time message of the signal from the first satellite vehicle 130-1. The wireless device 110 may use the time message as a time reference that may be associated with the time of the bit edge transition of the satellite vehicle. Thus, the wireless device 110 has knowledge of the bit edge transition timing based on the ability to decode the timing message.

Because the wireless device 110 also knows the relative bit edge transition timing for each of those satellite vehicles for which the time message was not decoded, the wireless device 110 is able to determine the time for each bit edge transition relative to the known bit edge transition of the first satellite vehicle 130-1.

The time bases of the signals from each of the satellite vehicles 130-1 through 130-n are synchronized to the same GPS time base. However, the signal arriving at wireless device 110 may vary over time due to different propagation delays experienced by different satellite signals. Thus, although the wireless device 110 knows the time of the bit edge transition of the first satellite 130-1 from decoding the timing message, the wireless device does not know whether the signal from each of the other satellite vehicles leads or lags the signal from the first satellite vehicle 130-1. Therefore, the wireless device is not able to immediately deduce the time of each bit edge transition for the second through nth satellites 130-2 through 130-n. Wireless device 110 is only able to determine the time of each bit transition immediately with an error that is a multiple of 20 milliseconds.

Wireless device 110 may resolve the ambiguity of the bit edge transition by windowing the bit edge transition and hypothesis testing. Wireless device 110 may impose a window on these bit edge transitions that is shorter than the desired time variation.

Empirical studies and modeling have revealed that the propagation delay from a GPS satellite vehicle to substantially any point on earth where the satellite is visible ranges from an absolute minimum of about 65 milliseconds to an absolute maximum of about 88 milliseconds, as long as the satellite is above zero degrees horizon. It is unlikely that the same location will experience both the minimum and maximum satellite propagation delays at the same time. However, the window may be set based on the difference between the maximum propagation delay and the minimum propagation delay. Thus, the window size may be less than approximately 22 milliseconds, less than approximately 23 milliseconds, or some other value. Utilizing an insufficient window duration may result in an inability to determine time hypotheses that result in a valid position determination. However, extending the window time excessively creates numerous time hypotheses to verify that a valid position determination will not be reasonably made. A window size of approximately 20, 21 or 22 milliseconds is convenient not only because it covers substantially the entire range of propagation delays, but also because it is on the order of a single bit period lasting 20 milliseconds. Thus, repositioning a window size of approximately 20, 21 or 22 milliseconds across all possibilities results in at most three different bit edge transitions from a single satellite vehicle that need to be accounted for in the time hypothesis test.

The wireless device 110 places a window near each received satellite signal bit edge transition and places the window to include at least one known bit edge transition from the first satellite 130-1. The wireless device 110 may then determine a set of time hypotheses based on the location of the window, the time of the known bit edge transition, and the location of the bit edge transitions of the other satellites relative to the known bit edge transition.

In one embodiment, wireless device 110 assumes the time base of each unknown bit edge transition occurring closest to the known bit edge time as the time of the known bit edge time. The wireless device 110 determines a position solution for the time hypothesis. Wireless device 110 may, for example, implement substantially any type of pseudorange measurement based location resolution. The wireless device 110 may have knowledge of the satellite positions based on, for example, valid ephemeris data for the satellites or based on a satellite orbit prediction algorithm.

Wireless device 110 may, for example, implement iterative position solution techniques such as weighted least squares, minimum least squares, weighted regression, Kalman (Kalman) filtering, and the like, or some combination thereof. Wireless device 110 may verify the location solution. If the location solution is successfully verified, then the location solution is the location solution for the wireless device 110. However, if the position solution is not valid, then the wireless device 110 shifts or otherwise updates the position of the window and updates the time hypothesis. Wireless device 110 repeats the location solution and verification process followed by the window relocation process until all disparate window placements and time hypotheses have been tested or until a valid location solution is determined.

Fig. 2 is a simplified functional block diagram of an embodiment of a positioning receiver 200. The positioning receiver 200 may be implemented, for example, within the wireless device of fig. 1 to perform positioning.

The receiver 200 includes an antenna 202 coupled to a receive front end 210. The output of the receive front-end is coupled to sampler 212. The output of sampler 212 is coupled to a buffer 214.

The receive front end 210 is configured to tune to a nominal receive frequency of the GPS satellite signals to receive a composite signal, which may include a plurality of pseudo noise code spread signals corresponding to a plurality of satellite vehicles. The receive front end 210 filters, amplifies, and frequency converts the received composite signal. Sampler 212 may be configured to sample the receive front-end output and convert the analog signal output from the receive front-end into a digital representation. Sampler 212 may be configured to sample the received signal at a rate higher than a chip rate associated with the pseudo-noise code. For example, sampler 212 may be configured to sample at a chip rate, twice the chip rate, four times the chip rate, or some other multiple or non-multiple of the chip rate. Sampler 212 may be configured to store the samples in a buffer 214.

The contents of the buffer 214 may be accessed by a plurality of correlators 220-1 through 220-k, which plurality of correlators 220-1 through 220-k may be configured substantially in parallel to speed up signal acquisition. Each correlator 220 may be configured to search a distinct pseudo-noise code space. Alternatively, multiple correlators 220 may be configured to search the same pseudo-noise code space, but may operate on distinct samples from buffer 214. In some embodiments, different subsets of correlators 220 are configured to perform distinct pseudo-noise code space searches across different sample groups from buffer 214. Each correlator 220 may determine a code phase offset for a particular code phase and may also determine bit edge transitions for a particular satellite signal associated with a pseudo noise code that configures the correlator 220 specifically.

The output from the correlator 220 is coupled to a navigation message demodulator/decoder 230 that may be configured to decode the navigation messages from each of those satellite vehicles for which signals were detected. The navigation message decoder 230 can be coupled to a time-based message decoder 234 that can examine successfully demodulated and decoded navigation messages and attempt to decode time-based messages from the navigation messages.

The timebase message decoder 234 may be coupled to the controller 240. Timebase message decoder 234 may notify or otherwise communicate timebase message information and associated satellite vehicle information to controller 240. Based on the time-based message information, the controller 240 may assign or otherwise determine a time for a bit edge transition from the satellite vehicle corresponding to the time-based message. The time of this bit edge transition may represent the propagation delay from the satellite vehicle to the receiver 200. The controller 240 need not resolve any ambiguity in the absolute time of the bit edge transition timebase at this point, but instead may select the bit edge transition timebase such that the total propagation delay measured at the receiver 200 is near the center of the range of expected propagation delays. When the position solution is determined, the actual bit edge transition timebase can be resolved.

The controller 240 may be in communication with a computer-readable medium, such as a memory 242. The memory may store one or more computer readable instructions that cause the controller to perform some, or all, of the methods described herein. In some implementations, the controller 240, in conjunction with the instructions in the memory 242, may be configured to perform some or all of the functions of the window module 250, hypothesis selector 260, position solving module 270, and verifier 280.

A windowing module 250 is coupled to each correlator 220 and receives bit edge transition information from the correlators 220. The window module 250 may be configured to filter or otherwise select only those bit edge transitions that occur within the duration of the window.

The controller 240 may be configured to initially place the window based on the position of the time-known bit edge transition. The controller 240 or the window module 250 may reposition the window subsequent to determining an invalid timing hypothesis.

Assume that selector 260 is configured to receive, point to, or identify a bit edge transition from window module 250. Assume that the selector 260 can be configured to set the time base for each of the bit edges within the window based on the known time of the bit edge transition. In one embodiment, the hypothesis selector 260 sets each bit edge transition within the window based on the known time of the bit edge transition. If the same satellite vehicle has more than one bit edge transition within the window, then the hypothesis selector 260 may use an arbitration rule. For example, assume that selector 260 may be configured to set the bit edge transition that is closest to the occurrence of a known bit edge transition based on the time of the known bit edge transition.

The position solution module 270 is configured to determine a position solution based on the timing hypotheses set by the hypothesis selector 260. At this point, the pseudorange measurements for each satellite are indistinguishable from the position solution module 270 over pseudorange measurements obtained using conventional approaches. Accordingly, the position solution module 270 may be configured to determine the position solution using conventional techniques, such as position solution techniques, which may include weighted least squares, infinitesimal least squares, weighted regression, kalman filtering, and the like, or some combination thereof.

The position solution module 270 may determine the solution in conjunction with satellite position information, which may be stored in memory 242. The satellite position information may be stored, for example, as one or more of a satellite almanac, a satellite ephemeris, a satellite orbit prediction function, or some combination thereof.

The verifier 280 processes the results from the position solution module 270 to determine if the solution is valid. If the position solution is valid, then the process is complete and the position of the receiver 200 is determined. If the position solution is invalid, the window module repositions the window and the hypothesis selector 260 generates another timing hypothesis to be tested. The verifier 280 may determine an invalid solution, for example, if the iterative position solution algorithm fails to converge after some predetermined number of iterations.

Fig. 3 is a simplified functional block diagram of an embodiment of verifier 280. The verifier 280 may be, for example, a verifier in the receiver of fig. 2. The verifier 280 receives the position solution information from the position solution module and processes the information according to a number of constraints to determine the validity of the position solution.

The verifier 280 may include an altitude verifier 310, a transmission delay verifier 320, a satellite vehicle altitude verifier 330, a user velocity verifier 340, a doppler residual verifier 350, or some combination thereof. The various validator 280 modules may operate independently of each other or one or more validator 280 modules may depend on each other. The number and type of modules within the verifier 280 are not limited to those illustrated in the embodiment of fig. 3.

The altitude verifier 310 may examine the position solution and compare the altitude of the position solution against the bounds of minimum and maximum altitudes. For example, altitude verifier 310 may include some depth below sea level that the effective altitude will not be below. Similarly, altitude verifier 310 may include a predetermined altitude that a valid altitude location solution will not exceed. An altitude that falls outside a predetermined range is identified as an invalid solution.

In those situations where the receiver has knowledge of altitude or is otherwise configured to determine a two-dimensional position fix, the altitude validator 310 may be omitted, disabled, or otherwise ignored.

Similarly, the transmission delay verifier 320 examines the propagation delays corresponding to the corrected time base as determined from the position solution and determines whether any of the propagation delays fall outside a predetermined range. As an example, the propagation delay for any point on the earth is estimated to range from approximately 65 milliseconds to 88 milliseconds as long as the satellite vehicle is above the zero degree horizon. If the corrected propagation delay from the position solution falls outside this range, the transmission delay verifier 320 may identify the solution as invalid.

Satellite vehicle elevation verifier 330 may determine whether all satellite vehicles utilized in the position solution are above the zero degree horizon. The satellite vehicle elevation verifier 330 may check the position solution against the assumed position of the satellite vehicle used to generate the position solution. The elevation angle of the satellite vehicle may be determined based on the position solution and knowledge of the assumed satellite position. If any of the satellite vehicle elevation angles is less than 0, SV elevation verifier 330 may invalidate the solution identifier.

The user velocity verifier 340 may calculate the velocity of the wireless device based on the location solution and the doppler values from each of the four satellite vehicles. Speeds outside the predetermined range may cause the user speed verifier to identify the position solution as invalid.

The doppler residual verifier 350 compares the calculated pseudorange variability to the measured pseudorange variability. The doppler residual verifier 350 may compare the measured doppler against theoretical doppler based on the location solution and determine whether the residual is greater than a predetermined threshold. If the residual falls outside of the predetermined range, the Doppler residual verifier 350 may identify the location solution as invalid.

Although each verifier may identify the location solution as invalid independently of each other, the output values of the verifiers are all provided to verification logic 360, which verification logic 360 is able to make a final determination as to the validity of the location solution based on one or more invalidity indications. The validation logic may, for example, be configured to indicate a single invalid indication, an invalid result of multiple invalid indications, or indicate an invalid result based on a predetermined combination of invalid indications or a weighted combination of invalid indications.

Fig. 4 is a simplified flow diagram of an embodiment of a method 400 for position location using hypothesis time settings. The method 400 may be implemented in the wireless device of fig. 1, for example, by the receiver of fig. 2.

The method 400 begins at block 410 where the receiver receives pseudo noise code spread signals from at least two satellite vehicles. The receiver proceeds to block 412 and determines the satellite vehicle identity, for example by correlating the received signal against a locally generated version of the pseudonoise code sequence.

The receiver proceeds to block 414 and determines a bit edge transition for each of the at least two satellite vehicle signals. The receiver can use correlation to determine these bit edge transitions and can integrate over several complete pseudo-noise code periods to improve detection sensitivity.

The receiver proceeds to block 420 and decodes at least one time stamp or otherwise determines a time reference associated with at least one of the satellite aircraft signals. The receiver may, for example, demodulate the navigation message and decode the time message from the satellite vehicle signal.

The receiver needs to determine at least one time reference to successfully perform the method 400. However, the number of ambiguous time hypotheses that need to be checked decreases with each additional time reference. At the limit of the four time references, the method 400 is no longer necessary for a generalized solution based solely on satellite vehicle signals, and the receiver can directly determine pseudoranges. However, the receiver may still utilize this method to enable position solution verification using a fifth satellite vehicle signal that does not require a time reference.

The receiver proceeds to block 430 and configures a time window for the bit edge transition based on the location of the known bit edge transition corresponding to the satellite vehicle for which the time reference is known. The duration of the window may be selected to be substantially a duration that matches the difference between the maximum satellite vehicle propagation delay and the minimum satellite vehicle propagation delay. As an example, the window may have a duration of less than about 22 milliseconds.

The receiver proceeds to block 440 and determines timing hypotheses for the bit edge transitions within the window. The receiver may, for example, assume that each bit edge transition in the window occurs based on a known time of the bit edge transition.

The receiver proceeds to block 450 and determines a position solution based on the pseudorange measurements and knowledge of the satellite vehicle position, e.g., determined based on almanac, satellite ephemeris data, satellite orbit predictions, or some combination thereof. The location solution may also rely on relevant location information (if any) available to the receiver. Such pertinent location information may include, for example, estimates of receiver altitude, combinations of doppler measurements observed at the receiver and corresponding pseudoranges, and the like, or some combination thereof.

The receiver may determine the position, for example, based on an iterative position determination algorithm such as a weighted least squares algorithm. The receiver proceeds to decision block 452 to determine whether the position determination algorithm converges on a solution. If not, the solution is invalid. The receiver proceeds to block 460.

If the receiver determines at decision block 452 that the position determination algorithm returns a position solution, the receiver proceeds to decision block 470 and determines whether the solution passes the verification process. If not, the receiver proceeds to block 460.

At block 460, the receiver shifts or otherwise reconfigures the window position to capture a different set of bit edge transition hypotheses. From block 460, the receiver returns to block 440 to repeat the timing hypothesis/position solution process.

If the location solution satisfies the verification process at decision block 470, the receiver proceeds to block 480 to return the location solution as the location of the receiver.

Fig. 5 is a simplified flow diagram of an embodiment of a location de-validation method 470. Method 470 may be implemented by a receiver performing the method of fig. 5.

The method 470 begins at decision block 510 where the receiver determines whether the position solution includes an altitude within predetermined limits. If not, the receiver proceeds to block 560 and identifies the solution as invalid.

If the receiver determines that the altitude constraint is satisfied, the receiver proceeds to decision block 520 to determine whether the propagation delay from the satellite vehicle used in this position solution determination is within a predetermined range of values. If not, the receiver proceeds to block 560 to identify the solution as invalid. When the receiver performs a 2D position solution using a known or given altitude, this step of determining whether the position solution altitude is within bounds may of course be bypassed.

If the receiver determines that the propagation delay constraint is satisfied, the receiver proceeds to decision block 530 to determine if the satellite vehicle used in the position solution is above the horizon for the device located at the position of the position solution. If not, the receiver proceeds to block 560 to identify the solution as invalid.

If the receiver determines that the satellite vehicle altitude constraint is satisfied, the receiver proceeds to decision block 540 to determine if the user speed falls within a predetermined range or limit. If not, the receiver proceeds to block 560 to identify the solution as invalid.

If the receiver determines that the user velocity satisfies the velocity constraint, the receiver proceeds to decision block 550 to determine if the Doppler residual is within predetermined limits. The receiver may compare the measured doppler against a theoretical doppler based on the position solution and the receiver clock frequency offset and determine whether the residual is greater than a predetermined threshold. If so, the receiver proceeds to block 560 to identify the solution as invalid. Otherwise, the receiver proceeds to block 570 and de-identifies the location as valid.

Fig. 6 is a simplified timing diagram 600 of an example of a position solution using an assumed time setting. Timing diagram 600 illustrates bit edge transitions for four satellite vehicles and four possible timing hypotheses that may be generated for a predetermined window duration of approximately 22 milliseconds.

The first satellite vehicle is assumed to be a satellite vehicle for which the time reference is known. Thus, the first SV bit edge transition 610 is a known and time-unambiguous bit edge transition, and only one bit edge transition need be illustrated. The time of adjacent bit edge transitions of the first SV may be determined by subtracting or adding 20 milliseconds from or to this known bit edge transition, where 20 milliseconds is the period of each bit.

The second satellite vehicle has two bit edge transitions 620-1 and 620-2 that can be identified relative to the first SV known bit edge transition 610. However, there is ambiguity as to whether the earlier bit edge transition 620-1 or the later bit edge transition 620-2 synced to this known bit edge transition 610.

Similarly, two bit edge transitions 630-1 and 630-2 for a third satellite vehicle are shown relative to the first SV known bit edge transition 610. Two bit edge transitions 640-1 and 640-2 for a fourth satellite vehicle are shown relative to the first SV known bit edge transition 610.

A first time base hypothesis is illustrated based on a first position 652 of the time window. Each bit transition 610, 640-2, 620-2, and 630-2 within window 652 is set relative to the time at which the bit edge transition is known for the first SV. A position solution may be determined based on the pseudoranges from the time base hypothesis to each satellite vehicle.

A second timing hypothesis is illustrated based on a second position 654 of the time window. The time window is shifted to capture at least one distinct bit edge transition that is not in the first position of the window. Bit transitions 630-1, 610, 640-2, and 620-2 within second position 654 of the time window are set relative to the time at which the bit edge transition is known for the first SV. A position solution may be determined based on the pseudoranges from the second time base hypothesis to each satellite vehicle.

A third timing hypothesis is illustrated based on a third position 656 of the time window. The time window is shifted to capture at least one distinct bit edge transition. Bit transitions 620-1, 630-1, 610, and 640-2 within a third position of time window 656 are set relative to the time at which the bit edge transition is known for the first SV. A position solution may be determined based on the pseudoranges from the third time base hypothesis to each satellite vehicle.

A fourth time base hypothesis is illustrated based on a fourth position 658 of the time window. The time window is shifted to capture at least one distinct bit edge transition. Bit transitions 640-1, 620-1, 630-1, and 610 within fourth position 658 of the time window are set relative to the time at which the bit edge transition is known for the first SV. A position solution may be determined based on the pseudoranges from the fourth time base hypothesis to each satellite vehicle.

Note that with the duration window shown in fig. 6, there are only four possible timing hypotheses. Further shifting of the time window will exclude known bit edge transitions. Therefore, the receiver will need to try at most four position solutions based on these four timing hypotheses before determining the correct position solution.

Fig. 7 is a simplified timing diagram 700 of an example of a position solution using the hypothetical time setting. The timing diagram 700 of fig. 7 illustrates two known time references for two satellite vehicles. Timing diagram 700 illustrates how the additional knowledge of the second time reference reduces the number of possible timing hypotheses to only two if the time window has a duration on the order shown.

The timing diagram 700 illustrates a first bit edge transition 710 for a first satellite vehicle with a known time reference. Similarly, a second bit edge transition 720 for a second satellite vehicle with a known time reference is shown.

Ambiguous bit edge transitions 730-1 and 730-2 for a third satellite vehicle and ambiguous bit edge transitions 740-1 and 740-2 for a fourth satellite vehicle are shown. A time reference has not been or cannot be determined for the third and fourth satellite vehicles.

The first time base hypothesis may be generated by placing the first time window 752 in a manner that captures at least first and second known bit edge transitions 710 and 720 and at least one bit edge transition 740-2 and 730-2 from each of those satellite vehicles lacking a known time reference.

The second timing hypothesis may be generated by positioning the second time window 754 to capture at least the first and second known bit edge transitions 710 and 720 and at least one bit edge transition 730-1 and 740-2 from each of those satellite vehicles lacking a known time reference. As shown in fig. 7, these timing hypotheses are the only two possible timing hypotheses for a time window of this size and for the known location of bit edge transitions 710 and 720. Further shifting of the time window will remove one of these known bit edge transitions from the window.

Methods and apparatus for determining a positioning solution where as few as one time reference for a plurality of SPS satellite signals is known, but bit edge transitions for at least four satellite signals are known and satellite position information is available are described herein. The methods and apparatus enable a receiver to determine a position solution in a poor coverage environment that is unable to demodulate the time information in the navigation message of the plurality of satellite signals.

As used herein, the term coupled or connected is used to refer not only to a direct coupling or connection, but also to an indirect coupling. Where two or more blocks, modules, devices, or apparatus are coupled, there may be one or more intervening blocks between the two coupled blocks.

The various illustrative logical blocks, modules, and circuits described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a Digital Signal Processor (DSP), a Reduced Instruction Set Computer (RISC) processor, an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method, process, or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. The various steps or actions in a method or process may be performed in the order presented, or may be performed in another order. Further, one or more process or method steps may be omitted, or one or more process or method steps may be added to the methods and processes. Additional steps, blocks, or actions may be added to the methods and processes at the beginning, end, or in between their existing elements.

In one or more exemplary embodiments, the functions described may be implemented in hardware, software, firmware, or any combination thereof. If implemented in software or firmware, the functions may be stored on a physical computer-readable medium as one or more instructions, information, or code encoded therein. Computer-readable media includes physical computer storage media. A storage media may be any available physical media that can be accessed by a computer. By way of example, and not limitation, such computer-readable media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store desired program code in the form of instructions or data structures and that can be accessed by a computer. Disk (disk) and disc (disc), as used herein, includes Compact Disc (CD), laser disc, optical disc, Digital Versatile Disc (DVD), floppy disk and blu-ray disc where disks (disks) usually reproduce data magnetically, while discs (discs) reproduce data optically with lasers.

The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present disclosure. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the disclosure. Thus, the present disclosure is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (29)

1. A method for positioning in a wireless receiver, the method comprising:

receiving a pseudo noise code spread signal from each of at least two satellite vehicles;

determining a bit transition edge time base for each pseudo noise code spread signal;

determining a time reference for at least one of the pseudo-noise code spread signals; and

determining a positioning solution for the wireless device based on the time reference and a bit transition edge timing of the pseudo-noise code spread signal from each of the at least two satellite vehicles.

2. The method of claim 1, further comprising correlating the pseudo-noise code spread signal with a locally generated pseudo-noise code sequence to identify the at least two satellite vehicles.

3. The method of claim 1, further comprising determining a time associated with a bit edge relative to the time reference.

4. The method of claim 1, wherein receiving the pseudo-noise code spread signal comprises receiving a global positioning system navigation message spread by a pseudo-noise code corresponding to a satellite vehicle.

5. The method of claim 1, wherein determining the bit transition edge timing comprises:

correlating the pseudo-noise code spread signal with a locally generated pseudo-noise code sequence; and

the transition time base of the associated phase reversal is determined.

6. The method of claim 1, wherein determining the time reference comprises decoding some or all of navigation messages from at least one of the pseudo-noise code spread signals.

7. The method of claim 1, wherein determining the positioning solution comprises:

determining a known time associated with a bit edge relative to the time reference;

configuring a time window encompassing bit transitions of the pseudo noise code spread signal from each of the at least two satellite vehicles;

generating a time hypothesis for at least one bit transition falling within the window for a signal from at least one satellite vehicle for which a time reference is unknown; and

determining the positioning solution based on the known time and the time hypothesis.

8. The method of claim 7, further comprising:

shifting the position of the time window;

generating an updated time hypothesis; and

determining an updated positioning solution based on the known time and the updated temporal hypothesis.

9. The method of claim 1, further comprising validating the positioning solution.

10. The method of claim 9, wherein validating the solution comprises at least one of altitude validation, transmitter propagation delay validation, satellite vehicle altitude validation, device speed validation, and doppler residual validation.

11. The method of claim 9, wherein validating the solution comprises determining whether an iterative position solution converges within a predetermined number of iterations.

12. A method for positioning in a wireless receiver, the method comprising:

receiving a pseudo noise code spread signal from each of at least two pseudo noise code spread signal transmitters;

determining a bit transition edge time base for each pseudo noise code spread signal;

determining a time reference for the first pseudo-noise code spread signal;

determining a time associated with a first bit transition of the first pseudo-noise code spread signal;

configuring a time window that captures the first bit transition and at least one bit transition from a second pseudo-noise code spread signal whose time reference is unknown;

generating a time hypothesis for the at least one bit transition from the second pseudo-noise code spread signal;

determining a positioning solution for the wireless device based on the time associated with the first bit transition and the time hypothesis for the at least one bit transition from the second pseudo-noise code spread signal; and

and verifying the positioning solution.

13. The method of claim 12, further comprising:

shifting the position of the time window;

generating an updated time hypothesis; and

determining an updated positioning solution based on the time associated with the first bit transition and the updated temporal hypothesis.

14. The method of claim 12, wherein configuring the time window comprises configuring a time window of less than 22 millisecond duration.

15. A method for positioning in a wireless receiver, the method comprising:

determining a time base of a bit edge transition for each Satellite Positioning System (SPS) signal of a plurality of SPS signals;

determining a time reference for at least one bit edge transition;

generating a time hypothesis for the plurality of bit edge transitions based on the time hypothesis and the time reference; and

determining a positioning solution based on the temporal hypothesis.

16. A positioning apparatus within a wireless device, the apparatus comprising:

a receiver configured to receive a plurality of pseudo noise code spread signals from a plurality of satellite positioning system satellite vehicles;

a correlator configured to determine a time base of bit edge transitions from each pseudo noise code spread signal of the plurality of pseudo noise code spread signals;

a time-based message decoder configured to determine a time reference for at least one of the pseudo-noise code spread signals;

an hypothesis selector configured to determine temporal hypotheses about bit edges from each of the plurality of pseudo-noise-code spread signals; and

a position solving module configured to determine a positioning solution based on the position reference and the time hypothesis regarding bit transitions from each of the plurality of pseudo-noise code spread signals.

17. The apparatus of claim 16, further comprising:

a windowing module configured to determine a time window in which at least one bit edge of each pseudo-noise code spread signal from the at least two pseudo-noise code spread signals occurs, and

wherein the hypothesis selector determines temporal hypotheses about bit edges occurring within the time window.

18. The apparatus of claim 17, wherein the time window comprises a time window of less than 22 millisecond duration.

19. The apparatus of claim 16, further comprising a verifier configured to verify the positioning solution based on at least one predetermined constraint.

20. The apparatus of claim 19, wherein the at least one predetermined constraint comprises at least one of an altitude constraint, a transmitter propagation delay constraint, a satellite vehicle altitude constraint, a device velocity constraint, and a doppler residual constraint.

21. The apparatus of claim 16, wherein the hypothesis selector is to update temporal hypotheses about the bit edges from each of the plurality of pseudo-noise-code spread signals if the verifier indicates an invalid position solution.

22. The apparatus of claim 16, wherein the time-based message decoder determines the time reference by decoding a message encoded on a first pseudo-noise-code spread signal of the plurality of pseudo-noise-code spread signals.

23. The apparatus of claim 16, wherein the hypothesis selector sets a time associated with a bit edge of each pseudo-noise-code spread signal from the plurality of pseudo-noise-code spread signals to a same time.

24. The apparatus of claim 23, wherein the same time is determined based on the time reference and a first bit edge of the at least one of the pseudo-noise-code spread signals associated with the time reference.

25. A positioning device within a wireless device, the device comprising:

means for receiving a pseudo-noise code-extended signal from each of at least two satellite vehicles;

means for determining a bit transition edge time base for each pseudo-noise code spread signal;

means for determining a time reference for at least one of the pseudo-noise code spread signals; and

means for determining a positioning solution for the wireless device based on the time reference and a bit transition edge timing of the pseudo-noise code spread signal from each of the at least two satellite vehicles.

26. The apparatus of claim 25, wherein the means for determining a positioning solution comprises:

means for determining a known time associated with a bit edge related to the time reference;

means for configuring a time window encompassing bit transitions of the pseudo-noise code spread signal from each of the at least two satellite vehicles;

means for generating a time hypothesis for at least one bit transition falling within the window for a signal from at least one satellite vehicle for which a time reference is unknown; and

means for determining the positioning solution based on the known time and the time hypothesis.

27. The apparatus of claim 26, further comprising:

means for shifting the position of the time window;

means for generating an updated temporal hypothesis; and

means for determining an updated positioning solution based on the time associated with the first bit transition and the updated temporal hypothesis.

28. The apparatus of claim 25, further comprising means for validating the positioning solution.

29. A computer-readable medium encoded with one or more computer-readable instructions, which, when executed by a computer, cause the computer to perform the acts of:

determining a bit transition edge time base for each pseudo noise code spread signal from the plurality of pseudo noise code spread signals;

determining a time reference for at least one pseudo-noise code spread signal of the plurality of pseudo-noise code spread signals; and

determining a positioning solution for the wireless device based on the time reference and a bit transition edge timing of each of the pseudo-noise code spread signals.