Complexity of Constructing Codes with Specified Correction Properties

The article investigates the complexity with which it is possible to construct codes that satisfy familiar asymptotic bounds for the error probability. Procedures for nonrandom choice of a binary linear code lying on the Gallager bound and for construction of a cascade code lying on the Forney bound are examined. It is shown that, for any code length $n$, the complexity of constructing a linear code is bounded from above by an exponent, while that for a cascade code is similarly bound by a power-law function of $n$.