HK1093239A - System for setting coarse gps time in a mobile station within an asynchronous wireless network - Google Patents

Abstract

A method and apparatus for setting coarse GPS time in a GPS receiver in a mobile station (MS) that is communicating with a base station and a position determining entity (PDE). The MS requests an assistance message from the PDE that includes a sequence of predicted navigation bits, including a predicted time indicator field, which is then located and decoded. Coarse time is set responsive to the time indicator value. A Pattern Match Algorithm may be performed to provide more precise GPS time. In order to better set coarse time, an expected error in the Time of Week may be determined, by for example using the expected network latency. The system described herein enables the use of IS-801 protocol by an MS in asynchronous networks by improving the coarse time setting process.

Description

System for setting coarse GPS time in mobile station in asynchronous wireless network

Related application

This application claims priority from U.S. provisional application No. 60/489,652, filed on 23/7/2003.

Technical Field

The present invention relates generally to positioning systems that determine the position of a mobile station, such as a cellular telephone, using wireless signals.

Background

Existing Global Positioning System (GPS) satellite-based positioning technologies utilize a network of satellites, commonly referred to as Space Vehicles (SVs), that transmit signals that are accurately phase referenced to GPS time. GPS receivers on the ground measure the relative times of arrival of signals from each SV that is "in-view" (i.e., the SV from which each such receiver can receive signals). The relative times of arrival of the signals, along with the precise locations of the SVs, are used to determine the position of a GPS receiver using a technique commonly referred to as trilateration. A relatively accurate estimate of GPS time is needed at the time of transmission of signals from each SV in order to accurately determine the position of each SV at the time of signal transmission. For example, the SV may move up to 950 meters per second relative to the earth. The position of an SV is calculated using a mathematical equation that predicts its position in orbit at a particular point in time. Due to the speed of the SVs, a one millisecond time error will equate to an SV position error of up to 0.95 meters. The resulting error in the GPS receiver position calculation may be different. However, it is a common rule of thumb that a one millisecond time error will result in an error of about 0.5 meters in the calculated GPS receiver position.

To know the exact time that a signal is transmitted from an SV, a standard GPS receiver demodulates the time of transmission from the received signal or maintains a clock bias estimate that estimates the difference between the local receiver clock and GPS time. Establishing a time offset between the free running clock of the GPS receiver and GPS time is commonly referred to as a "set clock". If the GPS receiver is receiving SV signals in good condition, the GPS receiver may set a clock based on information contained in the received signals. The received information indicates the time of transmission. However, even in the best case, setting the clock may take a significant amount of time (e.g., up to 6 seconds or more) due to the amount of time required to receive the necessary information transmitted by the SVs. Furthermore, in environments where information is blocked or impaired, the GPS receiver cannot set the clock to GPS time at all, and therefore cannot determine its position at all.

Another way to set the clock is to synchronize the clock to a reference clock that has a known relationship to GPS time. For example, synchronization to GPS time is straightforward in a CDMA Mobile Station (MS) such as a cellular telephone used in a CDMA network. This is because the CDMA network is synchronized with GPS time. Synchronization with GPS time means that transmissions from each base station within the network are referenced to GPS time. Thus, the CDMA receiver in the MS knows GPS time. Operating software within the MS may simply pass this GPS time to GPS receiver software by, for example, associating the GPS time with a precise hardware signal or pulse that allows the GPS receiver software to relate the GPS time to its own clock time in a precise manner. As described above, the prior knowledge of the precise GPS time within the GPS receiver can significantly shorten the time required to determine the GPS receiver position (commonly referred to as "obtaining GPS coordinates"). Especially in noisy environments, a priori knowledge of the precise GPS time may be important or even necessary to obtain the GPS coordinates.

In order to more quickly and efficiently determine GPS coordinates in a CDMA system, the electronics industry association/telecommunications industry association (EIA/TIA) employs a standard known as the "IS-801 standard" or simply "IS-801". IS-801 includes a set of rules (commonly referred to as a "protocol"). The protocol specifies the data content and message sequences that can be exchanged between a location server, commonly referred to as a PDE, and the MS. These IS-801 messages help the GPS receiver to measure virtual distances and/or generate location coordinates. For example, the IS-801 message includes a request for "ephemeris". Ephemeris is information about the SV orbit. The IS-801 message also includes other assistance information, such as information about the bit patterns that the SV IS expected to transmit. The prediction of the bits allows the GPS receiver to perform coherent integration over a longer period of time. This in turn increases the sensitivity of the GPS receiver.

However, some cellular networks, such as global system for mobile communications (GSM) networks, are not synchronized with GPS time. Such systems are referred to as "asynchronous". Thus, GPS receivers in asynchronous networks cannot directly access GPS time from the communication signal. A GPS system that cannot obtain GPS time from the communication system may take longer to determine GPS coordinates in the presence of interference or if signals from SVs are attenuated. In extreme cases, if there is too much interference, the GPS coordinates may not be determined. One method of determining GPS time in an asynchronous system is known as a "pattern matching" method. In the pattern matching method, the time at which a GPS signal is received at the MS is compared with the time at which the GPS signal is received at a reference receiver synchronized with GPS time. Assuming that the distance between the transmitting SV and the reference receiver is substantially equal to the distance between the transmitting SV and the GPS receiver, the time at which the reference receiver receives the signal may be used to set a clock within the GPS receiver. However, since the information transmitted by the GPS SVs is repetitive, efficient operation of the pattern matching method requires the MS to be "coarsely" synchronized with GPS time, e.g., within a few seconds. Otherwise, it is not possible to determine whether the information received by the GPS receiver was transmitted at the same time as the information received by the reference receiver.

For example, assume that a particular GPS SV transmits the same information every two seconds. Further assume that the clock in the GPS receiver may be cancelled by two seconds from the clock in the reference receiver. Now assume that the clock in the reference receiver and the clock in the GPS receiver both indicate that the information in question is received at exactly 12:00 pm. Since we do not know when the GPS receiver actually received the information, the information may in fact be received at full 12:00 pm, two seconds before 12:00 pm, or two seconds after 12:00 pm. In other words, the information received by the GPS receiver may be that the SV was actually sent at the same time, two seconds before, or two seconds after the reference receiver received the information. Therefore, it is not possible to determine whether the clock in the reference receiver is perfectly synchronized or out of synchronization with the MS for two seconds.

