No label defined (Q4242014)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1284420
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1284420

      Statements

      0 references
      1 February 2000
      0 references
      coding theory
      0 references
      split syndrom decoding
      0 references
      gradient-like decoding
      0 references
      information set decoding
      0 references
      covering set decoding
      0 references
      punctured split syndrom decoding
      0 references
      list cascade decoding
      0 references
      syndrom trellis decoding
      0 references
      weighted partitions decoding
      0 references
      minimal vectors ML decoding
      0 references
      complexity of algorithms
      0 references
      asymptotic behaviour of algorithms
      0 references
      construction of block codes
      0 references
      decoding
      0 references
      computation of important numerical parameters
      0 references
      minimum distance
      0 references
      weight spectrum
      0 references
      linear codes
      0 references
      asymptotically good codes
      0 references
      Gilbert-Varshamov bound
      0 references
      hard decision decoding
      0 references
      soft decision decoding
      0 references
      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].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references