Abstract:
The location of a receiver is determined by receiving respective ranging signals from each of a plurality of transmitters at known locations. The ranging signals are cross-correlated with respective model signals to provide respective cross-correlation functions. For cross correlation functions that are determined to include multipath noise, the multipath noise is estimated and removed. Respective delays of the cross-correlation functions are estimated and the location of the receiver is inferred from the delays.

Description:
FIELD AND BACKGROUND OF THE INVENTION 
     The present invention relates to positioning systems such as Global Navigation Satellite Systems (GNSS) and, more particularly, to a method of mitigating multipath noise in such systems. 
     A GNSS system is a space-based global navigation system in which the satellites of a constellation of satellites in orbit around the Earth transmit signals that are used by terrestrial receivers for purposes such as navigation. The existing GNSS systems include the GPS system operated by the United States of America and the GLONASS system operated by Russia. The present invention is described herein in terms of the GPS system. It will be clear to those skilled in the art how to use the principles of the present invention in the context of other GNSS systems such as the forthcoming European Galileo system or the forthcoming Chinese Compass navigation system. 
     The GPS system includes between 24 and 32 satellites in medium Earth orbit. The GPS ranging code that is available for public use is the C/A code which is a PseudoRandom binary Code (PRN) of 1,023 bits. Each satellite continuously transmits, as its ranging signal, sequences of its own unique PRN code that is orthogonal to all the other PRN codes. Modulated on top of each satellite&#39;s C/A code is a navigation message that includes an ephemeris (plural: ephemerides) that describes the satellite&#39;s orbit. The ephemerides are updated every two hours. 
     A GPS receiver generates its own copies of the C/A codes, nominally synchronized with the satellite transmissions. When the receiver receives the C/A codes of the currently visible satellites (typically 12-16 satellites in open terrain), the receiver cross-correlates its copies of the C/A code with the received C/A codes to determine the one-way travel times from the satellites to the receiver. Knowing the ephemerides, the receiver computes the locations of the satellites at the times of the transmissions to obtain ranges to the satellites. If the receiver&#39;s clock were perfectly synchronized with the satellites then signals from three satellites would suffice to triangulate the location (horizontal coordinates x and y and elevation z) of the receiver. Because clocks that could be synchronized that well with the atomic clocks used by the satellites are far too expensive for routine use, signals from four or more satellites are used to determine x, y, z and the time offset dt of the receiver&#39;s clock from the GPS clocks. If only the horizontal coordinates are needed for navigation then signals from three satellites suffice. 
     Dense urban environments present some of the hardest challenges for GNSS receivers. The characteristics of these environments, also known as “urban canyons”, generate two negative effects on GNSS receiver performance:
         Line of sight blockage between a transmitting satellite and the GNSS receiver due to high buildings decreasing the number of visible satellites.   Erroneous measurements (multipath errors) caused by satellite transmissions that are reflected from adjacent buildings and received by the GNSS receiver.       

     It would be highly advantageous to have a GNSS receiver that is more resistant to multipath noise than presently known GNSS receivers. 
     SUMMARY OF THE INVENTION 
     The method of the present invention is based on an algorithm for mitigating multipath effects in a GNSS receiver. A receiver using this algorithm benefits from improved measurement accuracy, leading to better positioning and navigation performance in multipath-prone environments. 
     The algorithm is an optimal echo delay estimation method using a combination of a high-resolution multipath mitigation technique with a peak estimation technique. It has been found that using the multipath mitigation technique for non-multipath scenarios yields results that are less good than a peak estimation technique for non-multipath scenarios. Therefore, according to the present invention, the multipath mitigation technique is activated based on a quality threshold mechanism that has been calibrated to ensure optimal results in both multipath and non-multipath scenarios. 
     The quality estimation mechanism is used to determine the probability that a multipath effect is present in the current sample being processed. Based on this probability, a system of the present invention uses either a multipath mitigation technique or a peak estimation technique for non-multipath scenarios. 
     The multipath mitigation technique approach allows multipath discrimination with a resolution that is better than the resolution of the measurements performed by the GNSS receiver. The method enables high-resolution discrimination by matching multipath effects using templates with a resolution that is higher than the original measurement resolution. 
     Therefore, according to the present invention there is provided a method of determining a location of a receiver, including the steps of: (a) using the receiver, receiving, from each of a plurality of transmitters at known locations, a respective ranging signal; and (b) for each ranging signal: (i) cross-correlating the each ranging signal with a respective model signal thereby obtaining a respective cross-correlation function, (ii) determining whether the respective cross-correlation function includes multipath noise, and (iii) if the respective cross-correlation function includes multipath noise: (A) estimating the multipath noise, and (B) removing the multipath noise from the respective cross-correlation function. 
     Furthermore, according to the present invention there is provided a device for determining a location at which a plurality of ranging signals are received from a plurality of transmitters at known respective locations, including: (a) a receiver for receiving the ranging signals; (b) at least one cross-correlator for cross-correlating each ranging signal with a respective model signal, thereby obtaining, for each ranging signal, a corresponding cross-correlation function; and (c) a multipath mitigation unit for, for each cross-correlation function: (i) determining whether the each cross-correlation function includes multipath noise, and (ii) if the each cross-correlation function includes multipath noise: (A) estimating the multipath noise, and (B) removing the multipath noise from the corresponding cross-correlation function. 
     Furthermore, according to the present invention there is provided A computer-readable storage medium having embodied thereon computer-readable code for mitigating multipath noise in a cross-correlation function obtained by cross-correlating a ranging signal with a model signal, the computer-readable code including: (a) program code for determining whether the cross-correlation function includes multipath noise; and (b) program code for, if the cross-correlation function includes multipath noise: (i) estimating the multipath noise; and (ii) removing the multipath noise from the cross-correlation function. 
     According to the basic method of the present invention, for determining the location of a receiver, the receiver is used to receive, from each of a plurality of transmitters at known locations, a respective ranging signal. The locations are known but not necessarily fixed as functions of time. Indeed, in the primary intended application of the method, the transmitters are satellites of a GNSS system, but note that the method is clearly applicable to positioning systems other than GNSS systems. Each ranging signal is cross-correlated with a respective model signal, thereby obtaining a respective cross-correlation function. For each cross-correlation function, it is determined whether the cross-correlation function includes multipath noise. If the cross-correlation function does in fact include multipath noise, the multipath noise is estimated and removed. 
     Preferably, the model signals are respective ranging codes of the various transmitters. For example, if the transmitters are GPS satellites, the model signals are the respective CIA codes of the satellites. 
     Preferably, to determine whether a ranging signal includes multipath noise, a template function is generated from the respective cross-correlation function of the ranging signal. A quality measure is computed for the cross-correlation function by comparing the template function to the cross-correlation function. Then the quality measure is compared to a predetermined threshold. Preferably, the template function has a predetermined shape, most preferably a triangular shape. The template function is generated by fitting the predetermined shape to the cross-correlation function. 
     Preferably, the multipath noise is estimated using least squares estimation. 
     Preferably, estimated multipath noise is removed from a cross-correlation function that has been found to include multipath noise by subtracting the multipath noise from the cross-correlation function. 
     Preferably, for each ranging signal, a respective delay of the ranging signal&#39;s cross-correlation function is estimated, most preferably by fitting a predetermined functional form such as a parabolic function to the cross-correlation function. “Fitting” a shape or a functional form to a cross-correlation function means that the shape or functional form is parametrized by parameters with adjustable values, and the values that give the best match of the shape or functional form to the cross-correlation function are found. 
     Most preferably, with the delays having been estimated, the location of the receiver is inferred from the delays. 
     A basic device for implementing the method of the present invention includes a receiver for receiving the ranging signals, one or more cross correlators and a multipath mitigation unit. The cross-correlator(s) is/are for cross-correlating each ranging signal with the respective model signal. The multipath mitigation unit is for determining whether the resulting cross-correlation functions include multipath noise and for estimating and removing the multipath noise from the cross-correlation functions that have been determined to include multipath noise. 
     Preferably, the device also includes a delay estimation unit for estimating respective delays of cross-correlation functions after multipath noise has been removed from the cross-correlation functions that require such removal. Most preferably, the device also includes a navigation unit for inferring the location of the device from the delays. 
     The scope of the invention also includes a computer-readable storage medium having embodied thereon computer-readable code for implementing the method of the invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various embodiments are herein described, by way of example only, with reference to the accompanying drawings, wherein: 
         FIG. 1  is a high-level block diagram of a GPS receiver of the present invention; 
         FIG. 2  is a block diagram of the computational flow of the algorithm of the present invention; 
         FIG. 3  shows a typical cross-correlation function in the absence of multipath noise; 
         FIG. 4  shows a typical cross-correlation function in the presence of multipath noise; 
         FIG. 5  is a partial high-level block diagram of a combined software implementation of the multipath mitigation and delay estimation units of  FIG. 1 . 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The principles and operation of multipath noise mitigation according to the present invention may be better understood with reference to the drawings and the accompanying description. 
     Referring now to the drawings,  FIG. 1  is a high-level block diagram of a GPS receiver  10  of the present invention. GPS receiver  10  includes a RF front end  12 , a set of correlators  14 , a multipath mitigation unit  16 , a delay estimation unit  18  and a navigation unit  20 . RF front end  12  receives and digitizes GPS ranging signals from the GPS satellite constellation. Each correlator  14  cross-correlates the ranging signals with a model signal that in the GPS case is the respective PRN code of one of the GPS satellites. In the absence of multipath noise, the delay of the peak of each cross-correlation would be a measure of the one-way travel time from the corresponding GPS satellite to UPS receiver  10 . Multipath noise in the received ranging signals tends to shift the cross-correlation delays to later times. Therefore, the cross-correlations produced by correlators  14  are input to multipath mitigation unit  16  that estimates and removes multipath noise from the cross-correlations, as described below, before the cross-correlations are input to delay estimation unit  18  that estimates the delays of the cross-correlations. The estimated delays are input to navigation unit  20  that performs the actual navigation calculations to determine the location of GPS receiver  10 . 
     The GPS system, like most GNSS systems, is a CDMA system, so that the signal received by RF front end  12  is a superposition of ranging signals from all the visible GPS satellites in the relevant frequency band (the L1 frequency band, centered at 1575.42 MHz, in the case of the publicly available C/A signals). The exceptional GNSS is GLONASS that is a FDMA system. 
     In principle, one correlator  14  suffices. The digitized ranging signals could be stored in a memory and cross-correlated sequentially with each relevant model signal. In practice, several correlators  14 , as shown in  FIG. 1 , are used in order to save time by cross-correlating with the relevant model signals in parallel. 
     Correlators  14 , multipath mitigation unit  16 , delay estimation unit  18  and navigation unit  20  may be implemented in hardware, in firmware, in software or as any combination of the three. Usually, correlators  14  are implemented in hardware for speed. 
     The multipath mitigation algorithm of the present invention is a combination of quality estimation using template generation and a least squares estimator for a two-ray signal model. The block diagram of  FIG. 2  shows the computational flow of the algorithm. 
     The algorithm uses the template quality estimation to decide whether or not to activate the multipath mitigation technique. If the quality is less then a predefined threshold (smaller values means less probability for multipath scenario) then peak estimation is performed over the signal cross-correlation itself. Otherwise Least Squares Estimation is performed over the signal cross-correlation. The echo cross-correlation is estimated and then is subtracted from the signal cross-correlation. The remaining estimated line-of-sight (LOS) correlation is inserted into the peak estimation block. 
     This approach yields optimal results for both line-of-sight and multipath scenarios. 
     Template quality estimation is a mechanism used to distinguish between LOS signals and LOS+multipath echoes. The template quality estimation mechanism generates a signal template, and then evaluates the difference between the signal template and the original correlation. The method requires normalization of the correlation pattern before evaluating the quality. The normalization is estimating the correlation peak (using lines intersection for example) and dividing the correlator output by this value. 
       FIG. 3  shows a typical cross-correlation function in the absence of multipath noise. The function is sampled discretely at equally spaced sampling times that are numbered by an index k along the horizontal axis of  FIG. 3 . The units of the function, on the vertical axis of  FIG. 3 , are arbitrary. The sampling interval T s  in this case is one-quarter of the duration T c  of a single CIA code chip. As can be seen in  FIG. 3 , in the absence of multipath noise, the cross-correlation function is triangular in the vicinity of the function&#39;s peak. Therefore, the preferred template is triangular. If the cross-correlation function is normalized to a peak value of 1, the slopes of the two sides of the triangle are m=±T s /T c . 
       FIG. 4  shows a typical cross-correlation function in the presence of multipath noise, along with the construction that is used to find the apex (t p , x p ) of an isosceles triangle that, after being normalized to a peak value of 1, is used as the template: straight lines are drawn through the two uppermost pairs of points of the cross-correlation function, as shown. The template is an isosceles triangle whose apex is at (t p , 1) and whose sides have the slopes m=T s /T c . This template is sampled at the sampling times of the cross-correlation function to obtain ideal normalized triangular correlation pattern values x ideal (k) at sampling indices k. The values of the cross-correlation function also are normalized by dividing by x p  to obtain normalized samples x sample (k) at the sampling indices k. The quality measure is
 
