Tail Behavior of Sphere-Decoding Complexity in Random Lattices
2009 (English)In: 2009 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, NEW YORK: IEEE , 2009, 729-733 p.Conference paper (Refereed)
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 solely determined by the inverse volume of a fundamental region of the underlying lattice. Particularizing this result to N x M, N >= M, i.i.d. Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by N - M + 1. We furthermore show that this tail exponent is not improved by lattice-reduction, which includes layer-sorting as a special case.
Place, publisher, year, edition, pages
NEW YORK: IEEE , 2009. 729-733 p.
Other Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-34885ISI: 000280141400149OAI: oai:DiVA.org:kth-34885DiVA: diva2:427872
IEEE International Symposium on Information Theory (ISIT 2009) Seoul, SOUTH KOREA, JUN 28-JUL 03, 2009
QC 201106292011-06-292011-06-172011-06-29Bibliographically approved