Patent Publication Number: US-8121220-B1

Title: Apparatus and method for reduced complexity maximum likelihood MIMO detection

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     Embodiments of the present invention generally relate to wireless communication systems, and more particularly to maximum likelihood detection in multiple-input multiple-output (MIMO) communication systems. 
     2. Description of the Related Art 
     To increase the transmission capacity and spectral efficiency of wireless communication, various wireless standards have proposed MIMO transmission schemes that use an array of transmit and receive antennas to carry multiple independent signals simultaneously and in the same bandwidth. Each of the separate transmit signals may be detected jointly from a set of receive signals using an optimal maximum likelihood (ML) detection scheme; however, the complexity of a complete exhaustive search ML detection method may increase exponentially with the number of antennas and the size of the signal constellation. As such, some implementations may limit MIMO detection to a sub-optimal search over a space of possible solutions that may require fewer computations but also may result in lower performance. 
     Example sub-optimal MIMO detection algorithms include linear zero-forcing (ZF) and minimum mean-squared-error (MMSE) receivers that may multiply the receive signals by an inverse of the channel response to cancel the interference effect of the channel, thereby extracting the separate transmit signals from the composite receive signals. While more computationally efficient than ML detection, such algorithms may amplify the additive noise reducing the performance of the system. Another sub-optimal MIMO algorithm may use non-linear decision feedback detection to decide each of the transmitted signals sequentially, thereby cancelling the interference of each detected transmit symbol successively from the composite received signal; however, incorrect decisions may propagate through the detection process resulting again in reduced performance. 
     Another sub-optimal non-linear detection algorithm, known as K-best sphere decoding, may perform a non-exhaustive search for the transmitted signal by limiting the number of candidate solutions kept after each stage of a multiple stage search. For each stage, K candidate solutions resulting from the previous stage may be extended to K*M candidate solutions, where M may equal the size of the signal constellation, and a cumulative metric may be calculated for each of the resulting K*M candidate solutions. The K*M candidate solutions may then be sorted by the cumulative metric, with only the “best” K candidate solutions retained for the next stage of calculation. While the number of total computations for non-exhaustive K-best sphere decoding may grow more slowly than exhaustive ML detection, the sorting process may require significant memory and may lack parallelism to speed the operation in chip implementations. 
     In addition to a hard decision detection result, i.e. a “best” estimate of the transmit symbols, wireless MIMO communication systems may use error correction codes that may require a soft decision reliability metric for each bit of the estimated transmit symbols. Because the K-best sphere decoding algorithm limits the search space, the set of candidate solutions at the final stage may not contain candidates for each possible bit value (0 or 1) in the set of estimated transmit symbols, as may be required for a soft decision reliability metric to input to a subsequent error correction decoder. 
     Thus, there exists a need for a reduced complexity maximum likelihood MIMO detection scheme that may provide near optimal performance, may parallelize for efficient implementation, and may provide both hard decision and soft decision results for a wireless MIMO communication system. 
     SUMMARY OF THE INVENTION 
     In a multiple-input multiple-output communication system, a transmit symbol vector and a set of soft decision metrics may be estimated using a reduced complexity maximum likelihood (ML) detection method based on a receive symbol vector and a QR decomposition of a set of permuted channel matrices derived from an estimated channel matrix. The reduced complexity ML detection method may use a different permuted channel matrix to estimate each transmit symbol in a transmit symbol vector and may estimate each transmit symbol as a value chosen from a subset of a signal constellation. A set of error distances may be calculated for the estimated transmit symbol vector, each error distance calculated choosing a different value from the signal constellation subset for a transmit symbol in the estimated transmit symbol vector. A pair of minimum error distances may be selected from the set of error distances calculated, one for each bit value of a bit in the estimated transmit symbol of the transmit symbol vector, and a soft decision metric may be calculated using the pair of minimum error distances. In some embodiments, the transmit symbols of a transmit symbol vector and the soft decision metrics for each transmit symbol may be determined in parallel. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a multiple-input multiple-output (MIMO) communication system including a maximum likelihood (ML) detection block. 
         FIG. 2  illustrates a prior art ML detection block using a QR decomposition of an estimated channel matrix. 
         FIG. 3  illustrates a simplified ML detector using a set of parallel error distance calculation units. 
         FIG. 4  illustrates a ML detection block using a set of parallel simplified ML detectors and QR decompositions of a set of permuted estimated channel matrices. 
         FIG. 5  illustrates a simplified ML detector as in  FIG. 3  modified for use in the ML detection block of  FIG. 4 . 
         FIG. 6  illustrates an example error distance calculation unit of  FIG. 5  for a multiple-input two-output communication system. 
         FIG. 7  illustrates an example error distance calculation unit of  FIG. 5  for a multiple-input three-output communication system. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  illustrates a MIMO system  100  with n transmit antennas  105  and m receive antennas  106 , which may be represented by the set of linear equations
 
 z=Hs+v    (1)
 