ζ=Σ| x   samples ( k )− x   ideal ( k )|
 
where the summation is over the 2T c /T s  samples, centered around the peak of the interpolated triangle, that are the samples that correspond to the main lobe of the cross-correlation function. The lower the value of ζ, the more the normalized cross-correlation main lobe resembles the ideal triangle. The threshold value of ζ that distinguishes cross-correlation functions whose delays are shifted by multipath noise from cross-correlation functions whose delays are not significantly shifted by multipath noise is system-specific and can be obtained by those skilled in the art from simulations of multipath and non-multipath scenarios.
 
     The least squares estimation is based on maximum likelihood estimation theory, assuming white Gaussian noise. The signal is modeled by:
 
 A   1 e jφ     1     R ( t−τ   1 )+ A   2 e jφ     2     R ( t−τ   2 )
 
where R is the auto-correlation function for the pseudo random code. The solution is obtained by solving a set of linear equations derived from the partial derivatives of the log maximum likelihood function according to each of the six parameters to be estimated θ=[A 1 ,φ 1 , τ 1 ,A 2 ,φ 2 , τ 2 ] T , under the constraint that τ 1 &lt;τ 2 . If it can be assumed that A1&gt;A2, that condition provides an additional constraint to improve the quality of the solution.
 
     After obtaining the estimated parameters the echo is subtracted from the received signal and peak estimation is performed. 
     The signal model for a single ray is given by A 1 e jφ     1   R(n−τ 1 ). The function can be at higher resolution then the actual correlator output to allow better discrimination between the echo and the LOS signal. 
     For a given code delay τ 1  we define a real function T 1 (n)=R(n−τ 1 ) and try to minimize: 
                     J   ⁡     (   u   )       =       ⁢       ∑     n   =   0       N   -   1       ⁢              x   ⁡     (   n   )       -       uT   1     ⁡     (   n   )              2                   =       ⁢       ∑     n   =   0       N   -   1       ⁢       (       x   ⁡     (   n   )       -       uT   1     ⁡     (   n   )         )     ⁢       (       x   ⁡     (   n   )       -       uT   1     ⁡     (   n   )         )     *                     =       ⁢         ∑     n   =   0       N   -   1       ⁢            x   ⁡     (   n   )            2       -       x   ⁡     (   n   )       ⁢     u   *     ⁢     T   1     ⁢     (   n   )       -                     ⁢           uT   1     ⁡     (   n   )       ⁢       x   *     ⁡     (   n   )         -       uu   *     ⁢       T   1   2     ⁡     (   n   )                       
