Reduced complexity sphere decoding using a geometrical approach

Published on May 4, 2014 in ICASSP (International Conference on Acoustics, Speech, and Signal Processing)
· DOI :10.1109/ICASSP.2014.6853934
Mahdi Abbasi1
Estimated H-index: 1
(YU: Yazd University),
Aliakbar Tadaion13
Estimated H-index: 13
(YU: Yazd University),
Saeed Gazor30
Estimated H-index: 30
(Queen's University)
In this paper we propose an algorithm with reduced complexity for the sphere detection (SD) which is used in multiple input multiple output (MIMO) detection algorithms without any performance degradation. The trade-off between the complexity and the bit error rate is a main challenge in wireless MIMO systems. The maximum likelihood (ML) detector considered as the optimum detector in the literatures. Since the complexity of the naive ML detectors is significantly high, the SD algorithms are proposed to lower the complexity. In this paper, we use the result of the geometrical decoder (GD) proposed in [8] which performs as the ML detector and has lower complexity than SD algorithm. We propose a method to further reduce the complexity of this SD algorithm. We show that the complexity is further reduced by almost 60%, i.e., the number of nodes visited by the proposed SD method is in average 60% less than that of the original one.
📖 Papers frequently viewed together
2 Citations
2012WiMob: Wireless and Mobile Computing, Networking and Communications
2 Citations
4 Authors (Weiliang Fan, ..., Xinyu Mao)
2 Citations
#1Mahdi Abbasi (YU: Yazd University)H-Index: 1
#2Aliakbar Tadaion (YU: Yazd University)H-Index: 13
Last. Mohammad Reza Taban (YU: Yazd University)H-Index: 11
view all 3 authors...
In this paper, we propose a simple method which may enhance the performance of zero-forcing (ZF) or lattice reduction (LR) algorithm in multiple input multiple output (MIMO) detection. As we know MIMO communication systems increase the spectral efficiency and data reliability. Designing detector for such systems that have low complexity and performance near to optimum have attracted much of attention. Optimum detection due to its complexity is not applicable. Famous suboptimal algorithms are ZF,...
2 CitationsSource
#1Shuangshuang Han (U of A: University of Alberta)H-Index: 7
#2Chintha Tellambura (U of A: University of Alberta)H-Index: 72
It is well known that although the conventional sphere decoder (SD) achieves optimal maximum likelihood (ML) performance at a reduced complexity compared to the naive ML detector, the SD computational complexity varies with signal noise ratio (SNR) and is high in the low SNR region. This paper proposes a new idea to overcome these drawback that reduces the complexity significantly at a negligible performance loss. The main idea is to scale the search radius of the original SD by a factor that de...
13 CitationsSource
#1Z. Y. Shao (HKU: University of Hong Kong)H-Index: 3
#2S. W. Cheung (HKU: University of Hong Kong)H-Index: 1
Last. T.I. Yuk (HKU: University of Hong Kong)H-Index: 4
view all 3 authors...
Geometric decoding (GD) is a newly proposed decoding technique for multiple-input multiple-output (MIMO) transmission over the fading channels. With a complete search on all symbol vectors in the lattice structure, GD requires about the same decoding complexity to achieve the same optimum block-error rates (BLERs) as that of ML decoding. In this paper, we propose a simple implementation of GD for optimum decoding of MIMO transmission. The GD decoder uses the channel matrix to construct a hyper p...
4 CitationsSource
#1Michael Samuel (UCLA: University of California, Los Angeles)H-Index: 5
#2Michael P. Fitz (UCLA: University of California, Los Angeles)H-Index: 33
A geometric decoding technique for finite lattices was presented by Seethaler et al. for flat-fading multiple-input multiple-output channels in the case of linear modulations with constant amplitude (PSK). In this paper, geometric decoding is extended to square PAM and QAM constellations. Geometric decoding is suboptimal but has the advantage that the search is done in the vicinity of a X-dimensional affine set. Therefore, a very small subset of the whole lattice is considered in decoding. This ...
12 CitationsSource
#1Babak Hassibi (California Institute of Technology)H-Index: 77
#2Haris Vikalo (California Institute of Technology)H-Index: 27
The problem of finding the least-squares solution to a system of linear equations where the unknown vector is comprised of integers, but the matrix coefficient and given vector are comprised of real numbers, arises in many applications: communications, cryptography, GPS, to name a few. The problem is equivalent to finding the closest lattice point to a given point and is known to be NP-hard. In communications applications, however, the given vector is not arbitrary but rather is an unknown latti...
1,059 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
#1Harold Artes (TU Wien: Vienna University of Technology)H-Index: 9
#2Dominik Seethaler (TU Wien: Vienna University of Technology)H-Index: 15
Last. Franz Hlawatsch (TU Wien: Vienna University of Technology)H-Index: 52
view all 3 authors...
It is well known that suboptimal detection schemes for multiple-input multiple-output (MIMO) spatial multiplexing systems (equalization-based schemes as well as nulling-and-cancelling schemes) are unable to exploit all of the available diversity, and thus, their performance is inferior to ML detection. Motivated by experimental evidence that this inferior performance is primarily caused by the inability of suboptimal schemes to deal with "bad" (i.e., poorly conditioned) channel realizations, we ...
194 CitationsSource
#1Mohamed Oussama Damen (U of A: University of Alberta)H-Index: 21
#2H. El GamalH-Index: 35
Last. Giuseppe CaireH-Index: 80
view all 3 authors...
Maximum-likelihood (ML) decoding algorithms for Gaussian multiple-input multiple-output (MIMO) linear channels are considered. Linearity over the field of real numbers facilitates the design of ML decoders using number-theoretic tools for searching the closest lattice point. These decoders are collectively referred to as sphere decoders in the literature. In this paper, a fresh look at this class of decoding algorithms is taken. In particular, two novel algorithms are developed. The first algori...
1,235 CitationsSource
We present a maximum-likelihood decoding algorithm for an arbitrary lattice code when used over an independent fading channel with perfect channel state information at the receiver. The decoder is based on a bounded distance search among the lattice points falling inside a sphere centered at the received point. By judicious choice of the decoding radius we show that this decoder can be practically used to decode lattice codes of dimension up to 32 in a fading environment.
1,566 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 By1