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.

, , , , , ,
IEEE Transactions on Information Theory
Department of Systems and Computer Engineering

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