  Two broad classes of graphical modeling problems for codes can be identified
in the literature: constructive and extractive problems. The former class of
problems concern the construction of a graphical model in order to define a new
code. The latter class of problems concern the extraction of a graphical model
for a (fixed) given code. The design of a new low-density parity-check code for
some given criteria (e.g. target block length and code rate) is an example of a
constructive problem. The determination of a graphical model for a classical
linear block code which implies a decoding algorithm with desired performance
and complexity characteristics is an example of an extractive problem. This
work focuses on extractive graphical model problems and aims to lay out some of
the foundations of the theory of such problems for linear codes.
  The primary focus of this work is a study of the space of all graphical
models for a (fixed) given code. The tradeoff between cyclic topology and
complexity in this space is characterized via the introduction of a new bound:
the tree-inducing cut-set bound. The proposed bound provides a more precise
characterization of this tradeoff than that which can be obtained using
existing tools (e.g. the Cut-Set Bound) and can be viewed as a generalization
of the square-root bound for tail-biting trellises to graphical models with
arbitrary cyclic topologies. Searching the space of graphical models for a
given code is then enabled by introducing a set of basic graphical model
transformation operations which are shown to span this space. Finally,
heuristics for extracting novel graphical models for linear block codes using
these transformations are investigated.
