This paper presents results on trellis complexity and low-complexity trellis diagrams of lattices. We establish constructive upper bounds on the trellis complexity of lattices. These bounds both improve and generalize the similar results of [35]. We also construct trellis diagrams with minimum number of paths for some important lattices. Such trellises are called minimal. The constructed trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm. In particular, a general structure for minimal trellis diagrams of Dn lattices is obtained. This structure corresponds to a new code formula for Dn. Moreover, we develop some important duality results which are used in both deriving the upper bounds, and finding the minimal trellises. All the discussions are based on a universal approach to the construction and analysis of trellis diagrams of lattices using their bases.

Additional Metadata
Keywords Korkin-zolotarev reduced basis, lattices, minimal trellis, successive minima, trellis complexity, trellis decoding
Persistent URL dx.doi.org/10.1109/18.705562
Journal IEEE Transactions on Information Theory
Citation
Banihashemi, A, & Blake, L.F. (Lan F.). (1998). Trellis complexity and minimal trellis diagrams of lattices. IEEE Transactions on Information Theory, 44(5), 1829–1847. doi:10.1109/18.705562