Abstract:
This invention discloses apparatus and methods for detecting transmit symbols from the receiving waveform samples at the receiver side for communications systems. The receiving waveform samples are corrupted by channel and noise effects and the detection is carried out with a maximum likelihood optimality criterion. This invention utilizes a successive linear constraint exchange scheme that formulates a sequence of linearly constrained minimization subproblems to allow the solutions to these subproblems, combined with certain quantization and mapping operations, to converge to the optimal maximum likelihood estimate. This invention is applicable to any digitally modulated communications systems, including but not limited to Multiple Input Multiple Output (MIMO) communications systems.

Description:
[0001]    This application claims the benefit of U.S. Provisional Application No. 62/175,451, filed on Jun. 15, 2015. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The present invention relates to apparatus and methods for detecting transmit symbols at the receiver side in a communications system. This invention detects the symbols optimally with a maximum likelihood criterion and is applicable to any digitally modulated communications systems, including but not limited to Multiple Input Multiple Output (MIMO) communications systems. 
       BACKGROUND OF THE INVENTION 
       [0003]    For a digital modulation communications system, the transmitter encodes information bits into transmit symbols, usually with forward error correction coding, and further modulates the transmit symbols into waveform to travel through the physical media (or channel) of the communication link to arrive at the receiver side. The receiver samples the incoming waveform and employs various digital receiver schemes to recover the information bits from the receiving waveform under channel and noise effects. 
         [0004]    One of the challenging tasks for implementing a robust receiver lies in the design of a symbol detector to optimally detect the transmit symbols with a maximum likelihood criterion. The design of a maximum likelihood symbol detector is particularly challenging for a MIMO communications system since it involves multi-dimensional search with an exponential growth complexity when the number of input and/or output increases. This invention discloses apparatus and methods to perform optimal maximum likelihood symbol detector that is applicable to any digitally modulated communications systems, including but not limited to MIMO communications systems. 
       SUMMARY OF THE INVENTION 
       [0005]    This invention presents apparatus and methods to compute for the transmit symbols from the observed receiving digital samples corrupted by channel and noise effects. In particular, the N receiving samples {y 1 , y 2 , . . . , y N } and the M transmit symbols {x 1 , x 2 , . . . , x M } at one symbol period are related in the following vector form: 
         [0000]    
       
      
       y=Hx+n  
      
     
         [0000]    where the N×1 vector 
         [0000]    
       
         
           
             y 
             = 
             
               [ 
               
                 
                   
                     
                       y 
                       1 
                     
                   
                 
                 
                   
                     
                       y 
                       2 
                     
                   
                 
                 
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       y 
                       N 
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    denotes the N receiving samples, the M×1 vector 
         [0000]    
       
         
           
             x 
             = 
             
               [ 
               
                 
                   
                     
                       x 
                       1 
                     
                   
                 
                 
                   
                     
                       x 
                       2 
                     
                   
                 
                 
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       x 
                       M 
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    denotes the M transmit symbols, the N×M matrix 
         [0000]    
       
         
           
             H 
             = 
             
               [ 
               
                 
                   
                     
                       h 
                       11 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       h 
                       
                         1 
                          
                         M 
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋱ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       h 
                       
                         N 
                          
                         1 
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       h 
                       NM 
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    denotes the channel state information and the N×1 vector 
         [0000]    
       
         
           
             n 
             = 
             
               [ 
               
                 
                   
                     
                       n 
                       1 
                     
                   
                 
                 
                   
                     
                       n 
                       2 
                     
                   
                 
                 
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       n 
                       N 
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    denotes the receiver additive noise. For generality, all these vectors and matrices are assumed complex-valued. 
         [0006]    In a typical communications system, each transmit symbol is selected from a pre-designated set of complex-valued, discrete points, termed the symbol constellation. For example, the Quadrature and Amplitude Modulation (QAM) defines transmit symbols from a rectangular grid where QAM-16 modulation contains 16 constellation points, QAM-64 contains 64 constellation points, so on and so forth. This invention uses the notation, Ω, to denote the set of the constellation points in an underlining communications system. 
         [0007]    Given the receiving sample vector y and a proper estimation of the channel state information matrix H through training sequences, the maximum likelihood symbol detector is designed to search for the transmit symbol vector x over all possible constellation points, and the corresponding optimization problem is defined as: 
         [0000]    
       
         
           
             
               min 
               
                 { 
                 
                   
                     
                       x 
                       m 
                     
                     ∈ 
                     Ω 
                   
                   , 
                   
                     m 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   ⋯ 
                    
                   
                       
                   
                   , 
                   M 
                 
                 } 
               
             
              
             
               
                  
                 
                   y 
                   - 
                   Hx 
                 
                  
               
               2 
               2 
             
           
         
       
     
         [0000]    where ∥·∥ 2  denotes the 2-norm of the enclosed operand. As each element of the symbol vector x is constrained to be selected from discrete points on the symbol constellation map, the solution to this maximum likelihood detector is non-trivial, especially when M is large. 
         [0008]    The respective least-squares problem can be defined by removing the requirement for the elements of x to be discrete points on the symbol constellation map: 
         [0000]    
       
         
           
             
               
                 min 
                 
                   { 
                   
                     
                       x 
                       m 
                     
                     , 
                     
                       m 
                       = 
                       1 
                     
                     , 
                     2 
                     , 
                     ⋯ 
                      
                     
                         
                     
                     , 
                     M 
                   
                   } 
                 
               
                
               
                 
                    
                   
                     y 
                     - 
                     Hx 
                   
                    
                 
                 2 
                 2 
               
             
              
             
                 
             
           
         
       
     
         [0000]    For this least-squares problem, the optimal solution is well-known and has a closed-form expression as: 
         [0000]        x   ls =( H   †   H ) −1   H   †   y    
         [0000]    where H †  denotes the Hermitian transpose of H. Without loss of generality, the matrix H † H is assumed invertible and well-conditioned in this invention as the use of “diagonal loading” technique by adding a small positive number to the diagonal elements of H † H can be practically applied to precondition the H † H matrix to avoid ill-conditioned issue. 
         [0009]    The simplest approximation to the maximum likelihood solution is to “quantize” each element of x ls  to the nearest (measured by Euclidean distance) discrete points on the symbol constellation map: 
         [0000]      {circumflex over (x)} ls =Q[x ls ] 
         [0000]    where Q[·] denotes the element-wise quantization of the enclosed vector to the nearest constellation point. When M&gt;1, the “quantized” least-squares solution, {circumflex over (x)} ls , rarely provides a satisfactory solution compared to the true maximum likelihood optimal solution for detecting the transmit symbols from the receiving samples corrupted by the channel and noise effect. Hence, there is a practical need to design a true maximum likelihood optimized symbol detector in a communications system, and this task is non-trivial, especially for a MIMO communications system. 
         [0010]    This invention reformulates the maximum likelihood problem by including the unquantized least-squares solution x ls  to the minimization objective function as: 
         [0000]    
       
         
           
             
               min 
               
                 { 
                 
                   
                     
                       x 
                       m 
                     
                     ∈ 
                     Ω 
                   
                   , 
                   
                     m 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   ⋯ 
                    
                   
                       
                   
                   , 
                   M 
                 
                 } 
               
             
              
             
               { 
               
                 
                   
                      
                     
                       y 
                       - 
                       
                         Hx 
                         ls 
                       
                     
                      
                   
                   2 
                   2 
                 
                 + 
                 
                    
                   
                     
                       H 
                       ( 
                       
                         x 
                         - 
                         
                           x 
                           ls 
                         
                       
                        
                     
                     2 
                     2 
                   
                   } 
                 
               
             
           
         
       
     
         [0000]    which can be derived by use of the following property for the least-squares solution: 
         [0000]        H   † ( y−Hx   ls )=0 
         [0000]    Note that the first term in the above reformulated maximum likelihood problem is a constant with respect to the symbol vector x and can be removed from the minimization objective function. Hence, the maximum likelihood problem can be further reformulated as: 
         [0000]    
       
         
           
             
               min 
               
                 { 
                 
                   
                     
                       x 
                       m 
                     
                     ∈ 
                     Ω 
                   
                   , 
                   
                     m 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   ⋯ 
                    
                   
                       
                   
                   , 
                   M 
                 
                 } 
               
             
              
             
                
               
                 
                   H 
                   ( 
                   
                     x 
                     - 
                     
                       x 
                       ls 
                     
                   
                    
                 
                 2 
                 2 
               
             
           
         
       
     
         [0011]    Let C be an arbitrary M×M unitary matrix, the maximum likelihood problem can now be readily transformed into a linearly constrained minimization problem: 
         [0000]    
       
         
           
             
               min 
               w 
             
              
             
               
                  
                 Aw 
                  
               
               2 
               2 
             
           
         
       
     
         [0000]    subject to M linear constraints given by: 
         [0000]      C † w=f 
         [0000]      where 
         [0000]      A=HC †   
         [0000]    
       
      
       f=x−x 
       ls  
      
     
         [0000]    and the M elements of the symbol vector x belong to the discrete constellation points: 
         [0000]      {x m  ε Ω, m=1,2, . . . , M}
 
         [0012]    Note that the transmit symbol vector x and the least-squares solution x ls  now appears in the form of the constraint values f in the linear constraint specification for this reformulated maximum likelihood problem. In this invention, the choice of the constraint matrix C is not unique and is only required to be unitary, i.e., C † =C −1 . Some practically useful choices of the constraint matrix C can be as simple as the identify matrix, I, or an unitary matrix derived from the Singular Value Decomposition (SVD) of H or the QR decomposition of H † : 
         [0000]    
       
         
           
             A 
             = 
             
               { 
               
                 
                   
                     
                       H 
                       , 
                     
                   
                   
                     
                       
                         C 
                         = 
                         I 
                       
                       , 
                     
                   
                   
                     
                       H 
                       = 
                       HI 
                     
                   
                 
                 
                   
                     
                       S 
                       , 
                     
                   
                   
                     
                       
                         C 
                         = 
                         
                           V 
                           † 
                         
                       
                       , 
                     
                   
                   
                     
                       
                         H 
                         = 
                         
                           USV 
                           † 
                         
                       
                       , 
                     
                   
                 
                 
                   
                     
                       
                         R 
                         † 
                       
                       , 
                     
                   
                   
                     
                       
                         C 
                         = 
                         
                           Q 
                           † 
                         
                       
                       , 
                     
                   
                   
                     
                       
                         H 
                         † 
                       
                       = 
                       QR 
                     
                   
                 
               
             
           
         
       
     
         [0013]    The above linear constraint formulation defines a full set of M linear constraints over the M-dimensional space with the corresponding constraint values specified by the differences of the transmit symbol vector x and the least-squares solution x ls , denoted by the vector f. Under this linear constraint minimization framework, this invention utilizes a successive linear constraint exchange scheme that formulates a sequence of linearly constrained minimization subproblems by selecting a reduced set of linear constraints from the full set of M constraints and by assigning proper constraint values to these selected constraints to allow the solutions to these subproblems, combined with certain quantization and mapping operations, to converge to the optimal maximum likelihood estimate of the transmit symbol vector x at the receiver side. Specifically, the core computational unit for this invention includes closed-form computation of solutions to linearly-constrained minimization subproblems, quantization of these subproblem solutions to the nearest constellation points and mapping of the quantized subproblem solutions to their respective neighboring symbol vectors confined to the pivoting property delineated in this invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]      FIG. 1  illustrates the maximum likelihood symbol detector in a MIMO communications system; 
           [0015]      FIG. 2  illustrates the quantization of an M-dimensional complex-valued vector u to an M-dimensional symbol vector x having elements specified by a symbol constellation map; 
           [0016]      FIG. 3  illustrates the augmentation process (augmentizer) for mapping an i-dimensional seed symbol vector x I     i    into an M-dimensional augmented symbol vector x, and the deaugmentation process (deaugmentizer) for mapping the M-dimensional augmented symbol vector x back to the i-dimensional seed symbol vector x I     i    and the (M-i)-dimensional seed complementary symbol vector x I     m−i   . 
           [0017]      FIG. 4  illustrates the mapping of a symbol vector x to its neighboring symbol vector  x  confined to the pivoting property; 
           [0018]      FIG. 5  illustrates the basic Augmentizer-Pivotizer Unit (APU); 
           [0019]      FIG. 6  illustrates an embodiment of the maximum likelihood symbol detector that has M branches with each branch consisting of a maximum likelihood estimation fired up by 1-dimensional seed symbol block; 
           [0020]      FIG. 7  illustrates an embodiment of the maximum likelihood estimation fired up by 1-dimensional seed symbol block for the m-th branch of the maximum likelihood symbol detector; 
           [0021]      FIG. 8  illustrates the APU with feedback; 
           [0022]      FIG. 9  illustrates the APU with seed duality. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0023]    A shown in  FIG. 1 , the receiver of a MIMO wireless communications system  1  with N antennas consists of a Radio Frequency (RF) to Analog Baseband Down Conversion block  10  to convert the N antenna output from RF to N analog baseband signals; N Analog-to-Digital Converters  11  to sample the N baseband analog signals into N streams of digital samples; a Digital Front-End Processing block  12  to perform digital baseband signal front-end processing such as automatic gain control, carrier and timing synchronization, etc.; and a Maximum Likelihood Symbol Detector  13  to estimate the M transmit symbols {x 1 , x 2 , . . . , x m } from the N digital samples {y 1 , y 2 , . . . , y N } at every symbol period of the communications system. This invention discloses apparatus and methods to implement the maximum likelihood symbol detector  13  that is applicable but not limited to the MIMO communications system  1 . 
         [0024]    This invention partitions the M-dimensional symbol vector x into two distinct i-dimensional symbol vector, x I     i   , and (M−i)-dimensional symbol vector, x I     M−i   , specified by the selection of two sets of mutually exclusive indices, I i  and I M−i : 
         [0000]        x   I     i     =x ( I   i ),  x   I     M−i     =x ( I   M−i ) 
         [0000]        I   i    ∪ I   M−i ={1,2,  . . . , M}   
         [0000]        I   i  ∩ I M−i =Ø
 
         [0000]    where I i  contains i indices and I M−i  contains (M−i) indices with i selected as an integer between I and M. The order of the indices in these two index sets has no significance in deriving the maximum likelihood detector and can be assumed in ascending order without loss of generality. For example, for M=8 and i=3 and the M-dimensional symbol vector given by: 
         [0000]    
       
         
           
             x 
             = 
             
               [ 
               
                 
                   
                     
                       x 
                       1 
                     
                   
                 
                 
                   
                     
                       x 
                       2 
                     
                   
                 
                 
                   
                     
                       x 
                       3 
                     
                   
                 
                 
                   
                     
                       x 
                       4 
                     
                   
                 
                 
                   
                     
                       x 
                       5 
                     
                   
                 
                 
                   
                     
                       x 
                       6 
                     
                   
                 
                 
                   
                     
                       x 
                       7 
                     
                   
                 
                 
                   
                     
                       x 
                       8 
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    When the two mutually exclusive index sets are chosen as I i ={1, 3, 5} and I M−i ={2, 4, 6, 7, 8}, the two reduced dimensional symbol vectors are given by: 
         [0000]    
       
         
           
             
               
                 x 
                 
                   I 
                   i 
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         x 
                         1 
                       
                     
                   
                   
                     
                       
                         x 
                         3 
                       
                     
                   
                   
                     
                       
                         x 
                         5 
                       
                     
                   
                 
                 ] 
               
             
             , 
             
                 
             
              
             
               
                 x 
                 
                   I 
                   
                     M 
                     - 
                     i 
                   
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         x 
                         2 
                       
                     
                   
                   
                     
                       
                         x 
                         4 
                       
                     
                   
                   
                     
                       
                         x 
                         6 
                       
                     
                   
                   
                     
                       
                         x 
                         7 
                       
                     
                   
                   
                     
                       
                         x 
                         8 
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
         [0025]    With this partition, this invention establishes a procedure to construct an M-dimensional symbol vector x from a given i-dimensional symbol vector x I     i    by solving a linearly-constrained minimization problem with i linear constraints and quantizing the solution to the nearest constellation points to generate the (M−i)-dimensional symbol vector x I     M−i   , and then concatenating x I     i    and x I     M−i    together to form x. The i-dimensional symbol vector x I     i    used as the input in this generation procedure is termed the seed symbol vector, the induced (M−i)-dimensional symbol vector x I     M−i    is termed the seed complementary symbol vector and the output M-dimensional symbol vector x is term the augmented symbol vector. In particular, the linearly-constrained minimization problem is defined as: 
         [0000]    
       
         
           
             
               min 
               w 
             
              
             
               
                 w 
                 † 
               
                
               
                 A 
                 † 
               
                
               Aw 
             
           
         
       
     
         [0000]    subject to i linear constraints on w, given by: 
         [0000]    
       
      
       C 
       I 
       
         i 
       
       † 
       w=x 
       I 
       
         i 
       
       −x 
       ls,I 
       
         i  
       
      
     
         [0000]      where 
         [0000]        C   I     i     =C (:,  I   i ) 
         [0000]    consists of the i columns of C indexed by I i  and 
         [0000]        x   ls,I     i     =x   ls ( I   i ) 
         [0000]    contains the i elements of x ls  indexed by I i . Note that the matrix C and vector x ls  are the constraint matrix and least-squares solution as defined in the SUMMARY OF THE INVENTION Section of this manuscript of the invention. 
         [0026]    A closed-form solution for the optimal w to this linearly-constrained minimization problem is well-known and given by: 
         [0000]        w   I     i     =C   I     i     f   I     i     −C   I     M−i   ( C   I     M−i     †   A   †   AC   I     M−i   ) −1   C   I     M−i     †   A   †   AC   I     i     f   I     i      
         [0000]      where 
         [0000]    
       
      
       f 
       I 
       
         i 
       
       =x 
       I 
       
         i 
       
       −x 
       ls,I 
       
         i  
       
      
     
         [0000]      and 
         [0000]        C   I     M−i     =C (: ,  I   M−i ) 
         [0000]    contains the (M−i) columns of C indexed by I M−i . Define the vector u I     M−i    as: 
         [0000]        u   I     M−i     =C   I     M−i     †   w   I     i     +x   ls,I     M−i   =−( C   I     M−i     †   A   †   AC   I     M−i   ) −1   C   I     M−i     †   A   †   AC   I     i     f   I     i     +x   ls,I     M−i    
 
         [0000]      where 
         [0000]        x   ls,I     M−i     =x   ls ( I   M−i ) 
         [0000]    contains the (M−i) elements of x ls  indexed by I M−i . The (M−i)-dimensional symbol vector x I     M−i    is generated by quantizing u I     M−i    element-wise to the nearest constellation points: 
         [0000]        x   I     M−i     =Q[u   I     M−i   ] 
         [0000]    where the quantizer Q[·]  2  denotes the quantization of each element of the enclosed vector to the nearest constellation point  20  with a pre-defined constellation map  21  as illustrated in  FIG. 2 . 
         [0027]    Note that when computing C I     M−i     †   w   I     i    in the above derivation the unitary property of the C matrix is applied, i.e., C I     M−i     †   C   I     i   =0 and C I     M−i     † C I     M−i   =I. As illustrated in  FIG. 3 , this procedure of generating the M-dimensional augmented symbol vector x from the i-dimensional seed symbol vector x I     i    is referred to as the augmentation process in the description of this invention and is represented by a block termed the augmentizer  30  which consists of the minimization  301 , quantization  302  and concatenation  303  steps; The reverse process of generating x I     i    and x I     M−i    back from (I i , x) is referred to as the deaugmentation process and is represented by a block termed the deaugmentizer  31  as illustrated in  FIG. 3 . Note that the augmented symbol vector x is uniquely determined by (I i , x I     i   ), (A, C, x ls ) and the symbol constellation map Ω. 
         [0028]    This invention delineates another procedure to map an M-dimensional symbol vector x to its neighboring symbol vector of the same dimension, denoted by  x =P[x], that satisfies the following property: By using any combination of (M−1) elements of  x  as an (M−1)-dimensional seed symbol vector, the remaining 1-element of  x  is the corresponding seed complementary symbol vector. The symbol vector  x  that satisfies this property is termed a pivoting symbol vector. In other words, the pivoting symbol vector  x  is an augmented symbol vector generated by using any combination of (M−1) elements of  x  as an (M−1)-dimensional seed symbol vector. Note that this generation must hold true for all M possible combinations of selecting (M−1) elements out of  x  where the order of the (M−1) selected elements is irrelevant. 
         [0029]    A systematic procedure illustrated in  FIG. 4  is applied to map an arbitrarily given M-dimensional symbol vector x to its neighboring pivoting symbol vector  x . As shown in  FIG. 4 , this procedure is referred to as the pivoting procedure in the description of this invention and represented as a block termed the pivotizer  4 . This pivoting procedure starts with a symbol vector x and an iteration variable k set to 0 as the initialization condition. In each iteration, the iteration variable k is modulo by M and increment by 1  40 ; the index set I M−1  is selected as taking the index k out from the M indices {1, 2, . . . , M}  41  and is used to form  x   I     M−1    from x  42 ; the augmentizer  30  constructs  x  based on the input (I M−1 ,  x   I     M−1   ); if this  x  equals x and the equality condition holds true for M consecutive iterations where k has looped through 1 to M  43 , the procedure terminates with  x  found to be the neighboring pivoting symbol vector to the original x  45 ; otherwise, x is replaced by  x   44  and another iteration starts with the iteration variable k modulo by M and increment by 1  40 . It should be apparent to those skilled in the art that the above pivoting procedure is only illustration of specific embodiment of the pivotizer. Any modified pivoting procedures should fall in the scope of this invention provided that the outcome of the procedure is a symbol vector that satisfies the pivoting property as define in this invention. For example, the arrangement of selecting the index k out from the M indices {1, 2, . . . , M} from 1 to M in ascending order is shown in  FIG. 4 , whereas descending order or any other index selection order is also applicable provided that the index k is looped through the overall M indices. 
         [0030]    As illustrated in  FIG. 5 , a computational unit is constructed by combining the augmentizer  30  and pivotizer  40  together and is referred to as the Augmentizer-Pivotizer Unit (APU)  5 . This APU is used as the core computational unit in the embodiment of this invention to compute for the optimal maximum likelihood transmit symbols given the receiving samples at the receiver side. 
         [0031]    As shown in  FIG. 6 , an embodiment of this invention employs M-branch of digital logic, which can be implemented as electronic circuit or computer program, to detect the maximum likelihood M-dimensional symbol vector, denoted by x ML . Each branch is used to generate a sequence of symbol vector estimates such that the estimates from one or more of these branches converge to x ML . To fire up the search procedure for the M-branch in  FIG. 6 , an initial estimate of x ML  is required. A convenient way to generate this initial estimate x(0) is to compute the least-squares estimate and apply direct quantization on each element of the least-squares estimate to its nearest constellation point  60 , i.e., 
         [0000]        x (0)= Q[x   ls ] 
         [0000]    Given H and y, the computation of this initial estimate is relatively simple and straightforward. Any other choices of initial estimate are also applicable to this search procedure in the embodiment of this invention. 
         [0032]    Specifically, the maximum likelihood symbol detector  6  starts with x(n)=x(0)  60  and uses the vector-to-scalar splitter  61  to separate the M elements of x(n) into M branches where each branch is fired up with the corresponding element of x(n). For the m-th branch, the 1-dimensional symbol vector x m (n) is used to fire up the maximum likelihood estimate block  7  to generate the M-dimensional symbol vector x m (n+1). The Best Estimate Selection block  62  is then applied to select the “best” estimate out of {x m (n+1), m=1,2, . . . , M} from the M branches and the resulting best estimate is denoted by x(n+1). A symbol vector is deemed “better” than another symbol vector provided that the error (or objective) function, ∥H(x−x ls )∥ 2   2 , associated with this symbol vector is smaller. The best estimate for this iteration, x(n+1), is compared to that for the last iteration, x(n)  63 ; if it is better, a better estimate has been found and x(n) is replaced by x(n+1)  64  to start another iteration of search; otherwise, the search procedure terminates with the “best” estimate output selected as x(n)  65 . 
         [0033]    In an embodiment of this invention, the “maximum likelihood estimate fired up by 1-dimensional seed symbol vector” block  7  for the m-th branch in  FIG. 6  is implemented as illustrated in  FIG. 7 . For one particular iteration n in the m-th branch, the maximum likelihood estimation block  7  in  FIG. 7  starts with initializing i as 1 and the 1-dimensional seed symbol vector as (I i , x I     i   )←(m, x m (n))  71 ; the augmentizer  30  generates the M-dimensional augmented symbol vector x; an M-dimensional to (i+1)-dimensional vector splitter  72  is then applied to map x into (M−i) pairs of (i+1)-dimensional seed symbol vectors (I i+1   (l) , x I     i+1     (l) ) defined as: 
         [0000]    
       
         
           
             
               
                 I 
                 
                   i 
                   + 
                   1 
                 
                 
                   ( 
                   l 
                   ) 
                 
               
               = 
               
                 { 
                 
                   
                     I 
                     i 
                   
                   , 
                   
                     
                       I 
                       
                         M 
                         - 
                         i 
                       
                     
                      
                     
                       ( 
                       l 
                       ) 
                     
                   
                 
                 } 
               
             
             , 
             
                 
             
              
             
               and 
                
               
                   
               
                
               
                 
                   x 
                   
                     I 
                     
                       i 
                       + 
                       1 
                     
                   
                   
                     ( 
                     l 
                     ) 
                   
                 
                  
                 
                   [ 
                   
                     
                       
                         
                           x 
                           
                             I 
                             i 
                           
                         
                       
                     
                     
                       
                         
                           
                             x 
                             
                               I 
                               
                                 m 
                                 - 
                                 i 
                               
                             
                           
                            
                           
                             ( 
                             l 
                             ) 
                           
                         
                       
                     
                   
                   ] 
                 
               
             
           
         
       
     
         [0000]    for l=1,2, . . . , M−i; each one of these (I i+1   (l) , x I     i+1     (l) ) is fed into an APU  73  to compute for a pivoting symbol vector  x   (l) , respectively; for i=1, the i-th dimensional seed vector (I i , x I     i   ) is also fed into an APU  74  to compute for a pivoting symbol vector  x ; the Best Estimate Selection block  75  then selects the best estimate from these pivoting symbol vectors and the output is denoted as  x   min ; for i=1, the output for this branch is temporarily assigned as: x m (n+1)← x   min    76 ; as i progresses from 1 to M−1,  x   min  is compared with the x m (n+1) computed for (i−1) and x m (n+1) for i is updated as  x   min  if  x   min  is better than x m (n+1)  76 ; the “Select (i+1)-dimensional seed symbol vector” block  77  is used to select one out of the (M−i) (i+1)-dimensional seed symbol vectors where a minimum error criterion is used to make the selection, i.e., the corresponding linearly constrained minimization subproblem for (I i+1   (l) , x I     i+1     (l) ) that yields the minimum error is selected as (I i+1 , x I     i+1   ); this seed symbol vector (I i+1 , x I     i+1   ) is then used as the input to the augmentizer  30  in  FIG. 7  to start the next loop of estimation procedure by increment i by 1 until i reaches M  78 ; when i reaches M the output for this branch in this iteration is generated as x m (n+1)  79 . 
         [0034]    Having described one embodiment of this invention, there are various modifications that can be made without departing from the scope of the invention. Several modification schemes that are applicable for deriving additional embodiments of this invention are provided below. 
         [0035]    1) The APU  5  as shown in  FIG. 5  is used to compute a pivoting symbol vector from an i-dimensional seed symbol vector with an augmentizer  30  and a pivotizer  4 . Extensions of this basic APU  5  can be derived by use of feedback as shown in  FIG. 8  and seed duality as shown in  FIG. 9 , respectively. The APU with feedback  8  in  FIG. 8  takes the pivoting symbol vector output  80  and deaugmentizes  31  it to an i-dimensional seed symbol vector to recompute a new pivoting symbol vector  30 ,  4 . This feedback can continue for a finite number of times or until the process converges, i.e., when two consecutive output pivoting symbol vectors are equal. The best pivoting symbol vector generated through this feedback process can be used as the final output of the APU. On the other hand, the APU with seed duality  9  in  FIG. 9  generates one pivoting symbol vector  x  by use of the i-dimensional seed symbol vector as in the basic APU  90 ,  91  and an additional pivoting symbol vector  z  by use of the (M−i)-dimensional seed complementary symbol vector  92 ,  93 ,  94 . More types of APU can also be derived by the mixture of using the mechanism of feedback and seed duality or any other applicable mechanism. Any type of APU that can generate one or more pivoting symbol vectors from an i-dimensional seed symbol vector can be adopted to derive additional embodiments of this invention. 
         [0036]    2) For each iteration n in the embodiment of  FIG. 6 , the embodiment has M branches corresponding to m=1,2, . . . , M. In addition, for the embodiment of each of these M branches in  FIG. 7 , there are M−1 loopback levels corresponding to i=1, 2, . . . , M−1. A sequence of pivoting symbol vectors is generated during one iteration n for the two variable loops specified by m and i. When a better pivoting symbol vector is encountered in any particular (m, i) loop, the iteration n can be terminated prematurely, without having to reach all possible (m, i) loops, by using this pivoting symbol vector as the better estimate for this iteration and proceed to the next iteration n+1. This iteration premature termination strategy can be adopted to derive additional embodiments of this invention. 
         [0037]    3) For each iteration n in the embodiment of  FIG. 6 , the embodiment has M branches corresponding to m=1,2, . . . , M. In addition, for the embodiment of each of these M branches in  FIG. 7 , there are M−1 loopback levels corresponding to i=1, 2, . . . , M−1. Over all the loops specified by the three variables (n, m, i), any two identical i-dimensional seed symbol vectors (I i , x I     i   ) to the input of the augmentizer  30  in  FIG. 7  generate the same pivoting symbol vectors at the output of the Best Estimate Selection  75  and hence all repetition of i-dimensional seed symbol vectors over (n, m, loops at the input of the augmentizer  30  can be avoided to save computation resource without performance degradation. A simple store-and-compare mechanism to keep track of all i-dimensional seed symbol vectors appearing at the input of the augmentizer  30  in  FIG. 7  can be adopted to derive additional embodiments of this invention. 
         [0038]    4) In the embodiment of  FIG. 7 , the “Select (i+1)-dimensional seed symbol vector” block  77  is used to select one out of (M−i) seed symbol vectors to pass onto the next loopback level of i+1. This block  77  can be modified to allow the selection of more than one seed symbol vectors to pass onto the next loopback level at the cost of more computational complexity. By properly buffering the output of this block  77 , the selection of more than one (i+1)-dimensional seed symbol vectors can be implemented and adopted to derive additional embodiments of this invention. In addition, besides the described minimum error selection criterion, other selection criterion can also be adopted to derive additional embodiments of this invention. 
         [0039]    5) In the embodiment of  FIG. 7 , there are (M−i) (i+1)-dimensional seed symbol vectors (I i+1   (l) , x I     i+1     (l) ) that are generated at the output of the “M-dimensional to (i+1)-dimensional vector splitter” block  72  and are fed into (M−i) APUs  73  to generate (M−i) pivoting symbol vectors  x   (l) . By selecting only a subset of these (M−i) (i+1)-dimensional seed symbol vectors to be fed into the APUs, the computational complexity can be reduced. This computational complexity reduction strategy with a proper subset selection criterion can be adopted to derive additional embodiments of this invention. 
         [0040]    The present invention has been described with specific embodiments above. However, it should be apparent to those skilled in the art that the above description is only illustration of specific embodiments and examples of the present invention. The present invention should therefor cover various modifications and variations made to the herein-described architecture and operations of the present invention, provided they fall within the scope of the present invention as defined in the following appended claims.