direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding

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.

Date
Speaker
Location
Language
22.11.2012 16:00
René van Bevern
TEL 512
english/german

Back to the research colloquium site.

Zusatzinformationen / Extras