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