# Patent

## Title
Position and time determination under weak signal conditions

## 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.

## Background
FIELD OF THE INVENTION
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
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.
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.
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.
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.
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




  
    
      ρ
      i
      
        (
        1
        )
      
    
    =
    
      Λ
      ×
      
        ⌊
        
          
            ρ
            i
          
          Λ
        
        ⌋
      
    
  
  ,
  
    
      ρ
      i
      
        (
        2
        )
      
    
    =
    
      
        ρ
        i
      
      -
      
        
          ρ
          i
          
            (
            1
            )
          
        
        .
      
    
  




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:

Make an estimation of the GPS time of signal arrival Tu.
Estimate the travel time of the signal tf. If the travel time can not be estimated, use 70 ms as an approximation for tf.
Calculate the satellite position at time Tu−tf as (Tu-tf), where ( ) is the satellite position as a function of time, which may be derived from ephemeris downloaded onto the receiver.
Use the estimated user position  to calculate the millisecond part of the pseudorange as:




  
    
      ρ
      i
      
        (
        1
        )
      
    
    =
    
      Λ
      ×
      
        ⌊
        
          
            
              
              
                
                  
                    
                      s
                      ⇀
                    
                    i
                  
                  ⁡
                  
                    (
                    
                      
                        T
                        u
                      
                      -
                      
                        t
                        f
                      
                    
                    )
                  
                
                -
                
                  u
                  ⇀
                
              
              
            
            +
            
              ct
              u
            
          
          Λ
        
        ⌋
      
    
  
  ,




where tu is the receiver clock offset.

Sum the parts ρi(1) and ρi(2) together to get ρi=ρi(1)+ρi(2).
Although a precise determination of the receiver clock offset tu should include the same information as a precise determination of what is here called the GPS time at arrival Tu (in the sense that if you know tu precisely, you should know Tu), 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 Tu 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:
At time Tu-tf the position of the ith satellite is , and the speed of the ith satellite is , where i is used for a satellite index.
The initial receiver position is  and initial clock offset is {circumflex over (t)}u.
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=∥−∥. The unit vector of {circumflex over (r)}i is




  
    
      
        a
        ⇀
      
      i
    
    =
    
      
        
          
            
              s
              ⇀
            
            i
          
          -
          
            u
            
              ⇀
              ^
            
          
        
        
          
            r
            ^
          
          i
        
      
      =
      
        
          
            a
            xi
          
          ·
          
            x
            ⇀
          
        
        +
        
          
            a
            yi
          
          ·
          
            y
            ⇀
          
        
        +
        
          
            a
            zi
          
          ·
          
            z
            ⇀
          
        
      
    
  
  ,




in which ,  and  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−ρi={circumflex over (r)}i+c{circumflex over (t)}u−ρi. The solution using five satellites can be given by:




  
    
      Δ
      ⁢
      
        
      
      ⁢
      
        ρ
        ⇀
      
    
    =
    
      [
      
        
          
            
              Δρ
              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
                
              
            
          
        
        ]
      
    
  



which gives Δ=HΔ.
With more than five satellites, we can use least square method to get the solution.
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




  
    
      κ
      ·
      
        (
        
          
            T
            u
          
          -
          
            
              T
              ^
            
            u
          
        
        )
      
    
    +
    
      
      
        
          u
          ⇀
        
        -
        
          u
          
            ⇀
            ^
          
        
      
      
    
  
  <
  
    
      Λ
      2
    
    .
  




Here Tu and  are the true signal arrive time and receiver position respectively, {circumflex over (T)}u and  are estimated initial signal arrive time and receiver position respectively, and κ is the maximum possible pseudo-range change rate (about 710 m/s).

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 Δ=HΔ 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.
Several publications discuss the above methods. A method using five satellites to perform the position fix is disclosed in U.S. Pat. Nos. 6,215,442 B1, and 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. Nos. 6,417,801 B1 and 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.
When the initial position and time is unknown or is less accurate such that the condition of




  
    
      κ
      ·
      
        (
        
          
            T
            u
          
          -
          
            
              T
              ^
            
            u
          
        
        )
      
    
    +
    
      
      
        
          u
          ⇀
        
        -
        
          u
          
            ⇀
            ^
          
        
      
      
    
  
  <
  
    Λ
    2
  




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.

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




  
    
      κ
      ·
      
        (
        
          
            T
            u
          
          -
          
            
              T
              ^
            
            u
          
        
        )
      
    
    +
    
      
      
        
          u
          ⇀
        
        -
        
          u
          
            ⇀
            ^
          
        
      
      
    
  
  <
  
    Λ
    2
  




