Description
Nearly optimal binary deletion-correcting code and code for the asymmetric channel.
Given integers \(n\geq 1\) and \(a\in\{0,1,\dots,n\}\), the associated 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}
By adapting a construction of Tenengolts [3], VT codes can be modified to yield slightly longer linear codes [4]. VT codes can be generalized to the \(q\)-ary case [5–7].
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,8].
Parents
- Constantin-Rao (CR) code — CR codes for \(G=\mathbb{Z}_{n+1}\) reduce to VT codes.
- Editing code
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]
- 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).
- [4]
- N. J. A. Sloane, “On Single-Deletion-Correcting Codes”, (2002) arXiv:math/0207197
- [5]
- M. Abroshan, R. Venkataramanan, and A. G. i Fabregas, “Efficient Systematic Encoding of Non-binary VT Codes”, (2018) arXiv:1708.04071
- [6]
- G. Tenengolts, “Nonbinary codes, correcting single deletion or insertion (Corresp.)”, IEEE Transactions on Information Theory 30, 766 (1984) DOI
- [7]
- K. Tatwawadi and S. Chandak, “Tutorial on algebraic deletion correction codes”, (2019) arXiv:1906.07887
- [8]
- 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).
Page edit log
- Victor V. Albert (2022-07-06) — most recent
- João Ribeiro (2022-07-06)
Cite as:
“Varshamov-Tenengolts (VT) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/vt_single_deletion