# Patent

## Title
Efficient optimal ML detector

## Abstract

An efficient optimal maximum-likelihood output detector reducing the complexity of demodulation/decoding computations in multiple-input multiple-output communication systems. A plurality of received signals may be combined into a plurality of combined received signals by multiplication of a matrix representing the plurality of received signals with another matrix that meets certain conditions. The plurality of combined received signals may then allow for slicing operations as well as calculation of distance metrics with significantly reduced complexity.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
The present application claims priority on the basis of the following U.S. Provisional Patent Application, the entire contents of which is herein incorporated by reference as though set forth in full: Ser. No. 60/676,132, filed on Apr. 28, 2005, and entitled “AN EFFICIENT OPTIMAL ML DETECTOR.”


BACKGROUND
This invention relates to the field of communication systems, and in particular, efficient maximum-likelihood (ML) detection for multiple-input multiple-output (MIMO) communication systems.
Wireless, as well as wired, communication systems may achieve high spectral efficiency by transmitting information over multiple antennas at the same time (i.e. simultaneously), or at about the same time, using the same frequency band. These systems are known as multiple-input multiple-output, or MIMO, systems.
One problem in designing MIMO systems is demodulating the received signals to recover transmitted bits. Typically, each received signal contains components of all transmitted signals, making demodulation more complicated than in a single-input single-output (SISO) system. To address this, many receivers employ linear equalization to separate the received signals. This approach is attractive for its low computational complexity, but it introduces a substantial performance penalty, resulting in significantly reduced data rates or ranges compared to what may otherwise be possible.
For better performance, ML detection may be used. Given a MIMO system described by r=Hx+n, where r is the received signal vector, H is the known (or estimated) channel matrix and n is additive noise, an ML detector searches over all possible transmit symbol vectors x to find the vector x which minimizes ||r−Hx||2. In a system with Nt spatial streams, each employing an M2-point constellation, this requires calculating M2Nt distance metrics. For example, in a system with two transmitted spatial streams, both transmitting 64-QAM (QAM=quadrature amplitude modulation) constellations, this method would require calculating 642=4096 distance metrics. This complexity is too costly and power-intensive for many applications.
To reduce the cost and power consumption, some systems employ sub-optimal ML schemes, such as sphere decoding. These schemes seek to reduce the amount of computation by reducing the size of the search space. Unfortunately, in exchange for reduced complexity, these schemes may sacrifice performance and/or exhibit high variance in computation times, making such schemes undesirable for many applications.
In view of the above, there is a need for improved detection techniques for MIMO systems.
SUMMARY
An apparatus and/or method for decoding multiple-input multiple-output transmissions, capable of performing optimal ML detection with reduced computational complexity, substantially as shown in and/or described in connection with at least one of the figures.



BRIEF DESCRIPTION OF THE DRAWINGS
These and other features, aspects and advantages of the present invention will be more fully understood when considered with respect to the following detailed description and accompanying drawings, wherein:
FIG. 1 is an overview diagram of one embodiment of a system of two stations communicating in accordance with the invention (while the teachings of the invention may be incorporated into both wired and wireless communication, FIG. 1 shows wireless communication);
FIG. 2 is a simplified flowchart of one embodiment of demodulation/decoding steps in accordance with the invention; and
FIG. 3 is a simplified flowchart of one embodiment of a procedure for calculating log-likelihood ratios in accordance with the invention.



DETAILED DESCRIPTION
The invention is described below, with reference to detailed illustrative embodiments. It will be apparent that the invention may be embodied in a wide variety of forms, some of which may be quite different from those of the disclosed embodiments. For example, while multiple-input multiple-output (MIMO) technology is often used in conjunction with wireless technology, the teachings of the invention may also be used in a wired system. Consequently, the specific structural and functional details disclosed herein are merely representative and do not limit the scope of the invention.
The invention described herein is capable of finding the optimal ML result with significantly reduced complexity compared to conventional schemes. Compared to conventional ML detectors, the invention described herein is capable of finding the same result with a complexity reduction on the order of a factor of M2, where M2 is the number of points in the constellation (e.g. M=8 in a 64-QAM system).
FIG. 1 shows one embodiment of a communication system including two communication stations 100, 110 communicating with each other. Stations 100, 110 may both be transceiver stations, capable of sending and receiving signals, or one could be sending only while the other only receives. Both stations could be communicating exclusively with each other or could be part of a greater communication network including other communication stations.
In the wireless multiple-input multiple-output system of FIG. 1, each station is capable of transmitting and/or receiving information via multiple antennas 101, 111, operating in the same, similar, or overlapping frequency bands. Hence, transmissions 120 between stations 100, 110 generally include a plurality of signals via multiple transmission channels. Also, the components in the system and the characteristics of the transmission channels will generally add noise, for example thermal noise and external interferences 130, to the signals during transmission.
Communication stations 100, 110 include electronic circuitry for the processing of information. Presuming that station 100 is capable of at least transmitting information, in some embodiments station 100 may generally include electronic circuitry for encoding signals 102, interleaving signals 103, symbol mapping 104 and radio frequency (RF) transmission 105. Similarly, presuming that station 110 is capable of at least receiving information, in some embodiments station 110 may generally include electronic circuitry for radio frequency reception 115, symbol detection/demodulation 114, de-interleaving 113 and decoding 112.
Referring now to FIG. 2, operations relating to the detecting/demodulating of received transmissions (e.g., block 114 in FIG. 1), particularly of received pluralities of signals in multiple-input multiple-output systems in accordance with the invention, will be described in more detail. FIG. 2 shows a descriptive flowchart of the steps followed by one embodiment of the present invention.
First, as represented by block 200, a plurality of signals is received by a communication station. The signals may be represented as a vector r. Received signal vector r relates to transmitted symbol vector x as follows:

