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 inve stigated. Using N, the number of distinct paths in a trellis, as the measur e of trellis complexity for Lattices, a trellis is called minimal if it min imizes N. It is proved that the previously discovered trellis diagrams of s ome of the above lattices (D-n, n odd, A(n), 4 less than or equal to n less than or equal to 9, A(4)*, A(5)*, A(6)*, A(9)* E-6, E-6*, and E-7*) are mi nimal. We also obtain minimal trellises fur A(7)* and A(8)*. It is known that the complexity N of any trellis of an n-dimensional lattic e with coding gain gamma satisfies N greater than or equal to gamma(n/2). s ere, this laser bound is improved for many of the root lattices and their d uals. For A(n) and A(n)(*) lattices, we also propose simple constructions f or low-complexity trellises in an arbitrary dimension ni and derive tight u pper bounds on the complexity of the constructed trellises. In some dimensi ons, the constructed trellises are minimal, while for some other values of n they have lower complexity than previously known trellises.