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. We show by a counter-example 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, we prove that if Λ is a sublattice of Zn then it has a trellis T, such that the maximum number of states in T is upper bounded by the volume of Λ. Furthermore, using a theorem due to Hermite, we show that every integral lattice Λ has a trellis T, such that the total number of paths in T can be bounded from above in terms of the volume of Λ. The resulting bounds are exponential in the dimension n and are seldom tight. Nonetheless, these are the first known general upper bounds on trellis complexity of lattices. © 1997 IEEE.

Duke Scholars

Author Vahid Tarokh Electrical and Computer Engineering