# zbMATH — the first resource for mathematics

Complexity bounds of error correction for low-density Gallager codes. (Russian) Zbl 0358.94017
Summary: It is shown that among the Gallager low-density binary codes there are codes with decoding for the correction of all errors up to multiplicity $$\alpha n$$ and with decoding complexity of order $$n\log n$$, where $$n$$ is the code length and $$\alpha$$ is a positive number.

##### MSC:
 94B60 Other types of codes 94B65 Bounds on codes
Full Text: