The “Art of Trellis Decoding” Is NP-Hard

DOI10.1007/978-3-540-77224-8_24zbMath1195.94092OpenAlexW1600624275MaRDI QIDQ5386095

N. Kashyap

Publication date: 17 April 2008

Published in: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77224-8_24

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• On the intractability of permuting a block code to minimize trellis complexity
• Codes on graphs: constraint complexity of cycle-free realizations of linear codes
• Matroid Pathwidth and Code Trellis Complexity
• Complexity of Finding Embeddings in a k-Tree
• Te "art of trellis decoding" is computationally hard-for large fields
• Dimension/length profiles and trellis complexity of linear block codes

This page was built for publication: The “Art of Trellis Decoding” Is NP-Hard