Graph homology code[1]
Description
This code's properties are derived from the size two chain complex associated with a particular graph. Given a connected simplicial (no self loops or muliedges) graph \(G = (V, E)\), which is not a tree, with incidence matrix \(\Gamma\) we can construct a code by choosing a parity check matrix which consists of all the linearly independent rows of \(\Gamma\). This is a \([n,k,d]\) code with \(n = |E|\), \(k = 1 - \mathcal{X}(G) = 1-|V|+|E|\), where \( \mathcal{X}(G)\) is the euler characteristic of the graph. The code distance is equal to the shortest size of a cycle, guaranteed to exist since \(G\) is not a tree.
Parent
Cousins
- Perfect binary code — A family of homology codes saturate the asymptotic Hamming bound [1].
- Calderbank-Shor-Steane (CSS) stabilizer code — CSS codes can also be constructed using homology techniques but for manifolds of dimension two or greater.
References
- [1]
- H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, 052105 (2007) arXiv:quant-ph/0605094 DOI
Page edit log
- Victor V. Albert (2021-12-16) — most recent
- Seyed Sajjad Nezhadi (2021-12-14)
Cite as:
“Graph homology code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2021. https://errorcorrectionzoo.org/c/homological_classical