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 the code. 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.Automaton-like decoders for the repetition code on a 2D lattice, otherwise known as the classical 2D Ising model, were developed by Toom [1,2]. An automaton by Gacs [3,4] and Tsirelson [5] yield local decoders for a 1D lattice.
Fault Tolerance
Triple modular redundancy (TMR) error-correction protocol [6] for fault-tolerant memory operations and classical gate operations; see section 2.6 and 2.7 Ref. [7] 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. [7] for a pedagogical explanation.The first threshold theorem for classical circuits was proven by von Neumann [8], which spurred the study of noisy classical circuits [9–12].
Realizations
Repetition codes, in conjunction with other codes, were used in magnetic disks [13].Communication protocols such as FlexRay [14].'
Parents
- Cyclic linear binary code — The repetition code is cyclic with generator polynomial \(1+x+\cdots+x^{n-1}\).
- Nearly perfect code
- Reed-Muller (RM) code — RM\((0,m)\) are repetition codes.
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 four-bit repetition code yields the \(D_4\) hyper-diamond lattice code via Construction A.
- \(E_8\) Gosset lattice — The \([8,1,8]\) repetition code can be used to obtain the \(E_8\) Gosset lattice code [15; Exam. 10.7.1].
- Single parity-check (SPC) code — Binary SPCs and repetition codes are dual to each other.
- \(q\)-ary repetition code
- Self-correcting quantum code — The repetition code associated with the 2D classical Ising model is a self-correcting classical memory [16][17; 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 [18; Sec. III].
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]
- L. F. Gray, “Toom’s Stability Theorem in Continuous Time”, Perplexing Problems in Probability 331 (1999) DOI
- [3]
- P. Gács, Journal of Statistical Physics 103, 45 (2001) arXiv:math/0003117 DOI
- [4]
- P. Gács, Journal of Statistical Physics 103, 45 (2001) DOI
- [5]
- B. S. Cirel’son, “Reliable storage of information in a system of unreliable components with local interactions”, Lecture Notes in Mathematics 15 (1978) DOI
- [6]
- 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
- [7]
- S. M. Girvin, “Introduction to quantum error correction and fault tolerance”, SciPost Physics Lecture Notes (2023) arXiv:2111.08894 DOI
- [8]
- J. von Neumann, “Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components”, Automata Studies. (AM-34) 43 (1956) DOI
- [9]
- N. Pippenger, “On networks of noisy gates”, 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) (1985) DOI
- [10]
- N. Pippenger, “Reliable computation by formulas in the presence of noise”, IEEE Transactions on Information Theory 34, 194 (1988) DOI
- [11]
- I. Benjamini, R. Pemantle, and Y. Peres, “Unpredictable paths and percolation”, The Annals of Probability 26, (1998) DOI
- [12]
- H. Kesten and B. P. Stigum, “A Limit Theorem for Multidimensional Galton-Watson Processes”, The Annals of Mathematical Statistics 37, 1211 (1966) DOI
- [13]
- T. Klove and M. Miller, “The Detection of Errors After Error-Correction Decoding”, IEEE Transactions on Communications 32, 511 (1984) DOI
- [14]
- “High-Performance Embedded Computing”, (2014) DOI
- [15]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [16]
- 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
- [17]
- 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
- [18]
- 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) (2018) arXiv:1803.06987 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