LP decoding of expander codes: a simpler proof

Abstract

A code $C \subseteq \F_2^n$ is a $(c,\epsilon ,\delta )$-expander code if it has a Tanner graph, where every variable node has degree $c$, and every subset of variable nodes $L_0$ such that $|L_0|\le \delta n$ has at least $\epsilon c|L_0|$ neighbors. Feldman et al. (IEEE IT, 2007) proved that LP decoding corrects $\frac{3\epsilon -2}{2\epsilon -1}\cdot (\delta n-1)$ errors of $(c,\epsilon ,\delta )$-expander code, where $\epsilon >2/3+\frac{1}{3c}$. In this paper, we provide a simpler proof of their result and show that this result holds for every expansion parameter $\epsilon >2/3$.

References in corpus (2)

• Towards Low-Complexity Linear-Programming Decoding
• On the Block Error Probability of LP Decoding of LDPC Codes