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
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
0.8342400193214417
0 references
0.8284121155738831
0 references
0.8248661160469055
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