Cycle code[16] 

Also known as Graph theoretic code, Graph homology code, Graph code.


A code whose parity-check matrix forms the incidence matrix of a graph. This code's properties are derived from the size two chain complex associated with the graph.

Let \(G\) be a finite, undirected, connected graph without loops and multiple edges. Let \(|V|\) be its number of vertices and \(|E|\) be its number of edges. Its parity check matrix \(H\) is an \(|V| \times |E|\) matrix whose rows are indexed by the vertices of \(G\), and whose columns are indexed by the edges of \(G\). The matrix element \(H_{ij}=1\) if vertex \(i\) belongs to the edge \(j\) and \(H_{ij}=0\) otherwise.


More generally, an \([n,k,d]\) cycle code constructed out of a graph with \(n = |E|\), \(k = 1 - \mathcal{X}(G) = 1-|V|+|E|\), where \( \mathcal{X}(G)\) is the euler characteristic of the graph [7]. The code distance is equal to the shortest size of a cycle, guaranteed to exist since \(G\) is not a tree.


  • Projective geometry code — Incidence matrices of graphs have no repeated columns since that would correspond to multi-edges.




Kasami, T. "A topological approach to construction of group codes." J. Inst. Elec. Commun. Engrs.(Japan) 44 (1961): 1316-1321.
Huffman, D. A. "A graph-theoretic formulation of binary group codes." Summaries of papers presented at ICMCI, part 3 (1964): 29-30.
Frazer, W. D. "A graph theoretic approach to linear codes." Proc. Second Annual Allerton Conf. On Circuit & System Theory. 1964.
S. Hakimi and H. Frank, “Cut-set matrices and linear codes (Corresp.)”, IEEE Transactions on Information Theory 11, 457 (1965) DOI
S. Hakimi and J. Bredeson, “Graph theoretic error-correcting codes”, IEEE Transactions on Information Theory 14, 584 (1968) DOI
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, (2007) arXiv:quant-ph/0605094 DOI
G. Zémor, “On Cayley Graphs, Surface Codes, and the Limits of Homological Coding for Quantum Error Correction”, Lecture Notes in Computer Science 259 (2009) DOI
J. Haah et al., “Magic state distillation with low space overhead and optimal asymptotic input count”, Quantum 1, 31 (2017) arXiv:1703.07847 DOI
Quantum Information and Computation 18, (2018) arXiv:1709.02789 DOI
Page edit log

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: homological_classical

Cite as:
“Cycle code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024.
@incollection{eczoo_homological_classical, title={Cycle code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Cycle code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024.