A class of codes is said to reach capacity $\cC$ of the binary symmetric channel if for any rate $R<\cC$ and any $\varepsilon>0$ there is a sufficiently large $N$ such that codes of length $\ge N$ and rate $R$ from this class provide error probability of decoding at most $\varepsilon$, under some decoding algorithm.
The study of the error probability of expander codes was initiated
in Barg and Z{\'e}mor (2002), where it was shown that they attain capacity
of the binary symmetric channel under a linear-time iterative decoding
with error probability falling exponentially with code length $N$.
In this work we study variations on the expander code construction and
focus on the most important region of code rates,
close to the channel capacity. For this region we estimate the decrease
rate (the error exponent) of error probability
of decoding for randomized ensembles codes. The resulting estimate
gives a substantial improvement of previous results for expander
codes and some other explicit code families.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-32.ps.gz
DIMACS Home Page