On the Complexity of Sphere Decoding in Digital Communications

Abstrakt:

Sphere Decoding, originally an algorithm to find vectors of short length in lattices, has recently been suggested by a number of authors as an efficient algorithm to solve various maximum likelihood (ML) detection problems in digital communication. Often the algorithm is referred to as an algorithm of polynomial complexity, and some papers have previously been published in communication literature in support of this claim. This is a somewhat surprising result, especially since the ML detection problem, in general, is known to be NP-hard. However, as will be argued in this talk by making some assumptions on the detection problems, these claims are probably not correct and the complexity of the algorithm is instead exponential

It will in this talk be argued that, although always exponential, the complexity is strongly dependent on some parameters of the communication system, such as for example the signal to noise ratio (SNR). This will be done by first briefly discussing the differences between the detection problem and the related lattice problem to show what assumptions can be made about the detection problem. It will then be outlined how these assumptions lead to an exponential lower bound on the complexity of the algorithm. Also, numerical examples will be given to show the effect of different parameters on the complexity. Special attention will be given to how the algorithm benefits from a high SNR.