Expander code[1] 

Also known as Sipser-Spielman code.

Description

LDPC code whose parity-check matrix is derived from the adjacency matrix of 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 defined as a \(D\)-left-regular graph with \(n\) left nodes, and \(m\) right nodes such that for any subset of left nodes \(S\) of size at most \(\gamma n\) the neighborhood \(N(S)\) is at least of size \(\alpha|S|\). Given a (\(n, m, D, \gamma, (1-\epsilon)D\)) expander graph, the corresponding expander code has rate of \(1 - m/n\) and a distance of at least \(2(1-\epsilon)\gamma n\) for any \(\epsilon < 1/2\). Explicit constructions for expander graphs [2] with any ratio \(n/m\) are known where \(D = \text{polylog}(n/m)\), \(\gamma = \Omega(1/D)\) and arbitrary \(\epsilon\) [5].

Protection

There exist minimum distance bounds [1,6] as well as bounds on decoding performance [7–9] in terms of features of the expander graph.

Rate

The rate is \(1 - m/n\) where \(n\) is the number of left nodes and \(m\) is the number of right nodes in the bipartite expander graph.

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 [10]). 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.'Find erasures and Decode' a.k.a. Viderman's algorithm correcting order \(\Omega(n)\) errors in order \(O(n)\) time [11].

Fault Tolerance

The flip decoding algorithm is fault tolerant against parity check errors [12]; see also course notes by M. Sudan.

Parent

  • Regular LDPC code — Expander codes yield an explicit (i.e., non-random) asymptotically good LDPC code family.

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 [13].
  • 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 [14].
  • Self-correcting quantum code — Constant-rate random (quantum) expander codes are self-correcting (quantum) memories, but have no thermodynamic phase transitions [15].
  • Quantum expander code

References

[1]
M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996) DOI
[2]
S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
[3]
A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
[4]
G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
[5]
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
[6]
H. L. J. A. K. Lal, “On Expanders Graphs: Parameters and Applications”, (2004) arXiv:cs/0406048
[7]
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
[8]
M. Dowling and S. Gao, “Fast Decoding of Expander Codes”, IEEE Transactions on Information Theory 64, 972 (2018) DOI
[9]
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
[10]
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
[11]
M. Viderman, “Linear-time decoding of regular expander codes”, ACM Transactions on Computation Theory 5, 1 (2013) DOI
[12]
D. A. Spielman, “Linear-time encodable and decodable error-correcting codes”, IEEE Transactions on Information Theory 42, 1723 (1996) DOI
[13]
B. Hemenway, R. Ostrovsky, and M. Wootters, “Local Correctability of Expander Codes”, (2015) arXiv:1304.8129
[14]
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
[15]
Y. Hong, J. Guo, and A. Lucas, “Quantum memory at nonzero temperature in a thermodynamically trivial system”, (2024) arXiv:2403.10599
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: expander

Cite as:
“Expander code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/expander
BibTeX:
@incollection{eczoo_expander, title={Expander code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, 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.), 2022. https://errorcorrectionzoo.org/c/expander

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