Description
Nearly optimal binary deletion-correcting code. Given integers \(n\geq 1\) and \(a\in\{0,1,\dots,n\}\), the associated binary Varshamov-Tenengolts code \(C_{n,a}\) corresponds to the set
\begin{align} C_{n,a}=\left\{x\in\{0,1\}^n: \sum_{i=1}^n i~x_i = a\mod (n+1) \right\}. \tag*{(1)}\end{align}
Protection
Corrects a single asymmetric error (a \(0\) mapped to a \(1\)), a single deletion, or a single insertion of an arbitrary bit in an arbitrary position for any choice of \(a\).
Rate
Rate-\(1\) code, with \(\log n+1\) bits of redundancy when \(a=0\). Nearly optimal.
Decoding
Decoder based on checksums \(\sum_{i=1}^n i~x_i^{\prime}\) of corrupted codewords \(x_i^{\prime}\) [2][3].
Parent
Cousin
- Linear binary code — By adapting a construction of Tenengolts [4], binary VT codes can be modified to yield slightly longer linear codes [5].
References
- [1]
- R. R. Varshamov and G. M. Tenengolts, Codes which correct single asymmetric errors (translated to English), Autom. Remote Control, 26(2), 286-290 (1965)
- [2]
- V. I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals (translated to English), Soviet Physics Dokl., 10(8), 707-710 (1966).
- [3]
- V. I. Levenshtein, Binary codes capable of correcting spurious insertions and deletions of one (translated to English), Prob. Inf. Transmission, 1(1), 8-17 (1965).
- [4]
- G. M. Tenengolts, Class of codes correcting bit loss and errors in the preceding bit (translated to English), Automation and Remote Control, 37(5), 797–802 (1976).
- [5]
- N. J. A. Sloane, “On Single-Deletion-Correcting Codes”, (2002) arXiv:math/0207197
Page edit log
- Victor V. Albert (2022-07-06) — most recent
- João Ribeiro (2022-07-06)
Cite as:
“Binary Varshamov-Tenengolts (VT) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/vt_single_deletion