# Upper bounds on trellis complexity of lattices

Conference Paper

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.

### Full Text

### Duke Authors

### Cited Authors

- Tarokh, V; Vardy, A

### Published Date

- December 1, 1997

### Published In

### Start / End Page

- 385 -

### International Standard Serial Number (ISSN)

- 2157-8095

### International Standard Book Number 10 (ISBN-10)

- 0780339568

### International Standard Book Number 13 (ISBN-13)

- 9780780339569

### Digital Object Identifier (DOI)

- 10.1109/ISIT.1997.613322

### Citation Source

- Scopus