Tail behavior of sphere-decoding complexity in random lattices
METADATA ONLY
Loading...
Author / Producer
Date
2009
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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 × 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.
Permanent link
Publication status
published
External links
Editor
Book title
2009 IEEE International Symposium on Information Theory
Journal / series
Volume
Pages / Article No.
729 - 733
Publisher
IEEE
Event
IEEE International Symposium on Information Theory (ISIT 2009)