Algorithm and implementation of the K-best sphere decoding for MIMO detection

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, a VLSI architecture is proposed for both algorithms. There are several low complexity and low-power features incorporated in the proposed algorithms and the VLSI architecture. The proposed hard-output KSE decoder and the soft-output MKSE decoder is implemented for 4/spl times/4 16-quadrature amplitude modulation (QAM) MIMO detection in a 0.35-/spl mu/m and a 0.13-/spl mu/m CMOS technology, respectively. The implemented hard-output KSE chip core is 5.76 mm/sup 2/ with 91 K gates. The KSE decoding throughput is up to 53.3 Mb/s with a core power consumption of 626 mW at 100 MHz clock frequency and 2.8 V supply. The implemented soft-output MKSE chip can achieve a decoding throughput of more than 100 Mb/s with a 0.56 mm/sup 2/ core area and 97 K gates. The implementation results show that it is feasible to achieve near-ML performance and high detection throughput for a 4/spl times/4 16-QAM MIMO system using the proposed algorithms and the VLSI architecture with reasonable complexity.     

The Diversity Order of the Semidefinite Relaxation Detector

In this paper, we consider the detection of binary (antipodal) signals transmitted in a spatially multiplexed fashion over a fading multiple-input-multiple-output (MIMO) channel and where the detection is done by means of semidefinite relaxation (SDR). The SDR detector is an attractive alternative to maximum-likelihood (ML) detection since the complexity is polynomial rather than exponential. Assuming that the channel matrix is drawn with independent identically distributed (i.i.d.) real-valued Gaussian entries, we study the receiver diversity and prove that the SDR detector achieves the maximum possible diversity. Thus, the error probability of the receiver tends to zero at the same rate as the optimal ML receiver in the high signal-to-noise ratio (SNR) limit. This significantly strengthens previous performance guarantees available for the semidefinite relaxation detector. Additionally, it proves that full diversity detection is also possible in certain scenarios when using a noncombinatorial receiver structure.     

Relaxed K -Best MIMO Signal Detector Design and VLSI Implementation

Signal detector is a key element in a multiple-input multiple-output (MIMO) wireless communication receiver. It has been well demonstrated that nonlinear tree search MIMO detectors can achieve near-optimum detection performance, nevertheless their efficient high-speed VLSI implementations are not trivial. For example, the hardware design of hard- or soft- output detectors for a 4 times 4 MIMO system with 64 quadrature amplitude modulation (QAM) still remains missing in the open literature. As an attempt to tackle this challenge, this paper presents an implementation-oriented breadth-first tree search MIMO detector design solution. The key is to appropriately modify the conventional breadth-first tree search detection algorithm in order to largely improve the suitability for efficient hardware implementation, while maintaining good detection performance. To demonstrate the effectiveness of the proposed design solution, using 0.13-mum CMOS standard cell and memory libraries, we designed a soft-output signal detector for 4 times 4 MIMO with 64-QAM. With the silicon area of about 31 mm², the detector can achieve above 100 Mb/s and realize the performance very close to that of the sphere decoding algorithm     

Soft input soft output Kalman equalizer for MIMO frequency selective fading channels

We consider the Kalman filter for equalization of a multiple-input multiple-output (MIMO), frequency selective, quasi-static fading channel. More specifically, we consider a coded system, where the incoming bit stream is convolutionally encoded, interleaved and then spatially multiplexed across the transmit antennas. Each substream is modulated into M-ary symbols before being transmitted over a frequency selective channel. At the receiver, we propose to use the Kalman filter as a low complexity MIMO equalizer, as opposed to the trellis based maximum a-posteriori (MAP) equalizer whose computational complexity grows exponentially with the channel memory, the number of transmit antennas and the spectral efficiency (bits/s/Hz) of the system. We modify the structure of the Kalman filter and enable it to process the a-priori (soft) information provided by the channel decoder, thereby allowing us to perform iterative (turbo) equalization on the received sequence. The iterative equalizer structure is designed for general M-ary constellations. We also propose a low complexity version of the above algorithm whose performance is comparable to its full complexity counterpart, but which achieves a significant complexity reduction. We demonstrate via simulations that for higher order constellations, when sufficient number of receive antennas are available (e.g. for a 2 transmitter, 3 receiver system, QPSK), the performance of the proposed algorithms after 4 iterations is within 1.5 dB of the non-iterative MAP algorithm with close to an order of magnitude complexity reduction. By objectively quantifying the complexity of all the considered algorithms we show that the complexity reduction for the proposed schemes becomes increasingly significant for practical systems with moderate to large constellation sizes and a large number of transmit antennas     

