Binary Varshamov-Tenengolts (VT) code[1][2]

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\}. \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”. math/0207197

Zoo code information

Internal code ID: vt_single_deletion

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: vt_single_deletion

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
BibTeX:
@incollection{eczoo_vt_single_deletion, title={Binary Varshamov-Tenengolts (VT) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/vt_single_deletion} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/vt_single_deletion

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/vt_single_deletion.yml.