Abstract:
Described is a generalized approach for integer parameter estimation, especially in the context of Global Navigation Satellite Systems (GNSS). The problem solved is the case where a definitively correct integer solution cannot be identified for all ambiguity parameters in a reliable way. The proposed solution is to apply a linear transformation to the ambiguities (multiply with a matrix) such that the images of the first and the second candidate (or more) are identical. That way, from the first and second (and possibly more) candidates of the integer least-squares solution, a subset of ambiguity combinations is derived that can be fixed. Thus, it is no longer necessary to choose between the solutions as they coincide for the new ambiguities. The advantage of this approach is maximizing all information still available when finally deriving additional parameters such as position, clock error, atmospheric errors and/or time correlated noise. This technique is applicable to real-time and post-processing applications, as well as to pure GNSS applications, GNSS integrated with other sensors (e.g. INS) and other applications that have to resolve multiple integer ambiguities. This may also apply to optical distance-measurement. GNSS applications include kinematic and static positioning with single base stations as well as with multiple base stations or reference station networks. They also comprise the integer parameter estimation methods used within the reference station network computations.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims benefit of U.S. Provisional Application 60/001,034, filed 30 Oct. 2007, of Ulrich Vollath for Generalized Partial Fixing, the content of which is incorporated herein by this reference. 
         [0002]    The subject matter of this application is related to U.S. Pat. No. 7,312,747, issued 25 Dec. 2007 of Ulrich Vollath and Kenneth Doucet for Multiple GNSS and FDMA High Precision Carrier-Phase Based Positioning, the content of which is incorporated herein by this reference. 
         [0003]    The subject matter of this application is related to U.S. Pat. No. 7,432,853, issued 7 Oct. 2008 of Ulrich Vollath for Ambiguity Estimation of GNSS Signals for Three or more Carriers, the content of which is incorporated herein by this reference. 
     
    
     FIELD OF THE INVENTION 
       [0004]    The present invention relates to processing of GNSS signal observations, and particularly to estimating integer ambiguities from carrier phase observations of GNSS signals. 
       BACKGROUND OF THE INVENTION 
     Overview 
       [0005]    The book S. Verhagen,  The GNSS integer ambiguities: estimation and validation , Delft University of Technology, 2004, provides a good overview of the steps of integer ambiguity estimation. A general model of GNSS observations is: 
         [0000]        y=Aa+Bb+e   (1) 
         [0006]    Here, yεR m  denotes the observation vector, aεZ n  is the vector of unknown integer parameters (ambiguities), bεR p  is the vector of additional model parameters as position, clock errors, atmospheric errors, time correlated noise, etc. A and B are the m×n respective m×p design matrices (Jacobians) of the observations with respect to the integer respective additional parameters. eεR m  is the observation noise vector with the a priori variance-covariance matrix Q=E[ee T ] where the matrix dimension is QεR m×m . 
         [0007]    Float Solution 
         [0008]    Normally using a least-squares adjustment, a Kalman filter or any other technique known to someone skilled in the art, the unknowns a and b are estimated simultaneously without applying the integer constraint on a. 
         [0009]    The result is the so-called float solution of estimates and their variance-covariance matrix: 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             a 
                             ^ 
                           
                         
                       
                       
                         
                           
                             b 
                             ^ 
                           
                         
                       
                     
                     ) 
                   
                    
                   
                       
                   
                    
                   and 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           
                             Q 
                             
                               a 
                               ^ 
                             
                           
                         
                         
                           
                             Q 
                             
                               
                                 a 
                                 ^ 
                               
                                
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                       
                       
                         
                           
                             Q 
                             
                               
                                 a 
                                 ^ 
                               
                                
                               
                                 b 
                                 ^ 
                               
                             
                             T 
                           
                         
                         
                           
                             Q 
                             
                               b 
                               ^ 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the matrix dimensions are Q â εR n×n , Q {circumflex over (b)} εR p×p , Q â{circumflex over (b)} εR n×p . 
         [0010]    A least squares solution would be: 
         [0000]    
       
         
           
             
               
                 
                   
                       
                   
                    
                   
                     
                       ( 
                       
                         
                           
                             
                               Q 
                               
                                 a 
                                 ^ 
                               
                             
                           
                           
                             
                               Q 
                               
                                 
                                   a 
                                   ^ 
                                 
                                  
                                 
                                   b 
                                   ^ 
                                 
                               
                             
                           
                         
                         
                           
                             
                               Q 
                               
                                 
                                   a 
                                   ^ 
                                 
                                  
                                 
                                   b 
                                   ^ 
                                 
                               
                               T 
                             
                           
                           
                             
                               Q 
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                       
                       ) 
                     
                     = 
                     
                       
                         ( 
                         
                           
                             
                               ( 
                               
                                 A 
                                  
                                 
                                     
                                 
                                  
                                 B 
                               
                               ) 
                             
                             T 
                           
                            
                           
                             
                               Q 
                               
                                 - 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 A 
                                  
                                 
                                     
                                 
                                  
                                 B 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             a 
                             ^ 
                           
                         
                       
                       
                         
                           
                             b 
                             ^ 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                       
                   
                    
                   
                     
                       ( 
                       
                         
                           
                             
                               Q 
                               
                                 a 
                                 ^ 
                               
                             
                           
                           
                             
                               Q 
                               
                                 
                                   a 
                                   ^ 
                                 
                                  
                                 
                                   b 
                                   ^ 
                                 
                               
                             
                           
                         
                         
                           
                             
                               Q 
                               
                                 
                                   a 
                                   ^ 
                                 
                                  
                                 
                                   b 
                                   ^ 
                                 
                               
                               T 
                             
                           
                           
                             
                               Q 
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                       
                       ) 
                     
                      
                     
                       
                         ( 
                         
                           A 
                            
                           
                               
                           
                            
                           B 
                         
                         ) 
                       
                       T 
                     
                      
                     
                       Q 
                       
                         - 
                         1 
                       
                     
                      
                     y 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0011]    This technique is given as an example of float parameter estimation and not limiting the application of the methods presented. 
         [0012]    Integer Least-Squares (ILS) 
         [0013]    The variance-covariance matrix Q â  defines a norm ∥·∥ Q     â   on R n : 
         [0000]      ∥ x∥   Q     â     =x   T   Q   â   −1   x   (5) 
         [0014]    Integer Least-Squares (ILS) is the strict mathematical integer solution to the problem of minimizing the Q â  norm of the difference of the float solution to integer solutions: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                       ⋓ 
                     
                     1 
                   
                   = 
                   
                     
                       
                         
                           arg 
                            
                           
                               
                           
                            
                           min 
                         
                         
                           z 
                           ∈ 
                           
                             Z 
                             n 
                           
                         
                       
                        
                       
                         
                           ( 
                           
                             z 
                             - 
                             
                               a 
                               ^ 
                             
                           
                           ) 
                         
                         T 
                       
                        
                       
                         
                           Q 
                           
                             a 
                             ^ 
                           
                           
                             - 
                             1 
                           
                         
                          
                         
                           ( 
                           
                             z 
                             - 
                             
                               a 
                               ^ 
                             
                           
                           ) 
                         
                       
                     
                     = 
                     
                       
                         
                           arg 
                            
                           
                               
                           
                            
                           min 
                         
                         
                           z 
                           ∈ 
                           
                             Z 
                             n 
                           
                         
                       
                        
                       
                         
                            
                           
                             z 
                             - 
                             
                               a 
                               ^ 
                             
                           
                            
                         
                         
                           Q 
                           
                             a 
                             ^ 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0015]    Well-known algorithms, for example LAMBDA [see P. DeJonge and C. Tiberius,  The lambda method for integer ambiguity estimation: implementation aspects,  1998], compute at least the “best candidate” {hacek over (a)} 1 . In addition, usually additional next candidate {hacek over (a)} 2  (“second candidate”), and possible more candidates {hacek over (a)} 3 , . . . , {hacek over (a)} k  in order of their Q â  norm are determined, in a similar way: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                       ⋓ 
                     
                     2 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         z 
                         ∈ 
                         
                           
                             Z 
                             n 
                           
                            
                           \ 
                            
                           
                             { 
                             
                               a 
                               ⋓ 
                             
                             } 
                           
                         
                       
                     
                      
                     
                       
                          
                         
                           z 
                           - 
                           
                             a 
                             ^ 
                           
                         
                          
                       
                       
                         Q 
                         
                           a 
                           ^ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       a 
                       ⋓ 
                     
                     i 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         z 
                         ∈ 
                         
                           
                             Z 
                             n 
                           
                            
                           \ 
                            
                           
                             { 
                             
                               
                                 
                                   a 
                                   ⋓ 
                                 
                                 1 
                               
                               , 
                               
                                 … 
                                  
                                 
                                     
                                 
                                  
                                 
                                   
                                     a 
                                     ⋓ 
                                   
                                   
                                     i 
                                     - 
                                     1 
                                   
                                 
                               
                             
                             } 
                           
                         
                       
                     
                      
                     
                       
                          
                         
                           z 
                           - 
                           
                             a 
                             ^ 
                           
                         
                          
                       
                       
                         Q 
                         
                           a 
                           ^ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0016]    The values of the norm ∥z−â∥ Q     â    are normally provided, too, for application of the validations tests described in the following section. 
         [0017]    For a given best candidate {hacek over (a)} 1  for the integer solution, the non-integer parameters of the model can be easily adjusted to the matching least-squares solution: 
         [0000]        {hacek over (b)}={circumflex over (b)}−Q   â{circumflex over (b)}   T   Q   â   −1 ( â−{hacek over (a)}   1 )  (10) 
         [0000]      and 
         [0000]        Q   {hacek over (b)}   =Q   {circumflex over (b)}   −Q   â{circumflex over (b)}   T   Q   â   −1   Q   â{circumflex over (b)}   (10) 
         [0018]    Validation 
         [0019]    The purpose of validation is to ensure that the best solution defined by the ILS is also the correct solution with a high probability. This is defined via the success rate, i.e. the probability that the best solution is equal to the correct solution a. 
         [0000]        P ( {hacek over (a)}   1   =a )  (11) 
         [0000]    If that probability exceeds an externally given minimum required probability threshold, the integer solution is accepted and in the following used to derive the non-integer parameters, in many applications the position is the primary non-integer parameter of interest. 
         [0020]    A common validation technique involves inspecting the best and second candidate solution of the ILS. In one well-known method, the ratio r of the norm of the second best candidate to the norm of the best candidate (the ratio of the χ 2  values) is used a discriminator. 
         [0000]    
       
         
           
             
               
                 
                   r 
                   = 
                   
                     
                       
                          
                         
                           
                             
                               a 
                               ⋓ 
                             
                             2 
                           
                           - 
                           
                             a 
                             ^ 
                           
                         
                          
                       
                       
                         Q 
                         
                           a 
                           ^ 
                         
                       
                     
                     
                       
                          
                         
                           
                             
                               a 
                               ⋓ 
                             
                             1 
                           
                           - 
                           
                             a 
                             ^ 
                           
                         
                          
                       
                       
                         Q 
                         
                           a 
                           ^ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0021]    The best solution {hacek over (a)} 1  is considered to be the correct integer solution if the ratio r exceeds a critical value r crit : 
         [0000]      r≧r crit   (13) 
         [0022]    Another acceptance criterion (see [J. Wang et al, A discrimination test procedure for ambiguity resolution on-the-fly,  Journal of Geodesy,  72(11), 1998]) uses the difference d of best and second candidate norms: 
         [0000]        d=∥{hacek over (a)}   2   −â∥   Q     â     −∥{hacek over (a)}   1   −â∥   Q     â     (14) 
         [0000]    Again, the best solution {hacek over (a)} 1  is considered to be the correct integer solution if the difference d exceeds a critical value d crit : 
         [0000]      d≧d crit   (15) 
         [0023]    The determination of the critical values, i.e. the value that must be exceeded to accept the solution as correct can be implemented in many different ways. In common implementations they include: a Fixed Ratio Test or a Fisher test for ratio validation [S. Verhagen,  The GNSS integer ambiguities: estimation and validation , Delft University of Technology, 2004], a Student-t-test or a standard normal distribution test for the difference of norms [J. Wang et al, A discrimination test procedure for ambiguity resolution on-the-fly,  Journal of Geodesy,  72(11), 1998]. In some embodiments, the critical values can be determined by Monte-Carlo-Simulations [S. Verhagen,  The GNSS integer ambiguities: estimation and validation , Delft University of Technology, 2004] or from precomputed tables using properties of the variance-covariance matrix [P. Teunissen et al., GNSS phase ambiguity validation: A review,  Proceedings Space, Aeronautical and Navigational Electronics Symposium SANE 2007, 107(2):1-6, 2007] 
         [0024]    Methods taking into account more than two candidates for validation do exist. One example is the Optimal Integer Aperture Estimation (OIAE) [S. Verhagen,  The GNSS integer ambiguities: estimation and validation , Delft University of Technology, 2004]. Instead of the norm of single candidates sets, 
         [0000]    
       
         
           
              
             
               - 
               
                 Norm 
                 2 
               
             
           
         
       
     
         [0000]    of multiple (theoretically all) candidate sets is summed up. 
         [0025]    The common property of the computation of critical values is that they typically depend only the variance-covariance-matrix, the number of ambiguities and possibly the over-determination of the float solution but do not depend on the candidates of the ILS. As a consequence, the critical values can be computed before the ILS is executed. Good accounts on possible tests based on first, second (and possibly more) candidates can be found in [S. Verhagen,  The GNSS integer ambiguities: estimation and validation , Delft University of Technology, 2004]. 
       SUMMARY 
       [0026]    This document describes a generalized approach for integer parameter estimation, especially in the context of Global Navigation Satellite Systems (GNSS). The problem solved is the case where a definitively correct integer solution cannot be identified for all ambiguity parameters in a reliable way. 
         [0027]    The proposed solution is to apply a linear transformation to the ambiguities (multiply with a matrix) such that the images of the first and the second candidate (or more) are identical. That way, from the first and second (and possibly more) candidates of the integer least-squares solution, a subset of ambiguity combinations is derived that can be fixed. Thus, it is no longer necessary to choose between the solutions as they coincide for the new ambiguities. An advantage of this approach is maximizing all information still available when finally deriving additional parameters such as position, clock error, atmospheric errors and/or time correlated noise. 
         [0028]    This technique is applicable to real-time and post-processing applications, as well as to pure GNSS applications, GNSS integrated with other sensors (e.g. INS) and other applications that have to resolve multiple integer ambiguities. This may also apply to optical distance-measurement. GNSS applications include kinematic and static positioning with single base stations as well as with multiple base stations respective reference station networks. They also comprise the integer parameter estimation methods used within the reference station network computations. 
         [0029]    Embodiments of the invention provide methods, apparatus, program instructions, and computer-readable media embodying program instruction, for estimating integer ambiguities from carrier phase observations of signals, comprising: determining from the carrier phase observations a ranked plurality of candidate sets of estimated integer ambiguities, applying a criterion to select one of the ranked plurality of candidate sets as a selected candidate set, forming a matrix G such that the image formed when matrix G is linearly combined with a selected candidate set is equal to the image formed when matrix G is linearly combined with a second candidate set, and applying the matrix G to the selected candidate set to determine a modified candidate set of estimated integer ambiguities. 
         [0030]    The signals can comprise GNSS signals, such as GNSS signals from at least four satellites. The signals can comprise signals from other sensors, such as Inertial Navigation System (INS) sensors. The signals can comprise optical signals used in optical distance measurement. The signals can comprise GNSS signals observed at multiple reference stations of a reference station network. The processing can be performed in real time (or near real time). The processing can be performed after data collection, as a post-processing operation. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0031]    These and other aspects and features of the present invention will be more readily understood from the embodiments described below with reference to the drawings, in which: 
           [0032]      FIG. 1  is a flow chart of post-processing with a sequential float solution; 
           [0033]      FIG. 2  is a flow chart of post-processing with a batch least squares approach; 
           [0034]      FIG. 3  is a flow chart of real-time processing; 
           [0035]      FIG. 4  is a flow chart of conventional fixing; 
           [0036]      FIG. 5  is a flow chart of generalized partial fixing with candidate validation in accordance with some embodiments of the invention; 
           [0037]      FIG. 6  is a flow chart of generalized partial fixing with a candidate validation variant in accordance with some embodiments of the invention; 
           [0038]      FIG. 7  is a flow chart of generalized partial fixing generating all needed candidates for validation in accordance with some embodiments of the invention; 
           [0039]      FIG. 8  is a flow chart of generalized partial fixing initially generating all needed candidates in accordance with some embodiments of the invention; 
           [0040]      FIG. 9  is a flow chart of integer least squares collection iteration in accordance with some embodiments of the invention; 
           [0041]      FIG. 10  is a flow chart of an integer least squares collection iteration variant in accordance with some embodiments of the invention; 
           [0042]      FIG. 11  is a flow chart of an integer least squares collection iteration variant in accordance with some embodiments of the invention; 
           [0043]      FIG. 12  is a flow chart of generalized partial fixing with search validation in accordance with some embodiments of the invention; and 
           [0044]      FIG. 13  shows an example GNSS receiver used in accordance with some embodiments. 
       
    
    
     DETAILED DESCRIPTION 
     Partial Fixing 
       [0045]    Partial fixing techniques are described in U.S. Pat. No. 7,312,747, issued 25 Dec. 2007 to Ulrich Vollath and Kenneth Doucet for Multiple GNSS and FDMA High Precision Carrier-Phase Based Positioning. 
         [0046]    In the current GNSS ambiguity resolution algorithms, there are some very different approaches to partial fixing. The purpose is always to determine a subset of ambiguities that can be successfully validated as a correct solution with a high probability.
       If the L 1  and L 2  ambiguities for first and second candidate differ, but their difference is the same, it is possible to fix the wide lane ambiguity.   If all ambiguities are the same except for one satellite (or a few satellites), all the other satellite ambiguities can be fixed.   In network processing, if first and second ambiguities are the same except for one station, that station can be removed from the ambiguity resolution. This is done repeatedly in the network processor.   A more complex approach tries to remove some satellites from an on-the-fly (OTF) solution. After some consistency tests on the multitude of solutions generated, a partial set of satellites might be fixed. This is typically applied in a real-time positioning system to partially fix only the GPS satellite ambiguities if for example the GLONASS satellite ambiguities cannot be fixed yet.   The most popular application is maybe fixing double difference ambiguities, because the undifferenced respective single-differenced ambiguities cannot be fixed due to the common errors included in the estimates. The partial ambiguities defined as the double differences (satellite to satellite differences of single differences) don&#39;t contain these common errors and can be fixed.       
 
         [0052]    Embodiments of the present invention will be presented that comprises and is more general than these methods. 
         [0053]    Formalization 
         [0054]    The prior-art concept is based on fixing only a subset of n f  of the n ambiguities while leaving the rest “floating”. Formally, this is equivalent to handling the unfixed ambiguities as a part of the {circumflex over (b)} vector in equation (2). In detail, the floating solution looks like the following with û being the unfixed part of the ambiguities and {circumflex over (f)} being the fixed part: 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             f 
                             ^ 
                           
                         
                       
                       
                         
                           
                             u 
                             ^ 
                           
                         
                       
                       
                         
                           
                             b 
                             ^ 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             Q 
                             
                               f 
                               ^ 
                             
                           
                         
                         
                           
                             Q 
                             
                               
                                 f 
                                 ^ 
                               
                                
                               u 
                             
                           
                         
                         
                           
                             Q 
                             
                               
                                 f 
                                 ^ 
                               
                                
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                       
                       
                         
                           
                             Q 
                             
                               
                                 f 
                                 ^ 
                               
                                
                               u 
                             
                             T 
                           
                         
                         
                           
                             Q 
                             
                               u 
                               ^ 
                             
                           
                         
                         
                           
                             Q 
                             
                               
                                 u 
                                 ^ 
                               
                                
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                       
                       
                         
                           
                             Q 
                             
                               
                                 f 
                                 ^ 
                               
                                
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                         
                           
                             Q 
                             
                               
                                 b 
                                 ^ 
                               
                                
                               
                                 u 
                                 ^ 
                               
                             
                           
                         
                         
                           
                             Q 
                             
                               b 
                               ^ 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0055]    Integer least squares is applied to the float solution vector {circumflex over (f)} together with the variance-covariance matrix Q {circumflex over (f)}  to get the fixed solution: 
         [0000]    
       
         
           
             
               
                 
                   
                     f 
                     ⋓ 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         z 
                         ∈ 
                         
                           Z 
                           ″ 
                         
                       
                     
                      
                     
                       
                         ( 
                         
                           z 
                           - 
                           
                             f 
                             ^ 
                           
                         
                         ) 
                       
                       T 
                     
                      
                     
                       
                         Q 
                         
                           f 
                           ^ 
                         
                         
                           - 
                           1 
                         
                       
                       ( 
                       
                         z 
                         - 
                         
                           f 
                           ^ 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0056]    After validation and fixing the ambiguities to {hacek over (f)}, the positions are computed similar to equations (9) and (10). Only the covariance parts concerning the fixed ambiguities is determining the position results: 
         [0000]        {hacek over (b)}={circumflex over (b)}−Q   {circumflex over (f)}{circumflex over (b)}   T   Q   {circumflex over (f)}   −1 ( {circumflex over (f)}−{hacek over (f)} )  (18) 
         [0000]      and 
         [0000]        Q   {hacek over (b)}   =Q   {circumflex over (b)}   −Q   {circumflex over (f)}{circumflex over (b)}   T   Q   f   −1   Q   {circumflex over (f)}{circumflex over (b)}   (19) 
         [0057]    Matrix Formulation 
         [0058]    An alternative formulation of this final step is more general while yielding the same results. Here, a (n f ×n) matrix maps the ambiguity vector to the part that is going to be fixed. 
         [0000]    
       
         
           
             
               
                 
                   
                     f 
                     ^ 
                   
                   = 
                   
                     
                       G 
                        
                       
                           
                       
                        
                       
                         a 
                         ^ 
                       
                     
                     = 
                     
                       G 
                        
                       
                         ( 
                         
                           
                             
                               
                                 f 
                                 ^ 
                               
                             
                           
                           
                             
                               
                                 u 
                                 ^ 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
             
               
                 
                   G 
                   = 
                   
                     
                       ( 
                       
                         I 
                         , 
                         0 
                       
                       ) 
                     
                     = 
                     
                       ( 
                       
                         
                           
                             1 
                           
                           
                             ⋯ 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             ⋯ 
                           
                           
                             0 
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                           
                             ⋮ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             0 
                           
                           
                             ⋯ 
                           
                           
                             1 
                           
                           
                             0 
                           
                           
                             ⋯ 
                           
                           
                             0 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
         [0059]    Now, by applying the rules of error propagation, the constraint solution is: 
         [0000]        {hacek over (b)}={circumflex over (b)}−Q   â{circumflex over (b)}   T   G   T ( GQ   â   G   T ) −1   G ( â−{hacek over (a)}   1 )  (22) 
         [0000]      and 
         [0000]        Q   {hacek over (b)}   =Q   {circumflex over (b)}   −Q   â{circumflex over (b)}   T   G   T ( GQ   â   G   T ) −1   GQ   â{circumflex over (b)}   (23) 
         [0060]    With 
         [0000]    
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         a 
                         ^ 
                       
                        
                       
                         b 
                         ^ 
                       
                     
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             Q 
                             
                               
                                 f 
                                 ^ 
                               
                                
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                       
                       
                         
                           
                             Q 
                             
                               
                                 u 
                                 ^ 
                               
                                
                               
                                 b 
                                 ^ 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
             
               
                 
                   
                     Q 
                     
                       a 
                       ^ 
                     
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             Q 
                             
                               f 
                               ^ 
                             
                           
                         
                         
                           
                             Q 
                             
                               
                                 f 
                                 ^ 
                               
                                
                               u 
                             
                           
                         
                       
                       
                         
                           
                             Q 
                             
                               
                                 f 
                                 ^ 
                               
                                
                               u 
                             
                             T 
                           
                         
                         
                           
                             Q 
                             
                               u 
                               ^ 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
           
         
       
     
         [0000]    the results of (18) and (19) are finally yielded. 
         [0061]    Widelane Fixing 
         [0062]    Another common application of partial fixing is to resolve the ambiguities only for a carrier phase combination known as the widelane. If N 1  and N 2  are the ambiguities for the frequencies L 1  and L 2  respectively, then the widelane ambiguity is defined as 
         [0000]        N   W   =N   L1   −N   L2   (26) 
         [0063]    The advantage is, that the associated carrier phase combination—the widelane phase—has a wavelength of about 86 cm for GPS. Compared to the some 19 cm on L I and the some 24 cm on L 2  the ambiguity can be resolved more easily in the presence of estimation errors. The way to prepare the float solution vector can again be expressed by a matrix G. If the float solution is setup to contain alternating N L1,i  and N L2,i  estimates for all ns satellites i 
         [0000]    
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         
                           N 
                           
                             
                               L 
                                
                               
                                   
                               
                                
                               1 
                             
                             , 
                             1 
                           
                         
                       
                     
                     
                       
                         
                           N 
                           
                             
                               L 
                                
                               
                                   
                               
                                
                               2 
                             
                             , 
                             1 
                           
                         
                       
                     
                     
                       
                         ⋮ 
                       
                     
                     
                       
                         
                           N 
                           
                             
                               L 
                                
                               
                                   
                               
                                
                               1 
                             
                             , 
                             ns 
                           
                         
                       
                     
                     
                       
                         
                           N 
                           
                             
                               L 
                                
                               
                                   
                               
                                
                               2 
                             
                             , 
                             ns 
                           
                         
                       
                     
                   
                   ) 
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
         [0000]    the following matrix derives the widelane estimates for this common method: 
         [0000]    
       
         
           
             
               
                 
                   
                     G 
                     W 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           0 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
           
         
       
     
         [0064]    Generalized Partial Fixing 
         [0065]    The idea of Generalized Partial Fixing (GPF) is new: to use more general matrices for the mapping of the original ambiguities to the ambiguities subset or ambiguity combinations that will be fixed. Especially, a properly defined matrix G can yield to a linear combination of the original ambiguities for which the images of the original first (two or more) candidates are equal. For the case of two candidates, this implies that the linear combination must have a size of one less than the original ambiguity vector as the null space of the mapping performed by the linear combination is one-dimensional. 
         [0066]    The null space of a matrix respectively the null space of the associated linear transformation is defined as the set of all vectors that map to the zero vector: 
         [0000]      nullspace( G )={ {right arrow over (x)}εR   n   :G{right arrow over (x)}= {right arrow over (0)}}  (28b) 
         [0067]    The task is to find a non-zero (n−1)×n matrix G of rank n−1 with (two candidate case): 
         [0000]      G{hacek over (a)} 1 =G{hacek over (a)} 2   (29) 
         [0068]    This is equivalent to: 
         [0000]      GΔ{hacek over (a)} 2 ={right arrow over (0)}  (30) 
         [0000]    with Δ{hacek over (a)} 2 ={hacek over (a)} 1 −{hacek over (a)} 2 . In other words, Δ{hacek over (a)} 2  is in the null space of G. 
         [0069]    For some formulations of the following validation steps, G must only contain integer entries in order to have the resulting transformed ambiguities also as integer numbers. The construction in the next section will show that this is easily achieved. 
         [0070]    The matrix G is called the GPF operator, mapping the input ambiguity space of dimension n to the output ambiguity space of dimension n−1. 
         [0071]    Construction of G 
         [0072]    A GPF operator matrix can be computed in an easy and effective way following the instructions below. Let the candidate difference vector be: 
         [0000]    
       
         
           
             
               
                 
                   
                     Δ 
                      
                     
                         
                     
                      
                     
                       
                         a 
                         ⋓ 
                       
                       2 
                     
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               δ 
                               1 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               δ 
                               n 
                             
                           
                         
                       
                       ) 
                     
                     = 
                     
                       ( 
                       
                         
                           
                             
                               
                                 
                                   a 
                                   ⋓ 
                                 
                                 
                                   1 
                                   1 
                                 
                               
                               - 
                               
                                 
                                   a 
                                   ⋓ 
                                 
                                 
                                   2 
                                   1 
                                 
                               
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               
                                 
                                   a 
                                   ⋓ 
                                 
                                 
                                   1 
                                   n 
                                 
                               
                               - 
                               
                                 
                                   a 
                                   ⋓ 
                                 
                                 
                                   2 
                                   n 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
           
         
       
     
         [0073]    For the illustrating examples below it is assumed that all δ i  are nonzero. Also, it is assumed that at least two ambiguities differ. The detailed descriptions following do not have these restrictions. 
         [0074]    The following matrix has all required properties: 
         [0000]    
       
         
           
             
               
                 
                   
                     G 
                     
                       Δ 
                        
                       
                           
                       
                        
                       
                         
                           a 
                           ⋓ 
                         
                         2 
                       
                     
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             δ 
                             2 
                           
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           
                             δ 
                             3 
                           
                         
                         
                           
                             - 
                             
                               δ 
                               2 
                             
                           
                         
                         
                           0 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                         
                           
                             δ 
                             n 
                           
                         
                         
                           
                             - 
                             
                               δ 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   32 
                   ) 
                 
               
             
           
         
       
     
         [0075]    For non-zero δ i  the matrix has obviously the full rank n−1. It can also be easily seen that it fulfills the equation GΔ{hacek over (a)} 2 =0. 
         [0076]    Instructions for Construction of G 
         [0077]    In detail, the matrix G Δ{hacek over (a)}     2    is constructed using the following instructions:
       1. Compute the n rows array Δ{hacek over (a)} 2  of component-wise differences between first and second candidate.   2. Create a matrix G with n−1 rows and n columns. Set all entries of G to zero. Set the current row index r of G to 1.   3. Go through all n elements δ i  of Δ{hacek over (a)} 2 .
           (a) If the current δ i  is not equal to zero then
               i. If there was already a previous non-zero entry δ p  in row p, then set the entry at column p and current row r of G to δ i  and set the entry at column i and current row r of G to −δ p  and increase the current row index r of G by 1.   ii. Set the previous non-zero entry δ P  to the current δ i . Set the index p of the previous non-zero entry to i.   
               (b) If the current δ i  is equal to zero, then set the entry at column i and current row r of G to 1 and increase the current row index r of G by 1.   
           4. Return G as the constructed GPF operator matrix.       
 
         [0086]    Alternative G Matrix 
         [0087]    Another possible G-Matrix is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       G 
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             a 
                             ⋓ 
                           
                           2 
                         
                       
                     
                     ′ 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             δ 
                             2 
                           
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             δ 
                             3 
                           
                         
                         
                           0 
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                         
                           0 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             δ 
                             
                               n 
                               - 
                               1 
                             
                           
                         
                         
                           … 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   33 
                   ) 
                 
               
             
           
         
       
     
         [0088]    Alternative Instructions 
         [0089]    This matrix version. G Δ{hacek over (a)}     2   ′ is constructed by:
       1. Compute the n rows array Δ{hacek over (a)} 2  of component-wise differences between first and second candidate.   2. Create a matrix G with n−1 rows and n columns. Set all entries of G to zero. Set the current row index r of G to 1.   3. Go through all n elements δ i  of Δ{hacek over (a)} 2 .
           (a) If the current δ i  is not equal to zero then
               i. If there was already a first non-zero entry δ p  in row p, then set the entry at column p and current row r of G to δ i  and set entry at column i and current row r of G to −δ p  and increase the current row index r of G by 1.   ii. If this is the first non-zero entry, then set the first non-zero entry δ p  to the current δ i . Set the index p of the first non-zero entry to i.   
               (b) If the current δ i  is equal to zero, then set the entry at column i and current row r of G to 1 and increase the current row index r of G by 1.   
           4. Return G as the constructed GPF operator matrix.       
 
         [0098]    Orthogonal G Matrix 
         [0099]    If the matrix G shall be orthogonal, i.e. its lines shall be linear independent, the following version can be used: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       G 
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           
                             a 
                             ⋓ 
                           
                           2 
                         
                       
                     
                     ″ 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             δ 
                             2 
                           
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             
                               δ 
                               1 
                             
                              
                             
                               δ 
                               3 
                             
                           
                         
                         
                           
                             
                               δ 
                               2 
                             
                              
                             
                               δ 
                               3 
                             
                           
                         
                         
                           
                             
                               - 
                               
                                 δ 
                                 1 
                                 2 
                               
                             
                             - 
                             
                               δ 
                               2 
                               2 
                             
                           
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             
                               δ 
                               1 
                             
                              
                             
                               δ 
                               n 
                             
                           
                         
                         
                           … 
                         
                         
                           
                             
                               δ 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                              
                             
                               δ 
                               n 
                             
                           
                         
                         
                           
                             
                               
                                 - 
                                 
                                   δ 
                                   1 
                                   2 
                                 
                               
                                
                               
                                   
                               
                                
                               … 
                             
                             - 
                             
                               δ 
                               n 
                               2 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   34 
                   ) 
                 
               
             
           
         
       
     
         [0100]    Instructions for Orthogonal G 
         [0101]    For the orthogonal variant, the matrix G Δ{hacek over (a)}   2  is constructed as:
       1. Compute the n rows array Δ{hacek over (a)} 2  of component-wise differences between first and second candidate.   2. Create a list L of all j indices l 1 , . . . , l j  in Δ{hacek over (a)} 2  with non-zero entries.   3. Create a matrix G with n−1 rows and n columns. Set all entries of G to zero. Set the current row index r of G to 1.   4. Go through all n elements δ i  of Δ{hacek over (a)} 2 .
           (a) If the current δ i  is not equal to zero then
               i. If this is the second non-zero entry besides the first one δ p  in row p, then:
                   A. set the entry at column p and current row r of G to δ i      B. set entry at column i and current row r of G to −δ p      C. increase the current row index r of G by 1.   
                   ii. If there were already at least two previous non-zero entries δ p  in row p, then:
                   A. set the columns j with j set to all values from 1 to i−1 of the current row r of G to δ 1 δ j      B. set the column i of the current row r of G to −δ p − . . . −δ i      C. increase the current row index r of G by 1.   
                   iii. Set the previous non-zero entry δ p  to the current δ i . Set the index p of the previous non-zero entry to i.   
               (b) If the current δ i  is equal to zero, then set the entry at column i and current row r of G to 1 and increase the current row index r of G by 1.   
           5. Return G as the constructed GPF operator matrix.       
 
         [0118]    Choice and Final Preparation of G 
         [0119]    In the following, any of those three realizations of the G matrix can be used. 
         [0120]    For compact results, i.e., to get small integer entries, the b may also be divided by their greatest common divisor for each row of G values, because with GΔ{hacek over (a)} 2 ={right arrow over (0)} also 
         [0000]    
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         
                           α 
                           1 
                         
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         ⋱ 
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         
                           α 
                           
                             n 
                             - 
                             1 
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 G 
                  
                 
                     
                 
                  
                 Δ 
                  
                 
                   
                     a 
                     ⋓ 
                   
                   2 
                 
               
               = 
               
                 
                   
                     ( 
                     
                       
                         
                           
                             α 
                             1 
                           
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             α 
                             
                               n 
                               - 
                               1 
                             
                           
                         
                       
                     
                     ) 
                   
                    
                   
                     0 
                     → 
                   
                 
                 = 
                 
                   0 
                   → 
                 
               
             
             , 
           
         
       
     
         [0000]    i.e. the null space of G is identical to the null space of 
         [0000]    
       
         
           
             
               ( 
               
                 
                   
                     
                       α 
                       1 
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     ⋱ 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     
                       α 
                       
                         n 
                         - 
                         1 
                       
                     
                   
                 
               
               ) 
             
              
             G 
           
         
       
     
         [0000]    if all the α i ≠0;1≦i≦n−1. 
         [0121]    Examples of GPF Matrix Computations 
         [0122]    The following paragraphs give examples of computing the GPF matrices for illustration of the given algorithms. The examples are given for a four ambiguity case. Different entries are chosen to be zero to show the different computations. 
         [0123]    Standard GPF Matrix 
         [0124]    All Entries Non-Zero 
         [0000]    Step 1.: Compute the 4 rows array Δ{hacek over (a)} 2  of component-wise differences between first and second candidate. 
         [0000]    
       
         
           
             
               Δ 
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       1 
                     
                   
                 
                 
                   
                     
                       δ 
                       2 
                     
                   
                 
                 
                   
                     
                       δ 
                       3 
                     
                   
                 
                 
                   
                     
                       δ 
                       4 
                     
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    with all entries non-zero.
 
