Discrete Math/Theory of Computing Seminar


An Efficient Algorithm for Constructing Minimal Trellises for Codes over Finite Abelian Groups


Vijay V. Vazirani
Georgia Institute of Technology


DIMACS, CoRE Building, room 431
Rutgers University


4:30 p.m.
Tuesday, September 24, 1996

The success of trellis coded modulation (which revolutionized transmission rates of modems in bandwidth limited channels), has led researchers to study block coded modulation. In this context, we present an efficient algorithm for computing the minimal trellis for a group code over a finite Abelian group, given a generator matrix for the code. An important application of our algorithm is to the construction of minimal trellises for lattices.

In this self-contained talk, we will show why trellises are important for efficient decoding, and will present structural properties of minimal trellises for group codes, established by Forney and Trott. We will also present the work of Kschischang and Sorokine, who obtained an efficient algorithm for computing the minimal trellis for linear codes over fields, before turning to codes over finite Abelian groups. A key idea in our work is a definition of a generator matrix for modules over rings $Z_{p^\alpha}$, where $p$ is a prime, that enjoys properties similar to those of a generator matrix for a vector space.

(This is joint work with Huzur Saran and B. Sundar Rajan.)

Document last modified on November 22, 1996