Talk abstract:

Codes and Systems on Graphs: Generalized State Realizations

G. David Forney, Jr.
Laboratory for Information and Decision Systems
Massachusetts Institute of Technology
forney@lids.mit.edu
Dave_Forney-LUSE27@email.mot.com

In coding theory or behavioral system theory, a code or system is simply a set of possible output sequences. In a state realization of a code/system (e.g., a trellis), a set of state variables is defined as well. Conventionally, state variables are defined on a sequential time axis corresponding to a subset of the integers.

In a generalized state realization of a code/system, state variables may be connected according to an arbitrary graph topology; i.e., the time axis is represented by a general graph. If the graph has cycles, then a substantial reduction in state complexity may be obtained. For example, the state complexity of a single-cycle graph realization (tail-biting trellis) can be as little as the square root of the state complexity of a conventional state realization (trellis). For another example, Reed-Muller codes have very simple generalized state realizations, in general with cycles. In general, the question of minimal generalized state realizations is wide open.

The sum-product algorithm may be applied to decode any generalized state realization. If the associated graph is finite and cycle-free, then sum-product decoding completes in a finite time and is exact. If the graph has cycles, then sum-product decoding becomes an approximate iterative decoding algorithm.

A linear or group generalized state realization generates a linear or group code/system. The dual of such a realization, appropriately defined, generates the dual code/system. The dual realization has the same symbol and state variables in the same graph topology as the primal realization, but replaces primal local constraints by their duals. A group code may be decoded using the dual graph, with appropriate Fourier transforms of the inputs and outputs; this can simplify decoding of high-rate codes.

Material used during the talk

Back to Codes, Systems and Graphical Models

1998-1999 Mathematics in Biology