Step 2.: Create a matrix G with 3 rows and 4 columns. Set all entries of G to zero.
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    Set the current row index r of G to 1. 
         [0125]    r=1 
         [0000]    Step 3.: Go through all n elements of Δ{hacek over (a)} 2 . 
         [0126]    Step 3. for δ i =δ 1 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. does not apply, no previous δ p      Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 1      Set the index p of the previous non-zero entry to i.   p=1   
               
           Step 3. (b) does not apply: δ i ≠0       
 
         [0134]    Step 3. for δ i =δ 2 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists.
               Set the entry at column 1 and current row 1 of G to δ 2  and set the entry at column 2 and current row 1 of G to −δ 1 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                   
                 
                 r=2 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 2      Set the index p of the previous non-zero entry to i.   p=2   
             
               
             
             Step 3. (b) does not apply: δ i ≠0 
           
         
       
     
         [0145]    Step 3. for δ i =δ 3 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 2 and current row 2 of G to δ 3  and set the entry at column 3 and current row 2 of G to −δ 2 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=3 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 3      Set the index p of the previous non-zero entry to i.   p=3   
             
               
             
             Step 3. (b) does not apply: δ i ≠0 
           
         
       
     
         [0156]    Step 3. for δ i ≠0:
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 3 and current row 3 of G to δ 4  and set the entry at column 4 and current row 3 of G to −δ 3 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     
                       δ 
                       4 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         3 
                       
                     
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=4 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δp=δ 4      Set the index p of the previous non-zero entry to i.   p=4   
             
               
             
             Step 3. (b) does not apply: δ i ≠0 
           
         
       
     
       Step 4.: Final Result 
       [0167]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     
                       δ 
                       4 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         3 
                       
                     
                   
                 
               
               ) 
             
           
         
       
     
       Result Check: 
       [0168]    
       
         
           
             
               G 
                
               
                   
               
                
               Δ 
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       
                         
                           δ 
                           2 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             1 
                           
                         
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         
                           δ 
                           3 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             2 
                           
                         
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         
                           δ 
                           4 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             3 
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           δ 
                           1 
                         
                       
                     
                     
                       
                         
                           δ 
                           2 
                         
                       
                     
                     
                       
                         
                           δ 
                           3 
                         
                       
                     
                     
                       
                         
                           δ 
                           4 
                         
                       
                     
                   
                   ) 
                 
               
               = 
               
                 ( 
                 
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0169]    First Entry Zero 
         [0000]    Step 1.: Compute the 4 rows array Δ{hacek over (a)} 2  of component-wise differences between first and second candidate. 
         [0000]    
       
         
           
             
               Δ 
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               ( 
               
                 
                   
                     0 
                   
                 
                 
                   
                     
                       δ 
                       2 
                     
                   
                 
                 
                   
                     
                       δ 
                       3 
                     
                   
                 
                 
                   
                     
                       δ 
                       4 
                     
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    Step 2.: Create a matrix G with 3 rows and 4 columns. Set all entries of G to zero. 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    Set the current row index r of G to 1. 
         [0170]    r=1 
         [0000]    Step 3.: Go through all n elements of Δ{hacek over (a)} 2 . 
         [0171]    Step 3. for δ i =δ 1 :
       Step 3. (a) does not apply: δ i =0   Step 3. (b) applies: δ i =0
           Set the entry at column 1 and current row 1 of G to 1.   
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 Increase the current row index r of G by 1. 
                 r=2 
               
             
           
         
       
     
         [0177]    Step 3. for δ i =δ 2 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. does not apply, no previous δ p      Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 2      Set the index p of the previous non-zero entry to i.   p=2   
               
           Step 3. (b) does not apply: δ i ≠0       
 
         [0185]    Step 3. for δ i ≠0:
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 2 and current row 2 of G to δ 3  and set the entry at column 3 and current row 2 of G to −δ 2 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=3 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 3      Set the index p of the previous non-zero entry to i.   p=3   
             
               
             
             Step 3. (b) does not apply: δ i ≠0 
           
         
       
     
         [0196]    Step 3. for δ i =δ 4 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 3 and current row 3 of G to δ 4  and set the entry at column 4 and current row 3 of G to −δ 3 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     
                       δ 
                       4 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         3 
                       
                     
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=4 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 4      Set the index p of the previous non-zero entry to i.   p=4   
             
               
             
             Step 3. (b) does not apply: δ i ≠0
 
Step 4.: Final result
 
           
         
       
     
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     
                       δ 
                       4 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         3 
                       
                     
                   
                 
               
               ) 
             
           
         
       
     
       Result Check: 
       [0207]    
       
         
           
             
               G 
                
               
                   
               
                
               Δ 
                
               
                   
               
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       
                         1 
                       
                       
                         0 
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         
                           δ 
                           3 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             2 
                           
                         
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         
                           δ 
                           4 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             3 
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   ( 
                   
                     
                       
                         0 
                       
                     
                     
                       
                         
                           δ 
                           2 
                         
                       
                     
                     
                       
                         
                           δ 
                           3 
                         
                       
                     
                     
                       
                         
                           δ 
                           4 
                         
                       
                     
                   
                   ) 
                 
               
               = 
               
                 ( 
                 
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0208]    Second Entry Zero 
         [0000]    Step 1.: Compute the 4 rows array Δ{hacek over (a)} 2  of component-wise differences between first and second candidate. 
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       1 
                     
                   
                 
                 
                   
                     0 
                   
                 
                 
                   
                     
                       δ 
                       3 
                     
                   
                 
                 
                   
                     
                       δ 
                       4 
                     
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    Step 2.: Create a matrix G with 3 rows and 4 columns. Set all entries of G to zero. 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
     
         [0209]    Set the current row index r of G to 1. 
         [0210]    r=1 
         [0000]    Step 3.: Go through all n elements of Δ{hacek over (a)} 2 . 
         [0211]    Step 3. for δ i =δ 1 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. does not apply, no previous δ p      Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ i      Set the index p of the previous non-zero entry to i.   p=1   
               
           Step 3. (b) does not apply: δ i ≠0       
 
         [0219]    Step 3. for δ i =δ 2 :
       Step 3. (a) does not apply: δ i =0   Step 3. (b) applies: δ i =0
           Set the entry at column 2 and current row 1 of G to 1.   
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 Increase the current row index r of G by 1. 
                 r=2 
               
             
           
         
       
     
         [0225]    Step 3. for δ i =δ 3 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 1 and current row 2 of G to δ 3  and set the entry at column 3 and current row 2 of G to −δ 1 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     
                       δ 
                       3 
                     
                   
                   
                     0 
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=3 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 3      Set the index p of the previous non-zero entry to i.   p=3   
             
               
             
             Step 3. (b) does not apply: δ i ≠0 
           
         
       
     
         [0236]    Step 3. for δ i =δ 4 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 3 and current row 3 of G to δ 4  and set the entry at column 4 and current row 3 of G to −δ 3 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     
                       δ 
                       3 
                     
                   
                   
                     0 
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     
                       δ 
                       4 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         3 
                       
                     
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=4 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 4      Set the index p of the previous non-zero entry to i.   p=4   
             
               
             
             Step 3. (b) does not apply: δ i ≠0
 
