# Patent

## Title
Near maximum likelihood spatial multiplexing receiver

## Abstract

This invention is related to a low-complexity MIMO detector in a wireless communication system with near optimal performance. An initial symbol estimation is performed for a received symbol vector. The soft information of the received symbol vector can be more accurately calculated using every candidate symbol vector of a combined set of candidate symbol vectors, wherein the combined set is generated based on the initial estimation. By combining aspects of both the linear detection and the ML detection, the complexity of the proposed detector becomes orders of magnitude lower than that of a ML detector, but the performance is very close to that of an ML detector.

## Background
FIELD OF THE INVENTION
The invention is related to wireless communication systems, and more particularly, to methods and apparatus of implementing low-complexity MIMO detectors in a wireless communication system with near maximum likelihood performance.
BACKGROUND OF THE INVENTION
Having evolved rapidly and steeply in the past two decades, the wireless communication systems now offer a wide variety of services such as multimedia communications, web browsing, audio and video streaming, online game playing, etc. Not surprisingly, the number of users accessing these services has also increased drastically. The resulting increase in data traffic together with the scarceness of wireless spectrum resources has made high efficiency data transmission an essential factor in the design of wireless communication systems.
The use of multiple-input-multiple-output (MIMO) techniques has thus become the new frontier of wireless communications. The MIMO technique basically employs multiple antennas at both transmitter and receiver to allow the transmission of parallel data streams over available spatial channels. Therefore, the MIMO techniques allow for high-rate data transfers and improved link quality.
The optimal MIMO detector for a wireless communication system is the maximum-likelihood (ML) detector, which seeks to minimize the average probability of error between the detected symbols and the transmitted symbols. However, designing an ML detector is equivalent to solving a non-deterministic polynomial-time (NP)-hard problem, which makes it impractical to implement due to its exponential complexity.
In practice, people have proposed different linear implementations to approximate the ML detectors so that the computational complexity is manageable. Examples of these approximation implementations include the minimum mean square error (MMSE) detectors and the zero forcing (ZF) detectors, which have conventionally been used for their low complexity. However, the performance of these conventional linear detectors drops significantly in poor channel conditions. Thus, there remains a considerable need for methods and apparatus in low-complexity MIMO detector designs that have high performance even in poor channel conditions.
SUMMARY OF THE INVENTION
The invention is directed to methods and apparatus for a low-complexity MIMO detector design in a wireless communication system with near optimal performance, even when the channel conditions are poor. To reduce the complexity, a new MIMO detector design is proposed to find an approximation to the ML problem based on the results of initial linear symbol detection. Thus by combining aspects of both the linear detection and the ML detection, the complexity of the proposed detector becomes orders of magnitude lower than that of a ML detector, yet the performance is very close to that of an ML detector. As will become apparent to those ordinarily skilled in the art upon review of the description below, the various aspects of the invention disclosed in this application allow for flexibility and low complexity in design as well as cost reduction in hardware.
In the present disclosure, the term “MIMO detector” is used as a non-limiting illustrative example of a multiple-in-multiple-out detector module that takes as input the received digital symbols from the multiple receive antennas, computes the soft information of transmitted data bits, and outputs the computed soft information to a channel decoder. The MIMO detector according to some aspect of the invention may be a standalone chip with its own storage in a receiver, or may be a module coupled to other functional modules (e.g., channel estimator, channel decoder) in a single receiver chip and share the storage with other modules. The MIMO detector according to some aspect of the invention may be completely implemented in hardware, or have part or all of its functionality performed in software.
According to an aspect of the invention, data transmitted in a broadband communication system with multiple transmit antennas and receive antennas is detected by first receiving, at a receiver of the communication system, a received symbol vector formed by received symbols where each received symbol is from one of the multiple receive antennas. The received symbol vector corresponds to transmitted symbol vector that is modulated by transmitted data bits according to a modulation scheme. Then, initial symbol estimation is performed to detect each transmitted symbol based on the received symbol vector. For each initially estimated symbol of the transmitted symbol vector, a candidate symbol set is generated. The number of candidate symbols in each of the candidate symbol set is a predetermined number. A combined set of candidate symbol vectors is then generated by using the candidate symbol sets corresponding to the initially estimated symbols. Soft information of the transmitted data bit streams is calculated using every candidate symbol vector of the combined candidate set. The transmitted data is then decoded and retrieved by a channel decoder based on the corresponding soft information.
According to another aspect of the invention, a MIMO detection apparatus for a wireless communication receiver is disclosed. The MIMO detection apparatus comprises an input port coupled to the multiple receive antennas of the receiver to receive a symbol vector, corresponding transmitted data bits. The MIMO detection apparatus further comprises a processor that performs initial symbol estimation after receiving the symbol vector, generates a combined candidate set of candidate vector according to the initially detected symbols, and further computes soft information of the transmitted data bits using every candidate symbol vector of the combined candidate set.
These and other aspects of the invention, including systems and computer program products corresponding to the above methods and apparatus, will be apparent to a person skilled in the art in view of the following drawings and detailed description.



BRIEF DESCRIPTION OF THE DRAWING
Aspects and features of the invention will become more apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures, wherein:
FIG. 1 is a conceptual block diagram of a wireless communication system to provide a context to an embodiment of the invention;
FIG. 2 is a block diagram showing a hardware implementation of a 2×2 MIMO detector according to one aspect of the invention;
FIG. 3 is a flow chart of a 2×2 MIMO detector according to one aspect of the invention;
FIG. 4 shows simulation results of the respective performance of a MIMO detector with and without the use of a combined candidate, according to an embodiment of the invention;
FIG. 5 compares the final performance of a MIMO detector according to an embodiment of the invention with that of a MMSE detector, a ZF detector and a ML detector.



