This is a research-expository paper. It deals with complexity issues in the theory of linear block codes. The main emphasis is on the theoretical performance limits of the best known codes. Therefore, the main subject of the paper are families of asymptotically good codes, i.e., codes whose rate and relative distance are nonvanishing fractions of the code length n. Directions of studying complexity were set in the 1977 paper by L.A. Bassalygo, V.V. Zyablov, and M.S. Pinsker, and this paper is, in a sense, an account of developments achieved along them in the later years. >From the coding-theoretic point of view, algorithmic problems that are studied in the paper are concerned with constructing good codes, encoding and decoding them, and computing important numerical parameters of the code. From the computation-theoretic point of view, algorithmic problems can be classified into easy, i.e., polynomial in the code length n, difficult (exponential), and intractable (for instance, NP-complete). Therefore, one has to study the best achievable performance of linear codes under various complexity restrictions. Accordingly, the paper consists of 3 main parts dealing with polynomial algorithms for decoding and construction of asymptotically good codes, exponential algorithms for maximum likelihood decoding and computing some parameters of codes, and NP-complete coding problems. The supporting material includes many general properties of linear codes. Many methods studied in the paper are illustrated by examples. Generally, the paper includes complete and self-contained proofs of the results. The coverage is extended from classical algorithms to very recent developments. We thoroughly study and compare different algorithms, especially those applicable to several seemingly non-related problems. This unified approach to algorithmic coding problems enables us to organize previously independent results in a self-contained part of coding theory. This paper will appear as a chapter in V. Pless, W. Cary Huffman, and R. Brualdi, Eds., Handbook of Coding Theory, Elsevier Science, to be published.
展开▼
