Reduced-complexity mimo detector with close-to ml error rate performance

Published on Mar 11, 2007
· DOI :10.1145/1228784.1228836
C. Hess1
Estimated H-index: 1
(ETH Zurich),
M. Wenk14
Estimated H-index: 14
(ETH Zurich)
+ 4 AuthorsWolfgang Fichtner53
Estimated H-index: 53
(ETH Zurich)
Maximum likelihood (ML) detection provides optimum error rate performance for uncoded multiple-input multiple-output (MIMO) systems. However, circuit complexity of a straightforward implementation of ML detection is uneconomic for high-rate systems. This paper addresses the VLSI implementation trade-offs of a MIMO detection algorithm that achieves close-to ML error rate performance with reduced computational complexity. The described implementations in a 0.25 μm CMOS technology for 4-4 MIMO systems feature a simple data-path, achieve high throughput, and use small silicon area. Important contributing factors to these results are efficient enumeration strategies and the application of simplified norms and sophisticated scheduling techniques together with a new low-complexity preprocessing scheme.
📖 Papers frequently viewed together
6 Authors (Andreas Burg, ..., Helmut Bölcskei)
595 Citations
1,180 Citations
350 Citations
#1P. Luethi (ETH Zurich)H-Index: 9
#2Andreas Burg (ETH Zurich)H-Index: 38
Last. Wolfgang Fichtner (ETH Zurich)H-Index: 53
view all 6 authors...
The QR decomposition is an important, but often underestimated prerequisite for pseudo- or non-linear detection methods such as successive interference cancellation or sphere decoding for multiple-input multiple-output (MIMO) systems. The ability of concurrent iterative sorting during the QR decomposition introduces a moderate overall latency, but provides the base for an improved layered stream decoding. This paper describes the architecture and results of the first VLSI implementation of an it...
81 CitationsSource
#1L.G. Barbero (Edin.: University of Edinburgh)H-Index: 13
#2John S. Thompson (Edin.: University of Edinburgh)H-Index: 53
A field-programmable gate array (FPGA) implementation of a new detection algorithm for uncoded multiple input-multiple output (MIMO) systems based on the complex version of the sphere decoder (SD) is presented in this paper. It achieves quasi-maximum likelihood (ML) performance in systems where a hardware implementation of the maximum likelihood detector (MLD) is unfeasible due to its high complexity. It achieves this with a highly parallel and fully pipelined architecture. In addition, differen...
28 CitationsSource
Jul 2, 2006 in SPAWC (International Workshop on Signal Processing Advances in Wireless Communications)
#1L.G. Barbero (Edin.: University of Edinburgh)H-Index: 13
#2John S. Thompson (Edin.: University of Edinburgh)H-Index: 53
A new detection algorithm for uncoded multiple input-multiple output (MIMO) systems based on the complex version of the sphere decoder (SD) is presented in this paper. The algorithm performs a fixed number of operations to detect the symbols, independent of the noise level. The algorithm achieves this by combining a novel channel matrix preprocessing with a search through a small subset of the complete receive constellation. Simulation results show it has only a very small bit error ratio (BER) ...
108 CitationsSource
#1Andreas Burg (ETH Zurich)H-Index: 38
#2M. Borgmanr (ETH Zurich)H-Index: 1
Last. Helmut Bölcskei (ETH Zurich)H-Index: 59
view all 5 authors...
We describe the VLSI implementation of MIMO detectors that exhibit close-to optimum error-rate performance, but still achieve high throughput at low silicon area. In particular, algorithms and VLSI architectures for sphere decoding (SD) and K-best detection are considered, and the corresponding trade-offs between uncoded error-rate performance, silicon area, and throughput are explored. We show that SD with a per-block run-time constraint is best suited for practical implementations.
49 CitationsSource
#1Zhan Guo (Lund University)H-Index: 1
#2P. Nilsson (Lund University)H-Index: 1
K-best Schnorr-Euchner (KSE) decoding algorithm is proposed in this paper to approach near-maximum-likelihood (ML) performance for multiple-input-multiple-output (MIMO) detection. As a low complexity MIMO decoding algorithm, the KSE is shown to be suitable for very large scale integration (VLSI) implementations and be capable of supporting soft outputs. Modified KSE (MKSE) decoding algorithm is further proposed to improve the performance of the soft-output KSE with minor modifications. Moreover,...
602 CitationsSource
#1Andreas BurgH-Index: 38
#2M. BorgmannH-Index: 9
Last. Helmut BölcskeiH-Index: 59
view all 6 authors...
Multiple-input multiple-output (MIMO) techniques are a key enabling technology for high-rate wireless communications. This paper discusses two ASIC implementations of MIMO sphere decoders. The first ASIC attains maximum-likelihood performance with an average throughput of 73 Mb/s at a signal-to-noise ratio (SNR) of 20 dB; the second ASIC shows only a negligible bit-error-rate degradation and achieves a throughput of 170 Mb/s at the same SNR. The three key contributing factors to high throughput ...
595 CitationsSource
#1Arogyaswami PaulrajH-Index: 98
#2Rohit U. NabarH-Index: 20
Last. D. GoreH-Index: 16
view all 3 authors...
Wireless networks are under constant pressure to provide ever-higher data rates to increasing numbers of users with greater reliability. This book is an accessible introduction to every fundamental aspect of space-time wireless communications. Space-time processing technology is a powerful tool for improving system performance that already features in the UMTS and CDMA2000 mobile standards. The ideal volume for graduate students and professionals, it features homework problems and other supporti...
3,057 Citations
#1Bertrand M. Hochwald (Bell Labs)H-Index: 28
#2S. ten Brink (Alcatel-Lucent)H-Index: 4
Last. S. ten Brink (Alcatel-Lucent)H-Index: 13
view all 2 authors...
Recent advancements in iterative processing of channel codes and the development of turbo codes have allowed the communications industry to achieve near-capacity on a single-antenna Gaussian or fading channel with low complexity. We show how these iterative techniques can also be used to achieve near-capacity on a multiple-antenna system where the receiver knows the channel. Combining iterative processing with multiple-antenna channels is particularly challenging because the channel capacities c...
2,033 CitationsSource
#1Dirk Wubben (University of Bremen)H-Index: 19
#2Ronald Böhnke (University of Bremen)H-Index: 12
Last. Karl-Dirk Kammeyer (University of Bremen)H-Index: 24
view all 5 authors...
Layered space-time codes have been designed to exploit the capacity advantage of multiple antenna systems in Rayleigh fading environments. A new efficient decoding algorithm based on QR decomposition is presented, which requires only a fraction of the computational effort compared with the standard decoding algorithm requiring the multiple calculation of the pseudo inverse of the channel matrix.
505 CitationsSource
We report on improved practical algorithms for lattice basis reduction. We propose a practical floating point version of theL3-algorithm of Lenstra, Lenstra, Lovasz (1982). We present a variant of theL3-algorithm with “deep insertions” and a practical algorithm for block Korkin—Zolotarev reduction, a concept introduced by Schnorr (1987). Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up to 66 random weights of arbitrary bit length within at...
1,180 CitationsSource
Cited By41
#1Konstantinos Nikitopoulos (University of Surrey)H-Index: 10
#2Georgios Georgis (University of Surrey)H-Index: 6
Last. Rahim Tafazolli (University of Surrey)H-Index: 59
view all 5 authors...
The recent paradigm shift towards the transmission of large numbers of mutually interfering information streams, as in the case of aggressive spatial multiplexing, combined with requirements towards very low processing latency despite the frequency plateauing of traditional processors, initiates a need to revisit the fundamental maximum-likelihood (ML) and, consequently, the sphere-decoding (SD) detection problem. This work presents the design and VLSI architecture of MultiSphere; the first meth...
10 CitationsSource
#1Georgios Georgis (University of Surrey)H-Index: 6
#2Konstantinos Nikitopoulos (University of Surrey)H-Index: 10
Last. Kyle Jamieson (Princeton University)H-Index: 28
view all 3 authors...
This paper presents the algorithmic design, experimental evaluation, and very large scale of integration (VLSI) implementation of Geosphere, a depth-first sphere decoder able to provide the exact maximum-likelihood solution in dense (e.g., 64) and very dense (e.g., 256, 1024) quadrature amplitude modulation (QAM) constellations by means of a geometrically inspired enumeration. In general, linear detection methods can be highly effective when the multiple input, multiple output (MIMO) channel is ...
7 CitationsSource
#1Hwanchol Jang (Gwangju Institute of Science and Technology)H-Index: 4
#2Saeid Nooshabadi (MTU: Michigan Technological University)H-Index: 20
Last. Heung-No Lee (Gwangju Institute of Science and Technology)H-Index: 21
view all 4 authors...
We propose a low-complexity, complex-valued sphere decoding (CV-SD) algorithm, which is referred to as circular sphere decoding (CSD) and is applicable to multiple-input–multiple-output (MIMO) systems with arbitrary 2-D constellations. CSD provides a new constraint test. This constraint test is carefully designed so that the elementwise dependence is removed in the metric computation for the test. As a result, the constraint test becomes simple to perform without restriction on its constellation...
4 CitationsSource
Jan 1, 2017 in NSDI (Networked Systems Design and Implementation)
#1Christopher Husmann (University of Surrey)H-Index: 3
#2Georgios Georgis (University of Surrey)H-Index: 6
Last. Kyle Jamieson (UCL: University College London)H-Index: 28
view all 4 authors...
Large MIMO base stations remain among wireless network designers’ best tools for increasing wireless throughput while serving many clients, but current system designs, sacrifice throughput with simple linear MIMO detection algorithms. Higher-performance detection techniques are known, but remain off the table because these systems parallelize their computation at the level of a whole OFDM subcarrier, sufficing only for the lessdemanding linear detection approaches they opt for. This paper presen...
20 Citations
Dec 1, 2016 in GLOBECOM (Global Communications Conference)
#1Konstantinos Nikitopoulos (University of Surrey)H-Index: 10
#2Daniil Chatzipanagiotis (University of Surrey)H-Index: 2
Last. Rahim Tafazolli (University of Surrey)H-Index: 59
view all 4 authors...
This work introduces MultiSphere, a method to massively parallelize the tree search of large sphere decoders in a nearly-independent manner, without compromising their maximum-likelihood performance, and by keeping the overall processing complexity at the levels of highly-optimized sequential sphere decoders. MultiSphere employs a novel sphere decoder tree partitioning which can adjust to the transmission channel with a small latency overhead. It also utilizes a new method to distribute nodes to...
13 CitationsSource
#1Esther P. Adeva (Integrated Device Technology)H-Index: 7
#2Gerhard Fettweis (TUD: Dresden University of Technology)H-Index: 73
The application of the turbo principle allows to exploit the full potential of multiple-input multiple-output (MIMO) communications at the cost of increasing the computational effort at the receiver. In the context of soft-input soft-output tree search detection, the computation of metric values and the optimal node order represents two of the most computationally demanding operations. Heuristic approaches may be applied to reduce the complexity, but their accuracy is compromised by the effect t...
11 CitationsSource
#1Youssef Nasser (AUB: American University of Beirut)H-Index: 14
#2Sébastien Aubert (Ericsson)H-Index: 4
Last. Fabienne Nouvel (INSA: Intelligence and National Security Alliance)H-Index: 11
view all 3 authors...
A simplified hard output sphere decoder for large MIMO systems with the use of efficient search center and reduced domain neighborhood study Abstract Multiple-input multiple-output (MIMO) with a spatial-multiplexing (SM) scheme is a topic of high interest for the next generation of wireless communications systems. At the receiver, neighborhood studies (NS) and lattice reduction (LR)-aided techniques are common solutions in the literature to approach the optimal and computationally complex maximu...
1 CitationsSource
#1Konstantinos Nikitopoulos (University of Surrey)H-Index: 10
Last. Dionysios ReisisH-Index: 12
view all 3 authors...
The complexity gains of sphere decoders (SDs) with Schnorr–Euchner enumeration and nonconstant amplitude constellations are limited by the required node ordering. Aiming at improving the implementation efficiency of SD without compromising optimality, this paper proposes a novel tree traversal for soft-output SDs providing the exact max-log MAP decoder performance. It consists of a predefined visiting order that approximates the exact Schnorr–Euchner enumeration (SEE) and a modified pruning metr...
9 CitationsSource
Aug 17, 2014 in SIGCOMM (ACM Special Interest Group on Data Communication)
#1Konstantinos Nikitopoulos (University of Surrey)H-Index: 10
#2Juan Zhou (UCL: University College London)H-Index: 1
Last. Kyle Jamieson (UCL: University College London)H-Index: 28
view all 4 authors...
This paper presents the design and implementation of Geosphere, a physical- and link-layer design for access point-based MIMO wireless networks that consistently improves network throughput. To send multiple streams of data in a MIMO system, prior designs rely on a technique called zero-forcing, a way of "nulling" the interference between data streams by mathematically inverting the wireless channel matrix. In general, zero-forcing is highly effective, significantly improving throughput. But in ...
34 CitationsSource
#1Michael Wu (Rice University)H-Index: 20
#2Bei Yin (Rice University)H-Index: 13
Last. Joseph R. Cavallaro (Rice University)H-Index: 45
view all 5 authors...
Multiple-input multiple-output (MIMO) wireless is an enabling technology for high spectral efficiency and has been adopted in many modern wireless communication standards, such as 3GPP-LTE and IEEE 802.11n. However, (optimal) maximum a-posteriori (MAP) detection suffers from excessively high computational complexity, which prevents its deployment in practical systems. Hence, many algorithms have been proposed in the literature that trade-off performance versus detection complexity. In this paper...
5 CitationsSource