DETAILED DESCRIPTION OF THE SPECIFIC EMBODIMENTS
The invention will now be described in detail with reference to the drawings, which are provided as illustrative examples of the invention so as to enable those skilled in the art to practice the invention. Notably, the figures and examples below are not meant to limit the scope of the invention to a single embodiment, but other embodiments are possible by way of interchange of some or all of the described or illustrated elements. Moreover, where certain elements of the invention can be partially or fully implemented using known components, only those portions of such known components that are necessary for an understanding of the invention will be described, and detailed descriptions of other portions of such known components will be omitted so as not to obscure the invention. Embodiments described as being implemented in software should not be limited thereto, but can include embodiments implemented in hardware, or combinations of software and hardware, and vice-versa, as will be apparent to those skilled in the art, unless otherwise specified herein.
In the present specification, an embodiment showing a singular component should not be considered limiting, rather, the invention is intended to encompass other embodiments including a plurality of the same component, and vice-versa, unless explicitly stated otherwise herein. Moreover, applicants do not intend for any term in the specification or claims to be ascribed an uncommon or special meaning unless explicitly set forth as such. Further, the invention encompasses present and future known equivalents to the known components referred to herein by way of illustration.
FIG. 1 is a block diagram that illustrates an exemplary wireless communication system with multiple transmit antennas and multiple receive antennas (MIMO system) to provide a context to an embodiment of the invention. MIMO system 100 employs Nt transmit antennas and Nr receive antennas for data transmission. MIMO system 100 consists of a MIMO transmitter 110 and a MIMO receiver 120. Transmitter 110 and receiver 120 are capable of implementing various aspects and embodiments of the invention, as described below.
Transmitter/Receiver can be implemented in an 802.11 chipset. In addition, the disclosed invention can also, for example, be applied to chipsets for other cellular standards like LTE and WiMax (802.16) as well as in any other communication system where MIMO transmission is used. Wired communications using MIMO may also implement invention disclosed herein. Those skilled in the art will understand how to implement the invention by adapting firmware or software of such chipsets under the functionality of the invention after being taught by the present disclosure.
In some embodiments, at transmitter 110, data to be transmitted is processed by a data processor (not shown) that encodes and interleaves the data based on one or more coding schemes to provide encoded data. The coding schemes are for different purposes such error detection and error correction, etc. Although most of communication systems adopt certain coding schemes for error correction, these channel coding schemes are not the claimed invention thus not further described hereafter. The encoded data is then modulated to become data symbols by one or more modulators, which may also receive pilot data that may be multiplexed with the encoded data. Typically, the pilot data is data of a known pattern and processed in a known manner thus may be used by receiver 120 to perform a number of functions such as acquisition, frequency and timing synchronization, channel estimation, coherent data demodulation and so on. There are many different modulation schemes that can be used (e.g., M-QAM, M-PSK, and so on.).
It is also contemplated that the invention is applicable where the modulation may be performed based on a single modulation scheme for all transmit antennas, one modulation scheme for each transmit antenna or each subset of transmit antennas, or one modulation scheme for each transmission channel or each group of transmission channels.
Often, orthogonal frequency division multiplexing (OFDM) (not shown) is used to mitigate inter-symbol interference between the multiple data symbols transmitted. The modulated data symbols are further OFDM modulated using an IFFT with the insertion of a cyclic prefix before they are transmitted via transmit antennas A1 through ANt over communication channel 130. This OFDM is however not necessary for the claimed invention to work.
At receiver 120 according to some aspects of the invention, the signals transmitted over communication channel 130 are received by receive antennas B1 through BNr. The received signals are OFDM demodulated by discarding the cyclic prefix and applying an FFT on the received samples on a per-carrier basis from all receive antennas. MIMO detector 122 processes these OFDM demodulated signals and generates the soft information of the transmitted data bits. Channel decoder 124 takes in the soft information and then decodes the data bits transmitted.
Although in FIG. 1 multiple connection lines (C1, C2, . . . CNt) are depicted between MIMO detector 122 and Channel decoder 124 with each line transferring the LLRs of one data symbol, persons skilled in the art will understand that it is also possible to implement the disclosed invention by connecting MIMO detector 122 and Channel decoder 124 via one line as the decoding can be performed based on one sequence of LLRs.
As an example of the above wireless system, assuming without loss of generality the number of transmit antennas Nt=2 and the number of receive antennas Nr=2, the received signal Y can be modeled as:




  
    
      
        Y
        =
        
          
            
              HX
              +
              N
            
            ⇔
            
              [
              
                
                  
                    
                      y
                      1
                    
                  
                
                
                  
                    
                      y
                      2
                    
                  
                
              
              ]
            
          
          =
          
            
              
                [
                
                  
                    
                      
                        h
                        11
                      
                    
                    
                      
                        h
                        12
                      
                    
                  
                  
                    
                      
                        h
                        21
                      
                    
                    
                      
                        h
                        22
                      
                    
                  
                
                ]
              
              ⁡
              
                [
                
                  
                    
                      
                        x
                        1
                      
                    
                  
                  
                    
                      
                        x
                        2
                      
                    
                  
                
                ]
              
            
            +
            
              [
              
                
                  
                    
                      n
                      1
                    
                  
                
                
                  
                    
                      n
                      2
                    
                  
                
              
              ]
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




