On the Complexity Distribution of Sphere Decoding
2011 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, Vol. 57, no 9, 5754-5768 p.Article in journal (Refereed) Published
We analyze the (computational) complexity distribution of sphere decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is fully determined by the inverse volume of the fundamental regions of the underlying lattice. Particularizing this result to N x M, N ≥ M, i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by N-M+1. A more refined analysis reveals that the corresponding average complexity of SD is infinite for N = M and finite for N >; M. Finally, for i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we analyze SD preprocessing techniques based on lattice-reduction (such as the LLL algorithm or layer-sorting according to the V-BLAST algorithm) and regularization. In particular, we show that lattice-reduction does not improve the tail exponent of the complexity distribution while regularization results in a SD complexity distribution with tails that decrease faster than polynomial.
Place, publisher, year, edition, pages
IEEE , 2011. Vol. 57, no 9, 5754-5768 p.
Complexity theory, Decoding, Lattices, MIMO, Polynomials, Probability density function, Symmetric matrices
IdentifiersURN: urn:nbn:se:kth:diva-46470DOI: 10.1109/TIT.2011.2162177ISI: 000295738800013ScopusID: 2-s2.0-80052360610OAI: oai:DiVA.org:kth-46470DiVA: diva2:453745
QC 201111032011-11-032011-11-032011-11-07Bibliographically approved