Fast Differential Unitary Space-Time Modulation Decoding for a MIMO Radio Channel

Improved decoding efficiency is achieved for differential unitaryspace-time modulation across a multiple-input multiple-output(MIMO) channel. The group nature of constellations used for signaltransmission, and hence a minimised search space for maximumlikelihood (ML) decoding are utilised to give this improvement. Aprocedure using lattice reduction for fast decoding across amultiple-input single-output (MISO) channel is generalised to aMIMO channel effectively, as a modification to a previousproposal, and used to generate the ML decoder search space.Further insight into the application of this algorithm is given.The decoding technique developed is shown to have very good errorperformance for reasonably sized MIMO channels.     

Tree-Search Multiple-Symbol Differential Decoding for Unitary Space-Time Modulation

Differential space-time modulation (DSTM) using unitary-matrix signal constellations is an attractive solution for transmission over multiple-input multiple-output (MIMO) fading channels without requiring channel state information (CSI) at the receiver. To avoid a high error floor for DSTM in relatively fast MIMO fading channels, multiple-symbol differential detection (MSDD) has to be applied at the receiver. MSDD jointly processes blocks of several received matrix-symbols, and power efficiency improves as the blocksize increases. But since the search space of MSDD grows exponentially with the blocksize and also with the number of transmit antennas and the data rate, the complexity of MSDD quickly becomes prohibitive. In this paper, we investigate the application of tree-search algorithms to overcome the complexity limitation of MSDD. We devise a nested MSDD structure consisting of an outer and a number of inner tree-search decoders, which renders MSDD feasible for wide ranges of system parameters. Decoder designs tailored for diagonal and orthogonal DSTM codes are given, and a more power-efficient variant of MSDD, so-called subset MSDD, is proposed. Furthermore, we derive a tight symbol-error rate approximation for MSDD, which lends itself to efficient numerical evaluation. Numerical and simulation results for different DSTM constellations and fading channel scenarios show that the new tree-search MSDD achieves a significantly better performance-complexity tradeoff than benchmark decoders.     

Symbol detection in spatial multiplexing system using particle swarm optimization meta-heuristics

Symbol detection in multi-input multi-output (MIMO) communication systems using different particle swarm optimization (PSO) algorithms is presented. This approach is particularly attractive as particle swarm intelligence is well suited for real-time applications, where low complexity and fast convergence is of absolute importance. While an optimal maximum likelihood (ML) detection using an exhaustive search method is prohibitively complex, PSO-assisted MIMO detection algorithms give near-optimal bit error rate (BER) performance with a significant reduction in ML complexity. The simulation results show that the proposed detectors give an acceptable BER performance and computational complexity trade-off in comparison with ML detection. These detection techniques show promising results for MIMO systems using high-order modulation schemes and more transmitting antennas where conventional ML detector becomes computationally non-practical to use. Hence, the proposed detectors are best suited for high-speed multi-antenna wireless communication systems. Copyright © 2008 John Wiley & Sons, Ltd.     

System Architecture and Implementation of MIMO Sphere Decoders on FPGA