Where the complex-valued channel gains h11, h12, h21, h22 of channel matrix H is known to receiver 120. As discussed above, pilot data is used to estimate channel gains. This and other techniques to estimate channel gains are well known in the art and not described in this disclosure for reason of brevity. Similarly, the noise variance can be estimated using pilot data. The known white channel additive noise n1 and n2 are complex Gaussian distributed with variance σ2.
It is further assumed without loss of generality that both transmit symbols x1 and x2 are from the same M-QAM constellation. Thus each symbol represents M transmit data bits. Accordingly, there are a total of 2M symbols in the constellation and a total of 22M possible symbol vectors. Using A to denote the symbol set and A2 to denote the symbol vector set, the transmit symbol vectors can be mathematically expressed as: XεA2{x1εA, x2εA}.
The transmit bits are denoted by bi, while b1, . . . , bM are mapped to the first symbol x1 and bM+1, . . . , b2M are mapped to the second symbol x2. The objective of a MIMO detector is to detect how likely the transmitted bits are 0s or 1s. As discussed above, one category of practical methods are linear detectors, such as the MMSE detectors or the ZF detectors. Such detectors have low complexity but the performance can be very poor in fading channels.
On the other hand, as also discussed above, a maximum likelihood (ML) detector is one of the non-linear detectors that give superior performance at the cost of very high complexity. As is well known, the maximum likelihood (ML) detector computes the soft information of transmit bits, in the form of log-likelihood ratio (LLR):




  
    
      
        
          L
          ⁢
          
            
          
          ⁢
          L
          ⁢
          
            
          
          ⁢
          
            R
            ⁡
            
              (
              
                b
                1
              
              )
            
          
        
        =
        
          
            
              min
              
                
                  
                    {
                    
                      X
                      c
                    
                    
                  
                  ⁢
                  
                    
                      
                        
                          
                            b
                            i
                          
                          =
                          0
                        
                      
                    
                    
                      
                        
                          
                            X
                            c
                          
                          ∈
                          
                            A
                            2
                          
                        
                      
                    
                  
                
                }
              
            
            ⁢
            
              
                
                  
                  
                    Y
                    -
                    
                      H
                      ⁢
                      
                        
                      
                      ⁢
                      
                        X
                        c
                      
                    
                  
                  
                
                2
              
              
                σ
                2
              
            
          
          -
          
            
              min
              
                
                  
                    {
                    
                      X
                      c
                    
                    
                  
                  ⁢
                  
                    
                      
                        
                          
                            b
                            i
                          
                          =
                          1
                        
                      
                    
                    
                      
                        
                          
                            X
                            c
                          
                          ∈
                          
                            A
                            2
                          
                        
                      
                    
                  
                
                }
              
            
            ⁢
            
              
                
                  
                  
                    Y
                    -
                    
                      H
                      ⁢
                      
                        
                      
                      ⁢
                      
                        X
                        c
                      
                    
                  
                  
                
                2
              
              
                σ
                2
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




Here, Xc=[x1c,x2c]T denotes a candidate transmit vector, {Xc|bi=0, XcεA2} the set of candidate vectors with the i-th bit being 0, and {Xc|bi=1, XcεA2} the set with the i-th bit being 1. It is obvious that the size of each set is 22M-1, which grows exponentially with respect to M.
To reduce the complexity, it is contemplated to find an approximation to Equation (2) based on the results of initial MMSE symbol detection. By combining the linear detection and the ML detector in some sense, a balance between performance and complexity can be achieved. As described below, the embodiments of the invention has a complexity that is orders of magnitude lower than that of an optimal ML detector but the performance is very close to the performance of a ML detector. The architecture and calculations of the proposed detector is optimized in a way to allow flexibility and low complexity in the hardware implementation.
According to one aspect of the invention, using the same 2×2 MIMO wireless system described before as an embodiment of a low-complexity near ML detector, the first step is to perform initial symbol detection of x1 or x2 based on a received symbol vector Y={y1, y2} using a linear MMSE detector.




  
    
      
        
          X
          mmse
        
        =
        
          
            
              
                
                  (
                  
                    
                      
                        H
                        *
                      
                      ⁢
                      H
                    
                    +
                    
                      
                        σ
                        2
                      
                      ⁢
                      
                        I
                        
                          2
                          ×
                          2
                        
                      
                    
                  
                  )
                
                
                  -
                  1
                
              
              ⁢
              
                H
                *
              
              ⁢
              Y
            
            ⇔
            
              [
              
                
                  
                    
                      x
                      1
                      mmse
                    
                  
                
                
                  
                    
                      x
                      2
                      mmse
                    
                  
                
              
              ]
            
          
          =
          
            
              
                
                  (
                  
                    
                      
                        [
                        
                          
                            
                              
                                h
                                11
                                *
                              
                            
                            
                              
                                h
                                21
                                *
                              
                            
                          
                          
                            
                              
                                h
                                12
                                *
                              
                            
                            
                              
                                h
                                22
                                *
                              
                            
                          
                        
                        ]
                      
                      ⁡
                      
                        [
                        
                          
                            
                              
                                h
                                11
                              
                            
                            
                              
                                h
                                12
                              
                            
                          
                          
                            
                              
                                h
                                21
                              
                            
                            
                              
                                h
                                22
                              
                            
                          
                        
                        ]
                      
                    
                    +
                    
                      [
                      
                        
                          
                            
                              σ
                              2
                            
                          
                          
                            0
                          
                        
                        
                          
                            0
                          
                          
                            
                              σ
                              2
                            
                          
                        
                      
                      ]
                    
                  
                  )
                
                
                  -
                  1
                
              
              ⁡
              
                [
                
                  
                    
                      
                        h
                        11
                        *
                      
                    
                    
                      
                        h
                        21
                        *
                      
                    
                  
                  
                    
                      
                        h
                        12
                        *
                      
                    
                    
                      
                        h
                        22
                        *
                      
                    
                  
                
                ]
              
            
            ⁡
            
              [
              
                
                  
                    
                      y
                      1
                    
                  
                
                
                  
                    
                      y
                      2
                    
                  
                
              
              ]
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




