A New Version of q-Ary Varshamov-Tenengolts Codes With More Efficient Encoders: The Differential VT Codes and The Differential Shifted VT Codes
Tuan Thanh Nguyen, Kui Cai, Paul H. Siegel
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>.