Coarse time synchronization ensures that the clock within the MS is synchronized with GPS time with sufficient accuracy to ensure that the pattern matching method can determine an accurate time without doubt. Several methods are known for establishing coarse time synchronization. In one approach, a transmit and acknowledge message pair is used. For example, the MS transmits a time request and simultaneously starts a local timer. The BTS receives the request from the MS and acknowledges receipt of the request by sending the current time. The MS receives a time estimate from the BTS. The MS then terminates the local timer and reads the elapsed time. Such a system may assist in establishing coarse synchronization, but it adds cost, may become more complex, and may cause undesirable time delays. Therefore, there is a need for a faster and more efficient system for setting coarse GPS time within a GPS receiver.

Disclosure of Invention

The method and system described herein enables the IS-801 protocol, which IS intended only for synchronous networks, to be used by Mobile Stations (MSs) in asynchronous systems by improving the procedures used to set coarse time. One implementation of the disclosed method and system allows a "pattern matching" algorithm to more accurately set the receiver's clock to accurate GPS time.

A method is described for setting coarse GPS time in a GPS receiver of a Mobile Station (MS) that communicates with a Position Determination Entity (PDE) through a base station. The GPS receiver is configured to periodically receive transmitted navigation bits from a plurality of SVs synchronized to GPS time. The navigation bits include at least one time indicator field. The MS requests a Sensitivity Assistance (SA) message from the PDE. The message includes a sequence of predicted navigation bits. In response to a request from the MS, an SA message is sent from the base station in approximate time with GPS time. The SA message is received in the MS and the time of reception is saved. Within the predicted navigation bits is located a predicted time indicator field. A predicted "time of week" (TOW) is determined in response to the located time indicator field. In response to the predicted TOW, coarse GPS time is set within the GPS receiver to reflect the receipt of the predicted navigation bits at the time indicated by the predicted TOW. Using the coarse time, the GPS receiver may more quickly and efficiently determine the position of the GPS receiver. For example, in response to the coarse GPS time and the predicted navigation bits, a pattern matching algorithm may be executed to provide accurate GPS time.

To better set the coarse time, the expected error in TOW can be determined by using the expected network delay. The step of setting coarse GPS time within the GPS receiver may then include adjusting the time to account for expected errors due to network delays.

The method disclosed herein enables conventional IS-801 messages to be used to assist in determining the position of a GPS receiver in an asynchronous network such as GSM or UMTS (Universal Mobile telephone service). In one described embodiment, the transmitted navigation bits have a format that includes a plurality of frames. Each frame is organized into a plurality of sub-frames. Each subframe has a "time indicator" field, such as a "week time" field. The SA message of the IS-801 standard includes a subframe of at least one predicted navigation bit. In such an embodiment, the method may further comprise locating a "predicted time indicator" field within the sub-frame of the predicted navigation bits and calculating the TOW in response to the predicted time indicator.

In some embodiments, the SA message includes a "data length" field specifying the length of the predicted navigation bits and a "reference bit number". The reference bit number locates the "actual reference bit" within the frame of actual navigation bits relative to the first bit of the frame that includes the actual reference bit.

The particular bit selected as the actual reference bit is selected because it corresponds to a predicted reference bit that is at a known location in the predicted navigation bitstream. The position of the prediction reference bit is known relative to the start of the predictive navigation bitstream. By locating the actual reference bits relative to the beginning of the frame and the predicted reference bits relative to the beginning of the predicted navigation bitstream, each field within the entire predicted navigation bitstream can be identified and located.

Once located, the time indicator field within the predicted navigation bits is decoded to provide a "predicted time indicator". Determining a TOW in response to the predicted time indicator, wherein a predicted first bit estimate in a sequence of predicted navigation bits is received at the TOW. Thus, upon receiving a predicted first bit of a sequence of predicted navigation bits within a GPS receiver, a coarse GPS time is set based on the TOW at which the predicted first bit of the sequence of predicted navigation bits is estimated to have been received. The predicted time indicator is defined with respect to a week time reference. The step of determining the TOW may comprise calculating a "week number" corresponding to the number of bits elapsed from the week time reference until the first bit in the sequence of predicted navigation bits. The step of calculating the week bit may comprise determining whether a predicted first bit of the sequence of predicted navigation bits is within the same subframe as the predicted time indicator and adjusting the predicted time indicator in response thereto.

Thus, a method of adjusting the calculation of the TOW is disclosed to take into account boundary conditions such as roll (where the sub-frame in which the TOW is placed is located directly before the transition at the end/beginning of the week) and the case where the first bit of the predicted navigation bit sequence is located in a different, adjacent frame to the TOW field.

The method may be implemented in an MS for determining position using navigation bits periodically transmitted from a plurality of SVs synchronized to GPS time. The periodically transmitted navigation bits include a time indicator field. The MS also communicates with one or more base stations and a Position Determination Entity (PDE).

Drawings

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

FIG. 1 shows a plurality of cellular base stations, GPS SVs, and a user holding a mobile device such as a cellular telephone;

FIG. 2 is a block diagram of a mobile device in an embodiment including a communication and positioning system;

FIG. 3 is a diagram of a message structure in a GPS signal including frames, subframes, and bytes;

FIG. 4 IS a diagram of the structure of a GPS Sensitivity Assist (SA) message 41 as specified by the IS-801 protocol;

FIG. 5 is a flowchart of a step of setting a coarse time by using SA messages in an asynchronous network; and

FIG. 6 is a bit map showing the communication between predicted navigation bits, frames of a GPS message, and the TOW field.

Detailed Description

In the following description, reference is made to the drawings wherein like numerals represent the same or similar elements.

Glossary of terms and acronyms

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

GPS: a global positioning system. 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 (Russian Glonass System) and the planned European Galileo System (European Galileo System).

CDMA: code division multiple access. CDMA is a high-capacity digital wireless technology that was pioneered and commercially developed by QUALCOMMTM corporation. CDMA is the main business opponent of the GSM standard.

GSM: global system for mobile communications. GSM is a widely used alternative digital wireless technology.

UMTS: universal mobile telephone service. UMTS is a next generation high capacity digital radio technology.