where H may be an m×n channel matrix  104 , s=[s 1  . . . s n ] T  may be an n×1 column vector  101  of complex-valued transmit symbols, z=[z 1  . . . z m ] T  may be an m×1 column vector  102  of complex-valued receive symbols, and v may be an m×1 column vector of complex-valued additive white Gaussian noise. Each complex-valued transmit symbol s i  in the transmit symbol vector  101  s may be taken from a QAM constellation C of size M, i.e. the transmit symbol vector  101  s may be taken from the 2n-dimensional constellation C×C . . . xC=C n . In some embodiments, the channel matrix  104 
 
                   H   =     [           h     1   ,   1           …         h     1   ,   n               ⋮       ⋱       ⋮             h     m   ,   1           …         h     m   ,   n             ]             (   2   )               
may contain a complex-valued channel response h i,j  that may represent a channel transfer characteristic between the j th  transmit antenna and the i th  receive antenna; while in other embodiments the channel matrix H  104  may contain an “equivalent” complex-valued channel response h i,j  that may represent a combined signal processing and channel transfer characteristic connecting the j th  transmit symbol to the i th  receive symbol. In a 2×2 MIMO communication system, for example, the sum of the first and second symbol may be transmitted by one antenna, and the difference of the first and second symbol may be transmitted by the other antenna. The channel matrix H  104  may be estimated at the receiver by a number of known techniques.
 
     A MIMO maximum likelihood (ML) detector  108  at the receiver may determine an estimate of the transmit symbol vector  103  ŝ by maximizing P(s=ŝ|z), the probability that the transmit symbol vector  101  s equals the estimated transmit symbol vector  103  ŝ given the receive symbol vector  102  z. For the MIMO system  100  described by equation (1), the exhaustive search maximum likelihood (ML) algorithm may search over all possible 2n-dimensional constellation points in C n  for the point that minimizes the error distance between the actual receive symbol vector  102  z and an estimated receive symbol vector Hŝ. 
                     argmin       s   ^     ∈     C   n         ⁢            z   -     H   ⁢     s   ^              2             (   3   )               
The complexity of an exhaustive “brute force” search for the estimated transmit symbol vector  103  ŝ may depend exponentially on the number of transmit antennas n and the size of the signal constellation C.
 
     As indicated in  FIG. 2  a MIMO ML detection block  108 A may use a QR decomposition of the channel matrix  104  H,
 
H=QR   (4)
 
where Q may be an m×m unitary orthogonal matrix, i.e. Q * Q=I, with * indicating the conjugate transpose operation and I an m×m identity matrix, and R may be an m×n upper triangular matrix with diagonal elements that may contain positive real numbers. While the QR decomposition of the channel matrix  104  H may not be unique, preferentially, some embodiments may use a QR decomposition in which the diagonal elements of R are positive and real valued. In some embodiments, where the number of receive antennas m&gt;n exceeds the number of transmit antennas, the last m−n rows of R may be zero. Expanding the matrices Q and R as Q=[Q 1  Q 2 ] and
 
             R   =     [           R   1               0       (     m   -   n     )     ⁢   xn             ]           
