On Minimal Tree Realizations of Linear Codes

A tree decomposition of the coordinates of a code is a mapping from the coordinate set to the set of vertices of a tree. A tree decomposition can be extended to a tree realization, i.e., a cycle-free realization of the code on the underlying tree, by specifying a state space at each edge of the tree, and a local constraint code at each vertex of the tree. The constraint complexity of a tree realization is the maximum dimension of any of its local constraint codes. A measure of the complexity of maximum-likelihood (ML) decoding for a code is its treewidth, which is the least constraint complexity of any of its tree realizations.It is known that among all tree realizations of a linear code that extends a given tree decomposition, there exists a unique minimal realization that minimizes the state-space dimension at each vertex of the underlying tree. In this paper, we give two new constructions of these minimal realizations. As a by-product of the first construction, a generalization of the state-merging procedure for trellis realizations, we obtain the fact that the minimal tree realization also minimizes the local constraint code dimension at each vertex of the underlying tree. The second construction relies on certain code decomposition techniques that we develop. We further observe that the treewidth of a code is related to a measure of graph complexity, also called treewidth. We exploit this connection to resolve a conjecture of Forney's regarding the gap between the minimum trellis constraint complexity and the treewidth of a code. We present a family of codes for which this gap can be arbitrarily large.

I. Introduction

Graphical models of codes and the decoding algorithms associated with them are now a major focus area of research in coding theory. Turbo codes, low-density parity-check (LDPC) codes, and expander codes are all examples of codes defined, in one way or another, on underlying graphs. A unified treatment of graphical models and the associated decoding algorithms began with the work of Wiberg, Loeliger, and Koetter [32], [33], and has since been abstracted and refined under the framework of the generalized distributive law [1], factor graphs [21], and normal realizations [7], [8]. The particular case of graphical models in which the underlying graphs are cycle-free has a long and rich history of its own, starting with the study of trellis representations of codes; see, e.g., [31] and the references therein.