Performance and complexity analysis of infinity-norm sphere-decoding

Authors

Dominik Seethaler and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 56, No. 3, pp. 1085-1105, Mar. 2010.

DOI: 10.1109/TIT.2009.2039034

Abstract

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 observed that using the l-infinity-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 of l-infinity-norm SD. For independent and identically distributed (i.i.d.) Rayleigh fading MIMO channels, we show that l-infinity-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 l-infinity-norm SD based on which we establish that its complexity scales exponentially in the system size. Finally, we characterize the tree pruning behavior of l-infinity-norm SD and show that it behaves fundamentally different from that of l2-norm SD.

Keywords

Algorithmic complexity, data detection, hardware complexity, infinity norm, maximum-likelihood, multiple-input multiple-output (MIMO) wireless

Download this document:

Copyright Notice: © 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.