and substituting equation (4) into equation (3) the maximum likelihood estimate may become
 
                       argmin       s   ^     ∈     C   n         ⁢            z   -         [           Q   1           Q   2           ]     ⁡     [           R   1               0       (     m   -   n     )     ⁢   xn             ]       ⁢     s   ^              2       =           argmin       s   ^     ∈     C   n         ⁢                Q   1   *     ⁢   z     -       R   1     ⁢     s   ^              2       +              Q   2   *     ⁢   z          2       =       argmin       s   ^     ∈     C   n         ⁢            y   -       R   1     ⁢     s   ^              2                 (   5   )               
where y=Q 1   * z may be a modified receive symbol vector  201  and Q 1  may be an m×n unitary matrix  206  consisting of the leftmost n columns of Q. Note that the term ∥Q *   2 z∥ 2  in equation (5) may not depend on the estimated transmit symbol vector  103  ŝ and thus may be eliminated from the minimization. Because R 1  may be an n×n upper triangular matrix  205 , equation (5) may be rewritten as
 
                       argmin       s   ^     ∈     C   n         ⁢            y   -       R   1     ⁢     s   ^              2       =           ∑     i   =   1     n     ⁢           ⁢              y   i     -       ∑     j   =   1     n     ⁢           ⁢       r     i   ,   j       ⁢       s   ^     j                2       ≡       ∑     i   =   1     n     ⁢           ⁢       ed   i     ⁡     (         s   ^     i     ,   …   ⁢           ,       s   ^     n       )           =     ED   ⁡     (     s   ^     )                 (   6   )               
where y i  may denote the i th  entry in the modified receive symbol vector  201  y, r i,j  may denote the entry in the i th  row and j th  column of the matrix R 1    205  and ŝ j  may denote the j th  entry in the estimated transmit symbol vector  103  ŝ. At the i th  stage of an iterative detection process, an incremental error distance metric ed i (ŝ i , . . . , ŝ n ) may depend on a current transmit symbol to be estimated ŝ and on all previous decisions of estimated transmit symbols ŝ i+1  to ŝ n . A maximum likelihood algorithm may minimize a total error distance metric ED(ŝ), which may be a sum of the n incremental error distance metrics, with one incremental metric calculated at each stage of an iterative detection process.
 
     Note that while Equation (6) uses a 2-norm, ∥x∥ 2 =(Re(x)) 2 +(Im(x)) 2 , for the incremental error distance metric ed i (ŝ i , . . . , ŝ n ) and the total error distance metric ED(ŝ), the error distance metrics may also be calculated using a 1-norm, ∥x∥=√{square root over (Re(x)) 2 +(Im(x)) 2 )}{square root over (Re(x)) 2 +(Im(x)) 2 )}, or an approximation thereof. One example approximation for the 1-norm may be ∥x∥=A+B/4 where A=max{|Re(x)|,|Im(x)|} and B=min{|Re(x)|,|Im(x)|}. For consistency, the remainder of the description continues, without limiting embodiments of the invention, to use the 2-norm. 
     Equation (6) may consist of n non-negative terms that may be minimized iteratively starting from the n th  term ed n (ŝ n )=∥y n −r n,n ŝ n ∥ 2 , which may depend only on estimating the n th  transmit symbol ŝ n . Using an estimate for the n th  transmit symbol ŝ n , the (n−1) th  term in equation (6) may then depend only on estimating the (n−1) th  transmit symbol ŝ n−1  as the (n−1) th  term may equal
 
 ed   n−1 ( ŝ   n−1   , ŝ   n )=∥ y   n−1   −r   n−1,n−1   ŝ   n−1   −r   n−1,n   ŝ   n ∥ 2    (7)
 
Similarly the k th  term may depend only on estimating the k th  transmit symbol ŝ k  given estimates for the other transmit symbols ŝ k+1  . . . ŝ n  where the k th  term may equal
 
                       ed   k     ⁡     (         s   ^     k     ,   …   ⁢           ,       s   ^     n       )       =              y   k     -       r     k   ,   k       ⁢       s   ^     k       -       ∑     j   =     k   +   1       n     ⁢           ⁢       r     k   ,   j       ⁢       s   ^     j                2             (   8   )               
