Abstract:
Described herein are systems and methods that are capable of determining receiver position and system time under weak signal conditions. When the receiver is unable to accurately determine the satellite signal travel time, e.g., due to weak signal reception or some other condition, the receiver can still estimate the pseudo-range for the satellite based on an initial receiver position and system time. In this case, the system and methods described herein provide the necessary initial receiver position and system time with enough accuracy to estimate the pseudo-range, even under weak signal conditions. The receiver can then use the estimated pseudo-range to determine a more accurate receiver position.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to position and time determination in a satellite based navigation receiver, e.g., GPS receiver, under weak signal conditions. 
       BACKGROUND OF THE INVENTION 
       [0002]    The global positioning system (GPS) is a satellite-based radio-navigation system built and operated by the United States Department of Defense. The system uses twenty-four satellites orbiting the earth at an altitude of about 11,000 miles with a period of about twelve hours. Some additional satellites may be present as spares. 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. 
         [0003]    Data is modulated to the GPS signal, in which each data bit spans 20 milliseconds. This data contains ephemeris that provides satellite orbit information and time information to help the receiver determine the system time. Under weak signal conditions, it is still possible for the receiver to acquire and track the GPS signal with a longer non-coherent integration time or other method. However, due to the low signal to noise ratio, the error rate of the decoded GPS broadcast data will be too high making it impossible to determine the signal transmit time. Under this condition, the traditional position calculation method can not be applied. 
         [0004]    Some prior art references have been published that deal with the above conditions. The central concept of these methods is adding another variable as system time to compensate for the uncertainty of the signal transmit time. An additional observation measurement is required to help to solve the additional variable. As a result measurements of at least five satellites are needed to calculate the final position. 
         [0005]    When the signal transmit time can not be determined, it is impossible to calculate the pseudo-range with the traditional method of multiplying the speed of light with the difference between the signal transmit time and receive time. Because only the C/A code is tracked, only a sub-millisecond fraction of the transmit time can be determined. As a result, the calculated pseudo-range will have 300 km ambiguity, which is the distance the signal travels in one millisecond. 
         [0006]    Given an estimated pseudo-range of one satellite ρ i , the pseudo-range can be divided into a millisecond part and a sub-millisecond part, ρ i =ρ i   (1) +ρ i   (2) , where 
         [0000]    
       
         
           
             
               
                 ρ 
                 i 
                 
                   ( 
                   1 
                   ) 
                 
               
               = 
               
                 Λ 
                 × 
                 
                   ⌊ 
                   
                     
                       ρ 
                       i 
                     
                     Λ 
                   
                   ⌋ 
                 
               
             
             , 
             
               
                 ρ 
                 i 
                 
                   ( 
                   2 
                   ) 
                 
               
               = 
               
                 
                   ρ 
                   i 
                 
                 - 
                 
                   
                     ρ 
                     i 
                     
                       ( 
                       1 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    The symbol └ ┘ indicates to take the integer value of the division. The symbol Λ is the distance light travels in 1 ms and is about 300 km. Under weak signal conditions, only the sub-millisecond part ρ i   (2)  can be obtained. The millisecond part ρ i   (1)  can be estimated and used to calculate the pseudo-range ρ i  by carrying out the following steps: 
         [0007]    Make an estimation of the GPS time of signal arrival T u . 
         [0008]    Estimate the travel time of the signal t f . If the travel time can not be estimated, use 70 ms as an approximation for t f . 
         [0009]    Calculate the satellite position at time T u −t f  as {right arrow over (s)} i (T u −t f ), where {right arrow over (s)} i ( ) is the satellite position as a function of time, which may be derived from ephemeris downloaded onto the receiver. 
         [0010]    Use the estimated user position U to calculate the millisecond part of the pseudorange as: 
         [0000]    
       
         
           
             
               
                 ρ 
                 i 
                 
                   ( 
                   1 
                   ) 
                 
               
               = 
               
                 Λ 
                 × 
                 
                   ⌊ 
                   
                     
                       
                          
                         
                           
                             
                               
                                 s 
                                 ⇀ 
                               
                               i 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   u 
                                 
                                 - 
                                 
                                   t 
                                   f 
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             u 
                             ⇀ 
                           
                         
                          
                       
                       + 
                       
                         ct 
                         u 
                       
                     
                     Λ 
                   
                   ⌋ 
                 
               
             
             , 
           
         
       
     
         [0000]    where t u  is the receiver clock offset. 
         [0011]    Sum the parts ρ i   (1)  and ρ i   (2)  together to get ρ i =ρ i   (1) +ρ i   (2) . 
         [0012]    Although a precise determination of the receiver clock offset t u  should include the same information as a precise determination of what is here called the GPS time at arrival T u  (in the sense that if you know t u  precisely, you should know T u ), the GPS time at arrival as used here likely does not convey the same information as the receiver clock offset. Thus, the GPS time at arrival is treated as independent of the receiver clock offset. By introducing the GPS time at arrival T u  as one additional degree of freedom for the solution of the PVT equation, at least five satellites need to be tracked to solve the PVT. The equations are shown by the following: 
         [0013]    At time T u −t f  the position of the i th  satellite is {right arrow over (s)} i , and the speed of the i th  satellite is {right arrow over (v)} i , where i is used for a satellite index. 
         [0014]    The initial receiver position is {right arrow over (û)} and initial clock offset is {circumflex over (t)} u . 
         [0015]    An initial range {circumflex over (ρ)} i  can be written as {circumflex over (ρ)} i ={circumflex over (r)} i +c{circumflex over (t)} u , where {circumflex over (r)} i =∥{right arrow over (s)} i −{right arrow over (û)}∥. The unit vector of {circumflex over (r)} i  is 
         [0000]    
       
         
           
             
               
                 
                   a 
                   ⇀ 
                 
                 i 
               
               = 
               
                 
                   
                     
                       
                         s 
                         ⇀ 
                       
                       i 
                     
                     - 
                     
                       u 
                       
                         ⇀ 
                         ^ 
                       
                     
                   
                   
                     
                       r 
                       ^ 
                     
                     i 
                   
                 
                 = 
                 
                   
                     
                       a 
                       xi 
                     
                     · 
                     
                       x 
                       ⇀ 
                     
                   
                   + 
                   
                     
                       a 
                       yi 
                     
                     · 
                     
                       y 
                       ⇀ 
                     
                   
                   + 
                   
                     
                       a 
                       zi 
                     
                     · 
                     
                       z 
                       ⇀ 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    in which {right arrow over (x)}, {right arrow over (y)} and {right arrow over (z)} correspond to the x, y and z axis. The difference between the initial range {circumflex over (ρ)} i  and the range ρ i  to be solved is Δρ i ={circumflex over (ρ)}−ρ i ={circumflex over (r)} i +c{circumflex over (t)} u −ρ i . The solution using five satellites can be given by: 
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               
                 ρ 
                 ⇀ 
               
             
             = 
             
               [ 
               
                 
                   
                     
                       Δρ 
                       1 
                     
                   
                 
                 
                   
                     
                       Δρ 
                       2 
                     
                   
                 
                 
                   
                     
                       Δρ 
                       3 
                     
                   
                 
                 
                   
                     
                       Δρ 
                       4 
                     
                   
                 
                 
                   
                     
                       Δρ 
                       5 
                     
                   
                 
               
               ] 
             
           
         
       
       
         
           
             H 
             = 
             
               
                 
                   [ 
                   
                     
                       
                         
                           a 
                           
                             x 
                              
                             
                                 
                             
                              
                             1 
                           
                         
                       
                       
                         
                           a 
                           
                             y 
                              
                             
                                 
                             
                              
                             1 
                           
                         
                       
                       
                         
                           a 
                           
                             z 
                              
                             
                                 
                             
                              
                             1 
                           
                         
                       
                       
                         
                           
                             
                               a 
                               ⇀ 
                             
                             1 
                           
                           · 
                           
                             
                               v 
                               ⇀ 
                             
                             1 
                           
                         
                       
                       
                         1 
                       
                     
                     
                       
                         
                           a 
                           
                             x 
                              
                             
                                 
                             
                              
                             2 
                           
                         
                       
                       
                         
                           a 
                           
                             y 
                              
                             
                                 
                             
                              
                             2 
                           
                         
                       
                       
                         
                           a 
                           
                             z 
                              
                             
                                 
                             
                              
                             2 
                           
                         
                       
                       
                         
                           
                             
                               a 
                               ⇀ 
                             
                             2 
                           
                           · 
                           
                             
                               v 
                               ⇀ 
                             
                             2 
                           
                         
                       
                       
                         1 
                       
                     
                     
                       
                         
                           a 
                           
                             x 
                              
                             
                                 
                             
                              
                             3 
                           
                         
                       
                       
                         
                           a 
                           
                             y 
                              
                             
                                 
                             
                              
                             3 
                           
                         
                       
                       
                         
                           a 
                           
                             z 
                              
                             
                                 
                             
                              
                             3 
                           
                         
                       
                       
                         
                           
                             
                               a 
                               ⇀ 
                             
                             3 
                           
                           · 
                           
                             
                               v 
                               ⇀ 
                             
                             3 
                           
                         
                       
                       
                         1 
                       
                     
                     
                       
                         
                           a 
                           
                             x 
                              
                             
                                 
                             
                              
                             4 
                           
                         
                       
                       
                         
                           a 
                           
                             y 
                              
                             
                                 
                             
                              
                             4 
                           
                         
                       
                       
                         
                           a 
                           
                             z 
                              
                             
                                 
                             
                              
                             4 
                           
                         
                       
                       
                         
                           
                             
                               a 
                               ⇀ 
                             
                             4 
                           
                           · 
                           
                             
                               v 
                               ⇀ 
                             
                             4 
                           
                         
                       
                       
                         1 
                       
                     
                     
                       
                         
                           a 
                           
                             x 
                              
                             
                                 
                             
                              
                             5 
                           
                         
                       
                       
                         
                           a 
                           
                             y 
                              
                             
                                 
                             
                              
                             5 
                           
                         
                       
                       
                         
                           a 
                           
                             z 
                              
                             
                                 
                             
                              
                             5 
                           
                         
                       
                       
                         
                           
                             
                               a 
                               ⇀ 
                             
                             5 
                           
                           · 
                           
                             
                               v 
                               ⇀ 
                             
                             5 
                           
                         
                       
                       
                         1 
                       
                     
                   
                   ] 
                 
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 Δ 
                  
                 
                     
                 
                  
                 
                   x 
                   ⇀ 
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           x 
                           u 
                         
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           y 
                           u 
                         
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           z 
                           u 
                         
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           T 
                           u 
                         
                       
                     
                   
                   
                     
                       
                         - 
                         
                           ct 
                           u 
                         
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
         [0016]    which gives Δ{right arrow over (ρ)}=HΔ{right arrow over (x)}. 
         [0017]    With more than five satellites, we can use least square method to get the solution. 
         [0018]    Because of the ambiguity of Λ in the pseudo-range calculation, the estimated user position and time should not be too far away from the true value, otherwise, the millisecond part of ρ i   (1)  will have and incorrect value and result in an incorrect receiver position calculation. This limitation gives a restriction on the initial position and initial time of 
         [0000]    
       
         
           
             
               
                 κ 
                 · 
                 
                   ( 
                   
                     
                       T 
                       u 
                     
                     - 
                     
                       
                         T 
                         ^ 
                       
                       u 
                     
                   
                   ) 
                 
               
               + 
               
                  
                 
                   
                     u 
                     ⇀ 
                   
                   - 
                   
                     u 
                     
                       ⇀ 
                       ^ 
                     
                   
                 
                  
               
             
             &lt; 
             
               
                 Λ 
                 2 
               
               . 
             
           
         
       
     
         [0000]    Here T u  and {right arrow over (u)} are the true signal arrive time and receiver position respectively, {circumflex over (T)} u  and {right arrow over (û)} are estimated initial signal arrive time and receiver position respectively, and κ is the maximum possible pseudo-range change rate (about 710 m/s). 
         [0019]    If the above condition can not be met, several methods can be applied to help remove the ambiguity of the pseudo-range. One of these methods is to introduce one or more additional observation measurements so the number of equations in Δ{right arrow over (ρ)}=HΔ{right arrow over (x)} is more than the number of variables. When using the least square method to solve the equations, we can get a residual of the solution. A grid is applied to the possible area covering the possible initial position. With all the possible initial positions and signal arrival times, the residual will reach the global minimum with the correct combination. These combinations should cover the span of all possible estimated signal arrival times and the area around the surface of the earth that can see all the satellites. Because this algorithm searches all the possible solutions and finds the minimum one, the computation time is significant and performing a position fix on an embedded computing system in a limited time is not practical. 
         [0020]    Several publications discuss the above methods. A method using five satellites to perform the position fix is disclosed in U.S. Pat. No. 6,215,442 B1, and U.S. Pat. No. 6,437,694 B1 discloses a method using Kalman filter. Methods using six or more satellites that find the minimum residual result as the final solution are described in U.S. Pat. No. 6,417,801 B1 and U.S. Pat. No. 6,734,821 B2. In U.S. Pat. No. 6,865,478 B2, a method is given to reduce the possible initial positions to reduce the computation time. U.S. Pat. No. 6,670,916 gives a height constraint condition so that four satellites can be used to compute the position. 
         [0021]    When the initial position and time is unknown or is less accurate such that the condition of 
         [0000]    
       
         
           
             
               
                 κ 
                 · 
                 
                   ( 
                   
                     
                       T 
                       u 
                     
                     - 
                     
                       
                         T 
                         ^ 
                       
                       u 
                     
                   
                   ) 
                 
               
               + 
               
                  
                 
                   
                     u 
                     ⇀ 
                   
                   - 
                   
                     u 
                     
                       ⇀ 
                       ^ 
                     
                   
                 
                  
               
             
             &lt; 
             
               Λ 
               2 
             
           
         
       
     
         [0000]    can not be met, none of above methods can be applied to calculate receiver position within a reasonable computation time especially for embedded electrical devices. 
         [0022]    Accordingly, there is a need for determining an initial position and time that is accurate enough to be used as a starting point to calculate the receiver position, and that can be performed within a reasonable computation time. This would provide relatively accurate initial position and time to meet the requirement of 
         [0000]    
       
         
           
             
               
                 κ 
                 · 
                 
                   ( 
                   
                     
                       T 
                       u 
                     
                     - 
                     
                       
                         T 
                         ^ 
                       
                       u 
                     
                   
                   ) 
                 
               
               + 
               
                  
                 
                   
                     u 
                     ⇀ 
                   
                   - 
                   
                     u 
                     
                       ⇀ 
                       ^ 
                     
                   
                 
                  
               
             
             &lt; 
             
               Λ 
               2 
             
           
         
       
     
         [0000]    to perform further position calculations. 
       SUMMARY 
       [0023]    Described herein are systems and methods that are capable of determining receiver position and system time under weak signal conditions. 
         [0024]    When the receiver is unable to accurately determine the satellite signal travel time, e.g., due to weak signal reception or some other condition, the receiver can still estimate the pseudo-range for the satellite based on an initial receiver position and system time. In this case, the system and methods described herein provide the necessary initial receiver position and system time with enough accuracy to estimate the pseudo-range, even under weak signal conditions. The receiver can then use the estimated pseudo-range to determine a more accurate receiver position. Preferably, the systems and methods described herein require low computational load, allowing the initial position and time to be computed in real time and/or on embedded systems. 
         [0025]    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 accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0026]      FIG. 1  is a block diagram illustrating an exemplary GPS receiver. 
           [0027]      FIG. 2  is a flow diagram illustrating a method for determining receiver position under weak signal conditions. 
       
    
    
     DETAILED DESCRIPTION 
       [0028]      FIG. 1  illustrates a receiver according to an exemplary embodiment of the invention. An RF front-end  100  processes the RF signal received at the antenna (not shown). Operations of a conversional RF front-end  100  include amplification, down-conversion, and analog-to-digital conversion. The RF front end  100  outputs an intermediate frequency (IF) signal  101  to the baseband section of the receiver. The IF input is multiplied in IF mixer  103  in-phase and quad-phase with a local frequency signal generated by a direct digital frequency synthesizer (DDFS)  102 . This mixing involves multiplying the IF input signal  101  by the local DDFS frequency which generates the in-phase and quad-phase component  104 . The DDFS  102  is driven by a carrier numerically controlled oscillator (NCO)  105 . In addition, carrier NCO  105  receives phase and frequency corrections from a processor  110 . Because of this correction, the DDFS frequency and phase is almost the same as that of the IF input signal  101 . Thus the I and Q signals produced by the IF mixers  103  are at near zero carrier frequency after being low-pass filtered to remove the high frequency components which are at twice the IF frequency band. 
         [0029]    The I and Q components  104  are correlated in correlators  106  with a locally-generated PRN sequence generated by a PN generator  107 . The PRN-sequence corresponds to the satellite whose signal is being processed by the baseband section at that time. The PN sequence generator is driven by code NCO  108 . The local code frequency is made equal to the code rate of I and Q paths by corrective feedback from the processor  110  to the code NCO  108 . In addition, the processor  110  controls the code NCO  108  to set the phase and frequency of local generated PN code. The correlator outputs are then sent to the processor  110  at every millisecond interval. The processor  110  is preferably a digital signal processor (DSP) or a general purpose CPU suitable for high speed arithmetic computations. Subsequent processing of the signals takes place in the processor  110 , which then sends the feedback to carrier NCO  105  and code NCO  108 . Also, the result of the processor is send to CPU  111 , which can be the same one as the processor or a different processor running in parallel. The CPU  111  will derive pseudo-ranges and Doppler measurements using the information of the signal tracking result and then calculate the receiver position. Memory  112 , which can include volatile and/or non-volatile memory, is used to store program and data. The ephemeris for the satellites are also stored in the memory  112  or obtained from other sources such as a GSM network. 
         [0030]    According to the exemplary receiver illustrated in  FIG. 1 , when the GPS signal is acquired and tracked, the ranging code is synchronized with the local generated code, and the local oscillator tracks the signal carrier, which enables the receiver to measure the Doppler of the satellite. The Doppler measurement for an i th  satellite can be expressed as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       f 
                       di 
                     
                     · 
                     L 
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               
                                 v 
                                 ⇀ 
                               
                               i 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   u 
                                 
                                 - 
                                 
                                   t 
                                   f 
                                 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               v 
                               ⇀ 
                             
                             u 
                           
                         
                         ] 
                       
                       · 
                       
                         
                           
                             u 
                             ⇀ 
                           
                           - 
                           
                             
                               
                                 s 
                                 ⇀ 
                               
                               i 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   u 
                                 
                                 - 
                                 
                                   t 
                                   f 
                                 
                               
                               ) 
                             
                           
                         
                         
                            
                           
                             
                               u 
                               ⇀ 
                             
                             - 
                             
                               
                                 
                                   s 
                                   ⇀ 
                                 
                                 i 
                               
                                
                               
                                 ( 
                                 
                                   
                                     T 
                                     u 
                                   
                                   - 
                                   
                                     t 
                                     f 
                                   
                                 
                                 ) 
                               
                             
                           
                            
                         
                       
                     
                     - 
                     
                       c 
                        
                       
                           
                       
                        
                       
                         
                           t 
                           . 
                         
                         u 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0031]    where f di  is the Doppler frequency, L is the wavelength of the L1 signal, {right arrow over (s)} i  and {right arrow over (v)} i  are the position and speed of the i th  satellite at time T u −t f  respectively, and {right arrow over (u)} and {right arrow over (v)} u  are receiver position and speed respectively. The quantity f di ·L expresses the Doppler in terms of a rate change of the distance between the satellite and receiver with time. The quantity −c{dot over (t)} u  takes into account receiver clock drift. In many cases, the receiver is not moving at a very high speed. Thus, some approximations can be applied such as ignoring the speed of the receiver, i.e., assuming {right arrow over (v)} u  is zero. This approximation is suitable if the purpose of this method is not to provide very accurate receiver position, but receiver position that is accurate enough to be used as an initial position or starting point in calculations for estimating the pseudo-range. The time of signal travel can also be ignored because the uncertainty of T u  is much more than t f . With these approximation, equation (1) can be simplified to the following: 
         [0000]    
       
         
           
             
               
                 
                   
                     V 
                     i 
                   
                   = 
                   
                     
                       
                         f 
                         di 
                       
                       · 
                       L 
                     
                     = 
                     
                       
                         
                           
                             s 
                             
                               . 
                               ⇀ 
                             
                           
                            
                           
                             ( 
                             
                               T 
                               u 
                             
                             ) 
                           
                         
                         · 
                         
                           
                             
                               u 
                               ⇀ 
                             
                             - 
                             
                               
                                 
                                   s 
                                   ⇀ 
                                 
                                 i 
                               
                                
                               
                                 ( 
                                 
                                   T 
                                   u 
                                 
                                 ) 
                               
                             
                           
                           
                              
                             
                               
                                 u 
                                 ⇀ 
                               
                               - 
                               
                                 
                                   
                                     s 
                                     ⇀ 
                                   
                                   i 
                                 
                                  
                                 
                                   ( 
                                   
                                     T 
                                     u 
                                   
                                   ) 
                                 
                               
                             
                              
                           
                         
                       
                       - 
                       
                         c 
                          
                         
                             
                         
                          
                         
                           
                             t 
                             . 
                           
                           u 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0032]    Here {dot over ({right arrow over (s)} i (T u ) is the derivative of position {right arrow over (s)} i (T u ) and is used as the speed of the satellite at time T u . The derivate of the satellite position can be calculated using a differential value (compute satellite position at different times and divide by the time difference) or a first derivative equation of the equation used to calculate position. 
         [0033]    The receiver position {right arrow over (u)} comprises three dimension coordinate components x, y and z. Including two additional variables, receiver time as T u  and receiver local oscillator frequency bias as {dot over (t)} u , equation (2) can be linearized as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       V 
                       i 
                     
                     ( 
                     
                       
                         
                           x 
                           ^ 
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           x 
                         
                       
                       , 
                       
                         
                           y 
                           ^ 
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           y 
                         
                       
                       , 
                       
                         
                           z 
                           ^ 
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           z 
                         
                       
                       , 
                       
                         
                           
                             T 
                             ^ 
                           
                           u 
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             T 
                             u 
                           
                         
                       
                       , 
                       
                         
                           
                             t 
                             
                               . 
                               ^ 
                             
                           
                           u 
                         
                         + 
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             
                               t 
                               . 
                             
                             u 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       
                         V 
                         i 
                       
                       ( 
                       
                         
                           x 
                           ^ 
                         
                         , 
                         
                           y 
                           ^ 
                         
                         , 
                         
                           z 
                           ^ 
                         
                         , 
                         
                           
                             T 
                             ^ 
                           
                           u 
                         
                         , 
                         
                           
                             t 
                             
                               . 
                               ^ 
                             
                           
                           u 
                         
                       
                       ) 
                     
                     + 
                     
                       
                         
                           ∂ 
                           
                             
                               V 
                               i 
                             
                             ( 
                             
                               
                                 x 
                                 ^ 
                               
                               , 
                               
                                 y 
                                 ^ 
                               
                               , 
                               
                                 z 
                                 ^ 
                               
                               , 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               , 
                               
                                 
                                   t 
                                   
                                     . 
                                     ^ 
                                   
                                 
                                 u 
                               
                             
                             ) 
                           
                         
                         
                           ∂ 
                           
                             x 
                             ^ 
                           
                         
                       
                        
                       Δ 
                        
                       
                           
                       
                        
                       x 
                     
                     + 
                     
                       
                         
                           ∂ 
                           
                             
                               V 
                               i 
                             
                             ( 
                             
                               
                                 x 
                                 ^ 
                               
                               , 
                               
                                 y 
                                 ^ 
                               
                               , 
                               
                                 z 
                                 ^ 
                               
                               , 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               , 
                               
                                 
                                   t 
                                   
                                     . 
                                     ^ 
                                   
                                 
                                 u 
                               
                             
                             ) 
                           
                         
                         
                           ∂ 
                           
                             y 
                             ^ 
                           
                         
                       
                        
                       Δ 
                        
                       
                           
                       
                        
                       y 
                     
                     + 
                     
                       
                         
                           ∂ 
                           
                             
                               V 
                               i 
                             
                             ( 
                             
                               
                                 x 
                                 ^ 
                               
                               , 
                               
                                 y 
                                 ^ 
                               
                               , 
                               
                                 z 
                                 ^ 
                               
                               , 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               , 
                               
                                 
                                   t 
                                   
                                     . 
                                     ^ 
                                   
                                 
                                 u 
                               
                             
                             ) 
                           
                         
                         
                           ∂ 
                           
                             z 
                             ^ 
                           
                         
                       
                        
                       Δ 
                        
                       
                           
                       
                        
                       z 
                     
                     + 
                     
                       
                         
                           ∂ 
                           
                             
                               V 
                               i 
                             
                             ( 
                             
                               
                                 x 
                                 ^ 
                               
                               , 
                               
                                 y 
                                 ^ 
                               
                               , 
                               
                                 z 
                                 ^ 
                               
                               , 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               , 
                               
                                 
                                   t 
                                   
                                     . 
                                     ^ 
                                   
                                 
                                 u 
                               
                             
                             ) 
                           
                         
                         
                           ∂ 
                           
                             
                               T 
                               ^ 
                             
                             u 
                           
                         
                       
                        
                       Δ 
                        
                       
                           
                       
                        
                       
                         
                           T 
                           ^ 
                         
                         u 
                       
                     
                     + 
                     
                       
                         
                           ∂ 
                           
                             
                               V 
                               i 
                             
                             ( 
                             
                               
                                 x 
                                 ^ 
                               
                               , 
                               
                                 y 
                                 ^ 
                               
                               , 
                               
                                 z 
                                 ^ 
                               
                               , 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               , 
                               
                                 
                                   t 
                                   
                                     . 
                                     ^ 
                                   
                                 
                                 u 
                               
                             
                             ) 
                           
                         
                         
                           ∂ 
                           
                             
                               t 
                               
                                 . 
                                 ^ 
                               
                             
                             u 
                           
                         
                       
                        
                       Δ 
                        
                       
                           
                       
                        
                       
                         
                           t 
                           
                             . 
                             ^ 
                           
                         
                         u 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0034]    where {circumflex over (x)}, ŷ, {circumflex over (z)}, {circumflex over (T)} u  and {dot over ({circumflex over (t)} u  are initial values of variables x, y, z, T u , and {dot over (t)} u  respectively. The symbol Δ for a variable indicates the difference between the initial value and the value to be solved. The above linearization is determined by taking a Taylor series expansion of V i  and keeping the first order partial derivative of the expansion. 
         [0035]    Some intermediate variables and equations are listed below to simplify the final result. 
         [0036]    The equations {circumflex over (r)} xi ={circumflex over (x)}−x si ({circumflex over (T)} u ),{circumflex over (r)} yi =(ŷ−y si ({circumflex over (T)} u )),{circumflex over (r)} zi =({circumflex over (z)}−z si ({circumflex over (T)} u )) represent the difference of the receiver and the i th  satellite coordinates in three dimensions based on the initial values. 
         [0037]    The equation {circumflex over (r)} i =∥{right arrow over (û)}−{right arrow over (s)} i ({circumflex over (T)} u )∥=√{square root over ({circumflex over (r)} xi   2 +{circumflex over (r)} yi   2 +{circumflex over (r)} zi   2 )} is the geometry distance from the receiver to the i th  satellite based on the initial values. 
         [0038]    The equation 
         [0000]    
       
         
           
             
               
                 v 
                 ^ 
               
               i 
             
             = 
             
               
                 
                   
                     
                       r 
                       ^ 
                     
                     xi 
                   
                   · 
                   
                     
                       
                         x 
                         . 
                       
                       si 
                     
                      
                     
                       ( 
                       
                         
                           T 
                           ^ 
                         
                         u 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     
                       r 
                       ^ 
                     
                     yi 
                   
                   · 
                   
                     
                       
                         y 
                         . 
                       
                       si 
                     
                      
                     
                       ( 
                       
                         
                           T 
                           ^ 
                         
                         u 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     
                       r 
                       ^ 
                     
                     zi 
                   
                   · 
                   
                     
                       
                         z 
                         . 
                       
                       si 
                     
                      
                     
                       ( 
                       
                         
                           T 
                           ^ 
                         
                         u 
                       
                       ) 
                     
                   
                 
               
               
                 
                   r 
                   ^ 
                 
                 i 
               
             
           
         
       
     
         [0000]    is radial speed or range change rate of the i th  satellite based on the initial values. 
         [0039]    The equation ΔV i =f di ·L−V i ({circumflex over (x)},ŷ,{circumflex over (z)},{circumflex over (T)} u ,{dot over ({circumflex over (t)} u ) is the difference of the measured Doppler and the calculated Doppler based on the initial values. 
         [0040]    Based on the above equations, the partial derivatives in equation (3) can be given by: 
         [0000]    
       
         
           
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         ∂ 
                         
                           
                             V 
                             i 
                           
                           ( 
                           
                             
                               x 
                               ^ 
                             
                             , 
                             
                               y 
                               ^ 
                             
                             , 
                             
                               z 
                               ^ 
                             
                             , 
                             
                               
                                 T 
                                 ^ 
                               
                               u 
                             
                             , 
                             
                               
                                 t 
                                 
                                   . 
                                   ^ 
                                 
                               
                               u 
                             
                           
                           ) 
                         
                       
                       
                         ∂ 
                         
                           x 
                           ^ 
                         
                       
                     
                     = 
                     
                       
                         
                           
                             f 
                             ^ 
                           
                           xi 
                         
                         
                           
                             r 
                             ^ 
                           
                           i 
                         
                       
                       = 
                       
                         
                           
                             
                               
                                 x 
                                 . 
                               
                               si 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               
                                 v 
                                 ^ 
                               
                               i 
                             
                             · 
                             
                               
                                 
                                   r 
                                   ^ 
                                 
                                 xi 
                               
                               / 
                               
                                 
                                   r 
                                   ^ 
                                 
                                 i 
                               
                             
                           
                         
                         
                           
                             r 
                             ^ 
                           
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         ∂ 
                         
                           
                             V 
                             i 
                           
                           ( 
                           
                             
                               x 
                               ^ 
                             
                             , 
                             
                               y 
                               ^ 
                             
                             , 
                             
                               z 
                               ^ 
                             
                             , 
                             
                               
                                 T 
                                 ^ 
                               
                               u 
                             
                             , 
                             
                               
                                 t 
                                 
                                   . 
                                   ^ 
                                 
                               
                               u 
                             
                           
                           ) 
                         
                       
                       
                         ∂ 
                         
                           y 
                           ^ 
                         
                       
                     
                     = 
                     
                       
                         
                           
                             f 
                             ^ 
                           
                           yi 
                         
                         
                           
                             r 
                             ^ 
                           
                           i 
                         
                       
                       = 
                       
                         
                           
                             
                               
                                 y 
                                 . 
                               
                               si 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               
                                 v 
                                 ^ 
                               
                               i 
                             
                             · 
                             
                               
                                 
                                   r 
                                   ^ 
                                 
                                 yi 
                               
                               / 
                               
                                 
                                   r 
                                   ^ 
                                 
                                 i 
                               
                             
                           
                         
                         
                           
                             r 
                             ^ 
                           
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         ∂ 
                         
                           
                             V 
                             i 
                           
                           ( 
                           
                             
                               x 
                               ^ 
                             
                             , 
                             
                               y 
                               ^ 
                             
                             , 
                             
                               z 
                               ^ 
                             
                             , 
                             
                               
                                 T 
                                 ^ 
                               
                               u 
                             
                             , 
                             
                               
                                 t 
                                 
                                   . 
                                   ^ 
                                 
                               
                               u 
                             
                           
                           ) 
                         
                       
                       
                         ∂ 
                         
                           x 
                           ^ 
                         
                       
                     
                     = 
                     
                       
                         
                           
                             f 
                             ^ 
                           
                           zi 
                         
                         
                           
                             r 
                             ^ 
                           
                           i 
                         
                       
                       = 
                       
                         
                           
                             
                               
                                 z 
                                 . 
                               
                               si 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               
                                 v 
                                 ^ 
                               
                               i 
                             
                             · 
                             
                               
                                 
                                   r 
                                   ^ 
                                 
                                 zi 
                               
                               / 
                               
                                 
                                   r 
                                   ^ 
                                 
                                 i 
                               
                             
                           
                         
                         
                           
                             r 
                             ^ 
                           
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           ∂ 
                           
                             
                               V 
                               i 
                             
                             ( 
                             
                               
                                 x 
                                 ^ 
                               
                               , 
                               
                                 y 
                                 ^ 
                               
                               , 
                               
                                 z 
                                 ^ 
                               
                               , 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               , 
                               
                                 
                                   t 
                                   
                                     . 
                                     ^ 
                                   
                                 
                                 u 
                               
                             
                             ) 
                           
                         
                         
                           ∂ 
                           
                             
                               T 
                               ^ 
                             
                             u 
                           
                         
                       
                       = 
                       
                         
                           
                             g 
                             ^ 
                           
                           i 
                         
                         
                           
                             r 
                             ^ 
                           
                           i 
                         
                       
                     
                      
                     
                       
 
                     
                      
                     
                       
                         
                           g 
                           ^ 
                         
                         i 
                       
                       = 
                       
                         
                           
                             
                               r 
                               ^ 
                             
                             xi 
                           
                           · 
                           
                             
                               
                                 x 
                                 .. 
                               
                               si 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             
                               r 
                               ^ 
                             
                             yi 
                           
                           · 
                           
                             
                               
                                 y 
                                 .. 
                               
                               si 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             
                               r 
                               ^ 
                             
                             zi 
                           
                           · 
                           
                             
                               
                                 z 
                                 .. 
                               
                               si 
                             
                              
                             
                               ( 
                               
                                 
                                   T 
                                   ^ 
                                 
                                 u 
                               
                               ) 
                             
                           
                         
                         - 
                         
                           
                             
                               x 
                               . 
                             
                             si 
                             2 
                           
                            
                           
                             ( 
                             
                               
                                 T 
                                 ^ 
                               
                               u 
                             
                             ) 
                           
                         
                         - 
                         
                           
                             
                               y 
                               . 
                             
                             si 
                             2 
                           
                            
                           
                             ( 
                             
                               
                                 T 
                                 ^ 
                               
                               u 
                             
                             ) 
                           
                         
                         - 
                         
                           
                             
                               z 
                               . 
                             
                             si 
                             2 
                           
                            
                           
                             ( 
                             
                               
                                 T 
                                 ^ 
                               
                               u 
                             
                             ) 
                           
                         
                         + 
                         
                           
                             v 
                             ^ 
                           
                           i 
                           2 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         ∂ 
                         
                           
                             V 
                             i 
                           
                           ( 
                           
                             
                               x 
                               ^ 
                             
                             , 
                             
                               y 
                               ^ 
                             
                             , 
                             
                               z 
                               ^ 
                             
                             , 
                             
                               
                                 T 
                                 ^ 
                               
                               u 
                             
                             , 
                             
                               
                                 t 
                                 
                                   . 
                                   ^ 
                                 
                               
                               u 
                             
                           
                           ) 
                         
                       
                       
                         ∂ 
                         
                           
                             t 
                             
                               . 
                               ^ 
                             
                           
                           u 
                         
                       
                     
                     = 
                     
                       - 
                       c 
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0041]    For five satellites, we can calculate the following matrixes: 
         [0000]    
       
         
           
             
               V 
               = 
               
                 [ 
                 
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             V 
                             1 
                           
                           · 
                           
                             
                               r 
                               ^ 
                             
                             1 
                           
                         
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             V 
                             2 
                           
                           · 
                           
                             
                               r 
                               ^ 
                             
                             2 
                           
                         
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             V 
                             3 
                           
                           · 
                           
                             
                               r 
                               ^ 
                             
                             3 
                           
                         
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             V 
                             4 
                           
                           · 
                           
                             
                               r 
                               ^ 
                             
                             4 
                           
                         
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             V 
                             5 
                           
                           · 
                           
                             
                               r 
                               ^ 
                             
                             5 
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             , 
             
               
 
             
              
             
               H 
               = 
               
                 [ 
                 
                   
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           x 
                            
                           
                               
                           
                            
                           1 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           y 
                            
                           
                               
                           
                            
                           1 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           z 
                            
                           
                               
                           
                            
                           1 
                         
                       
                     
                     
                       
                         
                           g 
                           ^ 
                         
                         1 
                       
                     
                     
                       
                         
                           r 
                           ^ 
                         
                         1 
                       
                     
                   
                   
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           x 
                            
                           
                               
                           
                            
                           2 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           y 
                            
                           
                               
                           
                            
                           2 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           z 
                            
                           
                               
                           
                            
                           2 
                         
                       
                     
                     
                       
                         
                           g 
                           ^ 
                         
                         2 
                       
                     
                     
                       
                         
                           r 
                           ^ 
                         
                         2 
                       
                     
                   
                   
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           x 
                            
                           
                               
                           
                            
                           3 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           y 
                            
                           
                               
                           
                            
                           3 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           z 
                            
                           
                               
                           
                            
                           3 
                         
                       
                     
                     
                       
                         
                           g 
                           ^ 
                         
                         3 
                       
                     
                     
                       
                         
                           r 
                           ^ 
                         
                         3 
                       
                     
                   
                   
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           x 
                            
                           
                               
                           
                            
                           4 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           y 
                            
                           
                               
                           
                            
                           4 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           z 
                            
                           
                               
                           
                            
                           4 
                         
                       
                     
                     
                       
                         
                           g 
                           ^ 
                         
                         4 
                       
                     
                     
                       
                         
                           r 
                           ^ 
                         
                         4 
                       
                     
                   
                   
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           x 
                            
                           
                               
                           
                            
                           5 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           y 
                            
                           
                               
                           
                            
                           5 
                         
                       
                     
                     
                       
                         
                           f 
                           ^ 
                         
                         
                           z 
                            
                           
                               
                           
                            
                           5 
                         
                       
                     
                     
                       
                         
                           g 
                           ^ 
                         
                         5 
                       
                     
                     
                       
                         
                           r 
                           ^ 
                         
                         5 
                       
                     
                   
                 
                 ] 
               
             
             , 
             
               
 
             
              
             
               
                 Δ 
                  
                 
                     
                 
                  
                 x 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         x 
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         y 
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         z 
                       
                     
                   
                   
                     
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             T 
                             . 
                           
                           u 
                         
                       
                     
                   
                   
                     
                       
                         
                           - 
                           c 
                         
                          
                         
                             
                         
                          
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             t 
                             . 
                           
                           u 
                         
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
         [0042]    These matrixes can be used in the following equation to solve for the receiver position and system time: 
         [0000]        V=H·Δx   (9) 
         [0043]    The above calculation can be repeated over several iterations until the result converges. In this case, the calculated results x, y, z, T, and {dot over (t)} u  of one iteration of the calculation are used as the initial values in the next iteration of the calculation and so on. The calculation is repeated until the calculated results are close enough to their corresponding initial values, e.g., such that the results are accurate enough to be used as starting points for estimating the pseudo-range. The final calculated position and time for each satellite may then be used as the initial position and time (starting points) for estimating the pseudo-range for the satellite, e.g., using the methods described in the background. 
         [0044]    For the case that there are more than five satellites, we use can use the least square equation Δx=(H T H) −1 H T V. 
         [0045]    Initial values for {circumflex over (x)}, ŷ, {circumflex over (z)}, {circumflex over (T)} u  and {dot over ({circumflex over (t)} u  can be based on approximations and the convergence range can be very wide. A reasonable guess of the system time for the first iteration is to use the time-of-ephemeris (toe) of ephemeris stored in memory or the real time clock (RTC) time of the device. The initial receiver position for the first iteration can be a previous known receiver position, e.g., a previously computed position stored in memory. If this position is not available, another method is to calculate the geometrical center of the acquired satellites at the selected time, and use the projection point of this geometrical center on the earth surface as the position. The value of {dot over ({circumflex over (t)} u  for the first iteration can be zero. 
         [0046]    The above computations may be performed in firmware on the CPU  111  and/or processor  110 , or dedicated hardware. 
         [0047]      FIG. 2  shows the overall steps for calculating the final receiver position according to exemplary embodiment, In the first step  200 , at least five satellites are acquired. In step  201 , Doppler measurement of each acquired satellite is taken. In step  202 , receiver position and time are computed using the methods described above. In step  203 , the computed receiver position and time for each satellite are used as starting points to estimate the pseudo-range for the satellite. In step  204 , the sub-millisecond part is applied to the estimated pseudo-range to determine the final pseudo-range for the satellite. The sub-millisecond part of the pseudo-range can be derived from the local code sequence and code phase. Finally, in step  205 , the receiver position is calculated based on the final pseudo-ranges of the satellites, which may be displayed to the user and/or stored in memory. 
         [0048]    Although the present invention has been described in terms of the presently preferred embodiments, it is to be understood that the disclosure is not to be interpreted as limiting. Various alterations and modifications will no doubt become apparent to those skilled in the art after having read this disclosure. For example, although the above embodiments have been described using the GPS system as an example, the techniques and methods may be used for other global satellite navigational systems including GLONASS, Galileo, secondary systems such as WASS, EGNOS, and MSAS, as well as hybrids of the above systems. Accordingly, it is intended that the appended claims be interpreted as covering all alterations and modifications as fall within the spirit and scope of the invention.