MS: a mobile station. An MS is any mobile wireless communication device, such as a cellular telephone having a baseband modem for communicating with one or more base stations. The MS of the present invention includes a GPS receiver to provide position determination capabilities.

BS: and a base station. A BS is an entity that communicates with mobile stations, for example, a BS may include a BTS, a Mobile Switching Center (MSC), a Mobile Positioning Center (MPC), a PDE, and any interworking function (IWF) useful for network connectivity.

BTS: a base transceiver station. A BTS is a fixed station used to communicate with mobile stations. Which includes an antenna for transmitting and receiving wireless information.

SV: a space vehicle. A set of SVs constitutes one of the main elements of a global positioning system. The SVs orbit the earth and play signals that are uniquely identifiable among other information.

Virtual distance measurement: virtual range measurement is a measurement used to determine the relative distance between a transmitter and a receiver. It is a method employed by GPS receivers and it is based on signal processing techniques to determine an estimated distance between the receiver and a selected SV. The range is measured from the signal transmission time from the SV to the receiver. "virtual" means that the clocks of the SVs are not synchronized with the receiver. Thus, the measurement contains an uncompensated period of clock error.

PDE: a location determination entity. The PDE is a system resource (e.g., a server) typically located within a CDMA network that works in conjunction with one or more GPS reference receivers, which are capable of exchanging GPS-related information with the MS. In an MS-assisted a-GPS session, the PDE sends GPS assistance data to the MS to enhance the signal acquisition process. The MS returns the virtual range measurements to the PDE, which is then able to calculate the position of the MS. Alternatively, in an MS-based A-GPS session, the MS sends the computed position results back to the PDE.

GPS SA message: a global position sensitivity assistance message. The GPS SA message IS defined in the IS-801 protocol. The GPS SA message includes predicted navigation bits for the currently visible SVs. The navigation bits are predicted by the PDE and sent from the PDE to the MS in OTA ("over the air") format.

IS-95: IS-95 refers to the industry Standard document published by the telecommunication industry Association/electronic industry Association-TIA/EIA-95-B entitled "Mobile Station-B enzyme Station Compatibility Standard for Wireless base spread Spectrum Systems" (Mobile Station-base Station compatible Standard for wideband spread Spectrum Systems).

IS-801: IS-801 refers to the industry Standard document published by the Telecommunications industry Association/electronics industry Association-TIA/EIA/IS-801 entitled "Position Determination Service Standard for Dual-Mode spread Spectrum System" (Position Determination Service Standard for Dual-Mode spread Spectrum System), which IS an attached Standard to IS-95 and IS-2000-5, describing the protocol between MS and PDE.

GPS coordinates: the GPS coordinates are the final result of the measurement and subsequent calculation process by which the position of the GPS user is determined.

IS-801 dialogue: the IS-801 session IS a sequence of data exchanges between the MS and the PDE in the manner specified by the IS-801 standard for the purpose of obtaining location coordinates. The sequence typically contains various GPS assistance messages sent by the PDE and pseudorange or position results sent by the MS. The session start is marked by either end by the time the request initiates the data exchange sequence and the session ends when the initiating end terminates the exchange sequence with a session end message.

Mobile Termination (MT) session: the MT session IS an IS-801 session initiated by the PDE.

Mobile Originated (MO) dialogue: the MO session IS an IS-801 session initiated by the MS.

OTA ("over the air") format: the OTA format is a format in which the message is physically transmitted.

Overview

The system described herein provides a method for "coarse setting local time" within a Mobile Station (MS). The system includes receiving a "timing assistance" message that includes the same information (and formatting) as a portion of a navigation message transmitted simultaneously from another source, such as a GPS satellite. The timing assistance message includes reference bits therein. The arrival time of the reference bit is recorded in the MS by a local clock. Assuming that the timing assistance message is transmitted at an appropriately calculated time to cause the timing assistance message to arrive at the MS at the same time as the navigation message is transmitted from the GPS SV, the relative time at which the reference bit was received can be calculated from information contained within the timing assistance message, such as a predicted time indicator field, as will be explained in more detail below.

One advantage of the disclosed method and apparatus IS that it extends the use of the IS-801 protocol from being originally used in synchronous systems to being usable in asynchronous systems to assist in determining the location of a Mobile Station (MS). Typically, a pattern matching algorithm can be used to improve the coarse time and set the receiver's clock to the precise GPS time by first setting the coarse time using the methods described herein. The method of setting a coarse time described herein IS useful because without the method described in the present invention, IS-801 messages exchanged between an MS and a server in a synchronous system cannot generally be used in a system utilizing an asynchronous network. In particular, in the IS-801 standard, there IS no dedicated message defined for time translation. A method for inferring a time estimate from an IS-801 message IS described.

FIG. 1 illustrates one environment in which the coarse time setting system described herein may be implemented. In one described environment, a GPS receiver and a cellular telephone are implemented together in a Mobile Station (MS). It should be apparent, however, that the present invention can be used with any other type of mobile station (other than a cellular telephone) that communicates with one or more land-based stations. Furthermore, the MS and GPS receiver need not be integrated together, but may be electrically coupled by a direct connection or wireless communication.

Fig. 1 shows a plurality of cellular base stations, generally referred to by reference numeral 10, GPS satellites, generally referred to by reference numeral 11, commonly referred to as Space Vehicles (SVs), and a user 13 holding an MS 14. As described in more detail with reference to FIG. 2, the MS 14 includes a position location system 27, such as a GPS system, and a communication system 22, such as a cellular telephone, which communicates with the cellular base station 10 using two-way communication signals 20. The user 13 may be walking as shown in the figure or may be traveling in a car or public transport, for example. For ease of description, position location system 27 is referred to herein as a "GPS" system, however, it should be appreciated that the system described herein may be implemented as any of a number of other types of location systems.

