Centered codes.

*(English. Russian original)*Zbl 0555.94014
Probl. Inf. Transm. 20, 81-91 (1984); translation from Probl. Peredachi Inf. 20, No. 2, 3-17 (1984).

The authors propose a method of constructing and decoding block codes that makes it possible to reduce the complexity of decoding without significantly increasing the error probability. It is shown that in the case of a BSC with strong noise, at transmission rates close to the channel capacity, there exist centered codes for which the exponent of the error probability is equal to the exponent of random coding, while the number of computational operations involved in decoding is proportional to mn exp\({}_ 2(nR/m)\), where n and R are the code length and rate, respectively; m is an arbitrary integer that is bounded from above by a quantity that depends on the difference C-R (C is the channel capacity), that increases as this difference decreases.