Improved Decoding of Expander Codes
Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang · IEEE Transactions on Information Theory · 2023
We study the classical expander codes, introduced by Sipser and Spielman, (1996). Given any constants$0 < \alpha, \varepsilon < 1/2$, and an arbitrary bipartite graph with$N$vertices on the left,$M < N$vertices on the right, and left degree$D$such that any left subset$S$of size at most$\alpha N$has at least$(1- \varepsilon)|S|D$neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly$\frac {\alpha N}{2 \varepsilon }$. This is strictly better than the best known previous result of$2(1- \varepsilon) \alpha N$Sudan, (2000), Viderman, (2013) whenever$\varepsilon < 1/2$, and improves the previous result significantly when$\varepsilon $is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever$\varepsilon < \frac {1}{4}$. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.