DIMACS TR: 2005-32

Decoding of Expander Codes at Rates Close to Capacity



Authors: Alexei Ashikhmin and Vitaly Skachek

ABSTRACT

The concatenation of nearly-MDS expander codes of Roth and Skachek, ``On Nearly-MDS Expander Codes,'' \emph{Proc. IEEE ISIT'04,} with `typical' LDPC codes is investigated. It is shown that for the rates $R=(1-\varepsilon)C$ ($C$ is the capacity of the binary symmetric channel (BSC)), under certain condition on the parameters of LDPC codes, these concatenated codes have decoding time linear in their length and polynomial in $1/\varepsilon$, and the decoding error probability decays exponentially. These codes are compared to the recently presented codes of Barg and Z\'emor, ``Error Exponents of Expander Codes,'' \emph{IEEE Trans. Inform. Theory,} 2002, and ``Concatenated Codes: Serial and Parallel,'' \emph{IEEE Trans. Inform. Theory,} 2005. It is shown that the latter families can not be tuned to have all the aforementioned properties.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-32.ps.gz
DIMACS Home Page