Step 4.: Final result
 
           
         
       
     
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     
                       δ 
                       3 
                     
                   
                   
                     0 
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     
                       δ 
                       4 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         3 
                       
                     
                   
                 
               
               ) 
             
           
         
       
     
       Result Check: 
       [0247]    
       
         
           
             
               G 
                
               
                   
               
                
               Δ 
                
               
                   
               
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       
                         0 
                       
                       
                         1 
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                     
                       
                         
                           δ 
                           3 
                         
                       
                       
                         0 
                       
                       
                         
                           - 
                           
                             δ 
                             1 
                           
                         
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         
                           δ 
                           4 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             3 
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           δ 
                           1 
                         
                       
                     
                     
                       
                         0 
                       
                     
                     
                       
                         
                           δ 
                           3 
                         
                       
                     
                     
                       
                         
                           δ 
                           4 
                         
                       
                     
                   
                   ) 
                 
               
               = 
               
                 ( 
                 
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0248]    Last Entry Zero 
         [0000]    Step 1: Compute the 4 rows array Δ{hacek over (a)} 2  of component-wise differences between first and second candidate. 
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       1 
                     
                   
                 
                 
                   
                     
                       δ 
                       2 
                     
                   
                 
                 
                   
                     
                       δ 
                       3 
                     
                   
                 
                 
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    Step 2.: Create a matrix G with 3 rows and 4 columns. Set all entries of G to zero. 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    Set the current row index r of G to 1. 
         [0249]    r=1 
         [0000]    Step 3.: Go through all n elements of Δ{hacek over (a)} 2 . 
         [0250]    Step 3. for δ i =δ 1 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. does not apply, no previous δ p      Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i .
               δ p =δ 1      Set the index p of the previous non-zero entry to i.   p=1   
               
           Step 3. (b) does not apply: δ i ≠0       
 
         [0258]    Step 3. for δ i =δ 2 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 1 and current row 1 of G to δ 2  and set the entry at column 2 and current row 1 of G to −δ 1 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=2 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ p  to the current δ i.  
               δ p =δ 2      Set the index p of the previous non-zero entry to i.   p=2   
             
               
             
             Step 3. (b) does not apply: δ i ≠0 
           
         
       
     
         [0269]    Step 3. for δ i =δ 3 :
       Step 3. (a) applies: δ i ≠0
           Step 3.(a) i. applies, previous δ p  exists
               Set the entry at column 2 and current row 2 of G to δ 3  and set the entry at column 3 and current row 2 of G to −δ 2 .   
               
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 
                   
                     Increase the current row index r of G by 1. 
                     r=3 
                   
                 
                 Step 3.(a) ii. Set the previous non-zero entry δ 1  to the current δ i .
               δ p =δ 3      Set the index p of the previous non-zero entry to i.   p=3   
             
               
             
             Step 3. (b) does not apply: δ i ≠0 
           
         
       
     
         [0280]    Step 3. for δ i =δ 4 :
       Step 3. (a) does not apply: δ i =0   Step 3. (b) does apply: δ i =0
           Set the entry at column 4 and current row 3 of G to 1.   
               
 
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
               
               ) 
             
           
         
       
       
         
           
             
               
                 Increase the current row index r of G by 1. 
                 r=4
 
