Trellis complexity of root lattices An, Dn, En, and their duals is investigated. Using N, the number of distinct paths in a trellis, as the measure of trellis complexity for lattices, a trellis is called minimal if it minimizes N. It is proved that the previously discovered trellis diagrams of some of the above lattices (Dn, n odd, An, 4 < n < 9, A, A£, Ag, Ag, E6, E£, and E-) are minimal. We also obtain minimal trellises for AC and Ag. It is known that the complexity N of any trellis of an n-dimensional lattice with coding gain 7 satisfies N > 7/2. Here, this lower bound is improved for many of the root lattices and their duals. For An and A* lattices, we also propose simple constructions for low-complexity trellises in an arbitrary dimension n, and derive tight upper bounds on the complexity of the constructed trellises. In some dimensions, the constructed trellises are minimal, while for some other values of n they have lower complexity than previously known trellises.

Additional Metadata
Keywords Complexity bounds, Lattices, Minimal trellises, Root lattices, Trellis complexity, Trellis construction
Persistent URL
Journal IEEE Transactions on Information Theory
Banihashemi, A. (1999). On the trellis complexity of root lattices and their duals. IEEE Transactions on Information Theory, 45(6), 2168–2172. doi:10.1109/18.782169