Dipl.-Inf. René van Bervern (TU Berlin)

A trellis is a graph associated with a linear code that is used for maximum-likelihood decoding. The decoding complexity of a linear code is strongly influenced by the state complexity of the trellis, which highly depends on the coordinate permutation of the linear code. The problem of finding the coordinate permutation of a linear code such that the state-complexity of the associated trellis is at most k has been referred to as the Art of Trellis Decoding and is NP-hard. We how that it is linear-time solvable if k is constant. To this end, we reduce the problem to Hypergraph Cutwidth, which we show to be fixed-parameter linear by, for the first time, applying an analog of the Myhill-Nerode theorem from formal language theory to a hypergraph problem.

Back to the research colloquium site.