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. 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 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 protocols such as FlexRay [7].'

Parents

Cousins

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”, SciPost Physics Lecture Notes (2023) arXiv:2111.08894 DOI
[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”, (2014) DOI
[8]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[9]
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
[10]
B. J. Brown et al., “Quantum memories at finite temperature”, Reviews of Modern Physics 88, (2016) arXiv:1411.6643 DOI
[11]
N. Rengaswamy et al., “Synthesis of Logical Clifford Operators via Symplectic Geometry”, 2018 IEEE International Symposium on Information Theory (ISIT) (2018) arXiv:1803.06987 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: repetition

Cite as:
“Repetition code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/repetition
BibTeX:
@incollection{eczoo_repetition, title={Repetition code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/repetition} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/repetition

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/edit/main/codes/classical/bits/easy/dual_hamming/repetition.yml.