r=Hx+n  EQUATION 1

wherein H represents the channel matrix and n represents noise.
In the case of a 2×2 multiple-input multiple output system, the above notation may be expanded to:




  
    
      
        
          [
          
            
              
                
                  r
                  1
                
              
            
            
              
                
                  r
                  2
                
              
            
          
          ]
        
        =
        
          
            
              [
              
                
                  
                    
                      h
                      11
                    
                  
                  
                    
                      h
                      12
                    
                  
                
                
                  
                    
                      h
                      21
                    
                  
                  
                    
                      h
                      22
                    
                  
                
              
              ]
            
            ⁡
            
              [
              
                
                  
                    
                      x
                      1
                    
                  
                
                
                  
                    
                      x
                      2
                    
                  
                
              
              ]
            
          
          +
          
            [
            
              
                
                  
                    n
                    1
                  
                
              
              
                
                  
                    n
                    2
                  
                
              
            
            ]
          
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        2
      
    
  




As represented by block 202, the system selects a matrix W. It is desirable to choose W such that the matrix product WH is triangular or nearly triangular, i.e. all of the elements above or below the diagonal should be zero or near zero. If n1 and n2 are uncorrelated, the matrix product WWH may preferably be diagonal or nearly diagonal, i.e., a matrix where the off-diagonal terms are zero or near zero. Here, WH represents the Hermitian transpose of the matrix W. To the extent that these conditions are not met, performance may be compromised.
In some embodiments one simple choice for a matrix W in a 2×2 multiple-input multiple output system is




  
    
      
        
          W
          =
          
            
              [
              
                
                  
                    
                      w
                      1
                    
                  
                
                
                  
                    
                      w
                      2
                    
                  
                
              
              ]
            
            =
            
              [
              
                
                  
                    
                      
                        h
                        ~
                      
                      
                        2
                        ,
                        2
                      
                    
                  
                  
                    
                      -
                      
                        
                          h
                          ~
                        
                        
                          1
                          ,
                          2
                        
                      
                    
                  
                
                
                  
                    
                      
                        h
                        ~
                      
                      
                        1
                        ,
                        2
                      
                      *
                    
                  
                  
                    
                      
                        h
                        ~
                      
                      
                        2
                        ,
                        2
                      
                      *
                    
                  
                
              
              ]
            
          
        
        ,
        
          

        
        ⁢
        
          
            where
            ⁢
            
              
            
            [
            
              
                
                  
                    
                      h
                      ~
                    
                    
                      1
                      ,
                      1
                    
                  
                
                
                  
                    -
                    
                      
                        h
                        ~
                      
                      
                        1
                        ,
                        2
                      
                    
                  
                
              
              
                
                  
                    
                      h
                      ~
                    
                    
                      2
                      ,
                      1
                    
                  
                
                
                  
                    
                      h
                      ~
                    
                    
                      2
                      ,
                      2
                    
                  
                
              
            
            ]
          
          ≡
          HP
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        3
      
    
  




