I IIIII IIIIIIII Ill lllll lllll lllll lllll lllll lllll lllll lllll 111111111111111111
`US007439907B2
`
`c12) United States Patent
`Wang et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,439,907 B2
`Oct. 21, 2008
`
`(54) NAVIGATION SIGNAL RECEIVER
`TRAJECTORY DETERMINATION
`
`(75)
`
`Inventors: Chi-Shin Wang, Half Moon Bay, CA
`(US); David Wang, Belmont, CA (US);
`Wentao Zhang, Mountain View, CA
`(US); Jun Mo, San Jose, CA (US); Lei
`Dong, Cupertino, CA (US)
`
`(73) Assignee: SIRF Technology Holdihgs, Inc., San
`Jose, CA (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 38 days.
`
`(21) Appl. No.: 11/561,758
`
`(22) Filed:
`
`Nov. 20, 2006
`
`(65)
`
`Prior Publication Data
`
`US 2008/0117100Al
`
`May 22, 2008
`
`(51)
`
`Int. Cl.
`GOJS 3/14
`(2006.01)
`(52) U.S. Cl. ............................. 342/357.02; 342/357.13
`(58) Field of Classification Search ............ 342/357.02,
`342/357.06, 357.13
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6,225,945 Bl
`
`5/2001 Loomis
`
`8/2002 Vayanos
`6,429,809 Bl
`6,559,793 Bl * 5/2003 Eschenbach
`6,570,530 B2
`5/2003 Gaal
`6,707,420 B2
`3/2004 Vayanos
`6,727,848 B2
`4/2004 Eschenbach
`6,930,635 B2
`8/2005 Vayanos
`2007/0152878 Al * 7/2007 Wang eta!.
`
`........... 342/357.03
`
`............
`
`342/357.06
`
`* cited by examiner
`
`Primary Examiner-Thomas H. Tarcza
`Assistant Examiner-Fred H. Mull
`(74) Attorney, Agent, or Firm-Orrick,
`Sutcliffe, LLP
`
`(57)
`
`ABSTRACT
`
`Herrington &
`
`The present invention provides methods and systems that
`enable a mobile navigation receiver to accurately determine
`its trajectory with non-current ephemeris
`in stand-alone
`mode. In an embodiment, the receiver computes the position
`for the same location using non-current ephemeris and cur(cid:173)
`rent ephemeris at different time instances. The receiver then
`determines a position correction by finding the difference
`between these two computed positions, and applies this cor(cid:173)
`rection to the trajectory generated with non-current ephem(cid:173)
`eris to obtain a more accurate trajectory. In another embodi(cid:173)
`ment, the receiver computes an initial position of the receiver
`using non-current ephemeris and finds the difference between
`the computed initial position and an accurate approximation
`of the initial position. The receiver then shifts the subsequent
`receiver trajectory computed using non-current ephemeris by
`the difference to obtain a more accurate trajectory.
`
`18 Claims, 5 Drawing Sheets
`
`Signal Strength
`Detector
`127
`
`RF Front End
`100
`
`107
`\.... r
`
`1------
`
`Correlator
`109
`
`e----1---------,
`
`108
`\_ Q
`
`Correlator
`llQ
`
`e-compass
`ill
`
`User interface
`125
`
`103
`
`Carrier NCO
`105
`
`SYS Clock
`104
`
`Code NCO
`ill
`
`Processor
`ill.
`
`Computational
`module
`lli
`
`..
`
`Memory
`ill
`
`GPS Receiver
`
`Motion Sensor
`llil.
`
`GPS start
`module
`123
`
`IPR2020-01192
`Apple EX1029 Page 1
`
`

