In the setting of quasi-static multiple-input multipleoutput (MIMO) channels, we consider the high signal-to-noise (SNR) asymptotic complexity required by the sphere decoding (SD) algorithm for decoding a large class of full rate linear space-time codes. With SD complexity being a function of the code and having random fluctuations with varying channel, noise
and codewords, the introduced SD complexity exponent manages to concisely describe the computational reserves required by the SD algorithm to achieve arbitrarily close to optimal performance in decoding the such codes. It is worth noting that, to date, this asymptotically describes the minimum known complexity required for a decoder and time-out policy to provably allow a gap to maximum likelihood performance that vanishes for increasing SNR. Bounds and exact expressions for the SD complexity exponent are then obtained for a large set of existing code designs of varying performance characteristics. For all currently known unified explicit code designs that are uniformly optimal with respect to the diversity multiplexing tradeoff (DMT), the SD complexity exponent is shown to take a particularly concise form as a function of the multiplexing gain.