SV 11 comprises any group of SVs used to locate a GPS receiver. The SVs are synchronized to emit wireless signals 12 synchronized to GPS time. These signals are generated at a predetermined frequency and in a predetermined format as will be described in more detail elsewhere herein. In a current GPS implementation, each SV transmits a GPS signal over the L frequency band on which the GPS receiver operates. As discussed in the background, when the GPS receiver 29 in the MS 14 detects a GPS signal 12, the GPS system 27 attempts to calculate the amount of time elapsed from the transmission to reception of the GPS signal 12. In other words, the GPS system 27 calculates the difference in the amount of time required for each GPS signal 12 to travel from its respective SV 11 to the GPS receiver 29. The relative measurement is called a virtual distance. The virtual distance is defined as: c (T)_user+T_bias-T_sv) Where c is the velocity of the GPS signal 12, T_userIs GPS time, T, when a signal 12 from a given SV 11 is received_biasIs based on the difference between the time of the user clock and the actual GPS time, and T_svIs the GPS time when SV 11 transmits signal 12. In the normal case, the receiver 29 needs to resolve four unknowns: x, Y, Z (Earth center Earth fixed rectangular coordinate system coordinates of receiver antenna) and T_bias(the receiver GPS time estimate deviates from true GPS time when the signal 12 is received). In this general case, solving the four unknowns typically requires measurements from four different SVs 11. However, this constraint may be relaxed in some cases. For example, if an altitude estimate is available, the number of SVs 11 required can be reduced from four to three, since altitude measurements can be used to define values in the Z direction, leaving only three unknowns to be resolved.

The cellular base station 10 comprises any collection of cellular base stations used as part of a communication network that communicate with the MS 14 using wireless signals 20. The cellular base station 10 is connected to a cellular infrastructure network 15 which provides communication services with a plurality of other communication networks such as a public telephone system 16, a computer network 17 such as the internet, a Position Determining Entity (PDE)18 (as defined above) and other various communication systems shown together in block 24. A GPS reference receiver 19, which may be within or near the base station 10 or at any other suitable location, communicates with the PDE18 to provide information useful for determining location, such as a GPS clock.

The terrestrial cellular infrastructure network 15 typically provides communication services that allow a user 13 of a cellular telephone to connect to another telephone using a telephone system 16; however, the cellular base station may also be used to communicate 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 cellular base station 10 is part of a GSM communication network; however, other types of asynchronous communication networks may be used in other embodiments.

FIG. 2 is a block diagram of one embodiment of a mobile device 14 including a communication and position location system.

In fig. 2, a cellular communication system 22 is shown connected to an antenna 21 that communicates using cellular signals 20. The cellular communication system 22 comprises suitable means such as a modem 23, hardware and software for communicating with and/or detecting signals 20 from the cellular base station and processing transmitted or received information.

A position location system 27 in the MS, in this embodiment a GPS system, is connected to a GPS antenna 28 to receive GPS signals 12 transmitted at an ideal GPS frequency or an approximate frequency. The GPS system 27 includes a GPS receiver 29, a GPS clock 30 (which may take into account clock bias and uncertainty factors), and any suitable hardware and software for receiving and processing GPS signals and for performing any necessary calculations to determine position using any suitable position location algorithm. 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 30 is intended to maintain accurate GPS time, however, since accurate time is often unknown, it is common practice to maintain time in GPS clock software by its value and the uncertainty about its value. It should be noted that after an accurate GPS fix coordinate, GPS time will be known very accurately (to within a few parts per billion of uncertainty in current GPS implementations).

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

The control system 25 is also connected to a user interface 26 comprising any suitable components for interfacing with a user, such as a keypad, a microphone/speaker for voice communication services and a display, such as a backlit LCD display. The mobile device control system 25 and user interface 26, connected to the position location system 27, provide the appropriate functionality for a GPS receiver and a two-way communication system for controlling user input and displaying results, for example.

Fig. 3 is a diagram of a standard message structure in the GPS signal 20. In one implementation, the SV transmits a sequence of frames at a rate of fifty bits per second (50 bps). The message structure comprises a 1500 bit length frame 31 consisting of 5 subframes 32. Each subframe contains ten bytes 34, each byte 34 being thirty bits long. Of the thirty bits, six bits are designated as parity bits, and the remaining 24 bits are source data bits. These 24 source data bits are referred to as "navigation" bits.

In one current GPS implementation, prior to transmission, each SV converts the 24 navigation bits in each byte to an "over the air" (OTA) format by modulo-2, adding to each of them the most recently computed parity bits of the previous byte (so-called D30 bits 35). Thus, if D30 bit 35 is a logical "1," then each source data bit will be inverted. If the D30 bit 35 is a logical "0," then the source data bits are not affected. The remaining six parity bits of the byte are then computed using a Hamming Code (Hamming Code). When an SV signal is received at the GPS receiver, the message is decoded from its OTA format to retrieve the source data bits. As discussed in more detail below, the acquisition of SV messages may take some time because it is done at a relatively slow speed of 50 bps. In noisy environments, accurate decoding may be difficult (or impossible) to achieve. Furthermore, the time information, referred to herein as a "SUBFRAME COUNT" (SUBFRAME COUNT) in the current GPS example, occurs only once every six seconds, meaning that the opportunity to decode the time sequence is quite rare. Decoding may be problematic in noisy environments and may lose the opportunity to determine one or more time sequences, which may result in a long time delay before time information can be successfully decoded.

Each 300-bit sub-frame 32 begins with a 30-bit "telemetry" (TLM) byte 36. The TLM byte 36 is followed by a 30-bit handover byte (HOW) 37. HOW comprises the 17 most significant bits of a 19-bit value. The 19-bit value is sometimes referred to as a "time of week" (TOW). The 17-bit long field contains the 17 most significant bits of TOW, which is referred to herein as a subframe count. The subframe count is a prediction time indicator used in the presently disclosed method for coarse time setting. In particular, the value in the subframe count field indicates the time at which the next subframe is relative to the beginning of the week. Because the subframe count is reset to zero at the beginning of each week and incremented every 6 seconds, the subframe count can be used as a subframe counter.

For the purposes of this document, a "sub-frame time point" is the time instant when one sub-frame period ends and the next begins. The subframe count is limited to a range of 0 to 100,799. It should be noted that every 6 seconds 100,800 times equals the number of seconds in a week. It should be appreciated that 100,800 is also the number of subframes transmitted per week. At the end of each week (i.e., when the subframe count reaches a maximum value), the subframe count is reset to zero. Thus, the first state of the subframe count (i.e., a subframe count of zero) occurs at a subframe time point, which coincides with the beginning of the current week. (in current GPS implementations, this point in time occurs at the midnight-saturday morning, where midnight is defined as 0000 hours on the coordinated Universal Time (UTC) scale, which is nominally called the Greenwich meridian.)

