We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L*, we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices, and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.

Additional Metadata
Keywords Dual code, Generalized Construction A, Group codes, Lattices, Tanner graph complexity, Tanner graph construction, Tanner graphs
Persistent URL dx.doi.org/10.1109/18.910592
Journal IEEE Transactions on Information Theory
Citation
Banihashemi, A, & Kschischang, F.R. (Frank R.). (2001). Tanner graphs for group block codes and lattices: Construction and complexity. IEEE Transactions on Information Theory, 47(2), 822–834. doi:10.1109/18.910592