Multiple-input-multiple-output (MIMO) systems use multiple antennas in both transmitter and receiver ends for higher spectrum efficiency. The hardware implementation of MIMO detection becomes a challenging task as the computational complexity increases. This paper presents the architectures and implementations of two typical sphere decoding algorithms, including the Viterbo-Boutros (VB) algorithm and the Schnorr-Euchner (SE) algorithm. Hardware/software codesign technique is applied to partition the decoding algorithm on a single field-programmable gate array (FPGA) device. Three levels of parallelism are explored to improve the decoding rate: the concurrent execution of the channel matrix preprocessing on an embedded processor and the decoding functions on customized hardware modules, the parallel decoding of real/imaginary parts for complex constellation, and the concurrent execution of multiple steps during the closest lattice point search. The decoders for a 4times4 MIMO system with 16-QAM modulation are prototyped on a Xilinx XC2VP30 FPGA device with a MicroBlaze soft core processor. The hardware prototypes of the SE and VB algorithms show that they support up to 81.5 and 36.1 Mb/s data rates at 20 dB signal-to-noise ratio, which are about 22 and 97 times faster than their respective implementations in a digital signal processor.     

ML Approaching MIMO Detection Based on Orthogonal Projection

A detection algorithm for spatially multiplexed multiple input multiple output (MIMO) systems is proposed. The receiver first estimates the MIMO channel and rearranges the layers according to the measured SNRs. To determine the candidate vectors, an orthogonal projection combined with the M-algorithm is used. Without performing the exhaustive full search of the maximum likelihood (ML) method, the proposed algorithm can reach the performance which is closely akin to the ML method. The computational complexity markedly decreases: 0.66% over the ML method in terms of the number of real multiplications.     

Semi-blind maximum-likelihood joint channel/data estimation for correlated channels in multiuser MIMO networks

The aim of this paper is to investigate receiver techniques for maximum likelihood (ML) joint channel/data estimation in flat fading multiple-input multiple-output (MIMO) channels, that are both (i) data efficient and (ii) computationally attractive. The performance of iterative least squares (LS) for channel estimation combined with sphere decoding (SD) for data detection is examined for block fading channels, demonstrating the data efficiency provided by the semi-blind approach. The case of continuous fading channels is addressed with the aid of recursive least squares (RLS). The observed relative robustness of the ML solution to channel variations is exploited in deriving a block QR-based RLS-SD scheme, which allows significant complexity savings with little or no performance loss. The effects on the algorithms’ performance of the existence of spatially correlated fading and line-of-sight paths are also studied. For the multi-user MIMO scenario, the gains from exploiting temporal/spatial interference color are assessed. The optimal training sequence for ML channel estimation in the presence of co-channel interference (CCI) is also derived and shown to result in better channel estimation/faster convergence. The reported simulation results demonstrate the effectiveness, in terms of both data efficiency and performance gain, of the investigated schemes under realistic fading conditions.     

Noncoherent MIMO Communication: Grassmannian Constellations and Efficient Detection

This paper considers the design of both a transmitter and a receiver for noncoherent communication over a frequency-flat, richly scattered multiple-input multiple-output (MIMO) channel. The design is guided by the fact that at high signal-to-noise ratios (SNRs), the ergodic capacity of the channel can be achieved by input signals that are isotropically distributed on the (compact) Grassmann manifold. The first part of the paper considers the design of Grassmannian constellations that mimic the isotropic distribution. A subspace perturbation analysis is used to determine an appropriate metric for the distance between Grassmannian constellation points, and using this metric, greedy, direct and rotation-based techniques for designing constellations are proposed. These techniques offer different tradeoffs between the minimum distance of the constellation and the design complexity. In addition, the rotation-based technique results in constellations that have lower storage requirements and admit a natural “quasi-set-partitioning” binary labeling.      

Soft quasi-maximum-likelihood detection for multiple-antenna wireless channels

The paper addresses soft maximum-likelihood (ML) detection for multiple-antenna wireless communication channels. We propose a soft quasi-ML detector that maximizes the log-likelihood function by deploying a semi-definite relaxation (SDR). Given perfect channel state information at the receiver, the quasi-ML SDR detector closely approximates the performance of the optimal ML detector in both coded and uncoded multiple-input, multiple-output (MIMO) channels with quadrature phase-shift keying (QPSK) modulation and frequency-flat Rayleigh fading. The complexity of the quasi-ML SDR detector is much less than that of the optimal ML detector, thus offering more favorable performance/complexity characteristics. In contrast to the existing sphere decoder, the new quasi-ML detector enjoys guaranteed polynomial worst-case complexity. The two detectors exhibit quite comparable performance in a variety of ergodic QPSK MIMO channels, but the complexity of the quasi-ML detector scales better with increasing number of transmit and receive antennas, especially in the region of low signal-to-noise ratio (SNR).     

