We analyze the (computational) complexity distribution of sphere decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is fully determined by the inverse volume of the fundamental regions of the underlying lattice. Particularizing this result to${N} \times {M},$${N} \geq {M}$, i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by${N}-{M}+1$. A more refined analysis reveals that the corresponding average complexity of SD is infinite for${N} = {M}$and finite for${N} > {M}$. Finally, for i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we analyze SD preprocessing techniques based on lattice-reduction (such as the LLL algorithm or layer-sorting according to the V-BLAST algorithm) and regularization. In particular, we show that lattice-reduction does not improve the tail exponent of the complexity distribution while regularization results in a SD complexity distribution with tails that decrease faster than polynomial.

Lattice-reduction (LR)-aided successive interference cancellation (SIC) is able to achieve close-to optimum error-rate performance for data detection in multiple-input multiple-output (MIMO) wireless communication systems. In this work, we propose a hardware-efficient VLSI architecture of the Lenstra-Lenstra-Lovász (LLL) LR algorithm for SIC-based data detection. For this purpose, we introduce various algorithmic modifications that enable an efficient hardware implementation. Comparisons with existing FPGA implementations show that our design outperforms state-of-the-art LR implementations in terms of hardware-efficiency and throughput. We finally provide reference ASIC implementation results for 130nm CMOS technology.

Promising approaches for efficient detection in multiple-input multiple-output (MIMO) wireless systems are based on sphere-decoding (SD). The conventional (and optimum) norm that is used to conduct the tree traversal step in SD is thel2-norm. It was, however, recently observed that using thel¿-norm instead reduces the hardware complexity of SD considerably at only a marginal performance loss. These savings result from a reduction in the length of the critical path in the circuit and the silicon area required for metric computation, but are also, as observed previously through simulation results, a consequence of a reduction in the computational (i.e., algorithmic) complexity. The aim of this paper is an analytical performance and computational complexity analysis ofl¿-norm SD. For independent and identically distributed (i.i.d.) Rayleigh fading MIMO channels, we show thatl¿-norm SD achieves full diversity order with an asymptotic SNR gap, compared tol2-norm SD, that increases at most linearly in the number of receive antennas. Moreover, we provide a closed-form expression for the computational complexity ofl¿-norm SD based on which we establish that its complexity scales exponentially in the system size. Finally, we characterize the tree pruning behavior ofl¿-norm SD and show that it behaves fundamentally different from that ofl2-norm SD.

In this paper we consider the vector perturbation (VP) precoding scheme for the multiuser MISO broadcast channel proposed by Hochwald et al. under the practical assumption that the receivers have limited dynamic range. In this case, VP precoding is shown to suffer from an error floor at high signal-to-noise ratio (SNR). As an alternative, we propose precoding with restricted VP (RVP), which takes the limited dynamic range of the receivers explicitly into account by restricting to a finite set of possible perturbation vectors at the transmitter side. We derive the diversity order of this RVP scheme and show that no error floor occurs and that the performance is superior to VP for the entire range of SNRs.

We analyze the (computational) complexity distribution of sphere-decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is solely determined by the inverse volume of a fundamental region of the underlying lattice. Particularizing this result to N × M, N ¿ M, i.i.d. Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by N - M + 1. We furthermore show that this tail exponent is not improved by lattice-reduction, which includes layer-sorting as a special case.

Lattice reduction by means of the LLL algorithm has been previously suggested as a powerful preprocessing tool that allows to improve the performance of suboptimal detectors and to reduce the complexity of optimal MIMO detectors. The complexity of the LLL algorithm is often cited as polynomial in the dimension of the lattice. In this paper we argue that this statement is not correct when made in the MIMO context. Specifically, we demonstrate that in typical communication scenarios the worst-case complexity of the LLL algorithm is not even finite. For i.i.d. Rayleigh fading channels, we further prove that the average LLL complexity is polynomial and that the probability for an atypically large number of LLL iterations decays exponentially.

The most promising approaches for efficient detection in multiple-input multiple-output (MIMO) wireless systems are based on sphere-decoding (SD). The conventional (and optimum) norm that is used to conduct the tree traversal step in SD is the l2-norm. It was, however, recently shown that using the linfin-norm instead significantly reduces the VLSI implementation complexity of SD at only a marginal performance loss. These savings are due to a reduction in the length of the critical path and the silicon area of the circuit, but also, as observed previously through simulation results, a consequence of a reduction in the computational (algorithmic) complexity. The aim of this paper is an analytical performance and computational complexity analysis of linfin-norm SD. For i.i.d. Rayleigh fading MIMO channels, we show that linfin-norm SD achieves full diversity order with an asymptotic SNR gap, compared to l2-norm SD, that increases at most linearly in the number of receive antennas. Moreover, we provide a closed-form expression for the computational complexity of linfin-norm SD.

In this paper, we consider MIMO spatial multiplexing systems and elaborate the impact of the channel condition number on the performance of ML and ZF detection. In particular, we show that for channels with bounded condition number ZF detection achieves the same diversity as ML detection. Motivated by this, we propose a novel threshold receiver that uses simple ZF detection for well-conditioned channels and ML detection for poorly conditioned channels. We show that this receiver achieves full diversity and we provide an upper bound on its SNR gap to ML detection. We further investigate cost-reduced versions of the threshold receiver and examine their performance in terms of simulation results.

