Skip to main content

Upper bounds on trellis complexity of lattices

Publication ,  Journal Article
Tarokh, V; Vardy, A
Published in: IEEE Transactions on Information Theory
December 1, 1997

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 A 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 where V(ΛA) 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)/2V(Λ) 2i2/n. Although these bounds are seldom tight, these are the first known general upper bounds on trellis complexity of lattices. © 1997 IEEE.

Duke Scholars

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

December 1, 1997

Volume

43

Issue

4

Start / End Page

1294 / 1300

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Tarokh, V., & Vardy, A. (1997). Upper bounds on trellis complexity of lattices. IEEE Transactions on Information Theory, 43(4), 1294–1300. https://doi.org/10.1109/18.605598
Tarokh, V., and A. Vardy. “Upper bounds on trellis complexity of lattices.” IEEE Transactions on Information Theory 43, no. 4 (December 1, 1997): 1294–1300. https://doi.org/10.1109/18.605598.
Tarokh V, Vardy A. Upper bounds on trellis complexity of lattices. IEEE Transactions on Information Theory. 1997 Dec 1;43(4):1294–300.
Tarokh, V., and A. Vardy. “Upper bounds on trellis complexity of lattices.” IEEE Transactions on Information Theory, vol. 43, no. 4, Dec. 1997, pp. 1294–300. Scopus, doi:10.1109/18.605598.
Tarokh V, Vardy A. Upper bounds on trellis complexity of lattices. IEEE Transactions on Information Theory. 1997 Dec 1;43(4):1294–1300.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

December 1, 1997

Volume

43

Issue

4

Start / End Page

1294 / 1300

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing