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

dimacs-www@dimacs.rutgers.edu
Document last modified on November 22, 1996