[Jump to code hierarchy]

Expander code [1]

Alternative Names: Sipser-Spielman code.

Description

LDPC code whose parity-check matrix is derived from the adjacency matrix of a bipartite expander graph [2] such as a Ramanujan graph or a Cayley graph of a projective special linear group over a finite field [3,4]. Expander codes admit efficient encoding and decoding algorithms and yield an explicit (i.e., non-random) asymptotically good LDPC code family.

The rate and distance of the expander code depend on specific parameters of the corresponding graph. A (\(n, m, D, \gamma, \alpha\)) bipartite expander graph is a \(D\)-left-regular graph with \(n\) left nodes and \(m\) right nodes. Every set \(S\) of at most \(\gamma n\) left nodes in such a graph has at least \(\alpha|S|\) neighbors. Given a (\(n, m, D, \gamma, (1-\epsilon)D\)) expander graph with \(\epsilon < 1/2\), the expander code has distance at least \(\gamma n/(2\epsilon) - O(1/\epsilon)\) (using asymptotic notation) [5; Thm. 3.1]. The bound is tight up to an arbitrarily small loss in expansion for left-regular graphs whose maximum right degree is at most \(1.1\) times the average [5; Thm. 3.2]. Explicit constructions for expander graphs [2] with any ratio \(n/m\) are known where \(D = polylog(n/m)\), \(\gamma = \Omega(1/D)\) and arbitrary \(\epsilon\) [6].

Protection

There exist minimum distance bounds [1,7] as well as bounds on decoding performance [8–10] in terms of features of the expander graph. For a (\(n, m, D, \gamma, (1-\epsilon)D\)) expander graph with \(\epsilon<1/2\), every nonzero error on a set \(S\) of fewer than \(\gamma n\) bits violates at least \((1-3\epsilon)D|S|\) parity checks [11; Claim 1]. The list-decoding radius is at least \((1/2+\Omega(1/D_{\max}))\gamma n/(2\epsilon)\) with list size polynomial in \(n\), where \(D_{\max}\) is the maximum right degree (using asymptotic notation) [5; Thm. 7.1]. This radius exceeds the Johnson bound for binary codes of distance \(\gamma n/(2\epsilon)\) when \(\epsilon \leq 1/4\), \(\gamma/\epsilon \leq 0.1\), and \(D_{\max}\) is at most \(1.1\) times the average right degree [5; Thm. 7.1].

Rate

The rate is at least \(1 - m/n\), where \(n\) is the number of left nodes and \(m\) is the number of right nodes in the bipartite expander graph. Expander codes yield an explicit (i.e., non-random) asymptotically good LDPC code family [1].

Encoding

Multiplication by generator matrix with runtime \(O(n^2)\)

Decoding

Decoding can be done in \(O(n)\) runtime using a greedy flip decoder [1] (see also [12]). The algorithm consists of flipping a bit of the received word if it will result in a greater number of satisfied parity checks. This is repeated until a codeword is reached. It corrects \((1-2\epsilon)\gamma n\) errors for \(\epsilon < 1/4\) [1].‘Find erasures and Decode’ a.k.a. Viderman’s algorithm correcting \((1-3\epsilon)\gamma n/(1-2\epsilon)\) errors for \(\epsilon < 1/3\) in order \(O(n)\) time [13]. Its erasure-decoding subroutine corrects up to \((1-\xi)\gamma n/(2\epsilon)\) erasures in linear time for any \(\xi > 0\) [5; Thm. 4.1].Linear-time decoder that guesses the expansion of the corrupted set and either runs Viderman’s find-erasures step or flips all bits with many unsatisfied parity checks [5; Thm. 5.4]. It corrects up to \((3\gamma/(16\epsilon)-\eta)n\) errors for any \(\eta > 0\) and \(\epsilon < 1/4\).Linear-time decoder for \(\epsilon \leq 1/8\) that guesses the size and expansion of the corrupted set and uses them to set the threshold of Viderman’s find-erasures step [5; Thm. 6.6]. It corrects up to \(((\sqrt{2}-1)\gamma/(2\epsilon)-\eta)n\) errors for \(\epsilon < (3-2\sqrt{2})/2\) and up to \(((1-2\epsilon)\gamma/(4\epsilon)-\eta)n\) errors otherwise, for any \(\eta > 0\).

Fault Tolerance

The flip decoding algorithm is fault tolerant against parity-check errors [14]; see also [15].