to perform further position calculations.

SUMMARY
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. 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.
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
FIG. 1 is a block diagram illustrating an exemplary GPS receiver.
FIG. 2 is a flow diagram illustrating a method for determining receiver position under weak signal conditions.



DETAILED DESCRIPTION
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.
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.
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 ith satellite can be expressed as:




  
    
      
        
          
            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
        )
      
    
  




where fdi is the Doppler frequency, L is the wavelength of the L1 signal,  and  are the position and speed of the ith satellite at time Tu-tf respectively, and  and  are receiver position and speed respectively. The quantity fdi·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  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 Tu is much more than tf. With these approximation, equation (1) can be simplified to the following:




  
    
      
        
          V
          i
        
        =
        
          
            
              f
              di
            
            ·
            L
          
          =
          
            
              
                
                  s
                  
                    .
                    ⇀
                  
                
                ⁡
                
                  (
                  
                    T
                    u
                  
                  )
                
              
              ·
              
                
                  
                    u
                    ⇀
                  
                  -
                  
                    
                      
                        s
                        ⇀
                      
                      i
                    
                    ⁡
                    
                      (
                      
                        T
                        u
                      
                      )
                    
                  
                
                
                  
                  
                    
                      u
                      ⇀
                    
                    -
                    
                      
                        
                          s
                          ⇀
                        
                        i
                      
                      ⁡
                      
                        (
                        
                          T
                          u
                        
                        )
                      
                    
                  
                  
                
              
            
            -
            
              c
              ⁢
              
                
              
              ⁢
              
                
                  t
                  .
                
                u
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




Here (Tu) is the derivative of position (Tu) and is used as the speed of the satellite at time Tu. 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.
The receiver position  comprises three dimension coordinate components x, y and z. Including two additional variables, receiver time as Tu and receiver local oscillator frequency bias as {dot over (t)}u, equation (2) can be linearized as




  
    
      
        
          
            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
        )
      
    
  




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, Tu, 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 Vi and keeping the first order partial derivative of the expansion.
Some intermediate variables and equations are listed below to simplify the final result.
The equations {circumflex over (r)}xi={circumflex over (x)}−xsi({circumflex over (T)}u),{circumflex over (r)}yi=(ŷ−ysi({circumflex over (T)}u)),{circumflex over (r)}zi=({circumflex over (z)}−zsi({circumflex over (T)}u)) represent the difference of the receiver and the ith satellite coordinates in three dimensions based on the initial values.
The equation {circumflex over (r)}i=∥−({circumflex over (T)}u)∥=√{square root over ({circumflex over (r)}xi2+{circumflex over (r)}yi2+{circumflex over (r)}zi2)} is the geometry distance from the receiver to the ith satellite based on the initial values.
The equation




  
    
      v
      ^
    
    i
  
  =
  
    
      
        
          
            r
            ^
          
          xi
        
        ·
        
          
            
              x
              .
            
            si
          
          ⁡
          
            (
            
              
                T
                ^
              
              u
            
            )
          
        
      
      +
      
        
          
            r
            ^
          
          yi
        
        ·
        
          
            
              y
              .
            
            si
          
          ⁡
          
            (
            
              
                T
                ^
              
              u
            
            )
          
        
      
      +
      
        
          
            r
            ^
          
          zi
        
        ·
        
          
            
              z
              .
            
            si
          
          ⁡
          
            (
            
              
                T
                ^
              
              u
            
            )
          
        
      
    
    
      
        r
        ^
      
      i
    
  




is radial speed or range change rate of the ith satellite based on the initial values.

The equation ΔVi=fdi·L−Vi({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.
Based on the above equations, the partial derivatives in equation (3) can be given by:




  
    
      
        
          
        
        ⁢
        
          
            
              ∂
              
                
                  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
        )
      
    
  




For five satellites, we can calculate the following matrixes:




  
    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
              
            
          
        
      
      ]
    
  




