Reduced complexity sphere decoding and application to interfering IEEE 802.15.3a piconets
The sphere decoding (SD) algorithm has been widely recognized as an important algorithm to solve the maximum likelihood detection (MLD) problem, given that symbols can only be selected from a set with a finite alphabet. The complexity of the sphere decoding algorithm is much lower than the directly implemented MLD method, which needs to search through all possible candidates before making a decision. However, in high-dimensional and low signal-to-noise ratio (SNR) cases, the complexity of sphere decoding is still prohibitively high for practical applications. In this paper, a simplified SD algorithm, which combines the K-best algorithm and SD algorithm, is proposed. With carefully selected parameters, the new SD algorithm, called SD-KB algorithm, can achieve very low complexity with acceptable performance degradation compared with the traditional SD algorithm. The low complexity of the new SD-KB algorithm makes it applicable to the simultaneously operating piconets (SOP) problem of the multi-band orthogonal frequency division multiplex (MB-OFDM) scheme for the high- speed wireless personal area network (WPAN). We show in particular that the proposed algorithm provides over 4 dB gain in bit error rate (BER) performance over the baseline MB-OFDM scheme when several piconets interfere with each other. The SD-KB algorithm can provide pseudo-MLD solutions, which have significant performance gain over the baseline method, especially when the signal-to-interference ratio (SIR) is low. The cost of performance improvement is higher complexity. However, the new SD algorithm has predictable computation complexity even in the worst scenario.