Lattice reduction (LR) is a powerful technique for improving the performance of suboptimum MIMO data detection methods. For LR-assisted data detection, the LLL algorithm has been considered almost exclusively so far. In this paper, we propose and develop the application of Seysen's algorithm (SA) to LR-assisted MIMO detection, and we show that the SA is a promising alternative to the LLL algorithm. Specifically, the SA outperforms the LLL algorithm in that it finds better lattice bases for MIMO systems of practical interest, which is reflected by an improved performance of SA-assisted detectors relative to their LLL-assisted counterparts. We present an efficient implementation of the SA whose per-iteration complexity is linear in the number of antennas, and we demonstrate that the SA requires significantly fewer iterations than the LLL algorithm.

This paper describes the first VLSI implementation of lattice reduction (LR) aided multi-antenna broadcast precoding with vector perturbation. The considered LR, scheme is based on Brun's algorithm for finding integer relations. We analyze its high-level architectural issues, we devise a corresponding low-complexity implementation, and, finally, we develop a suitable VLSI architecture. The resulting circuit provides reference for the true silicon complexity of LR, for broadcast precoding with vector perturbation

We propose an iterative receiver for horizontally encoded MIMO systems like the PARC proposal for MIMO-HSDPA. Our receiver uses a K-best-MAP demodulator to provide the channel decoder with approximate log-likelihood ratios. The complexity of K-best-MAP is reduced by exploiting the CRC present in each encoded layer. We show that K-best-MAP with list update is superior to demodulation using a fixed candidate list. Finally, our numerical results demonstrate significant SNR gains as compared to a receiver using MMSE-based successive interference cancelation.

MIMO-OFDM using bit-interleaved coded modulation (BICM) is an attractive scheme for wireless communications in frequency-selective fading channels. The BICM decoder requires log-likelihood ratios (LLRs) whose exact computation is extremely costly. In this paper, we present a novel method termed soft sphere-projection algorithm (SSPA) that provides approximate LLRs for the case of constant modulus symbol alphabets. The SSPA has very low computational complexity and performs nearly as well as the list sphere decoder. These properties are demonstrated by numerical simulations using synthetic and measured MIMO channels

The geometric mean of the eigenvalues of multiple-input multiple-output (MIMO) channels is a parameter occurring in a variety of instances, including MIMO transceiver design based on the so-called geometric mean decomposition (GMD), and MIMO mutual information at high SNR. In this paper, we derive the asymptotic geometric mean of MIMO channel eigenvalues in the case where the entries of the channel matrix are independent and identically distributed. We demonstrate that the result can be easily extended to channels with an exponential correlation model. As an application of the result, we provide an analytical expression for the asymptotic system capacity of GMD-based transceivers

Bit-interleaved coded modulation (BICM) is an attractive transmission scheme for MIMO wireless communications over fast fading channels. BICM receivers employing maximum-likelihood decoding require a soft demodulator (demapper) that calculates log-likelihood ratios (LLRs) for the coded bits. Because in the MIMO case the calculation of LLRs tends to he excessively complex, there is a strong demand for efficient soft demodulation algorithms that calculate approximate LLRs. Here, we develop the novel soft line-search demodulator (SLSD) by extending the recently introduced line-search detector (LSD) such that approximate LLRs are obtained with little extra computations. We show that the SLSD's BER performance Ls close to that of the list extension of the sphere decoding algorithm even though the complexity is significantly smaller.

In bit-interleaved coded modulation (BICM) systems employing maximum-likelihood decoding, a demodulator (demapper) calculates a log-likelihood ratio (LLR) for each coded bit, which is then used as a bit metric for Viterbi decoding. In the MIMO case, the computational complexity of LLR calculation tends to be excessively high, even if the log-sum approximation is used. Thus, there is a strong demand for efficient suboptimum MIMO-BICM demodulation algorithms with near-optimum performance. We propose an efficient MIMO-BICM demodulator that is derived by means of a Gaussian approximation for the post-detection interference. Our derivation results in an MMSE equalizer followed by per-layer LLR calculation (i.e., LLRs are calculated separately for each layer). The novel demodulator can be interpreted as an MMSE analogue of a recently proposed ZF-equalization based demodulator, as well as an extension of ZF-equalization based demodulation to correlated post-detection interference. Because it performs per-layer LLR calculation, it has the same (low) computational complexity as the ZF-equalization based demodulator. Simulation results demonstrate that the performance of our demodulator is close to that of LLR calculation using all layers jointly, and significantly better than that of the ZF-equalization based demodulator.

The conventional nulling-and-cancelling (NC) detection scheme for MIMO systems uses the layerwise post-detection mean-square errors (MSEs) as reliability measures for layer sorting. These MSEs are average measures that do not depend on the received vector. We propose a novel dynamic nulling-and-cancelling (DNC) detector that performs "dynamic" layer sorting based on the current received vector. Approximate a-posteriori probabilities (constructed by means of a Gaussian approximation for the postdetection interference) are used as measures of layer reliability. This results in an MMSE nulling technique that uses a simple layer-sorting rule with significantly improved performance. Our simulation results show that the DNC scheme can yield near-ML performance for a wide range of system sizes and signal-to-noise ratios.

It is well known that suboptimal detection schemes for MIMO spatial multiplexing systems (equalization-based as well as nulling-and-cancelling detectors) cannot exploit all of the available diversity. We show that this inferior performance is primarily caused by poorly conditioned channel realizations. We then present the novel sphere-projection algorithm (SPA) that is robust to poorly conditioned channels. The SPA is a computationally efficient add-on to standard suboptimal detectors. Simulation results show that the SPA is able to achieve near-ML performance and significantly increased diversity gains. The SPA's computational complexity is comparable to that of nulling-and-cancelling detectors and only a fraction of that of the Fincke-Phost sphere-decoding algorithm for ML detection (Fincke, U. and Phost, M., Math. of Comp., vol.44, p.463-71, 1985).