Where the initially detected symbols x1mmse and x2mmse can be detected according to equation (3) above. Then a candidate symbol set can be constructed to only include those candidate symbols (constellation points) which are ‘close’ enough to the initially detected symbols x1mmse and x2mmse. For a 2×2 MIMO detector, there are a total of two sets, which can, be denoted as below:




  
    
      
        
          V
          ⁡
          
            (
            
              x
              1
              mmse
            
            )
          
        
        ≡
        
          {
          
            
              x
              1
              c
            
            ⁢
            
              
              
                
                  
                    
                    
                      
                        x
                        1
                        c
                      
                      -
                      
                        x
                        1
                        mmse
                      
                    
                    
                  
                  2
                
                <
                
                  ɛ
                  1
                
              
              }
            
          
        
      
    
    
      
        (
        4
        )
      
    
  








  
    
      
        
          V
          ⁡
          
            (
            
              x
              2
              mmse
            
            )
          
        
        ≡
        
          {
          
            
              x
              2
              c
            
            ⁢
            
              
              
                
                  
                    
                    
                      
                        x
                        2
                        c
                      
                      -
                      
                        x
                        2
                        mmse
                      
                    
                    
                  
                  2
                
                <
                
                  ɛ
                  2
                
              
              }
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




To simplify the calculation of the two candidate symbol sets, the initial MMSE estimates x1mmse and x2mmse are hard sliced to the transmitted QAM constellation sets. In addition, the candidate symbol sets can be pre-computed and stored in look up tables. So, instead of calculating a candidate symbol set in real time, a candidate symbol set can be looked up given an initial MMSE symbol estimate (e.g., x1mmse or x2mmse).
The thresholds ε1 and ε2 can be properly adjusted to make each candidate symbol set contain K candidate symbols. This ensures the detector has a fixed complexity—a very desirable property to ensure completion of the detection in a fixed period of time using a fixed amount of resources.
While each candidate symbol set defines the candidates of one symbol in the transmitted symbol vector, the other symbols in the transmitted symbol vector are detected under the hypothesis that this symbol is the correct one. This can be done by using to a zero-forcing decision feedback equalizer (ZF-DFE) to estimate x2 given x1 as:




  
    
      
        
          
            x
            1
            c
          
          ∈
          
            
              V
              ⁡
              
                (
                
                  x
                  1
                  mmse
                
                )
              
            
            ⇒
            
              x
              2
              zfdfe
            
          
        
        =
        
          ⌈
          
            
              [
              
                
                  
                    
                      
                        h
                        12
                        *
                      
                    
                    
                      
                        
                          h
                          22
                          *
                        
                        ]
                      
                    
                  
                
                ⁡
                
                  [
                  
                    
                      
                        
                          
                            y
                            1
                          
                          -
                          
                            
                              h
                              11
                            
                            ⁢
                            
                              x
                              1
                              c
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            y
                            2
                          
                          -
                          
                            
                              h
                              21
                            
                            ⁢
                            
                              x
                              1
                              c
                            
                          
                        
                      
                    
                  
                  ]
                
              
            
            
              
                
                  
                  
                    h
                    12
                  
                  
                
                2
              
              +
              
                
                  
                  
                    h
                    22
                  
                  
                
                2
              
            
          
          ⌉
        
      
    
    
      
        (
        6
        )
      
    
  








  
    
      
        
          
            x
            2
            c
          
          ∈
          
            
              V
              ⁡
              
                (
                
                  x
                  2
                  mmse
                
                )
              
            
            ⇒
            
              x
              1
              zfdfe
            
          
        
        =
        
          ⌈
          
            
              [
              
                
                  
                    
                      
                        h
                        11
                        *
                      
                    
                    
                      
                        
                          h
                          21
                          *
                        
                        ]
                      
                    
                  
                
                ⁡
                
                  [
                  
                    
                      
                        
                          
                            y
                            1
                          
                          -
                          
                            
                              h
                              12
                            
                            ⁢
                            
                              x
                              2
                              c
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            y
                            2
                          
                          -
                          
                            
                              h
                              22
                            
                            ⁢
                            
                              x
                              2
                              c
                            
                          
                        
                      
                    
                  
                  ]
                
              
            
            
              
                
                  
                  
                    h
                    11
                  
                  
                
                2
              
              +
              
                
                  
                  
                    h
                    21
                  
                  
                
                2
              
            
          
          ⌉
        
      
    
    
      
        (
        7
        )
      
    
  




Where ┌•┐ denotes the slicing operation that makes hard detection decisions.
The combined candidate set can be expressed as the union of these two sets:

Ω{Xc=[x1cx2zfdfe]T|x1cεV(x1mmse)}∪{Xx=[x1zfdfex2c]T|x2cεV(x2mmse)}  (8)

and the LLRs can be computed as:





  
    
      
        
          L
          ⁢
          
            
          
          ⁢
          L
          ⁢
          
            
          
          ⁢
          
            R
            ⁡
            
              (
              
                b
                i
              
              )
            
          
        
        =
        
          
            
              min
              
                
                  
                    {
                    
                      X
                      c
                    
                    
                  
                  ⁢
                  
                    
                      
                        
                          
                            b
                            i
                          
                          =
                          0
                        
                      
                    
                    
                      
                        
                          
                            X
                            c
                          
                          ∈
                          Ω
                        
                      
                    
                  
                
                }
              
            
            ⁢
            
              
                
                
                  Y
                  -
                  
                    H
                    ⁢
                    
                      
                    
                    ⁢
                    
                      X
                      c
                    
                  
                
                
              
              2
            
          
          -
          
            
              min
              
                
                  
                    {
                    
                      X
                      c
                    
                    
                  
                  ⁢
                  
                    
                      
                        
                          
                            b
                            i
                          
                          =
                          1
                        
                      
                    
                    
                      
                        
                          
                            X
                            c
                          
                          ∈
                          Ω
                        
                      
                    
                  
                
                }
              
            
            ⁢
            
              
                
                
                  Y
                  -
                  
                    H
                    ⁢
                    
                      
                    
                    ⁢
                    
                      X
                      c
                    
                  
                
                
              
              2
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




