__
TR97-046 | 3rd October 1997 00:00
__

#### Complexity Issues in Coding Theory

**Abstract:**
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.