Repetition code
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.
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 yields a decoder for a 1D lattice [3].
Fault Tolerance
Triple modular redundancy (TMR) error-correction protocol [4] for fault-tolerant memory operations and classical gate operations; see section 2.6 and 2.7 Ref. [5] 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. [5] for a pedagogical explanation.
Realizations
Repetition codes, in conjunction with other codes, were used in magnetic disks [6].Communication protocol such as FlexRay [7] is using repetition code'
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
- Perfect binary code — Repetition codes are perfect for odd \(n\).
- Quantum repetition code
- Hamming code — The triple repetition code \([3,1,3]\) is the smallest Hamming code.
- \(D_4\) hyper-diamond lattice code — The four-bit repetition code yields the \(D_4\) hyper-diamond lattice code via the mod-two lattice construction.
- \(E_8\) Gosset lattice code — The \([8,1,8]\) repetition code can be used to obtain the \(E_8\) Gosset lattice code [8; Ex. 10.7.1].
- Single parity-check (SPC) code — Binary SPCs and repetition codes are dual to each other.
- \(q\)-ary repetition code
- Simplex code — \(S(2,1)\) reduces to the repetition code.
- Self-correcting quantum code — The repetition code associated with the 2D classical Ising model is a self-correcting classical memory [9; Sec. V.A].
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) DOI
- [4]
- 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
- [5]
- S. M. Girvin, “Introduction to Quantum Error Correction and Fault Tolerance”, (2023) arXiv:2111.08894
- [6]
- T. Klove and M. Miller, “The Detection of Errors After Error-Correction Decoding”, IEEE Transactions on Communications 32, 511 (1984) DOI
- [7]
- High-Performance Embedded Computing (Elsevier, 2014) DOI
- [8]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [9]
- B. J. Brown et al., “Quantum memories at finite temperature”, Reviews of Modern Physics 88, (2016) arXiv:1411.6643 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
Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/easy/repetition.yml.