Genetic algorithm assisted joint multiuser symbol detection andfading channel estimation for synchronous CDMA systems

A novel multiuser code division multiple access (CDMA) receiver based on genetic algorithms is considered, which jointly estimates the transmitted symbols and fading channel coefficients of all the users. Using exhaustive search, the maximum likelihood (ML) receiver in synchronous CDMA systems has a computational complexity that is exponentially increasing with the number of users and, hence, is not a viable detection solution. Genetic algorithms (GAs) are well known for their robustness in solving complex optimization problems. Based on the ML rule, GAs are developed in order to jointly estimate the users' channel impulse response coefficients as well as the differentially encoded transmitted bit sequences on the basis of the statistics provided by a bank of matched filters at the receiver. Using computer simulations, we showed that the proposed receiver can achieve a near-optimum bit-error-rate (BER) performance upon assuming perfect channel estimation at a significantly lower computational complexity than that required by the ML optimum multiuser detector. Furthermore, channel estimation can be performed jointly with symbol detection without incurring any additional computational complexity and without requiring training symbols. Hence, our proposed joint channel estimator and symbol detector is capable of offering a higher throughput and a shorter detection delay than that of explicitly trained CDMA multiuser detectors     

A Novel Maximum Likelihood Decoding Algorithm for Orthogonal Space-Time Block Codes

In this letter, we propose a low complexity Maximum Likelihood (ML) decoding algorithm for orthogonal spacetime block codes (OSTBCs) based on the real-valued lattice representation and QR decomposition.We show that for a system with rate r = K/T, where K is the number of transmitted symbols per T time slots, the proposed algorithm decomposes the original complex-valued system into a parallel system represented by 2K real-valued components, thus allowing for a simple and independent detection of the real and imaginary parts of each complex transmitted symbol. We further show that for square L-QAM constellations, the proposed algorithm reduces the decoding computational complexity from /spl pdelta/(L) for conventional ML to /spl pdelta/(?L) without sacrificing the performance.     

LDPC coded MIMO multiple access with iterative joint decoding

An efficient scheme for the multiple-access multiple-input multiple-output (MIMO) channel is proposed, which operates well also in the single user regime, as well as in a direct-sequence spread-spectrum (DS-CDMA) setting. The design features scalability and is of limited complexity. The system employs optimized low-density parity-check (LDPC) codes and an efficient iterative (belief propagation-BP) detection which combines linear minimum mean-square error (LMMSE) detection and iterative interference cancellation (IC). This combination is found to be necessary for efficient operation in high system loads /spl alpha/>1. An asymptotic density evolution (DE) is used to optimize the degree polynomials of the underlining LDPC code, and thresholds as close as 0.77 dB to the channel capacity are evident for a system load of 2. Replacing the LMMSE with the complex individually optimal multiuser detector (IO-MUD) further improves the performance up to 0.14 dB from the capacity. Comparing the thresholds of a good single-user LDPC code to the multiuser optimized LDPC code, both over the above multiuser channel, reveals a surprising 8-dB difference, emphasizing thus the necessity of optimizing the code. The asymptotic analysis of the proposed scheme is verified by simulations of finite systems, which reveal meaningful differences between the performances of MIMO systems with single and multiple users and demonstrate performance similar to previously reported techniques, but with higher system loads, and significantly lower receiver complexity.     

MIMO-FSK non-coherent detection with spatial multiplexing infast-fading environment