Cousins

  • Locally decodable code (LDC)— Expander codes are locally decodable provided that the inner code satisfies certain properties; there exist code families with rate approaching one [16].
  • Left-right Cayley complex code— Left-right Cayley complex codes can be viewed as Tanner-like codes on expander graphs [2], but with bits defined on squares and constraints on edges (as opposed to edges and vertices, respectively, for expander codes). Expander codes are also typically not locally testable [17].
  • \(q\)-ary LDPC code— Asymptotically good non-binary expander codes can be constructed [19][18; Thm. 7.16] by generalizing the originally binary expander constructions [1,20].
  • Self-correcting quantum code— Constant-rate random (quantum) expander codes are self-correcting (quantum) memories, but have no thermodynamic phase transitions [21].
  • Quantum expander code— Quantum expander codes are quantum analogues of expander codes.
  • Galois-qudit expander code— The explicit expander-code construction of [22] yields \([[N,K\geq N^{1-\epsilon},D\geq N^{1/r}/\operatorname{poly}(\log N)]]_q\) QLDPC Galois-qudit quantum expander codes with transversal \(C^{r-1} Z\) gates. Balanced products of the same expander-code complexes also yield \([n,k\geq n^{1-\epsilon},d\geq n/\operatorname{poly}(\log n)]_q\) LTCs exhibiting the multiplication property.
  • Expander LP code— Expander LP codes are lifted products of expander codes with different local codes [23].

References

  1. [1]

    M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996) DOI

  2. [2]

    S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI

  3. [3]

    A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI

  4. [4]

    G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI

  5. [5]

    X. Chen, K. Cheng, X. Li, and M. Ouyang, “Improved Decoding of Expander Codes”, (2022) arXiv:2111.07629

  6. [6]

    M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson, “Randomness conductors and constant-degree lossless expanders”, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing 659 (2002) DOI

  7. [7]

    H. L. J. A. K. Lal, “On Expanders Graphs: Parameters and Applications”, (2004) arXiv:cs/0406048

  8. [8]

    S. K. Chilappagari, Dung Viet Nguyen, B. Vasic, and M. W. Marcellin, “On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes”, IEEE Transactions on Information Theory 56, 1600 (2010) arXiv:0805.2427 DOI

  9. [9]

    M. Dowling and S. Gao, “Fast Decoding of Expander Codes”, IEEE Transactions on Information Theory 64, 972 (2018) DOI

  10. [10]

    K. Cheng, M. Ouyang, C. Shangguan, and Y. Shen, “When can an expander code correct \(Ω(n)\) errors in \(O(n)\) time?”, (2024) arXiv:2312.16087

  11. [11]

    D. Aharonov and L. Eldar, “Commuting Local Hamiltonians on Expanders, Locally Testable Quantum codes, and the qPCP conjecture”, (2013) arXiv:1301.3407

  12. [12]

    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, 82 (2007) DOI

  13. [13]

    M. Viderman, “Linear-time decoding of regular expander codes”, ACM Transactions on Computation Theory 5, 1 (2013) DOI

  14. [14]

    D. A. Spielman, “Linear-time encodable and decodable error-correcting codes”, IEEE Transactions on Information Theory 42, 1723 (1996) DOI

  15. [15]

    M. Sudan, Essential Coding Theory (2008) URL

  16. [16]

    B. Hemenway, R. Ostrovsky, and M. Wootters, “Local Correctability of Expander Codes”, (2015) arXiv:1304.8129

  17. [17]

    E. Ben-Sasson, P. Harsha, and S. Raskhodnikova, “Some 3CNF properties are hard to test”, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing 345 (2003) DOI

  18. [18]

    F. G. Jeronimo, “Fast decoding of explicit almost optimal ε-balanced q-ary codes and fast approximation of expanding k-CSPs”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

  19. [19]

    A. Rao, “Lecture 6: Expander Codes: Tanner Codes”, Coding Theory lecture notes, 14 Oct. 2019, University of Washington

  20. [20]

    G. Zemor, “On expander codes”, IEEE Transactions on Information Theory 47, 835 (2001) DOI

  21. [21]

    Y. Hong, J. Guo, and A. Lucas, “Quantum memory at nonzero temperature in a thermodynamically trivial system”, Nature Communications 16, (2025) arXiv:2403.10599 DOI

  22. [22]

    L. Golowich and T.-C. Lin, “Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes”, (2024) arXiv:2410.14662

  23. [23]

    P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, (2022) arXiv:2111.03654

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: expander

Cite as:
“Expander code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/expander, arXiv:2606.11484
BibTeX:
@incollection{eczoo_expander,
title={Expander code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/expander}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/expander

Cite as:

“Expander code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/expander, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/tanner/regular_tanner/regular_ldpc/expander.yml.