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

Zoo code information

Internal code ID: homological_classical

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: homological_classical

Cite as:
“Graph homology code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/homological_classical
BibTeX:
@incollection{eczoo_homological_classical, title={Graph homology code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/homological_classical} }
Permanent link:
https://errorcorrectionzoo.org/c/homological_classical

References

[1]
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, 052105 (2007). DOI; quant-ph/0605094

Cite as:

“Graph homology code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/homological_classical

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/homological_classical.yml.