It should be noted here that the subframe count is sometimes referred to, ambiguously, as "handover word" (HOW) or "Time of Week" (TOW). However, this is not the case in the present invention.

If a GPS receiver can receive SV signals from a GPS SV in good condition, the receiver can demodulate the navigation bits transmitted by the visible SV, and thus the receiver will be able to decode the subframe count. The subframe count may then be used to set the clock within the receiver to GPS time. However, receiving the subframe count may take up to 6 seconds, as the subframe count only occurs once in each subframe, i.e., once every six seconds. Furthermore, in environments where signals are blocked or weakened, data bits are not always demodulated or consume considerable time if possible. Thus, to enable high speed coarse time setting in asynchronous networks regardless of signal conditions, a system IS described herein that utilizes specific messages of the IS-801 protocol (GPS sensitivity assistance messages).

The Sensitivity Assistance (SA) message is provided from the PDE18 via a cellular communication signal 20. The SA message may be processed as described herein to provide a predicted HOW (rather than an actual HOW), which may then be used to set a coarse time.

Reference IS now made to fig. 4, which IS a block diagram of SA message 41 as specified by IS-801. The intended purpose of the SA message 41 at the time of presentation is to provide sensitivity assistance to the MS in determining location. The SA message 41 is a type of secondary message and it should be understood that formats other than secondary messages may be used. However, for ease of description, the domains described herein are referred to by their IS-801 name.

In the current implementation, the SA message 41 may include up to eight portions 42. Each portion 42 may contain up to sixteen data records. Each record is uniquely associated with one SV. Each data record may include a predicted navigation bit field 46 and a satellite PRN number field 47(SV PRN NUM). The predicted navigation bit field 46 may contain up to 510 predicted navigation bits. The predicted navigation bit field 46 for the currently visible SV is sent by the PDE18 (FIG. 1) to the MS 14 in OTA format. Thus, the encoding of the predicted navigation bits follows the same algorithm as the OTA encoding used by the SVs shown above. Because of this OTA encoding, the receiver must decode the subframe count in the predicted navigation bits within the SA message from the PDE18 in order to use the subframe count information to set the coarse GPS time.

Each portion 42 of the SA message includes a number of additional fields in addition to the record and associated fields within the record. Some of these additional domains are shown in fig. 4, followed by their current IS-801 name in parenthesis. The "reference BIT number" field 43(REF _ BIT _ NUM) conveys the location of the "real reference BITs" within a 1500-BIT GPS frame transmitted by the SV. The actual reference bit is a bit related to the last bit of the first half of the predicted navigation bit stream in the SA message (hereinafter referred to as "predicted reference bit") among the actual navigation bits transmitted from the SVs. Further information regarding the use of reference bits will be provided below.

The "data record SIZE" field 44(DR _ SIZE) specifies the length of each data record including the predicted navigation bits. In the current implementation, the value of DR _ SIZE is indicated in 2-bit increments.

The "number of data records" field 45(NUM _ DR _ P) specifies the number of data records in the portion. In one implementation, each data record is associated with a single SV, so the data record number field 45 also specifies the number of SVs up to 16, for which the information provided in the section is for.

PDE18 is able to predict the value of the navigation bits transmitted by the SVs at some time in the near future based on the fact that the domain of many navigation bits is constant. In addition, those bits that are not constant transition from their current state in a generally predictable manner. The reference receiver 19 conveys the navigation bits transmitted by the SVs to the PDE 18. Thus, the PDE18 knows the values of the navigation bits most recently transmitted by the GPS SVs. The PDE18 uses the values of the navigation bits received from the reference receiver 19 to predict the values of the navigation bits to be transmitted in the future. In particular, the predicted navigation bits are predicted by the PDE18 based on knowledge of the repetition of navigation bit values or knowledge that the values represented thereby will periodically increase over time by a known amount at a known rate.

In one example, in a synchronous CDMA network, PDE18 sends an SA message to the MS with 496 predicted navigation bits (equal to 9.92 seconds worth of navigation bits) for each SV that is visible. In synchronous networks, the predicted navigation bits in the SA message are used to increase the sensitivity of the GPS receiver. However, as described herein, in an asynchronous network, the SA message is used for a completely different purpose. That is, the SA message is used to set a coarse time in the asynchronous network. As long as the PDE18 sends at least six seconds worth of navigation bits to at least one SV, the complete HOW must be found somewhere in the prediction message. This predicted HOW may be decoded. From the decoded HOW, the clock of the GPS receiver can be set to coarse GPS time.

Fig. 5 IS a flow chart of the steps for setting a coarse time based on IS-801 type messages in an asynchronous network. FIG. 6 shows communication between the predicted navigation bits, one frame of a GPS message, and the sub-frame count field. In the following discussion, reference will be made to the IS-801 standard for the sake of illustration. It will be apparent that the method can be used in other position determining systems. However, the disclosed method and apparatus are most useful in an asynchronous system where an IS-801 message source IS available. The MS 14 (fig. 1) communicates with the base stations and receives requests, such as from a user, to determine the location of the MS.

At 51, an IS-801 type session (e.g., MO or MT IS-801 type session) IS initiated, and during the IS-801 type session (preferably at the beginning of the session), the MS requests an assistance message (SA data in IS-801 type format) from the PDE18 (fig. 1).

At 52, in response to the request from the MS, the PDE18 predicts future navigation bits using its GPS reference receiver 19 and forms an SA message as illustrated in fig. 4. In forming the SA message, PDE18 sets the reference bit number field to indicate the location of the actual reference bits corresponding to the predicted reference bits within the 1500-bit SV message frame (ranging from 0 to 1499). PDE18 also sets a value for the data record size field that specifies the length of the predictive navigation bit field. The PDE18 schedules the transmission of an SA message from a BTS at a time that will result in the MS receiving the first bit of the predicted navigation bit field of the SA message at a time that approximates the time at which a receiver in the MS receives the corresponding actual navigation bits from the GPS SVs.

