Description
\([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code. Its automorphism group is \(S_n\).Protection
Detects errors on up to \(\frac{n-1}{2}\) coordinates, corrects erasure errors on up to \(\frac{n-1}{2}\) coordinates. The generator matrix is \(G=\left[\begin{smallmatrix}1 & 1&\cdots& 1 & 1 \end{smallmatrix}\right]\).Rate
Code rate is \(\frac{1}{n}\), code distance is \(n\).Decoding
Calculate the Hamming weight \(d_H\) of an error word. If \(d_H\leq \frac{n-1}{2}\), decode the code as 0. If \(d_H\geq \frac{n+1}{2}\), decode the code as 1.Local automaton decoder for the repetition code on a 2D lattice based on Toom's rule [1–4].Local automaton decoder for the repetition code on a 1D lattice by Gacs that is translation-invariant, that does not require synchronization of local clocks, and that has a constant encoding rate [5,6].Local automaton decoder for the repetition code on a 1D lattice by Tsirelson [7].Local automaton decoder obtained from reinforcement learning [8].Fault Tolerance
Triple modular redundancy (TMR) error-correction protocol [9] for fault-tolerant memory operations and classical gate operations; see section 2.6 and 2.7 Ref. [10] for a pedagogical explanation.Threshold
Suppose each bit has probability \(p\) of being received correctly, independent for each bit. The probability that a repetition code is received correctly is \(\sum_{k=0}^{(n-1)/2}\frac{n!}{k!(n-k)!}p^{n-k}(1-p)^{k}\). If \(\frac{1}{2}\leq p\), then one can always increase the probability of success by increasing the number of physical bits \(n\); see section 2.2.1 Ref. [10] for a pedagogical explanation.The first threshold theorem for classical circuits was proven by von Neumann [11] using cellular automata [12] and which spurred the study of noisy classical circuits [13–16].Realizations
Repetition codes, in conjunction with other codes, were used in magnetic disks [17].Communication protocols such as FlexRay [18].'Cousins
- \([2^m-1,m,2^{m-1}]\) simplex code— The simplex code for \(m=2\) reduces to a four-bit repetition code.
- Perfect binary code— Repetition codes are perfect for odd \(n\).
- Quantum repetition code— A quantum repetition code can be thought of as a classical \([n,1,d]\) repetition code with classical distance \(d=\left\lfloor (n-1)/2\right\rfloor\) embedded in a quantum system.
- \([2^r-1,2^r-r-1,3]\) Hamming code— The triple repetition code \([3,1,3]\) is the smallest Hamming code.
- \(D_4\) hyper-diamond lattice— The \(D_4\) lattice is constructed out of the \([4,1,4]\) repetition and \([4,3,2]\) SPC codes via Construction A.
- \(E_8\) Gosset lattice— The \([8,1,8]\) repetition code can be used to obtain the \(E_8\) Gosset lattice [19; Exam. 10.7.1].
- Single parity-check (SPC) code— Binary SPCs and repetition codes are dual to each other.
- \(q\)-ary repetition code
- Klemm code— The generator matrix of the Klemm code consists of a sum of the generator matrix of the repetition code and twice the generator matrix of the SPC code [20].
- Compactified \(\mathbb{R}\) gauge theory code— The compactified \(\mathbb{R}\) gauge theory code is constructed from a hypergraph product of two repetition codes over the integers.
- Tiger surface code— The tiger surface code is constructed from a hypergraph product of two repetition codes over the integers.
- Self-correcting quantum code— The repetition code associated with the 2D classical Ising model is a self-correcting classical memory [21][22; Sec. V.A].
- \([[2m,2m-2,2]]\) error-detecting code— The \([[2m,2m-2,2]]\) error-detecting code is constructed via the CSS construction from an SPC code and its dual repetition code [23; Sec. III].
- Chamon model code— The Chamon model code can be obtained from a hypergraph product of three repetition codes [24], but done in a different way than the 3D surface code; see [25; Sec. 3.4].
- Sierpinsky fractal spin-liquid (SFSL) code— The Sierpinsky fractal spin-liquid code is a hypergraph product of the repetition code and the Newman-Moore code [26,27].
- Two-foliated fracton code— The two-foliated fracton code is a hypergraph product of the repetition code and the plaquette Ising code on a square lattice with periodic boundary conditions [28].
- Long-range enhanced surface code (LRESC)— LRESCs are constructed constructed using a hypergraph product of two copies of a concatenated LDPC-repetition seed code.
- Toric code— The toric code can be obtained from a hypergraph product of two repetition codes [29; Exam. 6].
- 3D surface code— The 3D planar (3D toric) code can be obtained from a hypergraph product of three repetition (cyclic) codes [30; Exam. A.1], but done in a different way than the Chamon code; see [25; Sec. 3.4].
- XZZX surface code— The Chamon model code can be obtained from a particular hypergraph product of three repetition codes [24]; see [25; Sec. 3.4]. Using only two repetition codes yields the XZZX code, making that code a 2D analogue of the Chamon code [25; Sec. 2].
Member of code lists
- \(q\)-ary linear codes
- Binary linear codes
- Classical codes
- Classical codes with a rate
- Classical codes with notable decoders
- Cyclic codes
- Evaluation codes
- Locally correctable codes
- Locally decodable codes
- Locally recoverable codes
- MDS codes
- Orthogonal arrays and friends
- Realized classical codes
- Self-correcting quantum codes and friends
- Universally optimal codes
Primary Hierarchy
Parents
The repetition code is cyclic with generator polynomial \(1+x+\cdots+x^{n-1}\).
Reed-Muller (RM) codeGRM Evaluation Divisible Linear \(q\)-ary Linear code over \(\mathbb{Z}_q\) LCC LRC Distributed-storage LDC ECC
RM\((0,m)\) are repetition codes.
Maximum distance separable (MDS) codeLinear \(q\)-ary OA LRC Distributed-storage \(t\)-design Universally optimal ECC
Repetition code
References
- [1]
- A. L. Toom, “Nonergodic Multidimensional System of Automata”, Probl. Peredachi Inf., 10:3 (1974), 70–79; Problems Inform. Transmission, 10:3 (1974), 239–246
- [2]
- Toom, Andrei L. "Stable and attractive trajectories in multicomponent systems." Multicomponent random systems 6 (1980): 549-575.
- [3]
- L. F. Gray, “Toom’s Stability Theorem in Continuous Time”, Perplexing Problems in Probability 331 (1999) DOI
- [4]
- G. Grinstein, “Can complex structures be generically stable in a noisy world?”, IBM Journal of Research and Development 48, 5 (2004) DOI
- [5]
- P. Gács, “Reliable computation with cellular automata”, Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC ’83 32 (1983) DOI
- [6]
- P. Gács, Journal of Statistical Physics 103, 45 (2001) arXiv:math/0003117 DOI
- [7]
- B. S. Cirel’son, “Reliable storage of information in a system of unreliable components with local interactions”, Lecture Notes in Mathematics 15 (1978) DOI
- [8]
- M. Park, N. Maskara, M. Kalinowski, and M. D. Lukin, “Enhancing quantum memory lifetime with measurement-free local error correction and reinforcement learning”, Physical Review A 111, (2025) arXiv:2408.09524 DOI
- [9]
- R. E. Lyons and W. Vanderkulk, “The Use of Triple-Modular Redundancy to Improve Computer Reliability”, IBM Journal of Research and Development 6, 200 (1962) DOI
- [10]
- S. M. Girvin, “Introduction to quantum error correction and fault tolerance”, SciPost Physics Lecture Notes (2023) arXiv:2111.08894 DOI
- [11]
- J. von Neumann, “Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components”, Automata Studies. (AM-34) 43 (1956) DOI
- [12]
- Von Neumann, John, and Arthur Walter Burks. "Theory of self-reproducing automata." (1966).
- [13]
- N. Pippenger, “On networks of noisy gates”, 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) (1985) DOI
- [14]
- N. Pippenger, “Reliable computation by formulas in the presence of noise”, IEEE Transactions on Information Theory 34, 194 (1988) DOI
- [15]
- I. Benjamini, R. Pemantle, and Y. Peres, “Unpredictable paths and percolation”, The Annals of Probability 26, (1998) DOI
- [16]
- H. Kesten and B. P. Stigum, “A Limit Theorem for Multidimensional Galton-Watson Processes”, The Annals of Mathematical Statistics 37, 1211 (1966) DOI
- [17]
- T. Klove and M. Miller, “The Detection of Errors After Error-Correction Decoding”, IEEE Transactions on Communications 32, 511 (1984) DOI
- [18]
- “High-Performance Embedded Computing”, (2014) DOI
- [19]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [20]
- S. T. Dougherty, P. Gaborit, M. Harada, A. Munemasa, and P. Sole, “Type IV self-dual codes over rings”, IEEE Transactions on Information Theory 45, 2345 (1999) DOI
- [21]
- L. E. Thomas, “Bound on the mass gap for finite volume stochastic ising models at low temperature”, Communications in Mathematical Physics 126, 1 (1989) DOI
- [22]
- B. J. Brown, D. Loss, J. K. Pachos, C. N. Self, and J. R. Wootton, “Quantum memories at finite temperature”, Reviews of Modern Physics 88, (2016) arXiv:1411.6643 DOI
- [23]
- N. Rengaswamy, R. Calderbank, H. D. Pfister, and S. Kadhe, “Synthesis of Logical Clifford Operators via Symplectic Geometry”, 2018 IEEE International Symposium on Information Theory (ISIT) 791 (2018) arXiv:1803.06987 DOI
- [24]
- Maurice, Denise. Codes correcteurs quantiques pouvant se décoder itérativement. Diss. Université Pierre et Marie Curie-Paris VI, 2014.
- [25]
- A. Leverrier, S. Apers, and C. Vuillot, “Quantum XYZ Product Codes”, Quantum 6, 766 (2022) arXiv:2011.09746 DOI
- [26]
- Y. Tan, B. Roberts, N. Tantivasadakarn, B. Yoshida, and N. Y. Yao, “Fracton models from product codes”, (2024) arXiv:2312.08462
- [27]
- T. Rakovszky and V. Khemani, “The Physics of (good) LDPC Codes II. Product constructions”, (2024) arXiv:2402.16831
- [28]
- N. P. Breuckmann, M. Davydova, J. N. Eberhardt, and N. Tantivasadakarn, “Cups and Gates I: Cohomology invariants and logical quantum operations”, (2024) arXiv:2410.16250
- [29]
- A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product LDPC codes”, 2012 IEEE International Symposium on Information Theory Proceedings 348 (2012) arXiv:1202.0928 DOI
- [30]
- L. Berent, T. Hillmann, J. Eisert, R. Wille, and J. Roffe, “Analog Information Decoding of Bosonic Quantum Low-Density Parity-Check Codes”, PRX Quantum 5, (2024) arXiv:2311.01328 DOI
Page edit log
- Bao Bach (2023-02-22) — most recent
- Victor V. Albert (2022-09-28)
- Victor V. Albert (2022-05-27)
- Victor V. Albert (2021-12-15)
- Yijia Xu (2021-12-14)
Cite as:
“Repetition code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/repetition