Convolutional
Error-Correcting Codes
by
Heide Gluesing-Luerssen
University of Kentucky and
University of Groningen (The
Netherlands)
March
13-15, 2007: Morton 318
Tuesday and Wednesday talks
are 5:00-6:30
P.M.
Thursday Talk is 7:00-8:30 P.M.
Part 1:
Introduction to Convolutional Coding Theory
Algebraically, a convolutional code is a direct summand of the free
module ${\mathbb F}[z]^n$ of polynomial vectors over a finite field
${\mathbb F}$. We will discuss different representations of
convolutional codes along with their relevant parameters. It will
be
shown how the process of encoding messages into code words can be
realized by linear shift registers which then will bring us to
minimal
encoders as well as to the representation of convolutional codes as
linear discrete-time dynamical systems. After the algebraic
considerations the error-correcting properties will be discussed,
and a
brief account of the most important decoding algorithm, the Viterbi
algorithm, will be given.
Part 2: Weight
Enumerators and a MacWilliams Duality Theorem
One of the most fundamental results of block coding theory is
MacWilliams' Duality Theorem. It states that the weight enumerator
of a
code is fully determined by the weight enumerator of the dual code
and
gives a concrete transformation formula. The weight enumerator of
a code
counts the various weights attained by the code words, and thus
contains
detailed information about the error-correcting quality of the
code. In
this talk we will present a generalization of MacWilliams' Duality
Theorem to convolutional codes. In order to do so one first needs a
meaningful and sufficiently detailed notion of weight enumerator
for
these codes. It turns out that for convolutional codes this is
achieved
by a weight adjacency matrix associated with the state transition
graph
of the chosen encoder.
Part 3: Isometry
for Convolutional Codes
MacWilliams' Equivalence Theorem tells us that two block codes are
isometric if and
only if they are monomially equivalent. In other words, codes that
are
related by a weight-preserving isomorphism differ only by a
permutation
and rescaling of the coordinates. It is of crucial importance that
the
weight-preserving mapping is linear and not just a bijection.
Indeed, it
is well known that block codes with the same weight enumerator
need not
be monomially equivalent. Hence, the weight enumerator does not
form a
complete invariant under
monomial equivalence. In this talk we
will show the somewhat surprising result that for a particular
class of
convolutional codes (not encompassing block codes) the weight
adjacency
matrix does form a complete invariant under monomial equivalence.
The
result can be regarded as a first step towards a meaningful notion
of
isometry for convolutional codes.