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.
