Tanner graphs for group block codes and lattices: Construction and complexity

We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important applicat ion of which is the representation of the label code of a lattice. The cons truction is based on the modular linear constraints imposed on the code sym bols 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 eff icient algorithm for finding a generating set for L*. In the process, we de velop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships a mong a group code, its GCA lattice, and their duals, We also study the problem of finding low-complexity TGs for Abelian group b lock codes and lattices, and derive tight lower bounds on the label-code co mplexity of lattices. It is shown that for many important lattices, the min imal label codes which achieve the lower bounds cannot be supported by cycl e-free Tanner graphs.