As the estimate for the k th  transmit symbol ŝ k  may affect the estimates for all subsequently estimated transmit symbols ŝ k−1  to ŝ 1 , an incorrect estimate may propagate errors through the rest of a detection process. A robust detection process may improve the error rate by searching over and retaining more possible solutions for symbols decided earlier in the process. Several innovations to improve robustness while simplifying a maximum likelihood search are presented as follows.
 
     As the first estimated transmit symbol ŝ n  may affect all subsequent transmit symbol estimates ŝ n−1  to ŝ 1 , in some embodiments of the invention, all possible values for the estimate of the n th  transmit symbol ŝ n  may be examined in the first stage and may be retained in all subsequent stages of detection to ensure a higher probability of propagating a correct decision throughout the detection process.  FIG. 3  illustrates this concept detailing a simplified ML detector  305  using multiple values for the n th  estimated transmit symbol ŝ n . Rather than limit the maximum likelihood search to a single value for the n th  estimated transmit symbol ŝ n , as done in conventional successive interference calculation detection methods, up to a total of M parallel error distance calculation units (EDCUs)  301  may be used, each one of the EDCUs  301  starting with one of the possible values of the n th  estimated transmit symbol ŝ n . 
     Within a given EDCU,  301  each subsequent stage, beyond a first stage that may set a single value for the n th  estimated transmit symbol ŝ n , may limit the number of candidate solutions retained to bound the search space thereby constraining the total computational complexity. At the end of all stages, the M parallel EDCUs  301  may output a set of total error distances {ED 1 (ŝ:ŝ n =“1”), . . . , ED M (ŝ:ŝ n =“M”)} with each error distance ED i (ŝ:ŝ n =“i”)  304  associated with a candidate solution for the estimated transmit symbol vector ŝ  103  having one of the M possible values for the n th  estimated transmit symbol ŝ n . Because all possible values for the estimated transmit symbol ŝ n  are included, the log likelihood ratio (LLR) calculation blocks  302  that may follow the EDCUs  301  in the simplified ML detector  305  may generate a LLR soft decision metric  303  for each possible bit in the n th  estimated transmit symbol ŝ n . 
     To limit the search complexity, some embodiments of the invention may start with a subset S of the constellation C that may contain less than M possible transmit symbols for the estimated transmit symbol ŝ n . To guarantee a LLR soft decision metric may be calculated for each possible bit value in ŝ n , for a square QAM constellation C of size M=2 2q , the subset S may be a square constellation of size K=(2 q−1 +1) 2  or larger. Note that a square constellation of size (2 q−1 ) 2  may be too small to guarantee a candidate solution for an LLR metric calculation, as at least one of the four quadrants (+, +), (+, −), (−, +) or (−, −) of the constellation C may contain symbols all having a bit with the same value of ‘0’ or ‘1’. With a subset S of size K, the simplified ML detector  305  in  FIG. 3  may reduce from M to K parallel EDCUs  301 , which may reduce the complexity of the ML detection significantly. For example, with a 256-QAM constellation C, a reduced size subset S of 81-QAM may be chosen, which may reduce the number of parallel EDCUs  301  by more than 75%. The size of the subset S may depend on the dimension of the channel matrix H and on a signal-to-noise ratio that may characterize the communication channel performance characteristics. An appropriate value for K may be determined by a performance simulation of the communication system. For a 2×2 and 3×3 MIMO communication system using a 64-QAM constellation C, a 36-QAM subset S may be used with minimal performance degradation. 
     In some embodiments, a subset S may be selected as a square constellation centered about a linear equalization solution for a transmit symbol, i.e. a set of points in a square subset S that minimizes the n th  error distance term ed n (ŝ n )=∥y n −r n,n ŝ n ∥ 2  in Equation (6). One possible linear equalization solution is a zero forcing (ZF) solution for a ZF estimated transmit symbol ŝ n,ZF =y n /r n,n . Thus, a simplified ML detector  305  may use a different subset S of the constellation C depending on the value of the modified received symbol y n  scaled by the positive real diagonal element r n,n . A simple lookup table may be used to determine which subset to select based on the value of ŝ n,ZF . For an example 36-QAM subset S of a 64-QAM constellation C, the real part (and similarly the imaginary part) of the symbols in the subset S may be determined as in Equation (9).
 
