A new ordering for efficient sphere decoding

Abstract

This paper presents a novel pre-processing stage that offers significant improvement in the computational efficiency of sphere decoding by imposing a geometrically-inspired ordering on the columns of the channel matrix. By studying the performance of a genie decoder, which has knowledge of the optimal radius, we find that the optimal ordering depends not only on the channel matrix, but also on the received point. Analysis of this idealized problem leads to the proposal of an enhanced ordering. We demonstrate via simulation that it closely matches with the optimal ordering and more importantly that it results in a dramatic increase in sphere decoding efficiency over a 4/spl times/4 MIMO flat fading channel. We emphasize that the performance benefit is particularly great at low SNRs and for high modulation orders, two traditionally challenging regimes for sphere decoders. We conclude by briefly discussing the polynomial complexity of the new ordering algorithm.