Ordered binary decision diagrams (OBDDs) are graph-based data structures fo
r representing Boolean functions. They have found widespread use in compute
r-aided design and in formal verification of digital circuits. Minimal trel
lises are graphical representations of error-correcting codes that play a p
rominent role in coding theory. This paper establishes a close connection b
etween these two graphical models, as follows. Let C be a binary code of le
ngth n, and let f(c)(x(1),...,x(n)) be the Boolean function that takes the
value 0 at x(1),...,x(n) if and only if (x(1),...,x(n)) is an element of C.
Given this natural one-to-one correspondence between Boolean functions and
binary codes, we prove that the minimal proper trellis for a code C with m
inimum distance d > 1 is isomorphic to the single-terminal OBDD for its Boo
lean indicator function f(c)(x(1),...,x(n)). Prior to this result, the exte
nsive research during the past decade on binary decision diagrams-in comput
er engineering-and on minimal trellises-in coding theory-has been carried o
ut independently. As outlined in this work, the realization that binary dec
ision diagrams and minimal trellises are essentially the same data structur
e opens up a range of promising possibilities for transfer of ideas between
these disciplines.