On the limits of sphere decoding
2005 (English)In: 2005 IEEE International Symposium on Information Theory (ISIT), Vols 1 and 2, NEW YORK: IEEE , 2005, 1691-1695 p.Conference paper (Refereed)
The sphere decoder has emerged as one of the most promising techniques for maximum likelihood detection of symbols transmitted over a general MIMO channel. Although efficient for problems of moderate size it is known that the original sphere decoder is of exponential (expected) complexity which limits its usage for large scale problems. However, at this stage, many alterations and improvements over the original algorithm have appeared in the literature. Herein we study a generic sphere decoder for the i.i.d. Rayleigh fading MIMO channel. The detection ordering and search radius (parameters of the algorithm) are allowed to be arbitrary functions of the decoder input, the only restriction being that the search radius is chosen such that the detection problem is solved. It is shown that the set of problem instances solvable by the sphere decoder in less than exponential time will tend to zero with increasing problem size. This extends previous results by providing a statement which is stronger than exponential expected complexity while relaxing the assumptions regarding the specific decoder implementation.
Place, publisher, year, edition, pages
NEW YORK: IEEE , 2005. 1691-1695 p.
MIMO systems, Rayleigh channels, decoding, maximum likelihood detection
IdentifiersURN: urn:nbn:se:kth:diva-34962DOI: 10.1109/ISIT.2005.1523633ISI: 000234713801102ScopusID: 2-s2.0-33749426390ISBN: 0-7803-9150-0OAI: oai:DiVA.org:kth-34962DiVA: diva2:427173
IEEE International Symposium on Information Theory Adelaide, AUSTRALIA, SEP 04-09, 2005
QC 201106272011-06-272011-06-172012-01-23Bibliographically approved