These matrixes can be used in the following equation to solve for the receiver position and system time:

V=H·Δx  (9)

The above calculation can be repeated over several iterations until the result converges. In this case, the calculated results x, y, z, Tu 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.
For the case that there are more than five satellites, we use can use the least square equation Δx=(HTH)−1HTV.
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.
The above computations may be performed in firmware on the CPU 111 and/or processor 110, or dedicated hardware.
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.
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.

## Claims

1. A method of determining position and time in a navigation receiver, comprising:
receiving and tracking a signal from a satellite at the receiver;
making a Doppler measurement for the satellite signal; and
computing the position and time based on the Doppler measurement,
wherein the computation of the position and time is performed over several iterations,
and wherein each iteration of the computation comprises solving a set of equations with coefficients derived from partial derivatives of a Doppler equation.

2. The method of claim 1, further comprising using the computed position and time to estimate a pseudo-range for the satellite.

3. The method of claim 1, wherein the receiver is unable to obtain accurate time information for the satellite signal before the time is computed.

4. The method of claim 1, further comprising receiving and tracking signals from at least five satellites.

5. The method of claim 4, further comprising:
making a Doppler measurement for each of the at least five satellites signals; and
computing the position and time based on the Doppler measurements for the at least five satellites.

6. The method of claim 1, wherein the Doppler measurement is derived from a local oscillator frequency of the receiver.

7. The method of claim 1, wherein the position and time computation uses five independent variables.

8. The method of claim 1, wherein initial values of the position and time are used in the first iteration of the computation.

9. The method of claim 8, wherein the initial value of the position comprises a previous position stored in memory on the receiver.

10. The method of claim 8, wherein the initial value of the time is based on a real time clock (RTC) or a time-of-ephemeris of ephemeris.

11. The method of claim 10, wherein the RTC comprises an external clock.

12. The method of claim 10, wherein the ephemeris is retrieved from memory on the receiver or from an external source.

13. The method of claim 8, further comprising:
computing a geometric center of acquired satellites;
using a projection point of the geometric center on the surface of the earth as the initial value of the position.

14. The method of claim 1, wherein the receiver comprises a GPS receiver, a GLONASS receiver, a Galileo receiver, or other GNSS satellite based navigation receiver.

15. A navigation receiver, comprising:
a radio frequency front-end for receiving satellite signals;
a baseband section for processing the received satellite signals; and
a processor coupled to the baseband section, wherein the processor is configured to make
a Doppler measurement for at least one of the satellite signals, and compute a position and time based on the Doppler measurement,
wherein the processor performs the computation of the position and time over several iterations,
and wherein each iteration of the computation comprises solving a set of equations with coefficients derived from partial derivatives of a Doppler equation.

16. The receiver of claim 15, wherein the processor is configured to use the computed position and time to estimate a pseudo-range for the satellite.

17. The receiver of claim 15, wherein the receiver is unable to obtain accurate time information for the satellite signal before the time is computed.

18. The receiver of claim 15, wherein the processor is configured to receive and track signals from at least five satellites.

19. The receiver of claim 18, wherein the processor is configured to make a Doppler measurement for each of the at least five satellites signals, and compute the position and time based on the Doppler measurements for the at least five satellites.

20. The receiver of claim 19, wherein the processors derives the Doppler measurement from a local oscillator frequency of the receiver.

21. The receiver of claim 15, wherein the position and time computation uses five independent variables.

22. The receiver of claim 15, wherein the processor uses initial values of the position and time in the first iteration of the computation.

23. The receiver of claim 22, wherein the initial value of the position comprises a previous position stored in memory on the receiver.

24. The receiver of claim 22, wherein the initial value of the time is based on a real time clock (RTC) or a time-of-ephemeris of ephemeris.

25. The receiver of claim 24, wherein the RTC comprises an external clock.

26. The receiver of claim 24, wherein the ephemeris is retrieved from memory on the receiver or from an external source.

27. The receiver of claim 22, wherein the processor computes a geometric center of acquired satellites, and uses a projection point of the geometric center on the surface of the earth as the initial value of the position.

28. The receiver of claim 15, wherein the receiver comprises a GPS receiver, a GLONASS receiver, a Galileo receiver, or other GNSS satellite based navigation receiver.