Decoding of Expander Codes at Rates Close to Capacity

The concatenation of nearly-MDS expander codes of Roth and Skachek, ``On Nearly-MDS Expander Codes,'' Proc. IEEE ISIT'04, with `typical' LDPC codes is investigated. It is shown that for the rates R=(1-e)C, where 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/e$, and the decoding error probability decays exponentially. These codes are compared to the recently presented codes of Barg and Zemor, ``Error Exponents of Expander Codes,'' IEEE Trans. Inform. Theory, 2002, and ``Concatenated Codes: Serial and Parallel,'' IEEE Trans. Inform. Theory, 2005. It is shown that the latter families can not be tuned to have all the aforementioned properties.