On the trellis complexity of root lattices and their duals

Trellis complexity of root lattices A_n, D_n, E_n, 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 (D_n, n odd, A_n, 4⩽n⩽9, A₄ *, A₅*, A₆*, A₉*, E₆, E₆*, and E₇*) are minimal. We also obtain minimal trellises for A₇* and A₈*. It is known that the complexity N of any trellis of an n-dimensional lattice with coding gain γ satisfies N⩾γ^n/2. Here, this lower bound is improved for many of the root lattices and their duals. For A_n and A_n* 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