Expander code[1]
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
Rate
Encoding
Decoding
Fault Tolerance
Parent
- Regular LDPC code — Expander codes yield an explicit (i.e., non-random) asymptotically good LDPC code family.
Cousins
- 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 [8].
- 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 et al., “Randomness conductors and constant-degree lossless expanders”, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC ’02 (2002) DOI
- [6]
- H. L. J. A. K. Lal, “On Expanders Graphs: Parameters and Applications”, (2004) arXiv:cs/0406048
- [7]
- D. A. Spielman, “Linear-time encodable and decodable error-correcting codes”, IEEE Transactions on Information Theory 42, 1723 (1996) DOI
- [8]
- E. Ben-Sasson, P. Harsha, and S. Raskhodnikova, “Some 3CNF properties are hard to test”, Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC ’03 (2003) DOI
Page edit log
- Victor V. Albert (2022-07-12) — most recent
- Jon Nelson (2021-12-15)
Cite as:
“Expander code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/expander