Re{ ŝ   n,ZF }&lt;−1 −7≦Re{ S}≦+ 3
 
−1≦Re{ ŝ   n,ZF }&lt;1 −5≦Re{ S}≦+ 5
 
Re{ ŝ   n,ZF }≧1 −3≦Re{ S}≧+ 7   (9)
 
     Following the set of EDCUs  301  in each simplified ML detector  305 , a log likelihood ratio calculation block  302  determines a soft decision metric  303 , i.e. a reliability metric, for each bit x k  in the estimated transmit symbol ŝ n . For a square constellation C of size M=2 2q , each estimated transmit symbol ŝ n  contains q “in-phase” bits and q “quadrature” bits. The log likelihood ratio (LLR) value of the k th  bit x k  may be written as 
                     LLR   ⁡     (       x   k     ❘   y     )       =       ln   ⁢       P   ⁡     (       x   k     =     1   ❘   y       )         P   ⁡     (       x   k     =     0   ❘   y       )           =     ln   ⁢         ∑       s   ^     ∈     S   1                 ⁢           ⁢       P   ⁡     (     y   ❘     s   ^       )       ⁢     P   ⁡     (     s   ^     )               ∑       s   ^     ∈     S   0                 ⁢           ⁢       P   ⁡     (     y   ❘     s   ^       )       ⁢     P   ⁡     (     s   ^     )                         (   10   )               
where S 1  may be the set of all estimated symbol vectors in the constellation C n  for which the k th  bit x k  in the estimated transmit symbol ŝ n  may be “1”. Similarly S 0  may be the complementary set of all estimated symbol vectors in the constellation C n  for which the k th  bit x k  in the transmit symbol ŝ n  may be “0”. Using the well known MAX-LOG-MAP approximation, equation (10) may be simplified to
 
                     LLR   ⁡     (       x   k     ❘   y     )       ≈       ln   ⁢           ⁢       max       s   ^     ∈     S   1         ⁢     exp   ⁢     {     -     ED   ⁡     (     s   ^     )         }           -     ln   ⁢           ⁢       max       s   ^     ∈     S   0         ⁢     exp   ⁢     {     -     ED   ⁡     (     s   ^     )         }             ≈         min       s   ^     ∈     S   1         ⁢     ED   ⁡     (     s   ^     )         -       min       s   ^     ∈     S   0         ⁢     ED   ⁡     (     s   ^     )                   (   11   )               
The set of error distances {ED 1 (ŝ:ŝ n =“1”), . . . , ED M (ŝ:ŝ=“M”)}  304  produced by the EDCUs  301  in the simplified ML detector  305  may be used to calculate the LLR for each bit x k  in the estimated transmit symbol ŝ n  using equation (11).
 
     The log likelihood ratio (LLR) calculation for a soft decision decoding that may follow the error distance calculation in the maximum likelihood detection receiver  108  may require an error distance metric for each possible bit x k  of each estimated transmit symbol ŝ i  for i=n to 1. The maximum likelihood search described above may provide such soft decision metrics  303  for each bit value x k  of the estimated transmit symbol ŝ n  but may not guarantee such soft decision metrics for the other estimated transmit symbols ŝ n−1  to ŝ 1  due to limiting the number of candidate solutions retained in the intermediate stages of the maximum likelihood calculation. Some embodiments of the invention may overcome this deficiency by using n parallel maximum likelihood searches, each search starting with a different estimated transmit symbol  402  ŝ k  for k=n to 1 chosen from the estimated transmit symbol vector ŝ as illustrated in  FIG. 4  and described below. 
     Note that in equation (1), the set of linear equations describing the MIMO communication system, may be written without loss of generality as
 
 z=HP   k   P   k   s+v=H   k   s   k   +v    (12)
 
