scientific article; zbMATH DE number 1284420
asymptotic behaviour of algorithmsasymptotically good codescoding theorycomplexity of algorithmscomputation of important numerical parametersconstruction of block codescovering set decodingdecodingGilbert-Varshamov boundgradient-like decodinghard decision decodinginformation set decodinglinear codeslist cascade decodingminimal vectors ML decodingminimum distancepunctured split syndrom decodingsoft decision decodingsplit syndrom decodingsyndrom trellis decodingweight spectrumweighted partitions decoding
This paper is Chapter 7 in the Handbook of Coding Theory (see Zbl 0907.94001 for the entire collection). It gives an excellent overview on the complexity of algorithms that can be used in Coding Theory in order to solve well known problems. It focusses on the asymptotic behaviour of algorithms connected to the construction of block codes, the decoding of such codes and the computation of important numerical parameters (such as minimum distance, weight spectrum and the like). The chapter is mainly concerned with linear codes since for nonlinear codes the main input for the given problems would be the codewords itself, and most algorithms are polynomial in the number of codewords, so nonlinear codes are not that exciting. For linear codes, however, the problems can be divided into ``easy problems (i.e. the problems that allow for an algorithm having polynomial complexity in the length of the code), and ``difficult problems (i.e. problems where the only known algorithms are of (sub)exponential complexity in the length of the code. The chapter is divided into 4 sections. Every (sub)section ends with an extensive list of suggestions for further reading. The references are collected in a huge list at the end of the chapter. In Section 1 some basic notions and models of computation are introduced. The rest of the section is devoted to giving some general results for long linear codes. Section 2 deals with the easy problems. The main results contained in this section are concerned with the construction of asymptotically good codes allowing for a decoding algorithm being polynomial in the length of the code. Section 3 is on ``difficult problems. The first being the construction of codes meeting the Gilbert-Varshamov bound. The accent of this section is in the rump-sub-sections which deal with hard decision decoding and soft decision decoding. The last topic in this section is the computation of important parameters of codes. The algorithms considered for Hard Decision Decoding are: Split Syndrom Decoding, Gradient-like Decoding, Information Set Decoding, Covering Set Decoding, Punctured Split Syndrom Decoding and List Cascade Decoding. For soft decision decoding they are: Minimal Vectors ML Decoding, Syndrom Trellis Decoding and Weighted Partitions Decoding. The computation of numerical parameters of codes focusses on the minimum distance and the weight spectrum. It is pointed out that finding minimal weight codewords in a linear code is closely connected to the decoding problem. Section 4 is devoted to intractable problems. It gives a list of problems that are known to be NP-complete and it briefly discusses these problems. For the entire collection see [Zbl 0907.94001].
- A method for efficiently computing the number of codewords of fixed weights in linear codes
- A commutative algebra approach to linear codes
- LDPC codes from Singer cycles
- Some new NP-complete coding problems
- Complexity aspects of guessing prefix codes
- On the Gröbner bases of some symmetric systems and their application to coding theory.
- On the weak order ideal associated to linear codes
- DAGS: key encapsulation using dyadic GS codes
- Linear codes with complementary duals meet the Gilbert-Varshamov bound
- Comments on ``Integer SEC-DED codes for low power communications
- Decomposition of modular codes for computing test sets and Graver basis
- Hamming codes for wet paper steganography
- Asymptotic behaviour of codes in rank metric over finite fields
- Enumerating all solutions of a Boolean CSP by non-decreasing weight
- Decoding one out of many
- scientific article; zbMATH DE number 1004583 (Why is no real title available?)
- On the ideal associated to a linear code
- The hardness of decoding linear codes with preprocessing
- Separating Models of Learning with Faulty Teachers
- McEliece Cryptosystem Implementation: Theory and Practice
- Hard Problems of Algebraic Geometry Codes
- On a Gröbner bases structure associated to linear codes
- Sur la complexité d'un problème de codage
- scientific article; zbMATH DE number 4047170 (Why is no real title available?)
- scientific article; zbMATH DE number 1284433 (Why is no real title available?)
- scientific article; zbMATH DE number 1335886 (Why is no real title available?)
- Algorithmic issues in coding theory
- scientific article; zbMATH DE number 1559526 (Why is no real title available?)
- Links between complexity theory and constrained block coding
- Trial set and Gröbner bases for binary codes
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- Error-correction of linear codes via colon ideals
- The complexity of error-correcting codes
- Diagnosis of partially observed Petri net based on analytical redundancy relationships
- Some Applications of Coding Theory in Computational Complexity
- Some Problems in Organic Coding Theory
- On those Boolean functions that are coset leaders of first order Reed-Muller codes
- On Linear Complexity of Finite Sequences: Coding Theory and Applications to Cryptography
- \textsf{FuLeeca}: a Lee-based signature scheme
- Post-quantum secure fully-dynamic logarithmic-size deniable group signature in code-based setting
- Coset leaders of the first order Reed-Muller codes in the classes of Niho functions and threshold functions
- Higher-order root-finding algorithm and its applications
- Information set decoding for ring-linear codes
- Coset leaders of the first-order Reed-Muller codes in four new classes of Boolean functions
- On the decoding of binary cyclic codes with the Newton identities
- Bounded distance decoding of linear error-correcting codes with Gröbner bases
- Gröbner bases and combinatorics for binary codes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4242014)