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