Princeton Theory Lunch

Title:

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

Speaker:

Vijay V. Vazirani
Georgia Institute of Technology

Place:

Computer Science Building, Room 402
Princeton University

Time:

Lunch will be served at 11:45 a.m.
Talk will begin at 12:10
Tuesday, November 26, 1996
Abstract:

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.)