scientific article; zbMATH DE number 1284420

From MaRDI portal
Publication:4242014





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].




Cited in
(47)








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)