The existing wireless mobile communication systems provide several types of services and mostly depend on channel coding to overcome any inferiority of channels. However, due to the increasing demands, for example for high-quality multimedia services, in which users can communicate with anyone regardless of time and place, the existing services have evolved data-oriented services. Accordingly, there is a high demand for next generation wireless transmission technology for transmitting the larger amount of data at a lower error rate. In particular, it is very important to transmit data at a high rate in a link in which the amount of required data is large.
For the next generation wireless communications, various antenna systems have been proposed. For example, a Multiple Input, Multiple output (MIMO) system, i.e., a typical antenna system, increases spectrum efficiency through all of transmission antennas without excessive use of a frequency bandwidth. Generally, MIMO is classified into Space-Time Coding (STC), Diversity, Beam Forming (BF), and Spatial Multiplexing (SM) according to the transmission structure and scheme of a transmitter, all of which provide high data rate and reliability.
A MIMO system adopts multiple antennas or array antenna to transmit/receive data in the transmitter and receiver. Multiple antennas are provided in different spatial positions, with different fading features, thus the received signals of adjacent antennas can be approximated as uncorrelated entirely as long as the spacing between adjacent antennas for transmitting/receiving signals in the MIMO system is large enough. The MIMO system takes full advantage of the spatial characteristics of multipath for implementing space diversity transmission and reception.
FIG. 1 illustrates an exemplary and simplified MIMO system 100 constructed by M Tx antennas 103 and N Rx antennas 104. As mentioned earlier, the antenna spacing between the Tx antennas and Rx antennas in the MIMO system in FIG. 1 is generally big enough, to guarantee the spatial un-correlation of signals. As FIG. 1 shows, in the transmitter, MIMO architecture unit 101 first transforms a channel of data stream into M channels of parallel sub data streams; then, multiple access transform unit 102 performs multiplex processing; finally, the corresponding M Tx antennas 103 transmit the signal simultaneously into the wireless channels. The MIMO architecture unit 101 can adopt any one of the MIMO processing methods, such as STTC (Space Time Trellis Code), space-time block code, space-time Turbo code, BLAST code and etc. While multiple access transform unit 102 can implements TDD, FDD or CDMA. Efficient demodulation of MIMO is non-trivial and currently a hot research topic.
In many communications receivers there is a need to separate multiple symbols that have undergone mixing due to a channel that introduces cross-talk. In particular, this is a key problem for MIMO receivers where this mixing is induced by the propagation channel. A common mathematical model for such a cross-talk channel is:y=Hs+e  (1)wherein                s is a transmitted vector (of length nt). The vector s has elements that are chosen by the transmitter from a finite alphabet S (Quadrature Amplitude Modulation (QAM) for example),        H is a channel matrix of dimension nr×nt, where nr is the number of receive antennas and nt the number of transmit antennas, and        e is a vector of additive Gaussian noise.        
The model (1) is general enough to also describe MIMO Systems that use (not-necessarily orthogonal) Space-Time Block Coding (STBC), by appropriately using a structured matrix H.
The receiver must detect s from an observed y. In systems that use Channel coding of any sort (convolutional, turbo, etc.) it is also of interest to compute soft decisions (reliability information) on the information bits bk,i that constitute s. One can show [1] that if all symbols are equally likely a priori this amounts to Computing
                              L          ⁡                      (                                          b                                  k                  ,                  i                                            |              y                        )                          =                  log          (                                                    ∑                                                      s                    ⁢                                          :                                        ⁢                                                                  b                                                  k                          ,                          i                                                                    ⁡                                              (                        s                        )                                                                              =                  1                                            ⁢                              exp                ⁡                                  (                                                            -                                              1                                                  N                          0                                                                                      ⁢                                                                                                                    y                          -                          Hs                                                                                            2                                                        )                                                                                    ∑                                                      s                    :                                                                  b                                                  k                          ,                          i                                                                    ⁡                                              (                        s                        )                                                                              =                  0                                            ⁢                              exp                ⁡                                  (                                                            -                                              1                                                  N                          0                                                                                      ⁢                                                                                                                    y                          -                          Hs                                                                                            2                                                        )                                                              )                                    (        2        )            where N0 is the power spectral density of the noise. Here bk,i (s) is the ith information bit of the kth element of the transmitted vector s. The notation s: bk,i (s)=β means the set of all vectors s for which bk,i equals β.
Evaluation of (2) amounts to marginalizing a probability density function and this can be done in a brute-force manner. The problem however is that this has too high complexity to be useful in practice. More precisely evaluating (2) requires O(2mnt) operations where m is the number of bits per symbol in s. Even with hardware in the foreseeable future this is not possible to implement even for moderately large nt.
Previous approaches to this problem include various approximations to (2). In the following some known approaches are presented along with a discussion of their main drawbacks:                Log-max approximation. This approximates the two sums in (2) with their largest term:        
                              L          ⁡                      (                                          b                                  k                  ,                  i                                            |              y                        )                          ≈                  log          (                                                    max                                                      s                    :                                                                  b                                                  k                          ,                          i                                                                    ⁡                                              (                        s                        )                                                                              =                  1                                            ⁢                              exp                ⁡                                  (                                                            -                                              1                                                  N                          0                                                                                      ⁢                                                                                                                    y                          -                          Hs                                                                                            2                                                        )                                                                                    max                                                      s                    :                                                                  b                                                  k                          ,                          i                                                                    ⁡                                              (                        s                        )                                                                              =                  0                                            ⁢                              exp                ⁡                                  (                                                            -                                              1                                                  N                          0                                                                                      ⁢                                                                                                                    y                          -                          Hs                                                                                            2                                                        )                                                              )                                    (        3        )            
The problems with this approach include:                There is a Performance loss associated with discarding all but one term in the sum.        Finding the maximum term in the sum requires solving an integer constrained least-squares problem. The best known technique for this is the sphere decoding algorithm [2] and its relatives, which has an average complexity that grows exponentially with nt [3]. Additionally, its complexity is random in the sense that the number of operations needed to compute (3) will be different for each received vector y. This presents a serious problem for implementation, as it requires either hardware designed for worst-case complexity, or data buffers of various kinds. The sequential structure of the sphere decoding algorithm also seriously limits the amount of parallelization which can be achieved when the algorithm is implemented in an ASIC.        List-sphere-decoding [4]. The idea is to approximate the sums in (2) with a sum over a subset of the terms, namely the terms encountered when running the so-called sphere decoding algorithm.        
The problems with this approach are                There is a Performance loss associated with discarding all but a subset of terms in the sum.        1. The sphere decoding algorithm and its relatives have an expected complexity exponential in nt [3]. Additionally its complexity is random and the list-sphere decoder inherits the implementational issues of the original sphere decoder.        2. There is an issue relating to how various parameters of the algorithm should be selected in order for the subsets (over which the sums in (2) are computed) to always contain at least one member.        Heuristic approximations based on linear preprocessing of the data. The problems with this approach is very poor to unacceptable Performance on slow fading Channels        