Centered Codes

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 in 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.