where P k  may be an n×n permutation matrix  408  with an n th  (i.e. last) column containing a “1” in the k th  row and zeroes in all other rows. A permuted transmit symbol vector s k =P k s=[π(s 1 , . . . , s k−1 , s k+1 , . . . , s n ), s k ] T  may thus contain a k th  transmit symbol s k  in the last row. The channel matrix H  104  may also be permuted by the permutation matrix  408  P k  resulting in a permuted channel matrix  404  H k =HP k , which may be represented in a QR decomposition form as
 
H k =Q k R k    (13)
 
The same maximum likelihood search process described above for the channel matrix H may be repeated using the QR decomposition of the permuted channel matrix  404  H k ; however, the search may start with all possible values for the estimated transmit symbol  402  ŝ k  rather than all possible values for the estimated transmit symbol  402  ŝ n .
 
     The rightmost expression in equation (5) may become equivalently 
                     argmin         s   ^     k     ∈     C   n         ⁢              y   k     -       R   1   k     ⁢       s   ^     k              2             (   14   )               
where y k =Q 1   k* z may be a modified receive symbol vector  401 . As with the maximum likelihood search described for the original channel matrix  104  H, an ML search for the permuted estimated transmit symbol vector ŝ k  in equation (14), using a QR decomposition of the permuted channel matrix  404  H k , may result in a soft decision result for each possible bit value of the estimated transmit symbol  402  ŝ k . Using n parallel searches based on n different permuted channel matrices  404  H k , for k=1 to n, each individual search starting with all possible values for the estimated transmit symbol  402  ŝ k , the combined search may result in a set of soft decision metrics  107  covering each bit value of the entire estimated transmit symbol vector  103  ŝ. Each of the simplified ML detectors  305  may use M EDCUs  301  that cover all possible values in the constellation C or may use K EDCUs  301  that cover a subset S of possible values. The subsets S used for each simplified ML detector  205  may differ depending on the value of the ZF estimated transmit symbol ŝ n,ZF =y n /r n,n  as described earlier. Within the MIMO ML detector  108 B, each of the n parallel simplified ML detectors  305  provide an estimated transmit symbol  402  ŝ k  and a soft decision metric  403  LLR k  using a structure as shown in  FIG. 3  and repeated in  FIG. 5  using the appropriate “permuted” inputs.
 
     While there may be (n−1)! different permutation matrices P k  that may produce a permuted channel matrix  404  H k  and a permuted estimated transmit symbol vector ŝ k  with an estimated transmit symbol  402  ŝ k  in the last row, simulation indicates minimal difference in performance choosing any one of them. In some embodiments, the permutation matrix P k  may be chosen, wherein the (n−1) leftmost columns of the permuted channel matrix  404  H k  may be ordered in increasing column rank (which may provide a performance advantage). 
     Each EDCU  301  in  FIG. 5  may produce one error distance for one candidate solution. Therefore, the complexity of the simplified maximum likelihood detection method may grow linearly with the number of EDCUs  301 , i.e. the size of the constellation C. This technique contrasts with prior art maximum likelihood detection that may grow exponentially with the size of the constellation C. 
       FIGS. 6 and 7  illustrate embodiments of an error distance calculation unit (EDCU)  301  for m×2 and m×3 MIMO communication systems. In general, an error distance calculated by the j th  EDCU  301  within the simplified ML detector  305  using the permuted channel matrix  404  H k  may determine a minimum error distance for a permuted estimated transmit symbol vector ŝ k  with an estimated transmit symbol ŝ k  equal to the “j th ” symbol, denoted as σ j , in the constellation C. To simplify the notation, and without loss of generality, consider the non-permuted channel matrix  104  H n =H, where the estimated transmit symbol  402  ŝ n  may already be in the “correct” last row of the estimated transmit symbol vector  103  ŝ n =ŝ. The total error distance may be written as 
                       ED   j   n     ⁡     (     s   ^     )       =         ED   j   n     ⁡     (       s   ^     =     [         s   ^     1     ,   …   ⁢           ,       s   ^       n   -   1       ,         s   ^     n     =     σ   j         ]       )       =       ∑     i   =   1     n     ⁢           ⁢       ed   i     ⁡     (         s   ^     i     ,   …   ⁢           ,       s   ^       n   -   1       ,         s   ^     n     =     σ   j         )                   (   15   )               