Upon arrival of the SA data from the PDE18, the receiver software marks the time indicated by the local clock when the first bit of the SA message is received, at 53. In an alternative approach, the time at which some other specific part of the SA message (e.g., the prediction reference bit of the predicted navigation bit) is received may be noted. PDE18 saves the indicated time. The receiver then decodes the SA message to determine the content of the message. It should be noted that although the first bit of the predicted navigation bits in the SA message is a reference point for synchronizing the predicted navigation bits with the actual navigation bits, any other well-defined reference in the actual navigation bitstream may be used. However, the first bit of the predicted navigation bit field in the SA message is easy to detect, which makes it a more convenient choice. It should also be noted that the rate at which the MS receives the predicted navigation bit stream is typically much greater than the rate at which the SV transmits the actual navigation rate. However, the method described in the present invention works as long as the first bit of the predicted navigation bit field of the SA message arrives at approximately the same time (or within a known time offset) as the corresponding bit transmitted by the SV.

At 54, after decoding the SA message, the MS will know the value of the reference bit number field 43 (FIG. 4) and the data record size 44. Using this information, the predicted subframe count field in the predicted navigation bits is located as described in more detail below with reference to fig. 6.

Reference is now made to fig. 6 in conjunction with fig. 5. As noted above, the value of the reference bit number field 43 conveys the location of the actual reference bits 61 (shown in fig. 6) within a 1500-bit GPS frame by the SV. It should be appreciated that the positioning of the actual reference bits shown in fig. 6 is only one example of actual reference bit positioning. In actual operation, the actual reference bits may be located anywhere within the frame 31. The actual reference bits 61 of the SV message correspond to the one bit 62 in the middle of the decoded predicted navigation bits (i.e., predicted navigation bits 62). Since the value of the reference navigation bit number field 43 indicates the distance of the actual reference bit 61 to the beginning of the frame 31 (i.e. the value from 0 to 1499 as indicated above), the distance to the nearest previous sub-frame count field 66 within the predicted navigation bit stream can be easily calculated.

According to one implementation, the prediction reference bit 62 is always the last bit in the SA message to predict the first half of the navigation bitstream. Then, using knowledge of the predicted navigation bit field length, the receiver software can determine where the sub-frame count field 66 is located within the predicted navigation bit stream. It should be noted that the positioning of the HOW, including the subframe count field 66, always starts at positioning bits 30, 330, 630, 930 and 1230, which are referenced from the beginning of the frame. This is because the format of the SV navigation message is strict. Thus, if the reference bit number field has a value of 1201 and the data record size 44 has a value of 398, then the first bit of the SA predictive navigation bit is 1001, which is the position of the actual reference bit, 1201 (provided by the reference bit number field 43) minus half the length of the data record (398/2) plus one equals 200.

Thus, since there are 300 bits in each of the five bytes of the 1500-bit frame, the first bit of the predicted navigation bit field will correspond to the 101 th bit of the fourth byte. Obviously, the sub-frame count in the fourth byte would not be included, since it occurs in bits 31-60, but would provide a sub-frame count in which the 229-bit fifth byte occurs within the SA prediction navigation bit field.

Referring again to FIG. 5, the MS then decodes 55 the located subframe count field 66. In the current implementation, decoding a byte within the predictive navigation bitstream requires that the D30 bits 35 (see fig. 3) of the previous byte be available. Therefore, to decode the HOW byte 37, the D30 bits 35 of the previous (TLM) byte 36 must be available in the predicted navigation bits. Therefore, the first decodable HOW byte in the predicted navigation bits must be preceded by a D30 bit. In the example provided above, where the first bit of the predictive navigation bit field is bit 1001, the D30 bit will occur 198 into the predictive navigation bit field (1199-. Thus, the D30 bit in the fifth byte before the sub-frame count will be available.

In one implementation, the following sub-steps are performed to decode the subframe count.

1. The position is determined within bit 64 of the SV navigation message frame, which corresponds to the first bit (i.e., positions 0-299) of its intra-subframe predicted navigation bit field 63. In the example provided above, the location is represented by the value 1001 and 900, 101.

2. The position of the start of the first decodable HOW byte is determined with respect to the first bit of the predictive navigation bits field 63 and the value of the 17-bit subframe count is saved. In the example provided above, the position is represented by the value 229. It should be noted that there may be more than one complete HOW byte within the predictive navigation bitstream. For example, if there are 496 predicted navigation bit bytes, then two full HOW bytes (and thus two full subframe count fields) may be used. For convenience of description, it will be assumed that the first HOW byte will be selected for decoding. Alternatively, any other HOW byte within the predictive navigation bitstream may be decoded.

3. The position of the D30 bit of the byte immediately preceding the HOW (the TLM byte in this implementation) is determined relative to the first bit of the predictive navigation bit field and this D30 bit value is saved. In the example provided above, the position may be represented by a value 198. In one implementation, in the case where the D30 bits of the immediately preceding byte do not have predictive navigation bits, this subframe count field cannot be decoded, and in that case the next subframe count field will be selected for decoding.

4. Decoding subframe count: if the D30 bits have a binary value of one to "1," then the bits of the subframe count are converted to obtain their decoded values from the OTA value of the subframe count. If the D30 bits have a binary value of one to "0," then the bits of the subframe count are already available.

At 56, the decoded subframe count value and the position of the subframe count field within the predicted navigation bits are used to decode the subframe count value. It should be understood that the subframe count value refers to the beginning of the subframe immediately following the subframe that includes the decoded subframe count field 66 referenced from the beginning of the week. It should be noted that in the IS-801 implementation, the length of the predictive navigation bit field 46 IS sufficiently long to include at least one sub-frame count value, and possibly two. As described above, the subframe count value has a value in the range of 0 to 100,799(100,800 possible values), which represents the number of subframes that have occurred since the start of the week. Further, as described above, one subframe is transmitted every six seconds. Thus, the subframe count indicates the number of six second intervals since the start of the week (coordinated universal time scale, morning, evening-sunday, morning, the scale is nominally referred to as the greenwich meridian).

A process for determining the time indicated by the subframe count field 66 is now disclosed. It should be noted that the time indicated by the subframe count is the start time of the subframe following the subframe that includes the subframe count. Note that there are 300 bits per subframe and each bit lasts 20 ms, the time for the start of the week is calculated (e.g., time 300 subframe count 20 ms). The calculated time indicates the number of milliseconds elapsed from the current GPS week to the time of the subframe associated with the subframe count of the SV transmission. To set the clock to a coarse time value, the difference between the transmit time and the receive time is negligible. It should be noted that in the example provided above, the subframe count is from the fifth subframe. Thus, the time calculated from the subframe count is the time at which the next frame starts. In other words, the time is 1501 minus 1001 bits after receiving the first bit of the predicted navigation bit field.

The time of the first bit in the predicted navigation bit field of the SA message is determined. This process is described with reference to fig. 54 and 6. In the example provided above, the first bit of the predictive navigation bit field is located at the value 1001 and is timed (300 subframe count 20 ms) ((1501-1001) 20 ms). Alternatively, the location of the first bit of the predicted navigation bit field with respect to the first bit of the subframe associated with the subframe count may be subtracted first. In other words, the time of the first bit of the predicted navigation bit field may be calculated as ((300 × subframe count) - (1501-) -1001)) 20 ms. In yet another alternative embodiment of the method, the value of the subframe count may be adjusted to indicate the beginning of the subframe carrying the subframe count.

