Expander code[1]

Description

Expander codes are binary linear codes whose parity check matrices are derived from the adjacency matrix of bipartite expander graphs. In particular, the rows of the parity check matrix correspond to the right nodes of the bipartite graph and the columns correspond to the left nodes. The codespace is equivalent to all subsets of the left nodes in the graph that have an even number of edges going into every right node of the graph. Since the expander graph is only left regular, these codes do not qualify as LDPC codes.

Expander codes are important because they admit efficient encoding and decoding algorithms and are asymptotically good (i.e., their rate and normalized distance are constant). 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 with any ratio \(n/m\) are known where \(D = \text{polylog}(n/m)\), \(\gamma = \Omega(1/D)\) and arbitrary \(\epsilon\) [2].

Protection

Bit flip errors of weight at most \((d-1)/2\) where \(d\) is the distance of the code and is linear in \(n\), the number of physical bits.

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 algorithm. 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.

Parent

Cousin

Zoo code information

Internal code ID: expander

Your contribution is welcome!

on github.com (edit & pull request)

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} }
Permanent link:
https://errorcorrectionzoo.org/c/expander

References

[1]
M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996). DOI
[2]
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

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/tree/main/codes/classical/bits/expander.yml.