Improved Decoding of Expander Codes

Authors Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.43.pdf
  • Filesize: 484 kB
  • 3 pages

Document Identifiers

Author Details

Xue Chen
  • University of Science and Technology of China, Anhui, China
Kuan Cheng
  • Peking University, China
Xin Li
  • Johns Hopkins University, Baltimore, MD, USA
Minghui Ouyang
  • Peking University, China

Cite AsGet BibTex

Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. Improved Decoding of Expander Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.43

Abstract

We study the classical expander codes, introduced by Sipser and Spielman [M. Sipser and D. A. Spielman, 1996]. Given any constants 0 < α, ε < 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 α N has at least (1-ε)|S|D neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly {α N}/{2 ε}. This is strictly better than the best known previous result of 2(1-ε) α N [Madhu Sudan, 2000; Viderman, 2013] whenever ε < 1/2, and improves the previous result significantly when ε 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 ε < 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
Keywords
  • Expander Code
  • Decoding

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Sanjeev Arora, Constantinos Daskalakis, and David Steurer. Message-passing algorithms and improved LP decoding. IEEE Trans. Inf. Theory, 58(12):7260-7271, 2012. URL: https://doi.org/10.1109/TIT.2012.2208584.
  2. Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the 34th Annual ACM STOC, pages 659-668. ACM, 2002. Google Scholar
  3. A. G. Dimakis, R. Smarandache, and P. O. Vontobel. Ldpc codes for compressed sensing. IEEE Transactions on Information Theory, 58(5):3093-3114, 2012. Google Scholar
  4. J. Feldman, T. Malkin, R. A. Servedio, C. Stein, and M. J. Wainwright. Lp decoding corrects a constant fraction of errors. IEEE Transactions on Information Theory, 53(1):82-89, 2007. URL: https://doi.org/10.1109/TIT.2006.887523.
  5. Jon Feldman, Martin J. Wainwright, and David R. Karger. Using linear programming to decode binary linear codes. IEEE Trans. Inf. Theory, 51(3):954-972, 2005. URL: https://doi.org/10.1109/TIT.2004.842696.
  6. Robert G. Gallager. Low-Density Parity-Check Codes. The MIT Press, September 1963. URL: https://doi.org/10.7551/mitpress/4347.001.0001.
  7. M.G. Luby, M. Amin Shokrolloahi, M. Mizenmacher, and D.A. Spielman. Improved low-density parity-check codes using irregular graphs and belief propagation. In Proceedings. 1998 IEEE International Symposium on Information Theory (Cat. No.98CH36252), page 117, 1998. Google Scholar
  8. Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. Ldpc codes achieve list decoding capacity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 458-469, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00050.
  9. T.J. Richardson and R.L. Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2):599-618, 2001. Google Scholar
  10. M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996. URL: https://doi.org/10.1109/18.556667.
  11. Madhu Sudan. A crash course on coding theory. availabel at http://people.seas.harvard.edu/~madhusudan/MIT/coding/ibm/, 2000.
  12. Michael Viderman. Linear-time decoding of regular expander codes. ACM Trans. Comput. Theory, 5(3), August 2013. URL: https://doi.org/10.1145/2493252.2493255.
  13. Michael Viderman. Lp decoding of codes with expansion parameter above 2/3. Inf. Process. Lett., 113(7):225-228, April 2013. URL: https://doi.org/10.1016/j.ipl.2013.01.012.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail