Upper bounds on trellis complexity of lattices

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 |S_i|⩽(2/√3)^i2(n-1)V(Λ)²ⁱ² n/. Although these bounds are seldom tight, these are the first known general upper bounds on trellis complexity of lattices