  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 l-2 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 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 l-2 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 l-2 norm
SD.
