Upper bounds on trellis complexity of lattices |
| |
Authors: | Tarokh V. Vardy A. |
| |
Affiliation: | AT&T Bell Labs., Murray Hill, NJ; |
| |
Abstract: | Unlike block codes, n-dimensional lattices can have minimal trellis diagrams with an arbitrarily large number of states, branches, and paths. In particular, we show by a counterexample that there is no f(n), a function of n, such that all rational lattices of dimension n have a trellis with less than f(n) states. Nevertheless, using a theorem due to Hermite, we prove that every integral lattice Λ of dimension n has a trellis T, such that the total number of paths in T is upper-bounded by P(T)⩽n!(2/√3)n2(n-1/2)V(Λ) n-1 where V(n) is the volume of Λ. Furthermore, the number of states at time i in T is upper-bounded by |Si|⩽(2/√3)i2(n-1)V(Λ)2i2 n/. Although these bounds are seldom tight, these are the first known general upper bounds on trellis complexity of lattices |
| |
Keywords: | |
|
|