# Discrete Math/Theory of Computing Seminar

## Title:

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

## Speaker:

- Vijay V. Vazirani
- Georgia Institute of Technology

## Place:

- DIMACS, CoRE Building, room 431
- Rutgers University

## Time:

- 4:30 p.m.
- Tuesday, September 24, 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.)

Document last modified on November 22, 1996