After the adjustment, the position 1001 of the first bit of the predicted navigation bit field may be subtracted from the position 1201 of the first bit of the subframe carrying the subframe count. The time to predict the beginning of the navigation bit field can be calculated as (300 × subframe count-1)) - (1201-.

It should be noted that the minimum length of the predictive navigation bit field is 330 bits to ensure that the required D30 bits are available. Furthermore, if the predicted navigation bits span the cycle roll, the subtraction from the subframe count must be modulo 100,800 to avoid negative values.

In another example using the IS-801 standard, assume that the length of the predicted navigation bit field IS 500 bits and the value of the reference bit number field specifies that the GPS frame IS at bit 700. Thus, since the reference bit number corresponds to the last bit of the first half of the predicted navigation bit, the first bit of the predicted navigation bit field is 700-500/2+ 1-451. Thus, the first bit of the predictive navigation bit field is the 451 th bit of the frame transmitted by the SV. Each subframe is 300 bits in length, each byte is 30 bits in length, and the HOW byte is the second byte in each subframe. Thus, bit #451 is located in the second subframe, after the HOW byte. In other examples, the first bit of the predicted navigation bit field may go back to the previous GPS frame, so the calculation of the position of the first bit of the predicted navigation bit field from the reference bit number must be done with a subtraction of the modulus 1500 (i.e., 1-2 ═ 1499).

Referring again to the flow chart of FIG. 5, at 57, the error (uncertainty or "coarse") in the coarse time is estimated. It should be appreciated that the "crutness" (i.e., degree of uncertainty) in setting GPS time may be approximately limited. This is because the coarseness depends primarily on the transmission delay of the network by which the PDE18 transmits the SA message to the MS. Which in turn depends on the transmission mode employed in a given network. Thus, the delay may be measured and/or predetermined. Therefore, when PDE18 transmits SA messages, most of the time error can be attributed to the time it takes for a bit to be sent from PDE18 to the receiver, which is referred to as the "network delay". In one example, the network delay may be in the range of a few seconds, however, adjustments may be made to account for the delay.

Thus, this uncertainty is usually a consideration of network delay, but other factors may be considered; alternatively, this error may be predetermined based on expected network delay conditions. Thus, when the PDE18 sends the SA message almost synchronously with the actual timing of the GPS SV sending the navigation message, most of the time error can be attributed to the time it takes to send a bit from the PDE18 to the receiver, referred to as the "network delay", and possibly in the range of a few seconds, in step 52.

At 58, the GPS receiver's clock 30 (FIG. 2) is set to a coarse time upon receiving the start of the predicted navigation bit field in the SA message. The clock bias is set to zero and the uncertainty in time is set to a predetermined error value. As mentioned above, the coarse time has uncertainty in accuracy, which is mainly attributable to network delay. In other words, the value of the clock setting is accurate only within the limits of the uncertainty caused by the network delay. Since the exact time is in most cases unknown to the GPS receiver before determining the position of the receiver, it is common practice in GPS clock software to maintain time by its value and an uncertainty associated with the value. In this case, the uncertainty of the coarse time may be in the range of a few seconds.

At 59, the predicted navigation bits are passed to a method, such as a pattern matching algorithm, which then determines the precise GPS time. In one embodiment, the predicted navigation bits are passed from the SA message in an invariant OTA format to a pattern matching algorithm, which is then executed to calculate the precise GPS time (which in a current implementation may be precise to within a few milliseconds). One pattern matching algorithm is disclosed in U.S. patent nos. 5,812,087, 6,052,081, and 6,377,209, issued to Norman f.

The GPS clock is then set to the calculated, accurate GPS time at 60. The position fix is then determined using any suitable procedure, using known GPS time. It should be noted that after performing a position location determination, GPS time is known to have an accuracy of a few nanoseconds. Thus, the highly accurate time may be used to reset the GPS clock after a position fix is determined.

Extended to allow determination of number of weeks

The previous discussion addresses the problem of establishing time in a week, which requires reference to specific assistance data typically provided by a server. However, this method does not solve the problem of the actual number of weeks. The number of weeks counts the number of GPS weeks that occur from the start of the GPS clock. (the GPS clock starts at 00:00 am on 6.1.1980). A particular data type may have a relatively long lifetime extending over the current week, an SV almanac being one example of this. Thus, it is sometimes necessary to establish a time estimate that also resolves the week number ambiguity.

In the IS-801 standard, the number of weeks IS transmitted by all SVs in subframe 1 (bits 1: 10 of the third byte in subframe 1). This information may be included in the SA prediction data provided by the IS-801 server and, therefore, an appropriate bit extraction code may be used to separate the week number field from the SA prediction data and subsequently to determine the week number.

It should be appreciated by those skilled in the art, in light of these teachings, that alternative embodiments may be implemented without deviating from the spirit or scope of the invention. The invention is not to be restricted except in light of the attached claims, which include all such embodiments and modifications when considered in conjunction with the foregoing description and accompanying drawings.

Claims (17)

1. A method for setting coarse GPS time in a GPS receiver, comprising:

a) requesting a predicted navigation bit sequence;

b) receiving the predicted navigation bits;

c) saving a receiving time of the navigation bit;

d) locating a predicted time indicator field within the predicted navigation bits;