Step 4.: Final result
 
               
             
           
         
       
     
         [0000]    
       
         
           
             G 
             = 
             
               ( 
               
                 
                   
                     
                       δ 
                       2 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         1 
                       
                     
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     
                       δ 
                       3 
                     
                   
                   
                     
                       - 
                       
                         δ 
                         2 
                       
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
               
               ) 
             
           
         
       
     
       Result Check: 
       [0286]    
       
         
           
             
               G 
                
               
                   
               
                
               Δ 
                
               
                 
                   a 
                   ⋓ 
                 
                 2 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       
                         
                           δ 
                           2 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             1 
                           
                         
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         
                           δ 
                           3 
                         
                       
                       
                         
                           - 
                           
                             δ 
                             2 
                           
                         
                       
                       
                         0 
                       
                     
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         0 
                       
                       
                         1 
                       
                     
                   
                   ) 
                 
                  
                 
                   ( 
                   
                     
                       
                         
                           δ 
                           1 
                         
                       
                     
                     
                       
                         
                           δ 
                           2 
                         
                       
                     
                     
                       
                         
                           δ 
                           3 
                         
                       
                     
                     
                       
                         0 
                       
                     
                   
                   ) 
                 
               
               = 
               
                 ( 
                 
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0287]    Computation of the Additional Model Parameters 
         [0288]    After fixing using the GPF method, the final task is to determine the updated additional model parameters. For example, if the position is the result of interest in positioning applications, the position has to be updated to the accuracy achieved using a fixed solution. 
         [0289]    The new solution for the non-integer parameters b is computed as: 
         [0000]        {hacek over (b)}   G   ={circumflex over (b)}−Q   â{circumflex over (b)}   T   G   T ( GQ   â   G   T ) −1   G ( â−{hacek over (a)}   1 )  (35) 
         [0000]    This is used to apply the partial fix to the floating solution results in order to compute the associated (partially) fixed position solution. 
         [0290]    For the variance-covariance matrix of the non-integer parameters the updated result is: 
         [0000]        Q   {hacek over (b)}     G     =Q   {circumflex over (b)}   −Q   â{circumflex over (b)}   T   G   T ( GQ   â   G   T ) −1   GQ   â{circumflex over (b)}   (36) 
         [0291]    This specifies the accuracy obtained for the additional model parameters after applying the partial fix. 
         [0292]    Additional Validation Step 
         [0293]    After application of the GPF the ambiguity resolution is not done yet. At this point in time just a partial solution has been computed. It still has to be proven that the partial solution is correct within the required probability limits. 
         [0294]    Candidate Validation 
         [0295]    3.2.1 Let the initial ILS search return the three best candidates {hacek over (a)} 1 , {hacek over (b)} 1  and {hacek over (a)} 3 . If the third best candidate {hacek over (a)} 3  is sufficiently improbable as a solution compared to the best solution {hacek over (a)} 1 , the GPF solution G{hacek over (a)} 1 —combining the probabilities of first and second candidate—can be validated and fixed. This is implemented by using the same validation test that was used originally for the first two candidates. For the ratio test, the result is a new ratio r G : 
         [0000]    
       
         
           
             
               
                 
                   
                     r 
                     G 
                   
                   = 
                   
                     
                       
                          
                         
                           
                             
                               a 
                               ⋓ 
                             
                             3 
                           
                           - 
                           
                             a 
                             ^ 
                           
                         
                          
                       
                       
                         Q 
                         
                           a 
                           ^ 
                         
                       
                     
                     
                       
                          
                         
                           
                             
                               a 
                               ⋓ 
                             
                             1 
                           
                           - 
                           
                             a 
                             ^ 
                           
                         
                          
                       
                       
                         Q 
                         
                           a 
                           ^ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   37 
                   ) 
                 
               
             
           
         
       
     
         [0296]    The partial solution G{hacek over (a)} 1  is considered to be the correct integer solution if the ratio r G  exceeds the critical value r crit : 
         [0000]      r G ≧r crit   (38) 
         [0297]    For the difference acceptance criterion, the difference d G  is: 
         [0000]        d   G   =∥{hacek over (a)}   3   −â∥   Q     â     −∥{hacek over (a)}   1   −â∥   Q     â     (39) 
         [0298]    Again, the partial solution G{hacek over (a)} 1  is considered to be the correct integer solution if the difference d G  exceeds the critical value d crit : 
         [0000]      d G ≧d crit   (40) 
       Search Validation 
       [0299]    3.2.2 Another validation technique presented in this section does not require computing a third best candidate. Instead, the ILS is repeated on the modified ambiguity vector to get a new best and second best candidate. This is followed by the normal validation step. If the validation succeeds, the GPF was successful. For this method it is required that the matrix G has only integer coefficients in order to have only integer solutions in the transformed ambiguity space. 
         [0300]    In case of a validation failure, the GPF procedure can be repeated to generate another new ambiguity vector with a dimension again one less than the modified ambiguities. This can be iterated until too few ambiguities are remaining in the solution so that the final parameters (usually the position) can no longer be determined accurately enough, or less than two ambiguity entries remain. 
         [0301]    For every iteration step, the new float solution â′ is computed: 
         [0000]        â′=G·â   (41) 
         [0302]    The associated variance-covariance matrix G is: 
         [0000]        Q   â′   =G·Q   â   G   T   (42) 
         [0303]    For the new float solution, the best solution according to ILS is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                       ⋓ 
                     
                     
                       1 
                       ′ 
                     
                   
                   = 
                   
                     
                       argmin 
                       
                         z 
                         ∈ 
                         
                           Z 
                           
                             n 
                             - 
                             1 
                           
                         
                       
                     
                      
                     
                       
                          
                         
                           z 
                           - 
                           
                             
                               a 
                               ^ 
                             
                             ′ 
                           
                         
                          
                       
                       
                         Q 
                         
                           
                             a 
                             ^ 
                           
                           ′ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   43 
                   ) 
                 
               
             
           
         
       
     
         [0304]    Similar, the new second candidate is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                       ⋓ 
                     
                     
                       2 
                       ′ 
                     
                   
                   = 
                   
                     
                       argmin 
                       
                         z 
                         ∈ 
                         
                           
                             Z 
                             
                               n 
                               - 
                               1 
                             
                           
                            
                           \ 
                            
                           
                             { 
                             
                               
                                 a 
                                 ⋓ 
                               
                               
                                 1 
                                 ′ 
                               
                             
                             } 
                           
                         
                       
                     
                      
                     
                       
                          
                         
                           z 
                           - 
                           
                             
                               a 
                               ^ 
                             
                             ′ 
                           
                         
                          
                       
                       
                         Q 
                         
                           
                             a 
                             ^ 
                           
                           ′ 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   44 
                   ) 
                 
               
             
           
         
       
     
         [0305]    3.3 Multiple Candidates 
         [0306]    Generally, more that the two best candidates could be possible integer solution with a sufficient probability. In principle, this could be solved by iterating the GPF algorithm until a good separation of best and second candidate is achieved or no ambiguities are left to remove from the solution. If all candidates are computed that are probable integer solutions for the given floating solution, a direct method can immediately produce a GPF fix without the iteration from the search validation and without giving up because the candidate validation with three candidates has failed. 
         [0307]    When ratio validation with a critical ratio r crit  is used, this collection {{hacek over (a)} 1 , . . . , {hacek over (a)} k } of all k probable integer solutions can be characterized as: 
         [0000]    
       
         
           
             
               
                 
                   
                     { 
                     
                       
                         
                           a 
                           ⋓ 
                         
                         1 
                       
                       , 
                       … 
                        
                       
                           
                       
                       , 
                       
                         
                           a 
                           ⋓ 
                         
                         k 
                       
                     
                     } 
                   
                   = 
                   
                     { 
                     
                       z 
                       ∈ 
                       
                         
                           
                             Z 
                             n 
                           
                            
                           
                             : 
                           
                            
                           
                               
                           
                            
                           
                             
                               
                                  
                                 
                                   z 
                                   - 
                                   
                                     a 
                                     ^ 
                                   
                                 
                                  
                               
                               
                                 Q 
                                 
                                   a 
                                   ^ 
                                 
                               
                             
                             
                               
                                  
                                 
                                   
                                     
                                       a 
                                       ⋓ 
                                     
                                     1 
                                   
                                   - 
                                   
                                     a 
                                     ^ 
                                   
                                 
                                  
                               
                               
                                 Q 
                                 
                                   a 
                                   ^ 
                                 
                               
                             
                           
                         
                         &lt; 
                         
                           r 
                           crit 
                         
                       
                     
                     } 
                   
                 
               
               
                 
                   ( 
                   45 
                   ) 
                 
               
             
           
         
       
     
         [0308]    Similarly, the collection {{hacek over (a)} 1 , . . . , {hacek over (a)} k } for the difference validation method with critical value d crit  is: 
         [0000]      { {hacek over (a)}   1   , . . . , {hacek over (a)}   k}   ={zεZ″:∥z−â∥   Q     â     −∥{hacek over (a)}   1   −â∥   Q     â     &lt;d   crit}   (46) 
         [0309]    This Integer Least Squares mechanization for more than two candidates using a predefined critical value is called Integer Least Squares Collection (ILSC). 
         [0310]    The construction of G can be easily generalized for k&gt;2 candidates. First of all, only k−1 independent differences have to be explicitly in the null space of G. With {hacek over (a)} 1 −{hacek over (a)} i  and {hacek over (a)} 1 −{hacek over (a)} j  all linear combinations are in the null space, too, especially 
         [0000]      {hacek over (a)} i −{hacek over (a)} j =({hacek over (a)} 1 −{hacek over (a)} j )−({hacek over (a)} 1 −{hacek over (a)} i )  (47) 
         [0311]    Thus, for the construction only the k−1 differences Δ i  are needed: 
         [0000]      Δ i   ={hacek over (a)}   1   −{hacek over (a)}   i+1   ,i= 1, . . . ,  k− 1  (48) 
         [0312]    They will be in the null space of the G matrix: 
         [0000]        G·Δ   i =0  (49) 
         [0313]    The row dimension of G will now be m=n−k+1, as one dimension is used up for each independent pair of candidates. Obviously k must be smaller than or equal to n. 
         [0314]    The multiple candidates G matrix G Δ     1     , . . . , Δ     k−1    is computed by: 
         [0000]      G Δ     1     , . . . , Δ     k−1   =G k−1   (50) 
         [0000]    with the iteration: 
         [0000]      G 1 =G Δ     1     (51) 
         [0000]        G   i   =G   G     i−1     ·Δ     i     ·G   i−1   ,i= 2, . . . ,  k− 1  (52) 
         [0315]    Complete Method 
         [0316]    This section uses the solutions described so far to present the complete work flow of using GPF in different variants. 
         [0317]    Complete Method using Candidate Validation 
         [0318]    For the candidate validation variant from section 3.2.1 the complete method is:
       1. Compute a float solution like for the standard ambiguity resolution methods   2. Compute at least the best and second best Integer Least-Squares solutions. Possibly compute all candidates within the predefined critical value determined by the chosen validation method.   3. Decide if the best solution can be validated using one of the state-of-the-art methods
           (a) If the best solution can be validated, fix the ambiguities to the best solution and continue computing fixed positions.   (b) In addition to the candidates computed in step 2, compute all candidates within the predefined critical value determined by the chosen validation method. Compute at least up to the third candidate, and maximally n candidates.   (c) If the number of candidates found to be below the critical value is less or equal to n, transform the first candidate solution and the variance-covariance matrix using the G matrix.   (d) If more than n candidates exist below the critical value, ambiguity resolution fails.   
           4. Fix the ambiguity combinations defined by G.       
 
         [0327]    Complete Method using Search Validation
       Using the search validation method from section 3.2.2, the complete work flow is:   1. Compute a float solution like for the standard ambiguity resolution methods   2. Compute the best and second best Integer Least-Squares solutions   3. Decide if the best solution can be validated using one of the state-of-the-art methods
           (a) If the best solution can be validated, fix the ambiguities to the best solution and continue computing fixed positions.   (b) If the best solution cannot be validated and the floating solution has at least two entries, compute the GPF matrix G using the defined instruction above.   (c) If the best solution cannot be validated and the floating solution has less than two entries, the ambiguity resolution fails.   
           4. Transform the floating solution and the variance-covariance matrix using the G matrix.   5. Repeat the process at step 2 using the modified floating solution and variance-covariance matrix.       
 
       Examples 
       [0337]    The following sections give examples of the application of Generalized Partial Fixing to the existing and for new problems. 
         [0338]    Wide-Lane 
         [0339]    Both L 1  and L 2  ambiguities N 1  and N 2  have the same difference δ for first and second candidate. 
         [0000]    
       
         
           
             
               
                 
                   
                     Δ 
                      
                     
                       
                         a 
                         ⋓ 
                       
                       2 
                     
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 N 
                                  
                                 
                                     
                                 
                                  
                                 
                                   1 
                                   best 
                                 
                               
                               - 
                               
                                 N 
                                  
                                 
                                     
                                 
                                  
                                 
                                   1 
                                   second 
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 N 
                                  
                                 
                                     
                                 
                                  
                                 
                                   2 
                                   best 
                                 
                               
                               - 
                               
                                 N 
                                  
                                 
                                     
                                 
                                  
                                 
                                   2 
                                   second 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                     = 
                     
                       ( 
                       
                         
                           
                             δ 
                           
                         
                         
                           
                             δ 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   53 
                   ) 
                 
               
             
           
         
       
     
         [0340]    Thus 
         [0000]        G =(δ,−δ)  (54) 
         [0341]    As the Null-space doesn&#39;t change when G is multiplied with a non-zero factor, the following matrix can be used as well: 
         [0000]    
       
         
           
             
               
                 
                   
                     G 
                     ′ 
                   
                   = 
                   
                     
                       
                         1 
                         δ 
                       
                        
                       G 
                     
                     = 
                     
                       ( 
                       
                         1 
                         , 
                         
                           - 
                           1 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   55 
                   ) 
                 
               
             
           
         
       
     
         [0000]    This transforms the fixed ambiguity combination to be the wide lane combination. 
         [0342]    Single Satellite Rejection 
         [0343]    If only one ambiguity is different, by definition of the GPF method that ambiguity is left out of the fixing process. 
         [0344]    Complex Example 
         [0345]    Let&#39;s assume there is a common bias on all ambiguities. This would for example be the case when one attempts to fix the single-differenced ambiguities directly. 
         [0000]    
       
         
           
             
               
                 
                   Δ 
                   = 
                   
                     ( 
                     
                       
                         
                           δ 
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           δ 
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   56 
                   ) 
                 
               
             
           
         
       
     
         [0346]    As the delta can be normalized by division by their GCD, we can assume δ=1. Applying GPF, the transformation becomes: 
         [0000]    
       
         
           
             
               
                 
                   G 
                   = 
                   
                     ( 
                     
                       
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           0 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           
                             - 
                             1 
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   57 
                   ) 
                 
               
             
           
         
       
     
         [0347]    This becomes an interesting variation of double-differencing the originally single-differenced estimates. Instead of having one common reference satellite for all other observations, a new reference satellite is used for each of the new ambiguity combinations. It can probably be shown that the approach is equivalent to the classical approach, and thus double-differencing follows implicitly from GPF. Actually, a different construction of G also fulfilling the GPF requirements would directly lead to the differencing operator: 
         [0000]    
       
         
           
             
               
                 
                   G 
                   = 
                   
                     ( 
                     
                       
                         
                           
                             δ 
                             2 
                           
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                         
                           0 
                         
                         
                           … 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             δ 
                             3 
                           
                         
                         
                           0 
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                         
                           0 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             δ 
                             
                               n 
                               - 
                               1 
                             
                           
                         
                         
                           … 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             - 
                             
                               δ 
                               1 
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   58 
                   ) 
                 
               
             
           
         
       
     
       DESCRIPTION OF THE DRAWINGS 
       [0348]    In  FIG. 1 ,  FIG. 2  and  FIG. 3  some implementations using ambiguity fixing are shown. Prior art versions of these use a standard ambiguity fixing block (emphasized with darker outlining in the figures). The ambiguity fixing block is improved by the GPF method in accordance with embodiments of the present invention. 
         [0349]      FIG. 1  displays a prior art method for post processing GNSS data using a sequential float solution, for example a Kalman filter. The float solution is updated for every GNSS data epoch read from the data storage. The result is available immediately after all GNSS data epoch have been read and processed. 
         [0350]    Referring to  FIG. 1 , the process flow starts at step  105 . The floating solution is initialized at step  110 . Step  115  checks whether more epochs of data are available. If yes, at step  120  the data is read and the next data epoch is prepared. Step  125  then updates the floating solution with the data epoch prepared at step  120 . When no more epochs of data are available, ambiguity fixing is attempted at step  130 . Step  135  checks whether ambiguity fixing was successful. If no, the initialization is determined to have failed at step  140 . If yes, at step  145  a position is computed using the fixed ambiguities and reported. Initialization ends successfully at step  150 . 
         [0351]      FIG. 2  shows an alternative prior art post processing formulation. Here, all the GNSS data epochs are accumulated, but not completely processed. This is finally done using a batch least squares method after all data had been accumulated, finally yielding the float solution. 
         [0352]    Referring to  FIG. 2 , the process flow starts at step  205 . The floating solution is initialized at step  210 . Step  215  checks whether more epochs of data are available. If yes, at step  220  the data is read and the next data epoch is prepared. Step  225  then accumulates the floating solution data. When no more epochs of data are available, the float solution is computed at step  230 . Ambiguity fixing is then attempted at step  235 . Step  240  checks whether ambiguity fixing was successful. If no, the initialization is determined to have failed at step  245 . If yes, at step  250  a position is computed using the fixed ambiguities and reported. Initialization ends successfully at step  255 . 
         [0353]      FIG. 3  is a flow chart of real-time processing. For every new GNSS data epoch, ambiguity fixing is attempted. If successful, a fixed position can be computed and reported. If not, the process is repeated whenever the next data epoch is available. 
         [0354]    Referring to  FIG. 3 , the process flow starts at step  305 . The floating solution is initialized at step  310 . A next epoch of data is acquired at step  315 . Step  320  updates the floating solution with the data acquired at step  315 . Ambiguity fixing is then attempted at step  325 . Step  330  checks whether ambiguity fixing was successful. If no, the flow returns to step  315  to acquire a next epoch of data. If yes, at step  335  a position is computed using the fixed ambiguities and reported. Initialization ends successfully at step  340 . 
         [0355]      FIG. 4  is a flow chart of a prior art ambiguity fixing process. The floating solution, for example computed by one of the methods shown in  FIG. 1 ,  FIG. 2  and  FIG. 3 , is used to determine a best and second ambiguity solution in the Integer Least Squares process. If the final validation succeeds, the solution is accepted and used, if not, no fixed solution can be computed. 
         [0356]    Referring to  FIG. 4 , the process flow starts at step  405 . The floating solution is initialized at step  410  with values for parameters a and Qa. An Integer Least Squares adjustment is computed at step  415  to determine best candidate a 1  and second best candidate a 2 . Validation of the solution is attempted at step  415 . Step  430  checks whether solution validation was successful. If no, then fixing is determined to have failed at step  435 . If yes, then the ambiguities are fixed with the current ambiguity solution candidate a 1  at step  440 . Fixing ends successfully at step  445 . 
         [0357]      FIG. 5  is a flow chart of generalized partial fixing with candidate validation in accordance with some embodiments of the invention. The approach of  FIG. 5  enhances the prior art method of  FIG. 4  by generating three instead of two candidates in the Integer Least Squares solution. If validation using the first two candidate solution fails, the third candidate solution is inspected. If the validation is now successful using the first and the third candidate, the GPF matrix G is computed from the first and second candidate and applied to the solution generating the final accepted solution. If this second validation fails, the whole initialization process fails. 
         [0358]    Referring to  FIG. 5 , the process flow starts at step  505 . A floating solution is computed at step  510  to determine floating values  515  for parameters a and Qa. An Integer Least Squares adjustment is computed at step  520  to determine candidates  525  comprising best candidate a 1  and second best candidate a 2  and third best candidate a 3 . Validation of the solution is attempted at step  530 . Step  535  checks whether solution validation was successful by comparing best candidate a 1  with second best candidate a 2 . If yes, then fixing is performed at step  540  using ambiguity candidate solution a 1  and fixing ends successfully at step  545 . If at step  535  it is determined that solution validation was not successful when comparing best candidate a 1  with second best candidate a 2 , then step  550  checks whether solution validation was successful by comparing best candidate a 1  with third best candidate a 3 . If no, then fixing fails at step  555 . If yes, then at step  560  the GPF solution a 1 ′ at  565  is computed using best candidate a 1  and second best candidate a 2 . Fixing is then performed at step  565  using GPF solution a 1 ′ and fixing ends successfully at step  545 . 
         [0359]      FIG. 6  is a flow chart of generalized partial fixing with a candidate validation variant in accordance with some embodiments of the invention.  FIG. 6  differs from the variant of  FIG. 5  in that the third candidate solution is not generated before the validation had been attempted for first and second solution. The third solution is not needed unless this first validation fails. In that case, the third solution is generated and compared to the first one. If the validation is now successful using the first and the third candidate, the GPF matrix G is computed from the first and second candidate and applied to the solution generating the final accepted solution. If this second validation fails, the whole initialization process fails. 
         [0360]    Referring to  FIG. 6 , the process flow starts at step  605 . A floating solution is computed at step  610  to determine floating values  615  for parameters a and Qa. An Integer Least Squares adjustment is computed at step  620  to determine candidates  625  comprising best candidate a 1  and second best candidate a 2 . Validation of the solution is attempted at step  630 . Step  635  checks whether solution validation was successful by comparing best candidate a 1  with second best candidate a 2 . If yes, then fixing is performed at step  640  using ambiguity candidate solution a 1  and fixing ends successfully at step  645 . If at step  635  it is determined that solution validation was not successful when comparing best candidate a 1  with second best candidate a 2 , then step  650  continues the integer least squares adjustment to obtain a third best candidate a 1  at  655 . Step  660  checks whether solution validation was successful by comparing best candidate a 1  with third best candidate a 3 . If no, then fixing fails at step  665 . If yes, then at step  670  the GPF solution a 1 ′ at  675  is computed using best candidate a 1  and second best candidate a 2 . Fixing is then performed at step  680  using GPF solution a 1 ′ and fixing ends successfully at step  645 . 
         [0361]      FIG. 7  is a flow chart of generalized partial fixing generating all needed candidates for validation in accordance with some embodiments of the invention. In  FIG. 7 , the Integer Least Squares Collection invocation generates the complete validation collection up to a candidate k. If this succeeds for a k≦n, the GPF is performed and the initialization is successful. Integer Least Squares Collection flow charts are found in  FIG. 9 ,  FIG. 10  and  FIG. 11 . This mechanization uses the generation of GPF matrices for more than two candidates, see chapter 3.3 “Multiple Candidates” above. 
         [0362]    Referring to  FIG. 7 , the process flow starts at step  705 . A floating solution is computed at step  710  to determine floating values  715  for parameters a and Qa. An Integer Least Squares adjustment is computed at step  720  to determine candidates  725  comprising best candidate a 1  and second best candidate a 2 . Validation of the solution is attempted at step  730 . Step  735  checks whether solution validation was successful by comparing best candidate a 1  with second best candidate a 2 . If yes, then fixing is performed at step  740  using ambiguity candidate solution a 1  and fixing ends successfully at step  745 . If at step  735  it is determined that solution validation was not successful when comparing best candidate a 1  with second best candidate a 2 , then step  750  invokes Integer Least Squares Collection to generate the complete validation collection  755  up to a k th  candidate: candidates a 3  . . . a k . Step  760  checks whether this has succeeded for a k≦n. If no, then fixing fails at step  765 . If yes, then at step  765  the GPF solution a 1 ′ at  770  is computed using candidates a 1  . . . a k . Fixing is then performed at step  775  using GPF solution a 1 ′ and fixing ends successfully at step  745 . 
         [0363]      FIG. 8  is a flow chart of generalized partial fixing initially generating all needed candidates in accordance with some embodiments of the invention. In the embodiment of  FIG. 8 , all candidates needed to validate the best solution are generated right away in the initial Integer Least Squares Collection. Next the first two candidates are validated as usual, and if this fails, GPF is applied if k&lt;=n. Again, the Integer Least Squares Collection flow charts are found in  FIG. 9 ,  FIG. 10  and  FIG. 11 . This implementation uses the generation of GPF matrices for more than two candidates, see chapter 3.3 “Multiple Candidates” above. 
         [0364]    Referring to  FIG. 8 , the process flow starts at step  805 . A floating solution is computed at step  810  to determine floating values  815  for parameters a and Qa. Integer Least Squares Collection is invoked at step  820  to determine candidates  825  comprising candidates a 1 , a 2  . . . a k . Validation of the solution is attempted at step  830 . Step  835  checks whether solution validation was successful by comparing best candidate a 1  with second best candidate a 2 . If yes, then fixing is performed at step  840  using ambiguity candidate solution a 1  and fixing ends successfully at step  845 . If at step  835  it is determined that solution validation was not successful when comparing best candidate a 1  with second best candidate a 2 , then step  850  checks whether k&lt;=n. If no, then fixing fails at step  855 . If yes, then at step  860  the GPF solution a 1 ′ at  865  is computed using candidates a 1 , a 2 , a k . Fixing is then performed at step  865  using GPF solution a 1 ′ and fixing ends successfully at step  845 . 
         [0365]      FIG. 9  is a flow chart of integer least squares collection iteration in accordance with embodiments of the invention. The procedure starts with a given candidate kstart in the ranked plurality of candidate sets possible. The iteration is continued until either no more candidate sets can be found that do not exceed the given critical value threshold or the given maximum candidate nmax had been generated. 
         [0366]    Referring to  FIG. 9 , the process flow starts at step  905 . A starting candidate k=kstart is set at step  910 . At step  915  a k th  best candidate better than v crit  is computed. Step  920  checks whether a candidate a k  has been found for the collection. If no, then the collection is reported at step  925  as the result of the ILS collection and the ILS collection is complete at  930 . If yes, then candidate A k  at  935  is added to the collection. Step  940  then checks whether k is less than nmax. If no, then the collection is reported at step  925  as the result of the ILS collection and the ILS collection is complete at  930 . If yes, then k is incremented at step  945  and the flow returns to step  915 . 
         [0367]      FIG. 10  shows a variant of the integer least squares collection iteration of  FIG. 9  in accordance with embodiments of the invention. While the first variant stops before the first candidate exceeding the critical value is generated, this time the generation continues until the first candidate exceeded the critical value has been generated. This candidate does not get included in the collection reported as a result. 
         [0368]    Referring to  FIG. 10 , the process flow starts at step  1005 . A starting candidate k=kstart is set at step  1010 . At step  1015  a k th  best candidate is computed. Step  1020  checks whether candidate A k  is better than v crit . If no, then the collection is reported at step  1040  as the result of the ILS collection and the ILS collection is complete at  1045 . If yes, then candidate A k  at  1025  is added to the collection. Step  1030  then checks whether k is less than nmax. If no, then the collection is reported at step  1040  as the result of the ILS collection and the ILS collection is complete at  1045 . If yes, then k is incremented at step  1035  and the flow returns to step  1015 . 
         [0369]      FIG. 11  shows a variant of the integer least squares collection iteration of  FIG. 9  in accordance with embodiments of the invention. In the embodiment of  FIG. 11 , always the first nmax candidates are generated. Then, only the candidates not exceeding the critical value threshold are reported as the collection. 
         [0370]    Referring to  FIG. 11 , the process flow starts at step  1105 . A starting candidate k=kstart is set at step  1110 . At step  1115  a k th  best candidate is computed. The resulting candidate A k  is added to the collection at  1120 . Step  1125  checks whether k is less than nmax. If no, then the part of the collection better than v crit  is reported at  1140  as the result and the ILS collection is complete at  1145 . If yes, then k is incremented and the flow returns to step  1115 . 
         [0371]      FIG. 12  is a flow chart of generalized partial fixing with search validation in accordance with embodiments of the invention. When the first validation fails, GPF is applied to substitute the original float solution. Then the whole search, validation and GPF process is repeated until a validation succeeds or no more than two entries remain in the modified float solution. 
         [0372]    Referring to  FIG. 12 , the process flow starts at step  1205 . A floating solution is computed at step  1210  to determine floating values  1215  for parameters a and Qa. Integer Least Squares adjustment is invoked at step  1220  to determine candidates  1225  comprising candidates a 1  and a 2 . Validation of the solution is attempted at step  1230 . Step  1235  checks whether solution validation was successful. If yes, then fixing is performed at step  1260  using the current ambiguity combination and fixing ends successfully at  1265 . If at step  1235  it is determined that solution validation was not successful, then step  1240  checks whether at least two entries are left. If no, then fixing fails at  1245 . If yes, then at step  1245  the GPF solution G, a′, Q a ′ at  1250  is computed from candidates a 1 , a 2 . Step  1255  replaces the current float solution with the GPF solution and flow returns to  1215 . 
         [0373]      FIG. 13  shows a block diagram of an example GNSS receiver which may be used in accordance with various embodiments described herein. In particular,  FIG. 13  illustrates a block diagram of a GNSS receiver in the form of a general purpose GPS receiver  1330  capable of demodulation of the L 1  and/or L 2  signal(s) received from one or more GPS satellites. A more detailed discussion of the function of such a receiver is found in U.S. Pat. No. 5,621,426. U.S. Pat. No. 5,621,426, by Gary R. 5 Lennen, entitled “Optimized processing of signals for enhanced cross-correlation in a satellite positioning system receiver.” Receivers capable of receiving and demodulating GPS L 5  signals and signals of other GNSS are similarly constructed. The description here is intended as illustrative and not in any way limiting as to the construction or operation of processors or of GNSS receivers useful in practicing embodiments of the invention. 
         [0374]    In  FIG. 13 , received L 1  and L 2  signals are generated by at least one GPS satellite. Each GPS satellite generates different signal L 1  and L 2  signals and they are processed by different digital channel processors  1352  which operate in the same way as one another.  FIG. 13  shows GPS signals (L 1 =1575.42 MHz, L 2 =1227.60 MHz) entering GPS receiver  1330  through a dual frequency antenna  1332 , commercially available from Trimble Navigation of Sunnyvale, Calif. Master oscillator  1348  provides the reference oscillator which drives all other clocks in the system. Frequency synthesizer  1338  takes the output of master oscillator  1348  and generates important clock and local oscillator frequencies used throughout the system. For example, in one embodiment frequency synthesizer  1338  generates several timing signals such as a 1st (local oscillator) signal LO 1  at 1400 MHz, a 2nd local oscillator signal LO 2  at 175 MHz, an SCLK (sampling clock) signal at 25 MHz, and a MSEC (millisecond) signal used by the system as a measurement of local reference time. 
         [0375]    A filter/LNA (Low Noise Amplifier)  1334  performs filtering and low noise amplification of both L 1  and L 2  signals. The noise figure of GPS receiver  1330  is dictated by the performance of the filter/LNA combination. The downconvertor  1336  mixes both L 1  and L 2  signals in frequency down to approximately 175 MHz and outputs the analogue L 1  and L 2  signals into an IF (intermediate frequency) processor  1350 . IF processor  1350  takes the analog L 1  and L 2  signals at approximately 175 MHz  30  and converts them into digitally sampled L 1  and L 2  inphase (L 1  I and L 2  I) and quadrature signals (L 1  Q and L 2  Q) at carrier frequencies 420 KHz for L 1  and at 2.6 MHz for L 2  signals respectively. 
         [0376]    At least one digital channel processor  1352  inputs the digitally sampled L 1  and L 2  inphase and quadrature signals. All digital channel processors  1352  are typically are identical by design and typically operate on identical input samples. Each 5 digital channel processor  1352  is designed to digitally track the L 1  and L 2  signals produced by one satellite by tracking code and carrier signals and to from code and carrier phase measurements in conjunction with the microprocessor system  1354 . One digital channel processor  1352  is capable of tracking one satellite in both L 1  and L 2  channels. Microprocessor system  1354  is typically a general purpose computing device which facilitates tracking and measurements processes, providing pseudorange and carrier phase measurements for a processor  1358 . In one embodiment, microprocessor system  1354  provides signals to control the operation of one or more digital channel processors  1352 . Processor  1358  typically performs functions of combining measurements to produce position, velocity and time information for the differential and surveying functions. Storage  1360  is coupled with processor  1358  and microprocessor system  1354 . Storage  1360  may comprise a volatile or non-volatile storage such as a RAM or ROM, or some other computer readable memory device or media. In one rover receiver embodiment, processor  1358  performs one or more of the methods of estimating integer ambiguities described herein. 
         [0377]    In some embodiments, such as in rover receivers, microprocessor  1354  and/or processor  1358  receive additional inputs for use in refining position information determined by GPS receiver  1330 . In some embodiments, corrections information is received and utilized such as satellite position information and/or corrections such as differential GPS corrections, or RTK corrections from a base station or a network of reference stations. 
         [0378]    A GNSS receiver such as receiver  1330  can be a standalone receiver for autonomous positioning (with or without satellite position and clock information provided from an external source), a base station receiver with communications link to a rover receiver, a reference receiver of a network of receivers, a rover receiver with communications link to receive corrections from a base station, a rover receiver with communications link to receive corrections from a network processor which processes observations from multiple reference receivers, etc. Processor  1358  can be incorporated in or associated with a GNSS receiver, or can be a separate processor. Processor  1358  can be used to processes previously obtained GNSS observation data in a post-processing mode, or to process data obtained in a real-time or near real-time mode. Processor  1358  can be a network processor which estimates ambiguities from observations of a single receiver, or from observations of two or more receivers. 
         [0379]    Any plurality of the above described aspects of the invention may be combined to form further aspects and embodiments, with the aim of providing additional benefits notably in terms of computation speed, precision estimation and system usability. 
         [0380]    Any of the above-described methods and their embodiments may be integrated into an apparatus such as a GNSS rover receiver, a GNSS reference receiver, a GNSS base station or a GNSS network station, and/or the processing methods described can be carried out in a processor which is separate from and even remote from the receivers used to collect the observations (e.g., observation data collected by one or more receivers can be retrieved from storage for post-processing, or observations from multiple network reference stations can be transferred to a network processor for near-real-time processing to generate a correction data stream and/or virtual-reference-station messages which can be transmitted to one or more rovers). Therefore, the invention also relates to a rover receiver, a reference receiver, a base station, a network station or a separate processor or even a processor incorporated in other apparatus. 
         [0381]    In one embodiment, the receiver of the apparatus of any one of the above-described embodiments is separate from the processing element. Post-processing and network processing of the observations may be performed. That is, the constituent elements of the apparatus for processing of observations does not itself require a receiver. The receiver may be separate from and even owned/operated by a different entity than the entity which is performing the processing. For post-processing, the observations may be retrieved from a set of data which was previously collected and stored, and processed with reference-station data which was previously collected and stored; the processing is conducted for example in an office computer or server computer long after the data collection and is thus not real-time. For network processing, multiple reference-station receivers collect observations of the signals from multiple satellites, and this data is supplied to a network processor which may for example generate a correction data stream or which may for example generate a “virtual reference station” correction which is supplied to a rover so that the rover can perform differential processing. The data provided to the rover may be ambiguities determined in the network processor, which the rover may use to speed its position solution, or may be in the form of corrections which the rover applies to improve its position solution. The network is typically operated as a service to rover operators, while the network operator is typically a different entity than the rover operator. This applies to each of the above-described apparatuses and claims. 
         [0382]    Any of the above-described methods and their embodiments may be implemented by means of a computer program. The computer program may be loaded on any suitable apparatus such as a processor, a rover receiver, a reference receiver or a network station as described above. Therefore, the invention also relates to a computer program, which, when carried out on a processor, a rover receiver, a reference receiver or a network station as described above, carries out any one of the above above-described methods and their embodiments. 
         [0383]    Embodiments of the invention also include a computer-readable medium or a computer-program product including the above-mentioned computer program. The computer-readable medium or computer-program product may for instance be a magnetic tape, an optical memory disk, a magnetic disk, a magneto-optical disk, a CD ROM, a DVD, a CD, a flash memory unit or the like, wherein the computer program is permanently or temporarily stored. The invention also relates to a computer-readable medium (or to a computer-program product) having computer-executable instructions for carrying out any one of the methods of the invention. 
         [0384]    Embodiments of the invention also relate to a firmware update adapted to be installed on processors or receivers already in the field, i.e. a computer program which is delivered to the field as a computer program product. This applies to each of the above-described methods and apparatuses. 
         [0385]    GNSS receivers may include an antenna, configured to received the signals at the frequencies broadcasted by the satellites, processor units, one or more accurate clocks (such as crystal oscillators), one or more computer processing units (CPU), one or more memory units (RAM, ROM, flash memory, or the like), and a display for displaying position information to a user. 
         [0386]    Where the terms “receiver”, “filter” and “processing element” are used herein as units of an apparatus, no restriction is made regarding how distributed the constituent parts of a unit may be. That is, the constituent parts of a unit may be distributed in different software or hardware components or devices for bringing about the intended function. Furthermore, the units may be gathered together for performing their functions by means of a combined, single unit. For instance, the receiver and the processing element may be combined to form a single unit, to perform the combined functionalities of the units. 
         [0387]    The above-mentioned units may be implemented using hardware, software, a combination of hardware and software, pre-programmed ASICs (application-specific integrated circuit), etc. A unit may include a computer processing unit (CPU), a storage unit, input/output (I/O) units, network connection units, etc. 
         [0388]    Although embodiments of the present invention have been described on the basis of detailed examples, the detailed examples only serve to provide the skilled person with a better understanding, and are not intended to limit the scope of the invention. The scope of the invention is much rather defined by the appended claims. 
         [0389]    Inventive concepts include but are not limited to the following:
   1. A method for estimating integer ambiguities from carrier phase observations of GNSS signals received at multiple stations from at least four satellites, comprising:
       a. determining from the carrier phase observations a ranked plurality of candidate sets of estimated integer ambiguities,   b. applying a criterion to select one of the ranked plurality of candidate sets as a selected candidate set,   c. forming a matrix G such that the image formed when matrix G is linearly combined with a selected candidate set is equal to the image formed when matrix G is linearly combined with a second candidate set, and   d. applying the matrix G to the selected candidate set to determine a modified candidate set of estimated integer ambiguities.   
       2. The method of 1, wherein determining a ranked plurality of candidate sets of estimated integer ambiguities comprises:
       i. simultaneously determining from the carrier phase observations a vector of unknown integer ambiguities and a vector of additional model parameters, without applying an integer constraint on the vector of unknown integer ambiguities, to obtain a float solution of estimates and their variance-covariance matrix, and   ii. determining the ranked plurality of candidate sets of estimated integer ambiguities from the vector of unknown integer ambiguities and its variance-covariance matrix.   
       3. The method of 2, wherein the additional model parameters include at least one of: position of a station at which the GNSS signals were received, receiver clock errors, satellite clock errors, atmospheric errors, and time-correlated noise.   4. The method of 2, wherein determining the ranked plurality of candidate sets of estimated integer ambiguities from the vector of unknown integer ambiguities and its variance-covariance matrix comprises applying integer least squares to the vector of unknown integer ambiguities.   5. The method of 1, wherein applying a criterion to select one of the ranked plurality of candidate sets as a selected candidate set comprises: determining a probability of correctness of at least one candidate set.   6. The method of 5, wherein determining a probability of correctness of at least one candidate set comprises: determining a statistical value for the selected candidate set, determining a statistical value for a second candidate set, and combining the statistical values to obtain a probability of correctness indicator.   7. The method of 6, wherein the probability of correctness indicator comprises one of: a ratio of second-best to best chi-squared values exceeding a threshold, differencing of chi-squared values, Fixed Ratio Test, Fisher test for ratio validation, a Student-t-test, a standard normal distribution test for the difference of norms, and Optimal Integer Aperture Estimation.   8. The method of 6, wherein forming a matrix G and applying the matrix G are performed only if the probability of correctness does not exceed a threshold.   9. The method of 6, further comprising determining whether the probability of correctness exceeds a threshold.   10. The method of 6, further comprising:
       i. determining whether probability of correctness of the selected candidate set relative to a second candidate set exceeds a threshold and, if not,   ii. determining whether probability of correctness of the selected candidate set relative to a third candidate set exceeds a threshold and, if yes, then   iii. forming the matrix G and applying the matrix G to the selected candidate set.   
       11. The method of 6, further comprising:
       i. determining whether probability of correctness of the selected candidate set relative to a second candidate set exceeds a threshold and, if not,   ii. generating a third candidate set and determining whether probability of correctness of the selected candidate set relative to the third candidate set exceeds a threshold and, if yes, then   iii. forming the matrix G and applying the matrix G to the selected candidate set.   
       12. The method of 6, further comprising:
       i. determining whether probability of correctness of the selected candidate set relative to a second candidate set exceeds a threshold and, if not,   ii. generating further candidate sets which do not exceed the threshold, and   iii. forming the matrix G using all of the further candidate sets such that the image formed when matrix G is linearly combined with a one further candidate set is equal to the image formed when matrix G is linearly combined with any other further candidate set, and   iv. applying the matrix G to the selected candidate set.   
       13. The method of 6, further comprising:
       i. determining whether probability of correctness of the selected candidate set relative to a second candidate set exceeds a threshold and, if not,   ii. generating a group of further candidate sets and determining probability of correctness of the selected candidate set relative to each of the further candidate sets in turn until probability of correctness of the selected candidate set relative to one of the further candidate sets exceeds a threshold, and then   iii. forming the matrix G and applying the matrix G to the selected candidate set.   
       14. The method of one of 12 or 13, wherein generating further candidate sets which do not exceed the threshold comprises: iteratively determining candidate sets which do not exceed the threshold and, with each iteration, determining whether another candidate set which does not exceed the threshold is possible.   15. The method of one of 12 or 13, wherein generating further candidate sets which do not exceed the threshold comprises: iteratively determining candidate sets and determining for each candidate set generated whether the threshold is exceeded.   16. The method one of 12 or 13, wherein generating further candidate sets which do not exceed the threshold comprises: determining a maximum number of candidate sets and subsequently determining for each candidate set generated whether the threshold is exceeded.   17. The method of 6, further comprising
       i. determining whether probability of correctness of the selected candidate set relative to a second candidate set exceeds a threshold and, if not, then   ii. forming the matrix G and applying the matrix G to the selected candidate set to determine a modified candidate set of estimated integer ambiguities,   iii. using the modified candidate set to determine a ranked plurality of new candidate sets, and   iv. applying a criterion to select one of the ranked plurality of new candidate sets as a selected new candidate set.   
       18. The method of 17, further comprising:
       1. determining whether probability of correctness of the selected new candidate set relative to a second new candidate set exceeds a threshold and, if not, then   2. forming a new matrix G such that the image formed when new matrix G is linearly combined with the selected new candidate set is equal to the image formed when new matrix G is linearly combined with a second new candidate set,   3. applying the new matrix G to the selected new candidate set to determine a new modified candidate set of estimated integer ambiguities,   4. using the new modified candidate set to determine a ranked plurality of new candidate sets, and   5. applying a criterion to select one of the ranked plurality of new candidate sets as a selected candidate set.   
       19. The method of 18, wherein each new candidate set represents a possible combination of integer ambiguities and wherein the selected new candidate set is tested for validity, the method further comprising: iteratively repeating steps 1. through 5. for successive new candidate sets until either a selected new candidate set is validated or no more possible combinations remain.   20. The method of 1, wherein the matrix G represents a mapping of the vector of unknown integer ambiguities to a subset of ambiguities to be fixed.   21. The method of 1, wherein each candidate set has an ambiguities space of dimension n, and matrix G maps an input ambiguity space of dimension n to an output ambiguity space of dimension n−1.   22. The method of one of 12, 13 or 14, wherein forming matrix G comprises: forming matrix G such that the image formed when matrix G is linearly combined with a third candidate set is equal to the image formed when matrix G is linearly combined with the selected candidate set.   23. The method of 22, wherein each candidate set has an ambiguities space of dimension n, and matrix G maps an input ambiguity space of dimension n to an output ambiguity space of dimension n−2.   24. The method of one of 12, 13, or 14, wherein forming matrix G comprises: forming matrix G such that the image formed when matrix G is linearly combined with a k th  candidate set is equal to the image formed when matrix G is linearly combined with the selected candidate set.   25. The method of 24, wherein each candidate set has an ambiguities space of dimension n, and matrix G maps an input ambiguity space of dimension n to an output ambiguity space of dimension n−(k−1).   26. The method of 1 wherein the matrix G contains non-integer entities.   27. The method of 1 wherein the matrix G contains only integer entities.   28. The method of 1, further comprising: using the selected candidate set to determine values for the additional model parameters.   29. The method of one of 17-19, further comprising: using the selected new candidate set to determine values for the additional model parameters.   30. A method of post-processing carrier phase observations of GNSS signals received over multiple epochs at multiple stations from at least four satellites to compute a position fix, comprising:
       i. Initializing a floating solution for a vector of unknown integer ambiguities and a vector of additional model parameters,   ii. Updating the floating solution with observations received at multiple epochs,   iii. Estimating integer ambiguities in accordance with one of 1-29 and, when successful,   iv. Using the estimated integer ambiguities to compute the position fix.   
       31. The method of  30 , wherein updating the floating solution comprises iteratively updating the floating solution with observations received at multiple epochs.   32. The method of 30, wherein the updating the floating solution comprises simultaneously updating the floating solution with observations received at multiple epochs.   33. A method of real-time processing of carrier phase observations of GNSS signals received over multiple epochs at multiple stations from at least four satellites to compute a position fix, comprising:   i. Initializing a floating solution for a vector of unknown integer ambiguities and a vector of additional model parameters,   ii. Updating the floating solution with observations received at multiple   epochs,   iii. Estimating integer ambiguities in accordance with one of 1-29 and, when successful,   iv. Using the estimated integer ambiguities to compute values for the additional model parameters.   34. A system comprising at least one processor and memory with instructions for carrying out the method of one of 1-33.   35. A program comprising instructions adapted to cause one or more processors to carry out the method of one of 1-33.   36. A tangible, computer-readable medium, in which is embodied a program comprising instructions adapted to cause one or more processors to carry out the method of one of 1-33.   37. A computer program product comprising the computer-readable medium of 36.