Improved Decoding of Expander Codes

DOI10.1109/TIT.2023.3239163arXiv2111.07629OpenAlexW4317794910MaRDI QIDQ6198924

Author name not available (Why is that?)

Publication date: 21 March 2024

Published in: (Search for Journal in Brave)

Abstract: We study the classical expander codes, introduced by Sipser and Spielman cite{SS96}. 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 $alphaN$ 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 $fracalphaN2varepsilon$. This is strictly better than the best known previous result of $2(1-varepsilon)alphaN$ cite{Sudan2000note, Viderman13b} 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<frac14$. 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.

Full work available at URL: https://arxiv.org/abs/2111.07629

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Improved Decoding of Expander Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198924)