where u=A 1 e jφ     1   .
 
     The complex derivative is defined as: 
                 ∂   J       ∂   v       =       1   2     ⁢     (         ∂   J       ∂     v   R         -     j   ⁢       ∂   J       ∂     v   1             )             
and its properties are:
 
                 ∂   v       ∂   v       =   1                   ∂     v   *         ∂   v       =   0                   ∂     vv   *         ∂   v       =           v   *     ⁢       ∂   v       ∂   v         +     v   ⁢       ∂     v   *         ∂   v           =         v   *     +   0     =     v   *               
Now let J be minimized by differentiating and equating to zero:
 
     
       
         
           
             
               
                 ∂ 
                 J 
               
               
                 ∂ 
                 u 
               
             
             = 
             
               
                 
                   ∑ 
                   
                     n 
                     = 
                     0 
                   
                   
                     N 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                   
                     
                       ∂ 
                       J 
                     
                     
                       ∂ 
                       u 
                     
                   
                   ⁢ 
                   
                     ( 
                     
                       
                         
                            
                           
                             x 
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                            
                         
                         2 
                       
                       - 
                       
                         
                           x 
                           ⁡ 
                           
                             ( 
                             n 
                             ) 
                           
                         
                         ⁢ 
                         
                           u 
                           * 
                         
                         ⁢ 
                         
                           
                             T 
                             1 
                           
                           ⁡ 
                           
                             ( 
                             n 
                             ) 
                           
                         
                       
                       - 
                       
                         
                           
                             uT 
                             1 
                           
                           ⁡ 
                           
                             ( 
                             n 
                             ) 
                           
                         
                         ⁢ 
                         
                           
                             x 
                             * 
                           
                           ⁡ 
                           
                             ( 
                             n 
                             ) 
                           
                         
                       
                       - 
                       
                         
                           uu 
                           * 
                         
                         ⁢ 
                         
                           
                             T 
                             1 
                             2 
                           
                           ⁡ 
                           
                             ( 
                             n 
                             ) 
                           
                         
                       
                     
                     ) 
                   
                 
               
               = 
               0 
             
           
         
       
       
         
           
             
               
                 
                   ∑ 
                   
                     n 
                     = 
                     0 
                   
                   
                     N 
                     - 
                     1 
                   
                 
                 ⁢ 
                 0 
               
               - 
               0 
               - 
               
                 
                   
                     T 
                     1 
                   
                   ⁡ 
                   
                     ( 
                     n 
                     ) 
                   
                 
                 ⁢ 
                 
                   
                     x 
                     * 
                   
                   ⁡ 
                   
                     ( 
                     n 
                     ) 
                   
                 
               
               - 
               
                 
                   u 
                   * 
                 
                 ⁢ 
                 
                   
                     T 
                     1 
                     2 
                   
                   ⁡ 
                   
                     ( 
                     n 
                     ) 
                   
                 
               
             
             = 
             0 
           
         
       
       
         
           
             
               
                 u 
                 * 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     n 
                     = 
                     0 
                   
                   
                     N 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                   
                     T 
                     1 
                     2 
                   
                   ⁡ 
                   
                     ( 
                     n 
                     ) 
                   
                 
               
             
             = 
             
               
                 
                   
                     ∑ 
                     
                       n 
                       = 
                       0 
                     
                     
                       N 
                       - 
                       1 
                     
                   
                   ⁢ 
                   
                     
                       
                         T 
                         1 
                       
                       ⁡ 
                       
                         ( 
                         n 
                         ) 
                       
                     
                     ⁢ 
                     
                       
                         x 
                         * 
                       
                       ⁡ 
                       
                         ( 
                         n 
                         ) 
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 -&gt; 
                 u 
               
               = 
               
                 
                   
                     ∑ 
                     
                       n 
                       = 
                       0 
                     
                     
                       N 
                       - 
                       1 
                     
                   
                   ⁢ 
                   
                     
                       
                         T 
                         1 
                       
                       ⁡ 
                       
                         ( 
                         n 
                         ) 
                       
                     
                     ⁢ 
                     
                       x 
                       ⁡ 
                       
                         ( 
                         n 
                         ) 
                       
                     
                   
                 
                 
                   
                     ∑ 
                     
                       n 
                       = 
                       0 
                     
                     
                       N 
                       - 
                       1 
                     
                   
                   ⁢ 
                   
                     
                       T 
                       1 
                       2 
                     
                     ⁡ 
                     
                       ( 
                       n 
                       ) 
                     
                   
                 
               
             
           
         
       
     
     We now extend the above derivation to two rays. The model is given by A 1 e jφ     1   R(n−τ 1 )+A 2 e jφ     2   R(n−τ 2 ). The minimization is performed over: 
               J   ⁡     (     u   ,   v     )       =         ∑     n   =   0       N   -   1       ⁢              x   ⁡     (   n   )       -       uT   1     ⁡     (   n   )       -       vT   2     ⁡     (   n   )              2       =         ∑     n   =   0       N   -   1       ⁢       (       x   ⁡     (   n   )       -       uT   1     ⁡     (   n   )       -       vT   2     ⁡     (   n   )         )     ⁢       (       x   ⁡     (   n   )       -       uT   1     ⁡     (   n   )       -       vT   2     ⁡     (   n   )         )     *         =       ∑     n   =   0       N   -   1       ⁢       (       x   ⁡     (   n   )       -       uT   1     ⁡     (   n   )       -       vT   2     ⁡     (   n   )         )     ⁢     (           x   *     ⁡     (   n   )       -       u   *     ⁢       T   1     ⁡     (   n   )         -       v   *     ⁢       T   2     ⁡     (   n   )           =           ∑     n   =   0       N   -   1       ⁢            x   ⁡     (   n   )            2       -       x   ⁡     (   n   )       ⁢     u   *     ⁢       T   1     ⁡     (   n   )         -       x   ⁡     (   n   )       ⁢     v   *     ⁢       T   2     ⁡     (   n   )         -         uT   1     ⁡     (   n   )       ⁢       x   *     ⁡     (   n   )         +         uT   1   2     ⁡     (   n   )       ⁢     u   *       +         uT   1     ⁡     (   n   )       ⁢     v   *     ⁢       T   2     ⁡     (   n   )         -         vT   2     ⁡     (   n   )       ⁢       x   *     ⁡     (   n   )         +         vT   2     ⁡     (   n   )       ⁢     u   *     ⁢       T   1     ⁡     (   n   )         +         vT   2   2     ⁡     (   n   )       ⁢     v   *         =           ∑     n   =   0       N   -   1       ⁢            x   ⁡     (   n   )            2       -       u   *     ⁢       γ   x     ⁡     (     τ   1     )         -       v   *     ⁢       γ   x     ⁡     (     τ   2     )         -     u   ⁢           ⁢       γ   x   *     ⁡     (     τ   1     )         +            u        2     ⁢     γ   ⁡     (   0   )         +       uv   *     ⁢       γ   ⁡     (       τ   1     -     τ   2       )       --     ⁢       vγ   x   *     ⁡     (     τ   2     )         +       u   *     ⁢   v   ⁢           ⁢     γ   ⁡     (       τ   1     -     τ   2       )         +            v        2     ⁢     γ   ⁡     (   0   )           =         ∑     n   =   0       N   -   1       ⁢            x   ⁡     (   n   )            2       -     (         u   *     ⁢       γ   x     ⁡     (     τ   1     )         +     u   ⁢           ⁢       γ   x   *     ⁡     (     τ   1     )           )     -       (         v   *     ⁢       γ   x     ⁡     (     τ   2     )         +     v   ⁢           ⁢       γ   x   *     ⁡     (     τ   2     )           )     ⁢     (            u        2     +          v        2       )     ⁢     γ   ⁡     (   0   )         +       γ   ⁡     (       τ   1     -     τ   2       )       ⁢     (       uv   *     +       u   *     ⁢   v       )                               
where T 2 (n)=R(n−τ 2 ). We use the identity
 
 uv*+u*v= 2( Re{u}Re{v}+Im{u}Im{v}≡f ( u,v ))
 
which implies
 
               J   ⁡     (     u   ,   v     )       =         ∑     n   =   0       N   -   1       ⁢           ⁢            x   ⁡     (   n   )            2       -     f   ⁡     (     u   ,       γ   x     ⁡     (     τ   1     )         )       -     f   ⁡     (     v   ,       γ   x     ⁡     (     τ   2     )         )       +       (            u        2     +          v        2       )     ⁢     γ   ⁡     (   0   )         +       γ   ⁡     (       τ   1     -     τ   2       )       ⁢     f   ⁡     (     u   ,   v     )                 
We now differentiate and equate to zero:
 
                 ∂     J   ⁡     (     u   ,   v     )           ∂   u       =           ∑     n   =   0       N   -   1       ⁢       -       T   1     ⁡     (   n   )         ⁢       x   *     ⁡     (   n   )           +         T   1   2     ⁡     (   n   )       ⁢     u   *       +         T   1     ⁡     (   n   )       ⁢     v   *     ⁢       T   2     ⁡     (   n   )           =   0                     ∂     J   ⁡     (     u   ,   v     )           ∂   v       =           ∑     n   =   0       N   -   1       ⁢       -       T   2     ⁡     (   n   )         ⁢       x   *     ⁡     (   n   )           +         T   2   2     ⁡     (   n   )       ⁢     v   *       +         T   1     ⁡     (   n   )       ⁢     u   *     ⁢       T   2     ⁡     (   n   )           =   0           
This can be rewritten in matrix form:
 
 A·[u*v*]   T   =b  
 
where
 
     
       
         
           
             
               A 
               = 
               
                 [ 
                 
                   
                     
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             T 
                             1 
                             2 
                           
                           ⁡ 
                           
                             ( 
                             n 
                             ) 
                           
                         
                       
                     
                     
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             
                               T 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               T 
                               2 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             
                               T 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               T 
                               2 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                         
                       
                     
                     
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             T 
                             2 
                             2 
                           
                           ⁡ 
                           
                             ( 
                             n 
                             ) 
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             , 
             
               b 
               = 
               
                 [ 
                 
                   
                     
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             
                               T 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               x 
                               * 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             
                               T 
                               2 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                           ⁢ 
                           
                             
                               x 
                               * 
                             
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                         
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
     A also can be written as: 
               A   =     [           γ   ⁡     (   0   )             γ   ⁡     (       τ   1     -     τ   2       )                 γ   ⁡     (       τ   1     -     τ   2       )             γ   ⁡     (   0   )             ]       ,     b   =       [             γ   x     ⁡     (     τ   1     )                   γ   x     ⁡     (     τ   2     )             ]     *                     γ   ⁡     (   k   )       =       ∑     n   =   0       N   -   1       ⁢       R   ⁡     (   n   )       ⁢     R   ⁡     (     n   -   k     )                           γ   x     ⁡     (   k   )       =       ∑     n   =   0       N   -   1       ⁢       R   ⁡     (   n   )       ⁢     x   ⁡     (     n   -   k     )                 
In γ x (k), x(n−k) is the discretely sampled cross-correlation that needs to have its multipath noise removed. The matrix equation A·[u*v*] T =b is solved for u and v for many values of τ 1  and τ 2  in the environment-dependent time interval in which the system designer expects to encounter the received signal and the multipath noise, and the solution that minimizes J is chosen. The parameters of the two-ray model then are: A 1 =|u|, φ 1 =phase of u, A 2 =|v|, φ 2 =phase of v. Note that the matrix A depends only on the autocorrelation function R and so can be calculated in advance. The cross-correlation with the echo subtracted is x(n)−A 2 e jφ     2   R(n−τ 2 ).
 
     It should be noted that firmware and software embodiments of multipath mitigation unit  16  can, in principle, achieve better separation of LOS signals from multipath echoes because the fineness of the sampling of the functions T 1 (n) and T 2 (n) is not limited, in the firmware and software embodiments, to the sampling frequency of hardware correlators  14 . 
     Peak estimation is performed in delay estimation unit  18  using a parabolic estimation method. It is performed over the modified correlation pattern after the subtraction, if needed, of ECHO from it. The parabolic peak estimation is based on the assumption that the correlation pattern highest values behave as a parabolic function. This is a valid assumption since the correlation is limited in bandwidth. A parabolic function is fitted to the 2T c /T s  samples centered on the maximum of the correlation pattern by one of several algorithms that are known in the art. The delay corresponding to the maximum of the parabola is the estimated delay used in the subsequent navigation calculation in navigation unit  20 . 
     As noted above, components  14 ,  16 ,  18  and  20  of  FIG. 1  may be implemented in hardware, in firmware, in software or as any combination of the three.  FIG. 5  is a high-level partial high-level block diagram of a combined software implementation  30  of multipath mitigation unit  16  and delay estimation unit  18 . Only the components of combined unit  30  that are relevant to the present invention are shown in  FIG. 5 . Combined unit  30  includes an input port  32 , a processor  34 , a random access memory (RAM)  36 , a read-only memory (ROM)  38  and an output port  40 , all communicating with each other via a common bus  42 . Cross-correlation functions from correlators  14  are received at input port  32 . In ROM  38  is stored executable code  44  for determining whether received cross-correlation functions include multipath noise as described above, executable code  46  for estimating and removing the multipath noise as described above, and executable code  48  for estimating the delays of the cross-correlation functions after multipath noise has been removed from the cross-correlation functions as needed, also as described above. Under the control of an operating system (not shown), processor  34  copies the executable code from ROM  38  to RAM  36 , executes the code in RAM  36 , and exports the resulting estimated delays to navigation unit  20  via output port  40 . 
     ROM  38  is an example of a computer-readable storage medium having embodied thereon computer-readable code for implementing the present invention. Other examples of such computer-readable storage media include compact disks and flash disks. 
     While the invention has been described with respect to a limited number of embodiments, it will be appreciated that many variations, modifications and other applications of the invention may be made. Therefore, the claimed invention as recited in the claims that follow is not limited to the embodiments described herein.