On Codes of Bounded Trellis Complexity

In this paper, we initiate a structure theory of linear codes with bounded trellis complexity. The theory is based on the observation that the family of linear codes over F_q, some permutation of which has trellis state-complexity at most omega, is a minor-closed family. It then follows from a deep result of matroid theory that such codes are characterized by finitely many excluded minors. We provide the complete list of excluded minors for omega = 1, and give a partial list for omega = 2. We also give a polynomial-time algorithm for determining whether or nor a given code has a permutation with state-complexity at most 1.