Accurate estimationand real-time compensation for phase offset and Doppler shift are essential for coherent multi-input multi-output (MIMO) systems. Here, a spatial multiplexing MIMO scheme with non-coherent frequency-shiftkeying (FSK) detection is proposed. It is immune to random phase interference and Doppler shift while increasingcapacity. It is valuable that the proposed spatial multiplexing MIMO based on energy detection (ED) is equivalentto a linear system, and there is no mutual interference caused by the product of simultaneous signals in square-lawprocessing. The equivalent MIMO channel model is derived as a real matrix, which remains maximal multiplexingcapacity and reduces the channel estimation complexity. Simulation results show that the proposed scheme hasoutstanding performance over Rician flat fading channel, and experimental system obtains four times the capacitythrough 4 antennas on both transmitter and receiver.     

广义空间调制系统的低复杂度检测算法

针对广义空间调制( GSM)系统接收端最大似然( ML)检测算法计算复杂度极高的缺点,提出了一种基于压缩感知( CS)信号重构理论的低复杂度信号检测算法。首先,在多输入多输出( MI-MO)信道模型下,通过改进正交匹配追踪( OMP)算法,得到一个激活天线索引备选集;然后,利用ML算法在该备选集中进行遍历搜索,检测出激活天线索引和星座调制符号。仿真结果表明所提算法的检测性能接近于ML算法,且复杂度约为ML算法的2%。因此,所提算法在保证检测性能的同时也大大降低了计算复杂度,实现了检测性能与复杂度之间的平衡。     

Code and receiver design for the noncoherent fast-fading channel

This paper deals with the design of coding/modulation and demodulation/decoding schemes for single- or multiple-antenna systems with focus on fast-fading channels, where channel state information (CSI) is not available at the transmitter and the receiver. We explore two possible solutions for this channel with increasing degree of sophistication. The first one utilizes pilots at the transmitter and a simple and explicit noniterative channel estimation algorithm at the receiver. We show that this pilot-assisted system is exactly equivalent, in terms of performance analysis and design, to an appropriately "degraded" system having perfect CSI at the receiver. The second scheme utilizes pilots and a family of well-justified and simple suboptimal iterative detection/estimation algorithms. It is shown that when turbo-like codes are considered in conjunction with this pilot-assisted transmission scheme and the proposed receiver algorithm, the unitary constellations investigated in the literature are inferior to simple pilot-assisted constellations in both complexity and performance. Specific instances of the proposed systems (that use optimized irregular low-density parity-check outer codes) are designed. The design examples provided show that the proposed systems can achieve a good tradeoff between complexity and performance and can be used to bridge the gap between the high complexity/high-performance optimal scheme and low-complexity/mediocre performance noniterative estimation/coherent detection scheme.     

Iterative tree search detection for MIMO wireless systems

This paper presents a reduced-complexity soft-input soft-output detection scheme, called iterative tree search detection, for multiple-input multiple-output wireless communication systems employing turbo processing at the receiver. In this scheme, a reduced search space is selected with the aid of the M-algorithm, and QAM signal constellations with block partitionable labels are used in order to make the detection complexity per bit almost independent of the modulation order, as well as asymptotically linear in the number of transmit antennas. Results from computer simulations are presented which demonstrate the capability of the scheme to approach optimal performance at considerably reduced complexity.     

MIMO Detection Techniques Based on Low Complexity Adaptive QR-Decomposition with M-Algorithm for 3GPP LTE Systems

In this paper, two novel multiple-input multiple-output (MIMO) detection algorithms, adaptive parallel QRDM (APQRDM) and adaptive iterative QRDM (AIQRDM) which are able to achieve the similar detection throughput as conventional QRDM while reducing the computational complexity, are introduced, and the system performances are evaluated on the platform of 3GPP LTE downlink. In both 2 ×?2 and 4 ×?4 MIMO, APQRDM and AIQRDM algorithms can achieve almost same packet error rate performance as those of conventional QRDM algorithm, while the computational complexity is significantly reduced. Also, the receiver employing APQRDM and AIQRDM detection algorithms shows the almost same throughput as the case of conventional MIMO detection algorithms. Furthermore, practical channel estimation techniques are employed, and the system performances are thoroughly analyzed and discussed.