A New Version of q-Ary Varshamov-Tenengolts Codes With More Efficient Encoders: The Differential VT Codes and The Differential Shifted VT Codes
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
The problem of correcting deletions and insertions has recently received significantly increased attention due to the DNA-based data storage technology, which suffers from deletions and insertions with extremely high probability. In this work, we study the problem of constructing non-binary burst-deletion/insertion correcting codes. Particularly, for the quaternary alphabet, our designed codes are suited for correcting a burst of deletions/insertions in DNA storage. Non-binary codes correcting a single deletion or insertion were introduced by Tenengolts (1984), and the results were extended to correct a fixed-length burst of deletions or insertions by Schoeny et al. (2017). Recently, Wang et al. (2021) proposed constructions of non-binary codes of length n, correcting a burst of length at most two for q-ary alphabets with redundancy <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log n+O(\log q \log \log n)$ </tex-math></inline-formula> bits, for arbitrary even q. The common idea in those constructions is to convert non-binary sequences into binary sequences, and the error decoding algorithms for the q-ary sequences are mainly based on the success of recovering the corresponding binary sequences, respectively. In this work, we look at a natural solution that the error detection and correction algorithms are performed directly over q-ary sequences, and for certain cases, our codes provide a more efficient encoder with lower redundancy than the best-known encoder in the literature. Particularly, (Single-error correction codes) We first present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion, providing an alternative simpler and more efficient encoder of the construction by Tenengolts (1984). Our construction is based on the differential vector, and the codes are referred to as the differential VT codes. In addition, we provide linear-time algorithms that encode user messages into these codes of length n over the q-ary alphabet for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q \geqslant 2$ </tex-math></inline-formula> with at most <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\lceil \log _{q} n\rceil +1$ </tex-math></inline-formula> redundant symbols, while the optimal redundancy required is at least <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log _{q} n+\log _{q} (q-1)$ </tex-math></inline-formula> symbols. Our designed encoder reduces the redundancy of the best-known encoder of Tenengolts (1984) by at least 2 redundant symbols or equivalently <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2\log _{2} q$ </tex-math></inline-formula> bits. (Burst-error correction codes) We use the idea of the binary shifted VT codes to define the q-ary differential shifted VT codes, and propose non-binary codes correcting a burst of up to two deletions (or two insertions) with redundancy <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log n+3\log \log n+ O(\log q)$ </tex-math></inline-formula> bits, which improves a recent result of Wang et al. (2021) with redundancy <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log n+O(\log q \log \log n)$ </tex-math></inline-formula> bits for all <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q\geqslant 8$ </tex-math></inline-formula>. We then extend the construction to design non-binary codes correcting a burst of either exactly or at most t deletions (or insertions) for arbitrary <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t\geqslant 2$ </tex-math></inline-formula>.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.001 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it