For the case n=2 illustrated in  FIG. 6 
 
 ED   j   2 ( ŝ )=ed 1 ( ŝ   1   , ŝ   2 =σ j )+ ed   2 ( ŝ   2 =σ j )=∥ y   1   −r   11   ŝ   1   −r   12 σ j ∥ 2   +∥y   2   −r   22 σ j ∥ 2    (16)
 
The second term in equation (16) (marked as  601  ed 2 (σ j ) in  FIG. 6 ) may be a constant given the value σ j , and the element r 11  may be positive real. Thus, the minimum error distance  501  for ED j   2  may be achieved by setting the estimated transmit symbol  401  ŝ 1  to the closest symbol in the constellation C to the complex value (y 1 −r 12 σ j )/r 11 =c 1 /r 11  as indicated in block  602  of  FIG. 6 .
 
For the case n=3 illustrated in  FIG. 7 
 
 ED   j   3 ( ŝ )= ed   1 ( ŝ   1   , ŝ   2   , ŝ   3 =σ j )+ ed   2 ( ŝ   2   , ŝ   3 =σ j )+ ed   3 ( ŝ   3 =σ j )
 
=∥ y   1   −r   11   ŝ   1   −r   12   ŝ   2   −r   13 σ j ∥ 2   +∥y   2   −r   22   ŝ   2   −r   23 σ j ∥ 2   +∥y   3   −r   33 σ j ∥ 2    (17)
 
The minimum error distance  501  for ED j   3  may be achieved by setting the estimated transmit symbol  401  ŝ 2  to the closest symbol in the constellation C to the complex value (y 2 −r 23 σ j )/r 22  followed by setting the estimated transmit symbol  401  ŝ 1  to the closest symbol in the constellation C to the complex value (y 1 −r 12  ŝ 2 −r 13 σ j )/r 11  as indicated by blocks  701  and  702  in  FIG. 7 .
 
     In some embodiments a simple binary search algorithm may be used to determine a closest symbol to a complex value c n /r n,n  in the constellation C for the estimated transmit symbol  401  ŝ n  as required in block  602  of  FIG. 6  and in blocks  701  and  702  of  FIG. 7 . As the diagonal element r n,n  may be positive real, the real and imaginary part of the estimated transmit symbol ŝ n  may be calculated independently in parallel. For a square constellation C of size M=2 2q  based on odd integer values, the real (or imaginary) part of a constellation point s may be specified by q “bit” values {b 0 , . . . , b q−1 } as 
                     Re   ⁢     {   s   }       =         (     -   1     )       b   0       ⁢     (         ∑     i   =   1       q   -   1       ⁢           ⁢       b   i     ⁢     2     q   -   i           +   1     )               (   18   )               
The sign bit may be determined as b 0 =sgn{c n }, where sgn{x}=1 if x&lt;1 and sgn{x}=0 if x≧0. The remaining bits may be determined iteratively from k=1 to q−1 as
 
                     b   k     =       -   sgn     ⁢     {       Re   ⁢     {     c   n     }       -       r   11     ·       (     -   1     )       b   0       ·     (         ∑     t   =   1       k   -   1       ⁢           ⁢       b   t     ⁢     2     q   -   t           +     2     q   -   k         )         }               (   19   )               
Note that Equation (19) may consist of simple additions, subtractions and shifts by powers of 2, which may be implemented in integrated circuits efficiently.
 
     Although illustrative embodiments of the invention have been described in detail herein with reference to the accompanying figures, it is to be understood that the invention is not limited to those precise embodiments. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed. As such, many modifications and variations will be apparent. Accordingly, it is intended that the scope of the invention be defined by the following Claims and their equivalents.