Unlike block codes, the number of distinct paths on the trellis diagrams of lattices (N) depends highly on the selected (trellis) coordinate system. Focusing on N as the measure of complexity, it is shown that the problem of finding a proper trellis of a lattice can be reduced to the problem of finding a proper basis for the lattice. For a lattice Λ with coding gain γ and dimension n, a lower bound of the form [γn/2] on N is derived. A trellis of Λ is called minimal if it achieves the lower bound (or more generally, if it minimizes N). For many important lattices like Barnes-Wall lattices BWn, n = 2m, the Leech lattice Λ24, Dn, Dn ⊥, En, En ⊥, and An, An ⊥, n≤9, we obtain the basis matrices which result in minimal trellis diagrams. For some other lattices like the Coxeter-Todd lattice K12, and An, An ⊥, n>9, trellises with small values of N (probably not minimal) are obtained. The constructed trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm.

Proceedings of the 1997 IEEE International Symposium on Information Theory
Department of Systems and Computer Engineering

Banihashemi, A, & Blake, Ian F. (Ian F.). (1997). Minimal trellis diagrams of lattices. In IEEE International Symposium on Information Theory - Proceedings.