Tail Behavior of Sphere-Decoding Complexity in Random Lattices

Details Tail Behavior of Sphere-Decoding Complexity in Random Lattices Tail Behavior of Sphere-Decoding Complexity in Random Lattices

2009-05-08

arxiv.org/abs/0905.1215v1

Computer Science

Information Theory

To be presented at IEEE ISIT 2009, Seoul, Korea

Scientific paper

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 NxM, 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.

Affiliated with

Also associated with

No associations

Rating

Tail Behavior of Sphere-Decoding Complexity in Random Lattices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tail Behavior of Sphere-Decoding Complexity in Random Lattices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tail Behavior of Sphere-Decoding Complexity in Random Lattices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-703394