`

`\C = -....l = N
`
`\C
`~ w
`-....l
`d r.,;_
`
`0 ....
`....
`('D .....
`rJJ =(cid:173)
`
`('D
`
`Ul
`
`QO
`0
`0
`N
`
`N ....
`(') :-+-
`0
`
`~
`
`~ = ~
`
`~
`~
`~
`•
`00
`~
`
`123
`module
`GPS start
`
`..
`
`121
`
`Memory
`
`119
`
`Motion Sensor
`
`•
`
`115
`
`module
`
`Computational
`
`•
`
`125
`
`User interface
`
`e-compass
`
`117
`
`FIG. 1A GPS Receiver
`
`-------1
`
`113
`
`Processor
`
`'----I
`
`Code NCO
`
`112
`
`-----------
`Carrier NCO ----,
`
`105
`
`104
`
`SYS Clock
`
`103
`
`1
`
`Correlator L-1--+---+--
`.--1
`
`110
`
`111
`
`PN Generator
`
`------1
`
`)-------11--------,
`\.. Q
`
`108
`
`DDFS l+-
`
`106
`
`Correlator L--l----------,
`
`...;;._-to! 109
`
`\.. I
`
`107
`
`\__ ___
`
`I
`
`101
`
`100
`
`RF Front End
`
`Detector
`
`127
`
`Signal Strength
`
`IPR2020-01192
`Apple EX1029 Page 2
`
`

`

`U.S. Patent
`
`Oct. 21, 2008
`
`Sheet 2 of 5
`
`US 7,439,907 B2
`
`\
`\
`\
`\
`\
`\
`
`(\
`
`..-
`co
`
`~
`
`I
`I
`I
`I
`I
`
`('t')
`I
`lO
`I.!)
`r-
`
`N
`I
`lO
`lO
`'r"'
`
`~
`I
`LO
`LO
`..-
`
`I..O
`1.0
`...-
`
`I
`
`I'-
`LO
`..-
`
`\
`
`CV)
`
`\
`\
`\
`\
`\\
`\ ~
`\
`I
`I
`I
`I
`I
`I
`
`I
`
`('I)
`I
`C")
`lO
`C\J~
`I
`('t')
`l.O
`..-
`
`..-
`I
`('t')
`l.O
`..-
`
`(")
`LO
`~
`
`~
`
`CD
`.
`(9
`u.
`
`IPR2020-01192
`Apple EX1029 Page 3
`
`

`

`U.S. Patent
`
`Oct. 21, 2008
`
`Sheet 3 of 5
`
`US 7,439,907 B2
`
`205~t
`
`(Exit (203)
`
`Indoor Area (201)
`
`e-compass direction (204)-----"t ~ Entrance (202)
`
`FIG. 2 USE OF E-COMP ASS IN LARGE INDOOR AREA
`
`IPR2020-01192
`Apple EX1029 Page 4
`
`

`

`U.S. Patent
`
`Oct. 21, 2008
`
`Sheet 4 of 5
`
`US 7,439,907 B2
`
`Indoor Area (301)
`
`C
`
`A(302)
`
`I
`i
`
`
`
`
`i .......................................................................................................................................................................................................................... , .... -............ -.....
`
`X
`
`FIG 3 USE OF MOTION SENSORS FOR INITIAL POSI1ION
`
`IPR2020-01192
`Apple EX1029 Page 5
`
`

`

`U.S. Patent
`
`Oct. 21, 2008
`
`Sheet 5 of 5
`
`US 7,439,907 B2
`
`T
`
`200 Meters
`
`500meters
`
`--------------------
`
`I r!Exit(404)
`I I I
`I X
`·-·---·-·----··-·-------·----j t ___ , __ :
`L_ ______
`f
`
`J
`
`403
`
`l
`
`;
`
`~ :
`
`I 11
`I J I
`
`y
`
`401__)
`
`X
`
`Entrance)
`
`(402)
`
`FIG 4. INDOOR AREA WITH KNOWN DIMENSIONS
`
`IPR2020-01192
`Apple EX1029 Page 6
`
`

`

`US 7,439,907 B2
`
`1
`NAVIGATION SIGNAL RECEIVER
`TRAJECTORY DETERMINATION
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to navigational
`receivers, and more particularly to systems and methods for
`determining the trajectory of a navigational receiver using
`non-current ephemeris.
`
`BACKGROUND OF THE INVENTION
`
`5
`
`2
`The signals from the navigational satellites are modulated
`with navigational data at 50 bits/second. This data consists of
`ephemeris, almanac, time information, clock and other cor(cid:173)
`rection coefficients. This data stream is formatted as sub-
`frames, frames and super-frames. A sub-frame consists of300
`bits of data and is transmitted for 6 seconds. In this sub-frame
`a group of30 bits forms a word with the last six bits being the
`parity check bits. As a result, a sub-frame consists of 10
`words. A frame of data consists of five sub-frames transmitted
`1 o over 30 seconds. A super-frame consists of 25 frames sequen(cid:173)
`tially transmitted over 12.5 minutes.
`The first word of a sub-frame is always the same and is
`known as TLM word and first eight bits of this TLM word are
`preamble bits used for frame synchronization. A Barker
`15 sequence is used as the preamble because of its excellent
`correlation properties. The other bits of this first word con(cid:173)
`tains telemetry bits and is not used in the position computa(cid:173)
`tion. The second word of any frame is the HOW (Hand Over
`Word) word and consists ofTOW (Time OfWeek), sub-frame
`20 ID, synchronization flag and parity with the last two bits of
`parity always being 'O's. These two 'O's help in identifying
`the correct polarity of the navigation data bits. The words 3 to
`10 of the first sub-frame contains clock correction coefficients
`and satellite quality indicators. The 3 to 10 words of the
`25 sub-frames 2 and 3 contain ephemeris. These ephemeris are
`used to precisely determine the position of the GPS satellites.
`These ephemeris are uploaded every two hours and are valid
`for four hours to six hours. The 3 to lOwords of the sub-frame
`4 contain ionosphere and UTC time corrections and almanac
`30 of satellites 25 to 32. These almanacs are similar to the
`ephemeris but give a less accurate position of the satellites
`and are valid for six days. The 3 to 10 words of the sub-frame
`5 contain only the almanacs of different satellites in different
`frames.
`The ephemeris are used in the computation of the position
`of the satellites at a given time. The accuracy of the computed
`receiver position depends upon the accuracy of the satellite
`positions which in-turn depends upon the age of the ephem(cid:173)
`eris. The use of current ephemeris results in better position
`estimation than one based on non-current or obsolete ephem(cid:173)
`eris. Therefore it is necessary to use current ephemeris to get
`a precise receiver position.
`A GPS receiver may acquire the signals and estimate the
`position depending upon the already available information. In
`the 'hot start' mode the receiver has current ephemeris and the
`position and time are known. In another mode known as
`'warm start' the receiver has non-current ephemeris but the
`initial position and time are known as accurately as the in the
`case of previous 'hot start'. In the third mode, known as 'cold
`50 start', the receiver has no knowledge of position, time or
`ephemeris. As expected the 'hot start' mode results in low
`Time-To-First-Fix (TTFF) while in the 'warm start' mode the
`receiver may wait to download new ephemeris which may
`take more than eighteen seconds. The 'cold start' takes still
`55 more time for the first position fix as there is no data available
`to aid signal acquisition and position fix.
`It is not always possible to maintain a copy of current
`ephemeris in the receiver. The reason may be that the receiver
`had no opportunity to download the ephemeris as it might
`60 have been in a powered off state for longer than four hours or
`because the received signal is very weak. Under these cases it
`is desirable to develop techniques to obtain better positioning
`accuracy with non-current ephemeris to reduce the warm start
`time. There are U.S. patents that disclose methods of fast
`65 signal acquisition in the presence of non-current ephemeris.
`U.S. Pat. No. 6,429,809, 6,707,420, 6,930,635, and published
`U.S. patent applications 2002/0154056, 2002/0149516,
`
`With the development of radio and space technologies,
`several satellites based navigation systems have already been
`built and more will be in use in the near future. One example
`of such satellites based navigation systems is Global Posi(cid:173)
`tioning System (GPS), which is built and operated by the
`United States Department of Defense. The system uses
`twenty-four or more satellites orbiting the earth at an altitude
`of about 11,000 miles with a period of about twelve hours.
`These satellites are placed in six different orbits such that at
`any time a minimum of six satellites are visible at any location
`on the surface of the earth except in the polar region. Each
`satellite transmits a time and position signal referenced to an
`atomic clock. A typical GPS receiver locks onto this signal
`and extracts the data contained in it. Using signals from a
`sufficient number of satellites, a GPS receiver can calculate
`its position, velocity, altitude, and time.
`A GPS receiver has to acquire and lock onto at least four
`satellite signals in order to derive the position and time. Usu(cid:173)
`ally, a GPS receiver has many parallel channels with each
`channel receiving signals from one visible GPS satellite. The
`acquisition of the satellite signals involves a two-dimensional
`search of carrier frequency and the pseudo-random number
`(PRN) code phase. Each satellite transmits signals using a
`unique 1023-chip long PRN code, which repeats every mil-
`lisecond. The receiver locally generates a replica carrier to
`wipe off residue carrier frequency and a replica PRN code
`sequence to correlate with the digitized received satellite
`signal sequence. During the acquisition stage, the code phase
`search step is a half-chip for most navigational satellite signal 40
`receivers. Thus the full search range of code phase includes
`2046 candidate code phases spaced by a half-chip interval.
`The carrier frequency search range depends upon the Doppler
`frequency due to relative motion between the satellite and the
`receiver. Additional frequency variation may result from local 45
`oscillator instability.
`Coherent integration and noncoherent integration are two
`commonly used integration methods to acquire GPS signals.
`Coherent integration provides better signal gain at the cost of
`larger computational load, for equal integration times.
`The power associated with noncoherent integration with
`one millisecond correlation is
`
`35
`
`N-!
`
`Power= I (/(n) 2 + Q(n) 2
`
`)
`
`n=O
`
`and the power associated with coherent integration is
`
`Power=
`
`N 1 )2 (N 1 )2
`(
`+ ~Q(n)
`~l(n)
`
`where I(n) and Q(n) denote the in-phase and quadra-phase
`parts of one-millisecond correlation values from the base(cid:173)
`band section at interval n, and N denotes the desired number
`of one-millisecond integration intervals.
`
`IPR2020-01192
`Apple EX1029 Page 7
`
`

`

`US 7,439,907 B2
`
`3
`2002/0130812, and 2003/0112176 by Qualconnn disclose
`methods for sending additional aiding information to receiv-
`ers to provide correction due to the use of old ephemeris. U.S.
`Pat. No. 6,727,848 and U.S. patent application2002/0186165
`disclose aiding by a reference receiver or through DGPS.
`When aided by the reference receiver, the required correction
`is generated at the remote reference receiver. U.S. Pat. No.
`6,225,945 assigned to Trimble Corp. obtains the position
`correction by integrating the velocity. While this method does
`not require current ephemeris for the computation of correc-
`tion, it is less accurate. Thus, these methods require additional
`aiding stations or involve computation and may be less accu(cid:173)
`rate.
`Therefore, there is a need for methods and systems that
`enable a mobile navigation receiver to accurately determine 15
`its trajectory with non-current ephemeris in stand-alone mode
`and does not require a large computation load.
`
`10
`
`5
`
`SUMMARY
`
`4
`In another embodiment, the receiver detects when the
`receiver makes a transition between an indoor and outdoor
`environment in a sniff mode. The receiver may do this by
`periodically, e.g., every 30 seconds, testing received signal
`strength to determine whether the receiver is currently in an
`indoor or outdoor environment. In this embodiment, the
`receiver may automatically start acquiring and tracking sat(cid:173)
`ellite signals to compute receiver trajectory when an indoor to
`outdoor transition is detected and use the last saved position
`as the initial position to correct the computed trajectory.
`In another embodiment, the user may manually enter a
`location or change in position into the receiver to correct the
`receiver trajectory. In this embodiment, when the user enters
`a location, the receiver computes the difference in position
`between the location entered by the user and the computed
`position at that time instance. The receiver then corrects the
`subsequent trajectory by shifting the computed trajectory by
`the difference. Thus, at any point the user finds an error in the
`computed trajectory including the initial position, the user
`20 may enter the correct location into the receiver to correct the
`trajectory.
`An advantage of the present invention is that it does not
`require the reception of aiding information from reference
`stations or any external sources.
`The above and other advantages of embodiments of this
`invention will be apparent from the following more detailed
`description when taken in conjunction with the accompany(cid:173)
`ing drawings.
`
`25
`
`Accordingly, the present invention provides methods and
`systems that enable a mobile navigation receiver to accurately
`determine its trajectory with non-current ephemeris in stand(cid:173)
`alone mode.
`In an embodiment, the receiver computes the position for
`the same location using non-current ephemeris and current
`ephemeris at different time instances. The receiver then deter(cid:173)
`mines a position correction by finding the difference between
`these two computed positions, and applies this correction to 30
`the subsequent receiver trajectory computed using non-cur(cid:173)
`rent ephemeris to obtain a more accurate trajectory. The cor(cid:173)
`rection dependence on constellation change due to the entry
`of new satellites may also be taken cared of. Later, subsequent
`downloading of new ephemeris ensures the continued accu-
`racy of the trajectory without the correction.
`In an embodiment, the receiver computes an initial position
`of the receiver using non-current ephemeris and finds the
`difference between the computed initial position and an accu(cid:173)
`rate approximation of the initial position. The receiver then 40
`shifts the subsequent receiver trajectory computed using non(cid:173)
`current ephemeris by the difference to obtain a more accurate
`trajectory.
`Various embodiments are provided for determining the
`approximate initial position of the receiver. In one embodi(cid:173)
`ment, the position of the receiver is saved in memory when the
`receiver or a vehicle carrying the receiver is powered off.
`When the receiver or vehicle is powered back on, the saved
`position is used as the initial position. In another embodi(cid:173)
`ment, the receiver uses an e-compass to determine the direc-
`tions in which the receiver enters and exits an indoor area. If
`the detected directions are opposite, then the receiver may
`assume that the entrance and exit are co-located and use the
`saved position as the initial position. If the directions are the
`same, then the receiver may assume that the entrance and exit
`are not co-located and use the saved position as an approxi(cid:173)
`mation. In another embodiment, the receiver uses a motion
`sensor to detect motion of the receiver. The receiver may use
`the motion sensor in conjunction with thee-compass to deter(cid:173)
`mine the difference in position between the exit and entrance
`of an indoor area, and add this difference to the last saved
`position to obtain the initial position. In another embodiment,
`the user may input the initial position into the receiver. For
`example, the user may input the co-coordinates when passing
`a landmark whose coordinates are known. In another embodi(cid:173)
`ment, the receiver may download the ephemeris in an outdoor
`environment when the TTFF is tolerable.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`35
`
`FIG. lA is a block diagram illustrating a GPS receiver
`according to an embodiment of the present invention.
`FIG. lB illustrates a method for determining the trajectory
`of a mobile navigational receiver with non-current ephemeris
`according to an embodiment of the present invention.
`FIG. 2 illustrates the use of an e-compass in a large indoor
`area according to an embodiment of the present invention.
`FIG. 3 illustrates the use of a speedometer and e-compass
`to correct a saved position according to an embodiment of the
`present invention.
`FIG. 4 illustrates initial position estimation based on
`45 approximate indoor dimensions.
`
`DETAILED DESCRIPTION
`
`50
`
`FIG. lA illustrates a receiver according to a preferred
`embodiment of the invention. An intermediate frequency (IF)
`signal input 101 enters a baseband section of the receiver
`from an analog-to-digital converter (ADC) output of a con(cid:173)
`ventional RF front-end 100. The IF input is multiplied in IF
`mixers 102 and 103 in-phase and in quadrature, respectively,
`55 with a local frequency signal generated by a direct digital
`frequency synthesizer (DDFS) 106. This mixing involves
`multiplying the ADC output 101 by the local DDFS fre(cid:173)
`quency in-phase which generates the in-phase component I
`107. In a parallel path the same signal 101 is multiplied by the
`60 DDFS frequency in quadrature (i.e., with a phase shift of 90
`degrees) to produce quadrature component Q 108. The DD FS
`106 is driven by a carrier numerically controlled oscillator
`(NCO) 105. In addition, carrier NCO 105 receives phase and
`frequency corrections from a processor 113. Because of this
`65 correction, the DDFS frequency and phase is almost the same
`as that of the ADC output 101. Thus the I and Q signals
`produced by the IF mixers 102 and 103 are at near zero carrier
`
`IPR2020-01192
`Apple EX1029 Page 8
`
`

`

`US 7,439,907 B2
`
`5
`frequency after being low-pass filtered to remove the high
`frequency components which are at twice the IF frequency
`band.
`The I and Q components 107 and 108 are correlated in
`correlators 109 and 110, respectively, with a locally-gener(cid:173)
`ated PRN sequence generated by a PRN generator 111. The
`PRN-sequence corresponds to the satellite whose signal is
`being processed by the baseband section at that time. The
`PRN sequence generator is driven by code NCO 112. The
`local code frequency is made equal to the code rate ofl and Q
`paths by corrective feedback from processor 113 to the code
`NCO 112. In addition, processor 113 sends a signal to PRN
`code generator 111 to set the starting phase of the locally
`generated code. The NCO 112 provides the correct clock
`signals to correlators 109 and 110. For example, NCO 112
`provides a clock signal to generate two samples per PRN chip
`in the signal acquisition stage and three samples per chip
`during the tracking stage. SYS CLK 104 provides to NCO
`105 and NCO 112 a common clock synchronization signal.
`The correlator outputs are then sent to processor 113 at every
`millisecond interval. The processor 113 is preferably a digital
`signal processor (DSP) core suitable for high speed arith(cid:173)
`metic computations. Subsequent processing of the signals
`take place in the processor 113, as will be described in detail
`below. Additional details of the receiver baseband section
`described above are contained in U.S. patent application Ser.
`No. 11/123,861 filed on May 6, 2005, the specification of
`which is incorporated herein by reference.
`The DSP core 113 receives one millisecond integrated
`( correlated) I and Q values from the GPS baseband section
`described above. In order to acquire a GPS signal in the DSP
`processor, all dwells ( set of carrier frequency, code offset) are
`searched. This is a two-dimensional search. Coherent inte(cid:173)
`gration and non-coherent integration are two commonly used
`integration methods to acquire GPS signals. Coherent inte(cid:173)
`gration provides better signal gain at the cost oflarger com(cid:173)
`putational load, for equal integration times.
`As shown in FIG. lA, the GPS receiver also includes a
`computational module 115 that receives GPS measurements
`from processor 113. The computational module 115 may be
`implemented in software executed on hardware for perform(cid:173)
`ing various functions of the invention described further
`below. The receiver may also include an e-compass 117 for
`providing direction information and a motion sensor 119 for
`providing motion information. The motion sensor 119 may be
`a gyro-meter, accelerometer, pedometer or other sensor. As
`explained further below, thee-compass 117 and/or motion
`sensor 119 may be used to correct and enhance the GPS
`position information. In some embodiments the GPS is pow(cid:173)
`ered on when the motion sensor 119 sends a signal to a start
`module 123. The signal may be generated when thee-com(cid:173)
`pass changes direction or when the motion detector detects
`motion from a standstill state. This signal is used to power on
`the GPS receiver. When activated, the start module 123 may
`power up the components necessary to acquire and track
`satellite signals including the RF-front end, the baseband
`section, etc. The receiver may further comprise a signal
`strength detector 127 for testing the received signal strength
`to detect indoor/outdoor transitions of the receiver, as dis(cid:173)
`cussed further below. The signal strength detector 127 may
`test the signal strength at the RF front end output or at another
`point in the receiver. The receiver also includes memory 121
`for storing receiver positions, ephemeris and other data used
`by the receiver as described further below. The receiver may
`also include a user interface 125 for manually entering data
`into the receiver.
`
`6
`A GPS receiver uses the downloaded ephemeris to accu(cid:173)
`rately compute the position of the visible satellites. Based on
`these satellite positions, the position of the receiver is esti(cid:173)
`mated. This computed position is more accurate if the ephem-
`5 eris used is current. In the case of GPS, the transmitted
`ephemeris are updated every two hours even though they are
`valid for a period of four hours. If the ephemeris is used
`beyond this period of four hours, the estimated satellite posi(cid:173)
`tions are less accurate causing an offset in the pseudorange,
`10 where the pseudorange is a first cut estimated distance of the
`satellite from the receiver with no correction applied for the
`receiver clock drift, atmospheric delay, etc. This pseudorange
`offset is approximately constant during a short period of time,
`e.g., two to three minutes, and therefore causes the computed
`15 position to shift from the true position. This offset is approxi(cid:173)
`mately constant over a short time interval as long as the
`satellite constellation has not been changed. If the satellite
`geometry or constellation changes, there is an additional shift
`in the position. Thus, it is necessary to download and use the
`20 current ephemeris to minimize this position error. However, it
`is not always possible to have the current ephemeris stored in
`the memory of the GPS receiver. One example is the case of
`a morning commute to the office where the GPS receiver is
`powered off for the remainder of the day and is not powered
`25 on again until the evening for the commute back home. The
`time gap is this case is more than four hours and the ephemeris
`becomes non-current. Also the visible satellites are different.
`Use of this non-current ephemeris results in a position esti(cid:173)
`mation with a shift in position and thus a proper vehicle
`30 navigation cannot be initiated. Further, there is a considerable
`delay if one opts to download new ephemeris from each of the
`satellites involved. This download requires eighteen seconds
`in addition to the signal track start time.
`Accordingly, for cases in which receiver has non-current
`35 ephemeris, the present invention provides fast methods and
`systems of estimating the error or shift in the position due to
`the non-current ephemeris. FIG. lB illustrates a method of
`estimating the error or shift due to the non-current ephemeris,
`and using the error or shift to correct the computed trajectory
`40 of the receiver. In this embodiment, an accurate approxima(cid:173)
`tion of the initial position 153 of the receiver is assumed to be
`available to the receiver. The initial position 153 may be the
`position where the receiver was last powered off. This
`approximation holds well, e.g., when the receiver is powered
`45 off and powered back on at approximately the same location.
`Other methods for determining the initial position 153 of the
`receiver are given below. The receiver also computes the
`initial position using the non-current ephemeris, an example
`of which is represented by reference number 155 in FIG. lB.
`50 The receiver then computes the difference in position 157
`between the initial position 155 computed using the non(cid:173)
`current ephemeris and the accurate initial position 153. This
`difference in position 157 provides an approximation of the
`error or shift due to the non-current ephemeris. The receiver
`55 corrects the subsequent receiver trajectory obtained with the
`non-current ephemeris by shifting this receiver trajectory by
`the difference 157. Thus the difference in position 157 pro(cid:173)
`vides the correction to be applied to the subsequent computed
`trajectory. An example of this is illustrated in FIG. lB. In this
`60 example, the subsequent receiver positions 155-1, 155-2,
`155-3, ... computed using the non-current ephemeris trace
`out the receiver trajectory 161 obtained with the non-current
`ephemeris. Each of these subsequent positions 155-1, 155-2,
`155-3, ...
`computed using the non-current ephemeris is
`65 shifted by the difference 157 to obtain corresponding cor(cid:173)
`rected positions 153-1, 153-2, 153-3, ... which trace out the
`corrected receiver trajectory 163. The direction of the differ-
`
`IPR2020-01192
`Apple EX1029 Page 9
`
`

`

`US 7,439,907 B2
`
`7
`ence 157 shown is FIG. lB is exemplary only as the actual
`difference may be in any direction. For ease of illustration
`only the first three subsequent positions are shown in FIG. lB.
`In some cases, the same location co-ordinates may be
`computed using current ephemeris and non-current ephem-
`eris at different time instances. For the example in which the
`receiver is powered off and powered back on at the same
`location, the same location co-ordinates may be computed
`using current ephemeris at the time of power off and using
`non-current ephemeris at the time of power on. In this 10
`example, the ephemeris at power on may have become non(cid:173)
`current due to a long time interval between power off and
`power on. Using these two computed positions, the subse(cid:173)
`quent receiver trajectory obtained with the non-current
`ephemeris can be corrected. This may be done by finding the 15
`difference between these two computed positions and shift(cid:173)
`ing the subsequent receiver trajectory obtained the non-cur(cid:173)
`rent ephemeris by the difference. Obviously, the two posi(cid:173)
`tions may be computed using different sets of satellites since
`different satellites may be visible at the power off and power 20
`on times.
`Thus in most of the cases, the initial position gives the true
`set of co-ordinates of the location where the navigation
`receiver is powered on with non-current ephemeris. The
`ephemeris becomes non-current due to the long time duration
`between power off and power on. At power on, the difference
`in the position computed with the non-current ephemeris and
`the one computed with current ephemeris provides the cor(cid:173)
`rection to be applied. Thus, the approximated true position is
`a function of the position computed using the non-current
`ephemeris and the correction.
`In another embodiment, the receiver may use a predicted
`satellite orbit or model instead of non-current ephemeris to
`estimate the satellite position for computing the trajectory of
`the receiver. Systems and methods for predicting satellite 35
`orbits based on historical navigation data stored in the
`receiver are disclosed in co-pending U.S. patent application,
`Ser. No. 11/558,614, titled "A Method andApparatus in Stan(cid:173)
`dalone Positioning Without Broadcast Ephemeris," filed on
`Nov.10, 2006, the specification of which is incorporated in its 40
`entirety by reference. The satellite orbit can be predicted
`based on historical broadcast ephemeris using a Kalman fil(cid:173)
`tering algorithm or a least squares estimator. In this embodi(cid:173)
`ment, the correction techniques of the present invention may
`also be used. The error due to the use of the predicted satellite 45
`orbit may be determined by finding the difference between
`the initial position computed using the predicted satellite
`orbit and the accurate initial position. The future trajectory
`may then be corrected by offsetting the trajectory with this
`determined error.
`While the correction is applied to the computed position
`using the non-current ephemeris, the existing constellation
`may change with the addition of some new satellite. In this
`case, the pseudorange and clock errors of the new satellite has
`to be corrected before using it in the determination of the 55
`position. Otherwise a jump in the position may occur.
`When the receiver is powered on in areas where multipath
`signals exists due to buildings in downtown areas or moun(cid:173)
`tains or trees in other areas, the computed position is not
`accurate. In such case, it is necessary to correct these multi-
`path effects to the maximum extent possible.
`The trajectory computation and correction may be per(cid:173)
`formed while the receiver is downloading new current
`ephemeris. Whenever the new ephemeris is available, it
`should be downloaded to compute the position with the 65
`proper correction for the pseudorange error. Once the new
`ephemeris is downloaded, the trajectory computation may be
`
`8
`carried out using the current ephemeris. The trajectory needs
`to be validated as new ephemeris is downloaded and used in
`the computation. The advantage of this embodiment is that
`the receiver does not have to wait for the download of the new
`ephemeris before computing receiver trajectory. This is
`because, while the new ephemeris is being downloaded, the
`receiver computes the trajectory using non-current ephemeris
`and corrects this trajectory to obtain a corrected trajectory.
`To perform the functions of the above embodiments, the
`computational module 115 may receive GPS measurements
`from the processor 113. Based on the received GPS measure(cid:173)
`ments, the