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.

Korkin-zolotarev reduced basis, lattices, minimal trellis, successive minima, trellis complexity, trellis decoding
dx.doi.org/10.1109/18.705562
IEEE Transactions on Information Theory
Department of Systems and Computer Engineering

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