e) determining a coarse time setting in response to said located time indicator field; and

f) setting coarse GPS time within the GPS receiver in response to a difference between the coarse time setting and the receive time.

2. The method of claim 1, further comprising executing a pattern matching algorithm to provide accurate GPS time.

3. The method of claim 1, further comprising:

a) determining an expected error in the coarse time setting; and

b) coarse GPS time is set within the GPS receiver taking into account the expected error in a GPS clock.

4. The method of claim 1, wherein the predicted navigation bits are received in a format comprising a plurality of frames, each frame organized into a plurality of subframes, each subframe having the time indicator field and comprising a subframe of at least one predicted navigation bit; the method further comprises:

locating the predicted time indicator field within at least one subframe of the predicted navigation bits; and

calculating the coarse GPS time from the predicted time indicator.

5. The method of claim 1, wherein the predicted navigation bit field is transmitted with a data length specifying a length of the sequence of predicted navigation bits and a reference bit number indicating a location of a predicted navigation bit within a frame of actual navigation bits, the method further comprising:

determining a location of a first bit within the predicted navigation bit sequence within a frame of actual navigation bits based on the value of the reference bit number and the data length;

locating the time indicator field within the predicted navigation bits based on the value of the reference bit number;

decoding the located time indicator field to provide a predicted time indicator;

determining the coarse GPS relative to a time at which the first bit of the predicted navigation bit sequence is received; and

setting a coarse GPS time within the GPS receiver consistent with the first bit of the predicted navigation bit sequence.

6. The method of claim 1, wherein the MS and the base station communicate using a GSM system.

7. A mobile station for determining position utilizing periodically transmitted navigation bits from a plurality of SVs synchronized with GPS time, said periodically transmitted navigation bits including a time indicator field, said mobile station also in communication with one or more base stations and a Position Determination Entity (PDE), said mobile station comprising:

a bi-directional communication system for communicating with the base station and the PDE;

a position location system including a GPS clock;

means for requesting an assistance message from the PDE, the assistance message comprising a sequence of predicted navigation bits transmitted from the base station that is approximately synchronized in time with GPS time;

means for storing a time of receipt of the assistance message;

means for locating the predicted time indicator field within the predicted navigation bits;

means responsive to said located time indicator field for determining a predicted time of week; and

means for setting a coarse GPS time within the GPS receiver in response to the predicted time of week and the received time.

8. The mobile station of claim 7, further comprising means responsive to said coarse GPS time and said predicted navigation bits for performing a pattern matching algorithm to provide precise GPS time.

9. The mobile station of claim 7, further comprising:

means for determining an expected error in the time of week; and

means for setting coarse GPS time within the GPS receiver, including means for setting the expected error in a GPS clock.

10. The mobile station of claim 7, wherein the transmitted navigation bits have a format comprising a plurality of frames, each frame organized into a plurality of subframes, each subframe having a time indicator field, and the assistance message comprises at least one subframe of predicted navigation bits, and further comprising:

means for locating a predicted time indicator field within a subframe of the predicted navigation bits; and

means for calculating the time of week in response to the predicted time indicator.

11. The mobile station of claim 10, wherein the assistance message includes a data length field specifying the length of the predicted navigation bits and a reference bit number specifying a bit within a frame of the actual navigation bits, and further comprising:

means responsive to said reference bit number field and said length field for determining a first bit of said sequence of predicted navigation bits, said first bit corresponding to the position of said first bit of said sequence within a frame of actual navigation bits;

means, responsive to the position of the first bit of the sequence of predicted navigation bits, for locating a time indicator field within the predicted navigation bits;

means, responsive to the predicted time indicator, for determining a time of week at the first bit of the sequence of predicted navigation bits; and

means for setting a coarse GPS time within the GPS receiver in correspondence with the first bit of the predicted navigation bit sequence and in response to the time of week.

12. In a Mobile Station (MS) in communication with a base station and a Position Determining Entity (PDE) using the ISO-801 standard, a GPS receiver configured to periodically receive transmitted navigation bits from a plurality of SVs synchronized with GPS time, the transmitted navigation bits having a format including a plurality of frames, each frame organized into a plurality of subframes, each subframe having a subframe count message, a method for synchronizing a GPS receiver with coarse GPS time, the method comprising:

requesting, by the MS, a Sensitivity Assistance (SA) message from the PDE, the SA message including

A predicted navigation bit field comprising a sequence of predicted navigation bits, said sequence comprising at least one sub-frame,

a data record size field specifying the length of the predictive navigation bit field, and

a reference bit number field indicating a bit within a frame of the actual navigation bits, thereby associating the predicted navigation bits with a set of navigation bits;

transmitting the SA message from the base station in approximately time with GPS time in response to the request from the MS;

receiving the SA message in the MS and saving a receiving time of the SA message;

determining a first bit of said sequence of predicted navigation bits corresponding to said position of said first bit of said sequence within a frame of actual navigation bits in response to said reference bit number field and said data record size field;

locating the subframe count field within the predicted navigation bits in response to the position of the first bit of the sequence of predicted navigation bits;

decoding the located subframe count field to provide a predicted subframe count value;

determining the time of week at the first bit of the predicted navigation bit sequence in response to the predicted subframe count value; and

setting coarse GPS time within the GPS receiver in response to the predicted subframe count and the receive time, consistent with the first bit of the predicted navigation bit sequence.

13. The method of claim 12 further comprising determining an expected error in the time of week, and the step of setting coarse GPS time further comprises setting the expected error.

14. The method of claim 13, wherein the predicted subframe count value is defined relative to a time of week reference, and the step of determining the time of week comprises calculating a number of bits of week corresponding to the number of bits elapsed from the time of week reference to the first bit of the sequence of predicted navigation bits in response to the predicted subframe count value and the position of the first bit of the sequence of predicted navigation bits.

15. The method of claim 14, wherein the step of calculating a one-week bit comprises determining whether the first bit of the sequence of predicted navigation bits is located in the same subframe as the subframe count field, and adjusting the predicted subframe count value in response to this determination.

16. The method of claim 12, further comprising performing a pattern matching algorithm responsive to the coarse GPS time and the predicted navigation bits to provide precise GPS time.

17. The method of claim 12, wherein the MS and the base station communicate using a GSM system.