Algorithmic issues in coding theory

DOI10.1007/BFB0058031MaRDI QIDQ4370031zbMATH OpenFDO

Authors Madhu Sudan

Publication date 1997

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0058031

zbMATH Keywords

decoding complexitylinear block codes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Decoding (94B35)

Review text

The paper introduces shortly basic definitions in the theory of error-correcting block codes and some of the most common construction of block codes. It is the aim of the author to proof the error-correcting properties of these codes in a simple manner such that a computer scientist with only a basic knowledge of algebra should be able to understand them. In the second half of the paper some algorithmic tasks in error-correction related to the computational complexity of the decoding process are described and several open problems in this area are presented. For the entire collection see [Zbl 0879.00061].

Recommendations

• scientific article; zbMATH DE number 1284420
• A new approach to error-correcting codes
• Some Applications of Coding Theory in Computational Complexity
• Algorithmic Results in List Decoding

Cited in

(9)

• Open problems in coding theory
• scientific article; zbMATH DE number 998059 (Why is no real title available?)
• Computing statistics for polynomial codes: an algorithm based on the Mann-Whitney U-test
• scientific article; zbMATH DE number 4047170 (Why is no real title available?)
• A new approach to error-correcting codes
• scientific article; zbMATH DE number 1335886 (Why is no real title available?)
• scientific article; zbMATH DE number 2011836 (Why is no real title available?)
• scientific article; zbMATH DE number 1751828 (Why is no real title available?)
• scientific article; zbMATH DE number 837790 (Why is no real title available?)

This page was built for publication: Algorithmic issues in coding theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4370031)