Talk abstract:

Trellises, Decision Diagrams, and Factor Graphs

John Lafferty
School of Computer Science
Carnegie Mellon University
lafferty@cs.cmu.edu

Ordered binary decision diagrams are graph-based data structures for representing Boolean functions. They have found widespread use in computer-aided design and in formal verification of hardware and software systems. This talk will survey the striking connections between binary decision diagrams and code trellises, highlighting the difference in emphasis and the complementary methods that have been developed in the computer engineering and coding theory communities.

The techniques developed for coding and verification have been most successful for classes of Boolean functions that have special structure. To address the exponential blowup in the sizes of decision diagrams and trellises for general functions and codes, it will be necessary to explore new graphical representations and algorithms. We will conclude this talk by introducing some recent work on "projection decoding" that attempts to make a step in this direction, using randomized constructions of factor graphs to represent codes that may not have an explicit sparse representation.

[This talk is the result of joint work with Alexander Vardy and Dan Rockmore.]

Back to Codes, Systems and Graphical Models

1998-1999 Mathematics in Biology