hesela.devVarshamov-Tenengolts code
A binary Varshamov-Tenengolts code groups fixed-length bit strings by a weighted-sum congruence to correct one deleted or inserted bit.
For n bits and a fixed residue a, VT_a(n) contains strings satisfying sum(i*x_i) = a modulo n+1, with positions i numbered from 1. The sum uses ordinary integers, not XOR. The decoder must know n and a. Sloane describes the construction and single-deletion decoder. [1]
A deletion shortens the observation without marking its missing coordinate. An erasure preserves a known coordinate. These are different decoder inputs. Recovering the original string need not identify which identical bit in a run disappeared; racetrack read models illustrate this distinction. [3]
The binary condition does not directly extend to nucleotide values 0,1,2,3. Nguyen et al. give 213 and 132: both weighted sums are 13, yet either can lose a symbol to produce 13. Nonbinary VT constructions need additional or different constraints. [2]
Decoding: Let w count received ones and let d = (a - sum(i*y_i)) modulo n+1 be the checksum deficiency. If d <= w, insert 0 with d ones to its right; otherwise insert 1 with d-w-1 zeros to its left. This requires a linear scan, not enumeration of the codebook. A returned word still assumes the correct block length, residue and one-deletion model. [1]
Relations
Limitations
- One deletion OR one insertion is not a guarantee for a deletion plus an insertion, two deletions, or a substitution. [2]
- This mathematical family alone does not establish a complete DNA-storage codec, biochemical constraints or measured recovery rates. [2]
Citations
- N. J. A. Sloane. On Single-Deletion-Correcting Codes (revised 7 November 2002), sections 1-2, equation (4).
- Nguyen, Cai and Siegel. Differential VT Codes and Differential Shifted VT Codes, arXiv:2311.04578v1 (2023), sections II-III.
- Yeow Meng Chee et al. Coding for Racetrack Memories, arXiv:1701.06874v1 (2017), sections I-II.
Sources & caveats
- Source-based mathematical definition. Status research describes the storage applications covered here, not the maturity of the theorem.
- Hesela's bounded binary enumeration and counterexamples are available at https://hesela.dev/research/vt-code/example.json with example.py and test_example.py; they are not media measurements or an all-length proof.