[Jump to code hierarchy]

Cycle code [1–7]

Alternative Names: Graph theoretic code, Graph homology code, Graph code.

Description

A code whose parity-check matrix is obtained from the incidence matrix of a graph over \(\mathbb{F}_2\). This code’s properties are derived from the size two chain complex associated with the graph. Not every binary linear code is homological, but there exist homological families that asymptotically saturate the Hamming bound [6].

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 incidence matrix is a \(|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. Over \(\mathbb{F}_2\), one row is redundant for a connected graph, so a parity-check matrix of the cycle code can be taken to be any full-rank set of \(|V|-1\) rows.

Protection

More generally, an \([n,k,d]\) cycle code constructed out of a connected graph has \(n = |E|\) and \(k = 1 - \chi(G) = 1-|V|+|E|\), where \(\chi(G)\) is the Euler characteristic of the graph [8]. The code distance is equal to the shortest size of a cycle, guaranteed to exist since \(G\) is not a tree.

Cousins

  • Graph-adjacency code— Graph-adjacency (cycle) codes’ generator (parity-check) matrices are defined using adjacency (incidence) matrices of graphs.
  • Quantum-inspired classical block code— Cycle codes have been known in classical coding theory, and have been rediscovered in the quantum context; see Ref. [8] for a brief exposition.
  • Generalized homological-product code— Cycle codes have been known in classical coding theory, and have been rediscovered in the quantum context; see Ref. [8] for a brief exposition.
  • Homological code— Cycle codes feature in generalizations of the surface code [8].
  • Perfect binary code— A family of cycle codes saturate the asymptotic Hamming bound [6].
  • Qubit CSS code— Cycle codes, including the Petersen cycle and Hoffman-Singleton cycle codes, feature in magic-state distillation protocols [9; Appx. A.2.1][10; Sec. VII.A].

Primary Hierarchy

Parents
Incidence matrices of graphs have no repeated columns since that would correspond to multi-edges. Therefore, cycle codes can be interpreted as projective codes.
Cycle code
Children

References

  1. [1]

    T. Kasami, “A topological approach to construction of group codes”, Journal of the Institute of Electrical Communication Engineers of Japan 44, 1316-1321 (1961)

  2. [2]

    D. A. Huffman, “A graph-theoretic formulation of binary group codes”, Summaries of papers presented at ICMCI, part 3, 29-30 (1964)

  3. [3]

    W. D. Frazer, “A graph theoretic approach to linear codes”, Proc. Second Annual Allerton Conf. On Circuit & System Theory. 1964

  4. [4]

    S. Hakimi and H. Frank, “Cut-set matrices and linear codes (Corresp.)”, IEEE Transactions on Information Theory 11, 457 (1965) DOI

  5. [5]

    S. Hakimi and J. Bredeson, “Graph theoretic error-correcting codes”, IEEE Transactions on Information Theory 14, 584 (1968) DOI

  6. [6]

    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

  7. [7]

    P. Dankelmann, J. D. Key, and B. G. Rodrigues, “Codes from incidence matrices of graphs”, Designs, Codes and Cryptography 68, 373 (2012) DOI

  8. [8]

    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

  9. [9]

    J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, “Magic state distillation with low space overhead and optimal asymptotic input count”, Quantum 1, 31 (2017) arXiv:1703.07847 DOI

  10. [10]

    Quantum Information and Computation 18, (2018) arXiv:1709.02789 DOI

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: homological_classical

Cite as:
“Cycle code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/homological_classical, arXiv:2606.11484
BibTeX:
@incollection{eczoo_homological_classical,
title={Cycle code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/homological_classical}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/homological_classical

Cite as:

“Cycle code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/homological_classical, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/graph/incidence/homological_classical.yml.