The complexity of sphere decoding perfect codes under a vanishing gap to ML performance
2011 (English)In: 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), IEEE , 2011, 2836-2840 p.Conference paper (Refereed)
We consider the complexity of the sphere decoding (SD) algorithm when decoding a class of full rate space-time block codes that are optimal, over the quasi-static MIMO channel, with respect to the diversity-multiplexing tradeoff (DMT). Towards this we introduce the SD complexity exponent which represents the high signal-to-noise ratio (SNR) exponent of the tightest run-time complexity constraints that can be imposed on the SD algorithm while maintaining arbitrarily close to maximum likelihood (ML) performance. Similar to the DMT exposition, our approach naturally captures the dependence of the SD algorithm's computational complexity on the codeword density, code size and channel randomness, and provides simple closed form solutions in terms of the system dimensions and the multiplexing gain.
Place, publisher, year, edition, pages
IEEE , 2011. 2836-2840 p.
, IEEE International Symposium on Information Theory - Proceedings, ISSN 2157-8095
IdentifiersURN: urn:nbn:se:kth:diva-46338DOI: 10.1109/ISIT.2011.6034092ISI: 000297465103044ScopusID: 2-s2.0-80054820303ISBN: 978-1-4577-0596-0ISBN: 978-1-4577-0594-6OAI: oai:DiVA.org:kth-46338DiVA: diva2:453683
IEEE International Symposium on Information Theory Proceedings, ISIT 2011. St. Petersburg. 31 July 2011 through 5 August 2011
QC 201111072011-11-032011-11-032012-04-03Bibliographically approved