In Equation 3, P represents a permutation matrix. To decode a symbol xj of a received signal (with j=1, 2), P could have the following values:




  
    
      
        P
        =
        
          {
          
            
              
                
                  [
                  
                    
                      
                        1
                      
                      
                        0
                      
                    
                    
                      
                        0
                      
                      
                        1
                      
                    
                  
                  ]
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    j
                  
                  =
                  1
                
              
            
            
              
                
                  [
                  
                    
                      
                        0
                      
                      
                        1
                      
                    
                    
                      
                        1
                      
                      
                        0
                      
                    
                  
                  ]
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    j
                  
                  =
                  2
                
              
            
          
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        4
      
    
  




However, other choices are possible for W, allowing for trade-offs between the complexity of calculating W and the resulting complexity of calculating log-likelihood ratios. These choices include, but are not limited to, the following approaches:
One approach may be to make the entry in column 1, line 1 of the matrix product WH a real number (as opposed to a complex number, i.e., a number that includes a real and an imaginary component based on the value of √{square root over (−1)}). This approach reduces the complexity of calculating distance metrics, discussed infra. Making the entry in column 1, line 1 of the matrix product WH a real number may be achieved by defining w1 as follows:




  
    
      
        
          w
          1
        
        =
        
          
            [
            
              
                
                  h
                  ~
                
                
                  2
                  ,
                  2
                
              
              ⁢
              
                
              
              -
              
                
                  h
                  ~
                
                
                  1
                  ,
                  2
                
              
            
            ]
          
          ⁢
          
            
              
              
                det
                ⁡
                
                  (
                  HP
                  )
                
              
              
            
            
              det
              ⁡
              
                (
                HP
                )
              
            
          
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        5
      
    
  




Another approach that may reduce the complexity of calculating distance metrics involves setting column 1, line 1 of the matrix product WH to a value of 1, which may be achieved by defining w1 as follows:




  
    
      
        
          w
          1
        
        =
        
          
            [
            
              
                
                  h
                  ~
                
                
                  2
                  ,
                  2
                
              
              ⁢
              
                
              
              -
              
                
                  h
                  ~
                
                
                  1
                  ,
                  2
                
              
            
            ]
          
          ⁢
          
            1
            
              det
              ⁡
              
                (
                HP
                )
              
            
          
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        6
      
    
  




Another approach may be to make the entry in the last column and line of the matrix product WH a real number. This reduces the complexity of the slicing operation, discussed infra. This condition is already true for the choice of w2 in Equation 3.
Similarly to the approach of setting column 1, line 1 of the matrix product to a value of 1, the last column and line of the matrix product WH may also be set to a value of 1. To do so, w2 may be defined as follows:




  
    
      
        
          w
          2
        
        =
        
          
            [
            
              
                
                  h
                  ~
                
                
                  1
                  ,
                  2
                
                *
              
              ⁢
              
                
              
              ⁢
              
                
                  h
                  ~
                
                
                  2
                  ,
                  2
                
                *
              
            
            ]
          
          ⁢
          
            1
            
              
                
                  
                  
                    
                      h
                      ~
                    
                    
                      1
                      ,
                      2
                    
                  
                  
                
                2
              
              +
              
                
                  
                  
                    
                      h
                      ~
                    
                    
                      2
                      ,
                      2
                    
                  
                  
                
                2
              
            
          
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        7
      
    
  




Finally, the diagonal values of the matrix W may be set to equal values to reduce the complexity of calculating distance metrics. This condition is true for the choices for matrix W suggested in Equations 3 and 5.
Referring again to FIG. 2, once a matrix W is selected, the term

||r−Hx||2  TERM 1

can, in a 2×2 multiple-input multiple output system, be represented by




  
    
      
        
          
          
            
              [
              
                
                  
                    
                      1
                      /
                      
                        
                          K
                          1
                        
                      
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      
                        
                          K
                          2
                        
                      
                    
                  
                
              
              ]
            
            ⁢
            
              (
              
                Wr
                -
                WHx
              
              )
            
          
          
        
        2
      
    
    
      
        TERM
        ⁢
        
          
        
        ⁢
        2
      
    
  




where Ki (here: i=1, 2) represent the diagonal values in the matrix product WWH. In a 2×2 multiple-input multiple-output system, K1 and K2 would represent the following entries:




  
    
      
        
          WW
          H
        
        =
        
          [
          
            
              
                
                  K
                  1
                
              
              
                0
              
            
            
              
                0
              
              
                
                  K
                  2
                
              
            
          
          ]
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        8
      
    
  




TERM 2, in turn, may be represented as




  
    
      
        
          
            1
            
              K
              1
            
          
          ⁢
          
            
              
              
                
                  y
                  1
                
                -
                
                  ax
                  1
                
              
              
            
            2
          
        
        +
        
          
            1
            
              K
              2
            
          
          ⁢
          
            
              
              
                
                  y
                  2
                
                -
                
                  bx
                  1
                
                -
                
                  cx
                  2
                
              
              
            
            2
          
        
      
    
    
      
        TERM
        ⁢
        
          
        
        ⁢
        3
      
    
  




where yi (i=1, 2) are components of vector y, which is the result of the product of matrix W and received signal vector r (block 204), i.e. y=Wr, and where a, b and c are values derived from the product of matrix W and channel matrix H as follows:




  
    
      
        WH
        =
        
          [
          
            
              
                a
              
              
                0
              
            
            
              
                b
              
              
                c
              
            
          
          ]
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        9
      
    
  




When searching for the minimum value of TERM 3 over x2, the search may be limited to the subterm

|y2−bx1−cx2|2  TERM 4

as x2 does not appear anywhere in the remainder of TERM 3. However, the minimum value of TERM 4 over x2 may also be determined by use of a slicing operation:

minx2|y2−bx1−cx2|2=|y2−bx1−Sc(y2−bx1)|2  EQUATION 10

where Sc(y) returns the constellation point closest to y/c. This operation is commonly referred to as slicing. For most constellation types (e.g. square-QAM constellations), slicing is a trivial operation, requiring little hardware or power. Slicers are well-understood and widely used in communication systems. Substitution of the minimum operation by a slicing operation reduces the complexity of calculating distance metrics Di from O ((M2)2) to O (M2), M2 being the number of points in a two-dimensional QAM constellation (block 206; see also the discussion of FIG. 3, infra).
For M2-QAM constellations, Sc(y) may be defined by Equation 11.
For M2-QAM constellations,




  
    
      
        
          
            
              S
              c
            
            ⁡
            
              (
              y
              )
            
          
          =
          
            
              c
              ⁢
              
                
              
              ⁢
              
                min
                ⁡
                
                  (
                  
                    
                      max
                      ⁡
                      
                        (
                        
                          
                            
                              2
                              ⁢
                              
                                ⌊
                                
                                  
                                    Re
                                    ⁢
                                    
                                      {
                                      
                                        y
                                        
                                          2
                                          ⁢
                                          c
                                        
                                      
                                      }
                                    
                                  
                                  +
                                  1
                                
                                ⌋
                              
                            
                            -
                            1
                          
                          ,
                          
                            
                              -
                              M
                            
                            +
                            1
                          
                        
                        )
                      
                    
                    ,
                    
                      M
                      -
                      1
                    
                  
                  )
                
              
            
            +
            
              ic
              ⁢
              
                
              
              ⁢
              
                min
                ⁡
                
                  (
                  
                    
                      max
                      ⁡
                      
                        (
                        
                          
                            
                              2
                              ⁢
                              
                                ⌊
                                
                                  
                                    Im
                                    ⁢
                                    
                                      {
                                      
                                        y
                                        
                                          2
                                          ⁢
                                          c
                                        
                                      
                                      }
                                    
                                  
                                  +
                                  1
                                
                                ⌋
                              
                            
                            -
                            1
                          
                          ,
                          
                            
                              -
                              M
                            
                            +
                            1
                          
                        
                        )
                      
                    
                    ,
                    
                      M
                      -
                      1
                    
                  
                  )
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            where
            ⁢
            
              
            
            ⁢
            
              ⌊
              •
              ⌋
            
            ⁢
            
              
            
            ⁢
            denotes
            ⁢
            
              
            
            ⁢
            the
            ⁢
            
              
            
            ⁢
            largest
            ⁢
            
              
            
            ⁢
            integer
            ⁢
            
              
            
            ⁢
            not
            ⁢
            
              
            
            ⁢
            greater
            ⁢
            
              
            
            ⁢
            than
            ⁢
            
              
            
            ⁢
            •
          
          ,
          
            
              and
              ⁢
              
                
              
              ⁢
              i
            
            ≡
            
              
                
                  -
                  1
                
              
              .
            
          
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        11
      
    
  




As shown in Equation 11, this operation has low complexity for square-QAM constellations, as it may be performed using a simple combination of scaling, truncation, and comparison operations. For non-square QAM constellations (e.g. 32-cross), the slicing operation may require additional logic, but may still be much simpler than performing an exhaustive search over M2 points. Slicers for non-square constellations are also well-understood and commonly used in communication systems.
The following formulas (collectively referred to as Equation 12) show a detailed walkthrough of how matrix W may be used to decrease the complexity of computations for calculating log-likelihoods in a 2×2 multiple-input multiple output system. Initially, assuming the system has additive white Gaussian noise where n1 and n2 are uncorrelated Gaussian variables, the max-log approximation {tilde over (L)}k of the log-likelihood ratio for bit k is defined in the first formula.




  
    
      
        
          
            
              
                
                  
                    L
                    ~
                  
                  k
                
                =
                
                ⁢
                
                  
                    1
                    
                      σ
                      2
                    
                  
                  ⁢
                  
                    (
                    
                      
                        min
                        
                          
                            x
                            |
                            
                              b
                              k
                            
                          
                          =
                          0
                        
                      
                      ⁢
                      
                        -
                        
                          min
                          
                            
                              x
                              |
                              
                                b
                                k
                              
                            
                            =
                            1
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    
                      
                      
                        r
                        -
                        Hx
                      
                      
                    
                    2
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    1
                    
                      σ
                      2
                    
                  
                  ⁢
                  
                    (
                    
                      
                        min
                        
                          
                            x
                            |
                            
                              b
                              k
                            
                          
                          =
                          0
                        
                      
                      ⁢
                      
                        -
                        
                          min
                          
                            
                              x
                              |
                              
                                b
                                k
                              
                            
                            =
                            1
                          
                        
                      
                    
                    )
                  
                
              
            
          
          
            
              
                
                ⁢
                
                  
                    
                    
                      
                        [
                        
                          
                            
                              
                                1
                                /
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      
                                    
                                    ⁢
                                    
                                      K
                                      
                                        
                                          
                                        
                                        ⁢
                                        1
                                      
                                    
                                  
                                
                              
                            
                            
                              0
                            
                          
                          
                            
                              0
                            
                            
                              
                                1
                                /
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      
                                    
                                    ⁢
                                    
                                      K
                                      
                                        
                                          
                                        
                                        ⁢
                                        2
                                      
                                    
                                  
                                
                              
                            
                          
                        
                        ]
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        (
                        
                          Wr
                          ⁢
                          
                            
                          
                          -
                          
                            
                          
                          ⁢
                          WHx
                        
                        )
                      
                    
                    
                  
                  2
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    1
                    
                      σ
                      2
                    
                  
                  ⁢
                  
                    (
                    
                      
                        min
                        
                          
                            x
                            |
                            
                              b
                              k
                            
                          
                          =
                          0
                        
                      
                      ⁢
                      
                        -
                        
                          min
                          
                            
                              x
                              |
                              
                                b
                                k
                              
                            
                            =
                            1
                          
                        
                      
                    
                    )
                  
                
              
            
          
          
            
              
                
                ⁢
                
                  (
                  
                    
                      
                        1
                        
                          
                            
                          
                          ⁢
                          
                            K
                            
                              
                                
                              
                              ⁢
                              1
                            
                          
                        
                      
                      ⁢
                      
                        
                          
                          
                            
                          
                          ⁢
                          
                            
                              y
                              
                                
                                  
                                
                                ⁢
                                1
                              
                            
                            ⁢
                            
                              
                            
                            -
                            
                              
                            
                            ⁢
                            
                              ax
                              
                                
                                  
                                
                                ⁢
                                1
                              
                            
                          
                          
                        
                        2
                      
                    
                    +
                    
                      
                        1
                        
                          
                            
                          
                          ⁢
                          
                            K
                            
                              
                                
                              
                              ⁢
                              2
                            
                          
                        
                      
                      ⁢
                      
                        
                          
                          
                            
                          
                          ⁢
                          
                            
                              y
                              
                                
                                  
                                
                                ⁢
                                2
                              
                            
                            ⁢
                            
                              
                            
                            -
                            
                              
                            
                            ⁢
                            
                              bx
                              
                                
                                  
                                
                                ⁢
                                1
                              
                            
                            ⁢
                            
                              
                            
                            -
                            
                              
                            
                            ⁢
                            
                              cx
                              
                                
                                  
                                
                                ⁢
                                2
                              
                            
                          
                          
                        
                        2
                      
                    
                  
                  )
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          Then
          ,
          
            for
            ⁢
            
              
            
            ⁢
            all
            ⁢
            
              
            
            ⁢
            bits
            ⁢
            
              
            
            ⁢
            k
            ⁢
            
              
            
            ⁢
            represented
            ⁢
            
              
            
            ⁢
            entirely
            ⁢
            
              
            
            ⁢
            in
            ⁢
            
              
            
            ⁢
            symbol
            ⁢
            
              
            
            ⁢
            
              x
              1
            
            ⁢
            
              :
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                
                  
                    L
                    ~
                  
                  k
                
                =
                
                ⁢
                
                  
                    1
                    
                      σ
                      2
                    
                  
                  ⁢
                  
                    (
                    
                      
                        min
                        
                          
                            
                              x
                              1
                            
                            |
                            
                              b
                              k
                            
                          
                          =
                          0
                        
                      
                      ⁢
                      
                        -
                        
                          min
                          
                            
                              
                                x
                                1
                              
                              |
                              
                                b
                                k
                              
                            
                            =
                            1
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    
                      min
                      
                        x
                        2
                      
                    
                    ⁢
                    
                      (
                      
                        
                          
                            1
                            
                              K
                              1
                            
                          
                          ⁢
                          
                            
                              
                              
                                
                                  y
                                  1
                                
                                -
                                
                                  ax
                                  1
                                
                              
                              
                            
                            2
                          
                        
                        +
                        
                          
                            1
                            
                              K
                              2
                            
                          
                          ⁢
                          
                            
                              
                              
                                
                                  y
                                  1
                                
                                -
                                
                                  bx
                                  1
                                
                                -
                                
                                  cx
                                  2
                                
                              
                              
                            
                            2
                          
                        
                      
                      )
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    1
                    
                      σ
                      2
                    
                  
                  ⁢
                  
                    (
                    
                      
                        min
                        
                          
                            
                              x
                              1
                            
                            |
                            
                              b
                              k
                            
                          
                          =
                          0
                        
                      
                      ⁢
                      
                        -
                        
                          min
                          
                            
                              
                                x
                                1
                              
                              |
                              
                                b
                                k
                              
                            
                            =
                            1
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      
                        
                          1
                          
                            K
                            1
                          
                        
                        ⁢
                        
                          
                            
                            
                              
                                y
                                1
                              
                              -
                              
                                ax
                                1
                              
                            
                            
                          
                          2
                        
                      
                      +
                      
                        
                          1
                          
                            K
                            2
                          
                        
                        ⁢
                        
                          
                            min
                            
                              
                                
                              
                              ⁢
                              
                                x
                                
                                  
                                    
                                  
                                  ⁢
                                  2
                                
                              
                            
                          
                          ⁢
                          
                            
                              
                              
                                
                                  y
                                  2
                                
                                -
                                
                                  bx
                                  1
                                
                                -
                                
                                  cx
                                  2
                                
                              
                              
                            
                            2
                          
                        
                      
                    
                    )
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    1
                    
                      σ
                      2
                    
                  
                  ⁢
                  
                    (
                    
                      
                        min
                        
                          
                            
                              x
                              1
                            
                            |
                            
                              b
                              k
                            
                          
                          =
                          0
                        
                      
                      ⁢
                      
                        -
                        
                          min
                          
                            
                              
                                x
                                1
                              
                              |
                              
                                b
                                k
                              
                            
                            =
                            1
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      
                        
                          1
                          
                            K
                            1
                          
                        
                        ⁢
                        
                          
                            
                            
                              
                                y
                                1
                              
                              -
                              
                                ax
                                1
                              
                            
                            
                          
                          2
                        
                      
                      +
                      
                        
                          1
                          
                            K
                            2
                          
                        
                        ⁢
                        
                          
                            
                            
                              
                                y
                                2
                              
                              -
                              
                                bx
                                1
                              
                              -
                              
                                
                                  S
                                  c
                                
                                ⁡
                                
                                  (
                                  
                                    
                                      y
                                      2
                                    
                                    -
                                    
                                      bx
                                      1
                                    
                                  
                                  )
                                
                              
                            
                            
                          
                          2
                        
                      
                    
                    )
                  
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            and
            ⁢
            
              
            
            ⁢
            
              where
              ⁡
              
                (
                
                  
                    min
                    x
                  
                  ⁢
                  
                    -
                    
                      min
                      y
                    
                  
                
                )
              
            
            ⁢
            A
            ⁢
            
              
            
            ⁢
            is
            ⁢
            
              
            
            ⁢
            shorthand
            ⁢
            
              
            
            ⁢
            for
            ⁢
            
              
            
            ⁢
            
              
                min
                x
              
              ⁢
              A
            
          
          -
          
            
              min
              y
            
            ⁢
            A
          
        
      
    
    
      
        EQUATION
        ⁢
        
          
        
        ⁢
        12
      
    
  




In the last formula for {tilde over (L)}k in Equation 12, the search over all possible values of x2 was replaced with the slicing operation Sc(y). As pointed out before, finding a value of x2 that minimizes the term |y2−bx1−cx2|2 thereby becomes a trivial task: the minimum value may be found by finding the constellation point closest to (y2−bx1), which, in turn, may be found by using the slicing operation. This reduces the computational complexity by O (M2) compared to conventional ML schemes.
In one embodiment, the candidate constellation point x1,i which minimizes Di is found and returned as a hard output (block 209).
In another embodiment, the calculated log-likelihood {tilde over (L)}k is provided as soft output (block 210). This soft output may then be used in subsequent decoding, as indicated by block 112 in FIG. 1.
FIG. 3 shows a flowchart illustrating one embodiment of a procedure for finding the soft output {tilde over (L)}k. In the flow chart, the set of valid constellation points is represented by Xj,i 300, with i=1 . . . M2 for each transmit stream j=1 . . . 2. The value Di 302 represents a distance metric for each candidate constellation point Xj,i 300. The result Lj,k 304 is the log-likelihood ratio for bit position k of transmit stream j.
Accordingly, the procedure of the exemplary embodiment shown in the flowchart in FIG. 3 involves iteration through an outer loop j=1 . . . 2 (commencing at block 308 and looping as represented by line 314) and two sequential inner loops i=1. . . M2 (commencing at block 310 and looping as represented by line 316) and k=1 . . . 2 log2(M) (commencing at block 306 and looping as represented by line 318).
As represented by blocks 320, 322, 324 the P matrix may be selected as discussed above in conjunction with Equation 4. Then, the matrix W may be calculated as discussed above in conjunction with Equation 3.
Calculation of distance metrics Di 302 as well as the slicing operation 312 may both be performed within the first inner loop. Here, this first inner loop has M2 iterations. Therefore, the number of distance metric computations may be reduced by a factor of M2 compared to conventional ML schemes.
Block 304 and loop 318 demonstrate the calculation of a soft output, for those embodiments in which a soft output is computed. For each bit position k represented in symbol xj, the minimum distance metric over all constellations points with bit k equal to 0 may be found. Likewise, the minimum distance metric over all constellation points with bit k equal to 1 may be found. These two values are combined by subtraction to produce a soft output. When scaled properly by an estimate of the noise variance, this soft output may represent the log-likelihood ratio of bit k.
In those embodiments in which a soft output is not computed (i.e. uncoded systems or systems with hard-input decoders), the calculation of the soft output represented by block 304 and loop 318 may be omitted. Instead, the global minimum over all distance metrics may be found, where the constellation point associated with said minimum represents the hard decision.
For simplicity of notation, the description herein assumed the same constellation for both transmit streams. However, in general, the present invention accommodates different constellations (i.e., different bit rates) on different transmit streams. The description above also only lays out a limited set of embodiments of the invention and it should be understood that other embodiments may be implemented in accordance with the teachings of the invention. In addition, modifications may be made to the embodiments described above that are still within the scope of the invention.
The teachings herein may be incorporated into a variety of systems. For example, the teachings may be incorporated into a wireless communications system such as one that supports one or more RF wireless standards including, without limitation, IEEE 802.11a, 802.11g, 802.11n, etc. The teachings herein also may be incorporated into other wireless or wired systems.
In one embodiment of the invention, a multiple-input multiple-output transmissions is detected by: receiving a plurality of signals; combining the plurality of signals to produce a plurality of combined signals, wherein the plurality of combined signals includes a first spatial stream, representing a series of first transmitted constellation points, with each transmitted constellation point being a member of a first set of candidate constellation points, and where each candidate constellation point represents a contribution to the plurality of combined signals, and a second spatial stream, representing a series of second transmitted constellation points, with each second transmitted constellation point being a member of a second set of candidate constellation points; and subtracting the contribution to the plurality of combined signals and calculating a distance metric using a slicer to determine a closest candidate constellation point among the second set of candidate constellation points for each candidate constellation point of the first set of candidate constellation points.
In one aspect of the invention, the plurality of signals are combined by multiplying the plurality of signals with a matrix W, wherein the product of a Hermitian transposition of the matrix W and the matrix W equals a diagonal or nearly diagonal matrix. The product of this matrix W and a channel matrix H may be triangular or nearly triangular.
In another aspect of the invention, the candidate constellation points of the first set of candidate constellation points represents bits. For each bit B represented in candidate constellation points of the first set of candidate constellation points: a first minimum distance metric is found among the distance metrics, wherein a value of bit B of the candidate constellation point associated with the first minimum distance metric is zero; a second minimum distance metric among the distance metrics is found, wherein a value of bit B of the candidate constellation point associated with the second minimum distance metric is one; and soft output is produced by calculating a difference between the first minimum distance metric and the second minimum distance metric.
In yet another aspect of the invention, one candidate constellation point is found among the first set of candidate constellation points to produce a hard output, wherein the distance metric calculated for the one candidate constellation point is a minimum distance metric among the distance metrics calculated for the first set of candidate constellation points.
In another embodiment of the invention, multiple-input multiple-output transmissions are detected by receiving a plurality of signals and combining the plurality of signals to produce a plurality of combined signals, the plurality of combined signals being usable to calculate distance metrics using a slicing operation.
In one aspect of the invention, the plurality of signals are combined by multiplying a vector representing the plurality of signals or a matrix representing the plurality of signals with another matrix W, wherein a product of a Hermitian transposition of the matrix W and the matrix W equals a diagonal or nearly diagonal matrix. The matrix W may be selected such that a product of the matrix W and a channel matrix H is triangular or nearly triangular.
In another aspect of the invention, a plurality of distance metrics is calculated using the plurality of combined signals. The plurality of distance metrics may be calculated using a slicing operation. A candidate constellation point may be identified that minimizes a value of a corresponding distance metric among the plurality of distance metrics. Log-likelihood ratios may be calculated for a plurality of bits represented in one or more transmitted symbols using the plurality of distance metrics, the transmitted symbols having been transmitted using the plurality of signals.
It should further be appreciated that the various components and features described herein may be incorporated in a system independently of the other components and features. For example, a system incorporating the teachings herein may include various combinations of these components and features. Thus, not all of the components and features described herein may be employed in every such system.
Different embodiments of the invention may include a variety of hardware and software processing components. In some embodiments of the invention, hardware components such as controllers, state machines and/or logic are used in a system constructed in accordance with the invention. In some embodiments, code such as software or firmware executing on one or more processing devices may be used to implement one or more of the described operations.
While certain exemplary embodiments have been described above in detail and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive of the invention. In particular, it should be recognized that the teachings of the invention apply to a wide variety of systems and processes. It will thus be recognized that various modifications may be made to the illustrated and other embodiments of the invention described above, without departing from the inventive scope. In view of the above it will be understood that the invention is not limited to the particular embodiments or arrangements disclosed, but is rather intended to cover any changes, adaptations or modifications which are within the scope and spirit of the invention.

## Claims

1. A method of detecting multiple-input multiple-output (MiMO) transmissions, comprising:
performing by one or more processors and/or circuits integrated within a single chip:
receiving a plurality of signals;
combining the plurality of signals to produce a plurality of combined signals, the plurality of combined signals including: a first spatial stream, representing a series of first transmitted constellation points, each transmitted constellation point being a member of a first set of candidate constellation points, and each candidate constellation point representing a contribution to the plurality of combined signals, and a second spatial stream, representing a series of second transmitted constellation points, each second transmitted constellation point being a member of a second set of candidate constellation points;
and for each candidate constellation point of the first set of candidate constellation points: subtracting the contribution to the plurality of combined signals, and calculating a distance metric using a slicer to determine a closest candidate constellation point among the second set of candidate constellation points.

2. The method of claim 1, wherein the plurality of signals are combined by multiplying the plurality of signals with a matrix W, wherein the product of a Hermitian transposition of the matrix W and the matrix W equals a diagonal or nearly diagonal matrix.

3. The method of claim 2, wherein the product of the matrix W and a channel matrix H is triangular or nearly triangular.

4. The method of claim 1, wherein each of the candidate constellation points of the first set of candidate constellation points represents bits, comprising calculating a soft output for each of the bits using the distance metrics.

5. The method of claim 4, comprising: for each bit B
represented in candidate constellation points of the first set of candidate constellation points:
finding a first minimum distance metric among the distance metrics, wherein a value of bit B of the candidate constellation point associated with the first minimum distance metric is zero;
finding a second minimum distance metric among the distance metrics wherein a value of bit B of the candidate constellation point associated with the second minimum distance metric is one; and
producing the soft output by calculating a difference between the first minimum distance metric and the second minimum distance metric.

6. The method of claim 1, comprising finding one candidate constellation point among the first set of candidate constellation points, wherein the distance metric calculated for the one candidate constellation point is a minimum distance metric among the distance metrics calculated for the first set of candidate constellation points, to produce a hard output.

7. The method of claim 3, wherein each of the candidate constellation points of the first set of candidate constellation points represents bits, comprising:
for each bit B represented in candidate constellation points of the first set of candidate constellation points:
finding a first minimum distance metric among the distance metrics, wherein a value of bit B of the candidate constellation point associated with the first minimum distance metric is zero;
finding a second minimum distance metric among the distance metrics, wherein a value of bit B of the candidate constellation point associated with the second minimum distance metric is one; and
producing a soft output by calculating a difference between the first minimum distance metric and the second minimum distance metric.

8. A method of detecting multiple-input multiple-output transmissions, comprising:
performing by one or more processors and/or circuits integrated within a single chip:
receiving a plurality of signals;
combining the plurality of signals to produce a plurality of combined signals, the plurality of combined signals being usable to calculate distance metrics using a slicing operation;
calculating a plurality of distance metrics using the plurality of combined signals; and
calculating log-likelihood ratios for a plurality of bits represented in one or more transmitted symbols using the plurality of distance metrics, the transmitted symbols having been transmitted using the plurality of signals.

9. A detector, configured to detect multiple-input multiple-output transmissions, comprising:
a sigal receiver, configured to receive a plurality of signals;
a signal combiner, configured to combine the plurality of signals to produce a plurality of combined signals, the plurality of combined signals being usable to calculate distance metrics using a slicing operation;
a distance metrics calculator, configured to calculate a plurality of distance metrics using the plurality of combined signals; and
a log-likelihood calculator, configured to calculate log-likelihood ratios for a plurality of bits represented in one or more transmitted symbols using the plurality of distance metrics, the transmitted symbols having been transmitted using the plurality of signals.