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.
The complexity of sphere decoding perfect codes under a vanishing gap to ML performance
ISIT 2011, IEEE International Symposium on Information Theory, July 31-August 5, 2011, Saint-Petersburg, Russia
Type:
Conference
City:
Saint-Petersburg
Date:
2011-07-31
Department:
Communication systems
Eurecom Ref:
3551
Copyright:
© 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
See also:
PERMALINK : https://www.eurecom.fr/publication/3551
