Project topics and materials
Get Complete Project Material File(s) Now! »
MIMO detection algorithms
Assuming perfect channel knowledge at the receiver and considering systems with space-time coding and spatial multiplexing, the algorithms to separate the data streams, exploited in literature, can be divided into four main categories:
1. Linear Detection Methods: they simply invert the channel matrix. In this family, there are:
• Zero Forcing (ZF): it multiplies the inverse of the channel matrix by the received signal vector. It does not take into account the noise, and for this reason, it has not good results in terms of performance.
• Minimum Mean Square Error (MMSE): it minimizes the square error between the received and the transmitted vectors, taking into account the noise and operating on each component, separately. This method is not able to reach the maximum diversity order Mr Mt, but it is limited to Mr − Mt + 1. This causes a low Bit Error Rate (BER) at high SNRs.
2. Interference Cancellation method (IC): it first detects the stronger stream, among all received signal vectors, by means of ZF or MMSE, and removes it before detecting the next stronger streams. Two main techniques are exploited:
• SUccessive Cancellation (SUC): it randomly chooses a component of the received vector and assumes the others as interference. It removes the contribution of it from the vector: this procedure is repeated for each symbol in the vector. This method reaches a diversity order, which is comparable with that of MMSE.
Sphere Decoder Algorithm
• Ordered SUccessive Cancellation (OSUC): similarly as SUC, it chooses the component with the highest Signal to Interference Noise Ratio (SINR). It achieves an higher diversity order than SUC, but it has limited performance, because ZF or MMSE is employed for the initial choice.
3. Maximum Likelihood (ML) detector: it minimizes the difference be-tween the received signal vector and the vector of transmitted symbols dis-torted by the channel. The problem of deriving the ML estimation ˜s for the transmitted signal vector is formally stated as ˜ min y − Hs 2 (2.4) s = arg S∈ΩMt. where OMt is the set of possible values for transmitted symbol vectors s.This method is optimal, since it minimizes the error probability and reaches the maximum diversity order, but a direct implementation of ML detection is the exhaustive search that explicitly computes (2.4) for all candidate symbols s ∈ OMt . The detector has to examine 2R hypothesis for each received symbol vector. If for low rates, such as R ≤ 8bpcu, this is feasible, for large Mt and constellations it is practically unfeasible. As an example, for a 4 × 4 with a 16QAM modulation, corresponding to R ≤ 16bpcu, the number of candidates to be examined is 65536.
4. Sphere Decoder Algorithm (SDA): it has been introduced as a viable alternative to the ML detector, able to guarantee optimal performance, but only with a polynomial complexity [29]. It consists in limiting the search to only those points, which lie inside an hypersphere, with a certain radius, around the received vector. A detailed description of SDA is presented in the following paragraph.
Sphere Decoder Algorithm
SDA achieves ML performance, showing a polynomial average complexity [30]. It reduces the number of candidate symbols to be considered, without excluding the ML solution. Anyway, the term Sphere Decoder was born to indicate a family of algorithms: one differs from each other, essentially for the way to visit the tree. The follow-ing paragraph presents a complete description of a depth–first Schnorr–Euchner SDA, which is the starting point of this research. For completeness, the section 2.5 reports other versions of the SDA, presented in literature. The Sphere Decoder Algorithm is composed of three main steps: radius con-straint, tree construction and tree exploration.
• Radius Constraint (RC)
The calculation of (2.4) is formulated as a tree visit problem, constrained to only those Hs points that lie inside a hypersphere with radius r, around the received point y. This means that: y − Hs 2 ≤ C (2.5).
Other versions of Sphere Decoder Algorithm
The different versions of SDA can be classified, based on three aspects:
1. System model: complex–valued versus real–valued.
The main difference between these two categories is the tree construction and the average number of visited nodes, directly related to the throughput. In fact, in a real–valued system, the tree has a double number of levels than in a complex–valued one, and a number of sons, which is equal to the root of the cardinality of the corresponding complex–valued constellation. Considering the previous example, shown in the section 2.4, of a 4×4 MIMO system with 16QAM modulation, the tree has Mt = 4 levels and |O| = 16 sons (O is a complex–valued constellation), in a complex-valued model. In √
a real–valued one, instead, it has 2Mt = 8 levels and | O| = 4 sons. Clearly, the number of leaves is the same for both choices. The actual number of tree nodes that are visited is directly related to the throughput, which may also be affected by the use of a real or complex– valued channel model. While several authors proved that complex–valued model results in a lower number of visited nodes with respect to real–valued one [1], it was shown in [33] [34] that the latter offers two advantages: (i) it involves a lower global number of elementary real–valued operations and (i) allows for simple enumeration techniques. For this reason real–valued model is more suitable for practical implementation.
2. Direction of the tree exploration: breath–first versus depth–first While the depth–first strategy (see the tree exploration in 2.4) first chooses one symbol at each level and goes down, coming back only later for ex-amining the other alternative points at that same level, the breath–first concurrently selects more than one point at each level. The main exponent of this family is the K-best: it expands the K more promising points at each level. A big value of K avoids a great loss of BER, but it requires to expand an high number of paths in parallel, employing a huge amount of hardware resources. On the other hand, a small K causes a BER degradation. The algorithm finishes when it reaches the leaf level, and the ML solution is rep-resented by the leaf with the minimum ED, among all K leaves. In this way, the K-best, and, more in general the breath–first strategy, is characterized by a fixed number of visited nodes, and therefore a fixed throughput [35]. In the depth–first, instead, the actual number of tree nodes that are visited in the detection of a received symbol vector is a stochastic value and its average depends on signal to noise ratio. This implies that detection throughput is not constant.
3. Enumeration: Fincke Pohst (FP) versus Schnorr-Euchner (SE) The FP method is the fist introduced from an historical point of view [36]. It consists in considering the nodes of a level with the natural order. For example, in the case of a 4PAM, where sons are {−3, −1, 1, 3}, the nodes are visited exactly with that order. Only later, a more efficient method has been introduced, such as the SE strategy ((see the tree exploration in 2.4)).
Table of contents :
List of Figures
List of Tables
1 Introduction
I Hard MIMO detection
2 MIMO systems
2.1 MIMO functions
2.2 MIMO system model
2.3 MIMO detection algorithms
2.4 Sphere Decoder Algorithm
2.5 Other versions of Sphere Decoder Algorithm
3 Look-ahead Sphere Decoder Algorithm
3.1 State of the Art
3.2 Look-ahead methodology
3.3 Look–ahead optimization of SDA
3.3.1 DFG representation
3.3.2 Linear approximation and look–ahead transformation
3.3.3 Performance evaluation of LASDA
3.3.4 A modified search strategy: Test & Restart
3.3.5 Performance evaluation of LASDA with Test & Restart
3.4 Architecture design
3.4.1 S block
3.4.2 High level architecture
3.5 Synthesis results
3.6 Comparisons with the state of the art
3.7 Discussion of the results
II Soft MIMO detection
4 Towards Soft Detection
4.1 Complexity evaluation of a soft-output MIMO detector
4.1.1 Description of the system
4.1.1.1 The algorithm of the Elementary Signal Estimator
4.1.2 Hardware implementation
4.1.2.1 Apriori stat block
4.1.2.2 cov block
4.1.2.3 cholesky block
4.1.2.4 invs block
4.1.2.5 f block
4.1.2.6 antenna n block
4.1.3 Synthesis results
5 Soft MIMO detection: the idea of a multi-algorithm detector
5.1 State of the Art
5.2 Analysis
6 Flexible Soft-Input Soft-Output detector: List Sphere Decoding and Linear MMSE Detection
6.1 Description of the system
6.1.1 List Sphere Detector (LSD)
6.1.2 MMSE-IC Linear Equalizer
6.2 Flexibility and divergence analysis of iterative LSD
6.2.1 Flexibility parameters
6.2.2 Analysis of divergence using EXIT chart
6.3 Comparisons between LSD and MMSE-IC
6.3.1 Block Fading Channel
6.3.2 Fast Fading Channel
6.3.3 Block and Fast Fading Channel for a 2 × 2-MIMO system
6.3.4 Complexity comparison
6.4 Discussion of the results
7 ASIP implementation of LSD
7.1 ASIP design flow
7.1.1 An ADL based tool: Coware Processor Designer
7.2 First suboptimal ASIP of LSD
7.2.1 Flexibility parameters and architectural choices
7.2.1.1 Babai Point selection
7.2.1.2 PED computation
7.2.1.3 computation
7.2.1.4 SE enumeration
7.2.1.5 List management
7.2.2 Instruction Set Architecture
7.2.2.1 INIT instruction
7.2.2.2 BABAI instruction
7.2.2.3 CHECK instruction
7.2.3 Sample program
7.2.4 Synthesis results
7.3 Improved ASIP: increased clock frequency
7.3.1 Performance
7.3.2 Comparison with the State of the Art
7.3.3 Efficient pipeline usage: the pipeline-interleaving
7.4 Discussion of the results
8 Conclusions
References
