An Exponential Lower Bound on the Expected Complexity of Sphere Decoding
2004 (English)In: Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing, 2004, 393-396 p.Conference paper (Refereed)
The sphere decoding algorithm is an efficient algorithm used to solve the maximum likelihood detection problem in several digital communication systems. The sphere decoding algorithm has previously been claimed to have polynomial expected complexity. While it is true that the algorithm has an expected complexity comparable to that of other polynomial time algorithms for problems of moderate size it is a misconception that the expected number of operations asymptotically grow as a polynomial function of the problem size. In order to illustrate this point we derive an exponential lower bound on the expected complexity of the sphere decoder.
Place, publisher, year, edition, pages
2004. 393-396 p.
Digital communication, Gaussian noise, MIMO, Maximum likelihood decoding, Maximum likelihood detection, Maximum likelihood estimation, Polynomials, Quadrature amplitude modulation, Sensor systems, Signal to noise ratio
Signal Processing Telecommunications
IdentifiersURN: urn:nbn:se:kth:diva-63596DOI: 10.1109/ICASSP.2004.1326846ISI: 000222179500099ScopusID: 2-s2.0-4544278544OAI: oai:DiVA.org:kth-63596DiVA: diva2:482435
IEEE International Conference on Acoustics, Speech, and Signal Processing, Montreal, CANADA, MAY 17-21, 2004
QC 201202012012-01-232012-01-232014-12-11Bibliographically approved