Complexity Limited Sphere Decoder and its SER Performance Analysis

It is well known that the sphere decoder has polynomial complexity at high signal to noise ratio (SNR). However, the worst case complexity is exponential leading to severe decoding time delay. In this paper, we present a scheme to overcome the worst case complexity of the sphere decoder. If the number of visited lattice points reaches the threshold, the detected symbol vector is determined between two candidate symbol vectors. One candidate symbol vector is obtained from the demodulated output of ZF receiver which is initial stage of the sphere decoder. The other candidate symbol vector consists of two sub-symbol vectors. The first sub-symbol vector consists of lately visited lattice points running from the most upper layer. The second one contains corresponding demodulated outputs of zero-forcing (ZF) receiver. Between these two candidate symbol vectors, the one with smaller Fuclidean distance to the received symbol vector is chosen as detected symbol vector. In addition, we show the upper bound of symbol error rate (SER) performance for the sphere decoder using the proposed scheme. In the simulation, the proposed scheme shows the significant reduction of the worst case complexity while having negligible SER performance degradation.