Note that σ2 is removed in equation (9) as a common scaling factor that without any effect on the performance.
To avoid redundant calculations, the following intermediate variables (A, B, C, D and E) need to be computed only once in a pre-processing step:




  
    
      
        {
        
          
            
              
                A
                =
                
                  
                    
                      
                      
                        h
                        11
                      
                      
                    
                    2
                  
                  +
                  
                    
                      
                      
                        h
                        21
                      
                      
                    
                    2
                  
                
              
            
          
          
            
              
                B
                =
                
                  
                    
                      h
                      11
                    
                    ⁢
                    
                      h
                      12
                      *
                    
                  
                  +
                  
                    
                      h
                      21
                    
                    ⁢
                    
                      h
                      22
                      *
                    
                  
                
              
            
          
          
            
              
                C
                =
                
                  
                    
                      
                      
                        h
                        12
                      
                      
                    
                    2
                  
                  +
                  
                    
                      
                      
                        h
                        22
                      
                      
                    
                    2
                  
                
              
            
          
          
            
              
                D
                =
                
                  
                    
                      h
                      11
                      *
                    
                    ⁢
                    
                      y
                      1
                    
                  
                  +
                  
                    
                      h
                      21
                      *
                    
                    ⁢
                    
                      y
                      2
                    
                  
                
              
            
          
          
            
              
                E
                =
                
                  
                    
                      h
                      12
                      *
                    
                    ⁢
                    
                      y
                      1
                    
                  
                  +
                  
                    
                      h
                      22
                      *
                    
                    ⁢
                    
                      y
                      2
                    
                  
                
              
            
          
        
      
    
    
      
        (
        12
        )
      
    
  




Consequently, Equations (3), (6), (7), and the effective channel gains can be rewritten as follows:




  
    
      
        
          [
          
            
              
                
                  x
                  1
                  mmse
                
              
            
            
              
                
                  x
                  2
                  mmse
                
              
            
          
          ]
        
        =
        
          
            
              [
              
                
                  
                    
                      C
                      +
                      
                        σ
                        2
                      
                    
                  
                  
                    
                      -
                      
                        B
                        *
                      
                    
                  
                
                
                  
                    
                      -
                      B
                    
                  
                  
                    
                      A
                      +
                      
                        σ
                        2
                      
                    
                  
                
              
              ]
            
            ⁡
            
              [
              
                
                  
                    D
                  
                
                
                  
                    E
                  
                
              
              ]
            
          
          
            
              
                (
                
                  A
                  +
                  
                    σ
                    2
                  
                
                )
              
              ⁢
              
                (
                
                  C
                  +
                  
                    σ
                    2
                  
                
                )
              
            
            -
            
              
                
                B
                
              
              2
            
          
        
      
    
    
      
        (
        13
        )
      
    
  








  
    
      
        
          x
          2
          zfdfe
        
        =
        
          ⌈
          
            
              E
              -
              
                B
                ⁢
                
                  
                
                ⁢
                
                  x
                  1
                  c
                
              
            
            C
          
          ⌉
        
      
    
    
      
        (
        14
        )
      
    
  








  
    
      
        
          x
          1
          zfdfe
        
        =
        
          ⌈
          
            
              D
              -
              
                
                  B
                  *
                
                ⁢
                
                  x
                  2
                  c
                
              
            
            A
          
          ⌉
        
      
    
    
      
        (
        15
        )
      
    
  




FIG. 2 is a block diagram showing a hardware implementation of a 2×2 MIMO detector according to one aspect of the invention. MIMO detector 200 consists of an optional pre-processing module 202, initial symbol estimation module 204, candidate symbol set generation module 206, ZF-DFE hard detection modules 208a and 208b, Distance Computation modules 210a and 210b, and LLR Calculation module 212.
Optionally, pre-processing module 202 takes as input channel gains h11, h12, h21, h22 of channel matrix H and the variance σ2 of the channel noise determined by other modules (not shown) of receiver 120. Pre-processing module 202 calculates the values of intermediate variables A, B, C, D and E according to equations (12) and then stores the values for use by initial symbol estimation module 204 and ZR-DFE hard detection modules 208a and 208b in the subsequent process.
According to some aspect of the invention, initial symbol estimation module 204 makes a preliminary detection of the transmitted symbol vector, i.e., [x1mmse, x2mmse] by using a MMSE detector that implements equation (3) described before. In some embodiments, initial symbol estimation module 204 can be more efficiently implemented according to equation (13) as discussed above using the values of A, B, C, D and E that are pre-calculated by module 202.
It is also contemplated that initial symbol estimation module 204 may use any other conventional linear symbol detector that is well known in the art, such as a Zero Forcing detector, MMSE, MMSE-SIC, V-BLAST detectors.
According to some aspect of the invention, candidate symbol set module 206 generates a set of candidate symbols for each initially estimated symbol in the transmitted symbol vector, which is calculated by initial symbol estimation module 204.
Specifically, equations (4) and (5) are used to construct a candidate symbol set for each of the estimated symbols x1mmse and x2mmse to only include those constellation points which are ‘close” enough to the initially estimated symbols x1mmse and x2mmse respectively. In some embodiments, the closeness is measured in terms of Euclidean distance. In some other embodiments, the closeness may be defined in other metrics different from Euclidean distance. For example, the sum of per coordinate absolute value difference (also called a Norm-1 measure) may be used instead. Also, per hard sliced QAM point customized set can be constructed. This is advantageous when dealing with QAM points that are near the edge of the constellation or at its corners, which will become more apparent in the discussion below.
As described before, to ensure the MIMO detectors have fixed complexity, the size of the candidate symbol set can be a pre-determined number K (e.g., K=4, 5, . . . , or 25). However, the candidate set size can also be adjusted to tradeoff between performance and cost (the cost of power consumption and/or memory space.)
Once K is fixed, candidate symbol set module 206 adjusts the threshold values ε1 and ε2 of equations (4) and (5) respectively to make sure that each candidate symbol set contain K candidate symbols.
In some embodiments, to simplify the calculation of the candidate sets thus reduce power consumption during run time, candidate symbol set module 206 does not calculate the candidate set on the fly. Instead, a possible candidate symbol set of a given set size for each symbol in the constellation can be pre-calculated once. All possible candidate symbol sets for various set sizes are stored in a look-up table that can be looked up by the corresponding symbol and set size. At run time, candidate symbol set module 206 simply uses the candidate symbol set size and a specific initially estimated symbol (e.g., x1mmse or x2mmse) to look up the corresponding set of candidate symbols.(e.g., X1C or X2C). For example, if K=4, then X1C consists of four candidate symbols that are closest to x1mmse, X2C consists of four candidate symbols that are closest to x2mmse.
It will be appreciated that different methods or criteria can be applied to find possible candidates regardless of their complexity because the look-up table can be generated offline.
It is also contemplated that instead of using such candidate sets, the symbol candidates can be generated on the fly with some simple rules. For example, if the set of candidates is defined to be within a squared area around the initially estimated symbols, the hardware logic to find these candidates should be fairly simple.
According to some aspect of the invention, ZF-DFE detection modules are used to generate an overall (or combined) set of candidate symbol vectors for a transmitted symbol vector of size N. The overall (or combined) set is a union of candidate symbol vector sets, where each candidate symbol vector set is of size K and corresponds to one of the N initially estimated symbols of the transmitted symbol vector.
In some embodiments, each receive antenna has a corresponding dedicated ZF-DFE hard detection module. Thus the number of ZF-DFE hard detection modules (e.g., 208a, 208 b, etc) equals N, i.e., the total number of symbols in a transmitted symbol vector.
Each ZF-DFE module (208a or 208b) takes as an input a candidate symbol set generated by module 206 and generates a candidate symbol vector set as an output. Each candidate symbol set corresponds to one of the N initially estimated symbols determined by module 204. For a given candidate symbol in a given candidate symbol set, the ZF-DFE detection module assumes that the given candidate symbol is the correct symbol that has been transmitted. The ZF-DFE module then uses a zero-forcing decision feedback equalizer to detect the rest of the N-1 symbols in the received symbol vector. A candidate symbol vector is then formed with the given candidate symbol and the N-1 ZF-DFE detected symbols. The ZF-DFE module does this for each of the K candidate symbol in a given candidate symbol set, thus generates a candidate symbol vector set that consists of K candidate symbol vectors.
The overall (combined) set of candidate symbol vectors is formed by taking the union of the N candidate symbol vector sets determined by the N ZF-DFE detection modules. It is noted that in reality, the size of the overall (combined) set is typically much smaller than the sum of the size of the N candidate symbol vector sets since there is likely overlapping of candidate symbol vectors among the candidate symbol vector sets. This reduction in size is advantageous as it significantly reduces the complexity for the computing of the soft information of transmitted bits using the LLR method discussed above.
Unlike the existing methods, where the candidate sets for the N spatial streams are generated separately and each candidate set is only used for calculating the bit LLR values of one spatial stream, it is contemplated to use every candidate distance to update all bit LLR values of all the spatial streams, regardless to which candidate set the candidate symbol vector comes from. This results in much better performance, especially when K is small, without any added calculation.
Returning to the 2×2 MIMO detector as depicted in FIG. 2, assuming K=4, ZF-DFE hard detection module 208a implements equation (6) to find an estimated symbol x2 for each of the four candidate symbols in the candidate symbol set X1C corresponding to the initially estimated symbol x1mmse. The resulting four candidate symbol vectors thus can be denoted as:

X2zfdfe=={{X1C1X2zfdfe1},{X1C2X2zfdfe2},{X1C3X2zfdfe3},{X1C4X2zfdfe4}}

Similarly, ZF-DFE hard detection module 208b implements Equation (7) to estimate x1 for each of the four candidate symbols in the candidate symbol set X2C corresponding to the initially estimated symbol x2mmse.

As described before, the 2×2 MIMO detector may use a pre-processing module that pre-calculates the variables A, B, C, D and E according to one aspect of the invention. Therefore, the hardware design of ZF-DFE detection modules 208a and 208(b) can also be simplified by implementing equations (14) and (15) respectively with the values of A, B, C, D and E retrieved from pre-processing module 202.
Distance calculation modules (e.g., 210a and 210b) calculate for every candidate symbol vector in the overall (combined) set the distance between the received symbol vector.
It is noted that although FIG. 2 depicts two distance calculation modules, persons skilled in the art will recognize that a single distance calculation module can be used to perform the calculation for both data streams.
In some embodiments, LLR calculation module 212 then calculates all bit LLR values according to equation (9). The result is then passed to a channel decoder (e.g., channel decoder 124 as in FIG. 1) in the MIMO detector to decode the transmit data bits.
A flow chart of an example embodiment of determining soft information of transmitted data in a broadband communication system with multiple transmit antennas and (N) receive antennas is shown in FIG. 3. The first step is performing initial symbol estimation for each symbol of the symbol vector (302), where the symbol vector consists of the OFDM demodulated symbols corresponding to the multiple symbols received from the multiple antennas. As discussed above, any conventional linear symbol detection methods can be used in this step, such as MSEE and ZF detectors.
Optionally, a pre-processing step (304) can be performed to calculate and store a set of variable values that only need to be calculated once for a given set of channel gains and the received symbol vector. As discussed above, the same set of variables will also be used in some subsequent steps. Thus by pre-calculating and storing these values, the power consumption during run time and calculation delay can be reduced. For a 2×2 MIMO detector, the variable values that need only calculated once are described by equation set (12).
After the initial symbol estimation (302), a candidate symbol set is determined for each initially estimated symbol of the transmitted symbol vector (306). For a symbol vector having N symbols, N candidate symbol sets are generated in step 306. Each candidate symbol set consists of K candidate symbols (or constellation points) that are closest to the corresponding initially estimated symbol.
K is a parameter that can be pre-determined during the channel estimation time to account for the channel condition. In general, the larger the value of K is, the more accurate the symbol detection is, but also more calculation will be necessary. Geometrically, there are 4 nearest neighbors to each constellation point (except the ones on the boundary). So, the reasonable range of K is 4-25. The typical choice of K includes 5, 9 and 25.
Once K is chosen, for a given modulation scheme, all possible candidate symbol sets can be calculated offline and stored in a look up table (308) by calculating for each constellation point in the constellation the closest K points. Generating a candidate symbol set for a particular initially estimated symbol becomes a simple table look up using the initial estimated symbol and K as indices since each initially estimated symbol is also a constellation point.
Once they are determined, the N candidate symbol sets can be applied to generate (310) a combined set of candidate symbol vectors.
Certain embodiments use a ZF-DFE method to obtain a candidate symbol vector set as an output for a given candidate symbol set. Specifically, for a given candidate symbol in a given candidate symbol set, the ZF-DFE detection method assumes that the given candidate symbol is the correct symbol that has been transmitted, then uses a zero-forcing decision feedback equalizer to detect the rest of the N-1 symbols in the transmitted symbol vector. For example, in the case of N=2, equations (6) and (7) are solved respectively to estimate symbol x2 given x1 and estimate x1 given x2. A candidate symbol vector is then formed by combining the given candidate symbol and the N-1 corresponding ZF-DFE detected symbols. The ZF-DFE detection is performed for each of the K candidate symbol in a given candidate symbol set, and accordingly generates a candidate symbol vector set that consists of K candidate symbol vectors.
The combined set of candidate symbol vectors is formed by taking the union of the N candidate symbol vector sets determined by the N ZF-DFE detection. It will be appreciated that the number of candidate symbol vectors in the overall set is typically less than the sum of all the symbol vectors in the N candidate symbol vector sets (N×K) as it is likely that there are many overlapped candidate symbol vectors among these candidate symbol vector sets.
The soft information of a transmitted symbol vector is then calculated (312). In some embodiments, the soft information is calculated according to an LLR equation (314) (e.g. equation (9)), which computes the distance between the transmitted symbol vector and every candidate symbol vector in the combined set.
The computed soft information of the transmitted symbol vector is then output to a channel decoder for decoding the transmit data bits.
The various aspects of the invention discussed above allow a MIMO detector to be implemented to meet the real time constraints with a minimal cost in hardware and have improved performance and/or reduced complexity as compared to existing approaches.
According to one aspect of the invention, complexity reduction is achieved through the use of the table-based candidate set generation. Otherwise, to directly compute the candidates per spatial stream, it requires 3×2M real additions/subtractions and 2×2M real multiplications in order to compute the distances to all the constellation symbols, plus the additional logic to sort and find the K smallest distances. Table 1 shows the number of arithmetic operations required per QAM symbol for the candidate set calculation if a look-up table is not used. This is the amount of calculations that can be saved by using the lookup table-based candidate set generation, according to one aspect of the invention. Of course, there are also other methods that can save calculations. For instance, by taking the lattice structure into account, one natural approach is to start the search from the nearest neighbors, so that the process can be terminated early once the K nearest candidates are found. However, the required extra logic for boundary checks and sorting operations can still be costly.







TABLE 1







Required computations for generation of candidate set 


for one QAM-symbol if not using a look-up table.









Operations
64QAM
256QAM





Adds/Subs
192
768


Muls
128
512









To show the efficacy of one example embodiment of the MIMO detection according to one aspect of the invention, a floating point simulation is set up for 2×2, 20 MHz transmission under the 802.11n type-B Non-LOS channel model. In the simulation, the Protocol Data Unit (PDU) packet size is 256 bytes, modulation scheme is 256QAM, Binary Convolutional Coding scheme with a coding rate of 3⁄4. In addition, ideal channel estimation is assumed. The result is averaged over 10,000 packet transmissions. Simulation results are presented below in FIGS. 4-6. In each of the figures, the x-axis is the SNR and the y-axis is the Packet Error Ratio (PER).
In FIG. 4, the performance of the proposed detector with and without the use of joint candidate set is compared. It shows a gain of around 1.5 dB at PER of 1% by employing the joint candidate set for distance updating.
FIG. 5 compares the final performance of the proposed detector, with that of a MMSE detector, a ZF detector and a ML detector. At 1% PER, its performance is about 4 dB better than the conventional MMSE/ZF-based methods, and is less than 0.5 dB worse than the optimal ML detector.
As the simulation results clearly demonstrate, the use of combined candidate set significantly improve the performance to approach that of the ML detection.
Although the invention has been particularly described with reference to the preferred embodiments thereof, it should be readily apparent to those of ordinary skill in the art that changes and modifications in the form and details may be made without departing from the spirit and scope of the invention. It is intended that the appended claims encompass such changes and modifications.

## Claims

1. A method for detecting transmitted data in a broadband communication system with multiple transmit antennas and receive antennas, the method comprising:
receiving, at a receiver of the communication system, a received symbol vector wherein each symbol of the received symbol vector is from a corresponding antenna of the multiple receive antennas, wherein the received symbol vector corresponds to a transmitted symbol vector that are modulated according to transmitted data bits using a modulation scheme;
performing an initial symbol estimation for each symbol of the transmitted symbol vector based on the corresponding received symbol vector;
generating a candidate symbol set for each of the initially estimated symbol of the transmitted symbol vector, wherein the number of candidate symbols in each of the candidate symbol set is a predetermined number;
generating a combined set of candidate symbol vectors by using the candidate symbol sets corresponding to the initially estimated symbols; and
computing soft information of the transmitted symbol vector using every candidate symbol vector of the combined set.

2. The method of claim 1, wherein the modulation scheme is an M-QAM.

3. The method of claim 1, wherein the modulation scheme is an M-PSK.

4. The method of claim 1, wherein the initial symbol estimation is performed using a linear detector.

5. The method of claim 4, wherein the linear detector is a linear MMSE detector.

6. The method of claim 4, wherein the linear detector is a linear Zero-Forcing detector.

7. The method of claim 1, wherein the initial symbol estimation comprises pre-calculating and storing intermediate variables that need to be computed only once.

8. The method of claim 1, wherein generating a candidate symbol set for an initially estimated symbol of the transmitted symbol vector comprises:
calculating the distance between each constellation point in the constellation and the constellation point corresponding to the initially estimated symbol; and
selecting a pre-determined number of constellation points that are closest according to the calculated distance to the constellation point corresponding to the initially estimated symbol.

9. The method of claim 8, wherein the distance is Euclidean distance.

10. The method of claim 8, wherein the pre-determined number is chosen based on a trade-off between performance and implementation complexity and in the range of 4-25.

11. The method of claim 1, wherein generating a candidate symbol set comprises:
identifying offline, for different set sizes and a given candidate symbol, a set of candidate symbols that are the closest to the given candidate symbol;
storing the identified sets of candidate symbols for different set sizes and different candidate symbol in a look-up table; and
looking up the set of candidate symbols for an initially detected symbol and the pre-determined number.

12. The method of claim 1, wherein generating the combined set comprises:
generating a candidate symbol vector set for each candidate symbol set that corresponds to an initially estimated symbol in the transmitted symbol vector; and
forming the combined candidate set for the transmitted symbol vector by taking a union of the candidate symbol vector sets for all of the initially estimated symbols in the transmitted symbol vector.

13. The method of claim 12, wherein generating a candidate symbol vector set for a candidate symbol set comprises:
for each candidate symbol in the candidate symbol set, determining a corresponding candidate symbol vector; and
combining all the determined candidate symbol vectors.

14. The method of claim 13, wherein determining a corresponding candidate symbol vector corresponding to a candidate symbol comprises:
assuming the candidate symbol is the correct transmitted symbol in the transmitted symbol vector;
calculating the rest of the transmitted symbols in the transmitted symbol vector using a linear Zero-Force Decision Feedback equalizer or other similar decision feedback equalizer; and
generating the candidate symbol vector by combining the candidate symbol and the calculated rest of the transmitted symbols.

15. A MIMO detection apparatus for a wireless communication receiver, comprising:
an input port coupled to the multiple receive antennas of the receiver to receive a symbol vector corresponding to a transmitted symbol vector that are modulated according to transmitted data bits; and
a processor that performs initial symbol estimation each symbol of the transmitted symbol vector based on the corresponding received symbol vector, generates a candidate symbol set for each initially estimated symbol of the transmitted symbol vector, wherein the number of candidate symbols in each of the candidate symbol set is a predetermined number, generates a combined candidate set of candidate symbol vectors by using the candidate symbol sets corresponding to the initially estimated symbols, and further computes soft information of the transmitted symbol vector using every candidate symbol vector of the combined set.

16. The apparatus of claim 15, wherein the processor performs the following to generate a candidate symbol set for an initially estimated symbol of the transmitted symbol vector:
calculating the distance between each constellation point in the constellation and the constellation point corresponding to the initially estimated symbol; and
selecting a pre-determined number of constellation points that are closest to the constellation point corresponding to the initially estimated symbol.

17. The apparatus of claim 15, wherein the pre-determined number is chosen based on a trade-off between performance and implementation complexity and in the range of 4-25.

18. The apparatus of claim 15, wherein the processor performs the following to generates the combined set:
generating a candidate symbol vector set for each candidate symbol set that corresponds to an initially estimated symbol in the transmitted symbol vector; and
forming the combined candidate set for the transmitted symbol vector by taking a union of the candidate symbol vector sets for all of the initially estimated symbols in the transmitted symbol vector.

19. The apparatus of claim 15, wherein the processor further performs the following to generate a candidate symbol vector set for a candidate symbol set:
for each candidate symbol in the candidate symbol set, determining a corresponding candidate symbol vector; and
combining all the determined candidate symbol vectors.

20. The apparatus of claim 15, wherein the processor performs the following to determine a corresponding candidate symbol vector corresponding to a candidate symbol:
assuming the candidate symbol is the correct transmitted symbol in the transmitted symbol vector;
calculating the rest transmitted symbols in the transmitted symbol vector using a linear Zero-Force Decision Feedback equalizer or other similar decision feedback equalizer; and
generating the candidate symbol vector by combining the candidate symbol and the calculated rest of the transmitted symbols.

21. The apparatus of claim 15, wherein the processor performs the following to generate a candidate symbol set:
identifying offline, for different set sizes and a given candidate symbol, a set of candidate symbols that are the closest to the given candidate symbol;
storing the identified sets of candidate symbols for different set sizes and different candidate symbol in a look-up table; and
looking up the set of candidate symbols for an initially detected symbol and the pre-determined number.