Binary Codes for Correcting Asymmetric Adjacent Transpositions and Deletions

Codes in the Damerau-Levenshtein metric have received some attention by the research community recently owing to their applications in DNA-based data storage. In particular, Gabrys, Yaakobi, and Milenkovic designed a length-n code correcting a single deletion and s adjacent transpositions 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">$(1+2s)\log n$ </tex-math></inline-formula> bits of redundancy. In this work, we consider a new setting where both deletions and asymmetric adjacent transpositions may occur. For asymmetric transpositions, 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">$s^{+}0$ </tex-math></inline-formula>-right shifts (i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$01 \rightarrow 10$ </tex-math></inline-formula>) and 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">$s^ - 0$ </tex-math></inline-formula>-left shifts (i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$10 \rightarrow 01$ </tex-math></inline-formula>) may occur. We present several constructions of the binary codes correcting these errors in various cases. In particular, we design a code correcting a single deletion, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$s^{+}$ </tex-math></inline-formula> right-shift, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$s^ - $ </tex-math></inline-formula> left-shift errors 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">$(1+s)\log (n+s+1)+1$ </tex-math></inline-formula> bits of redundancy where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$s=s^{+}+s^ - $ </tex-math></inline-formula>. In addition, we investigate uniquely-decodable codes correcting <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t~0$ </tex-math></inline-formula>-deletions and s adjacent transpositions 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">$(t+2s)\log n+o(\log n)$ </tex-math></inline-formula> bits of redundancy. Then, we study the code for correcting <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t~0$ </tex-math></inline-formula>-deletions, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$s^{+}$ </tex-math></inline-formula> right-shift, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$s^ - $ </tex-math></inline-formula> left-shift errors with list-decoding algorithms. Our main contribution here is the construction of a list-decodable code with list size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n^{s})$ </tex-math></inline-formula> and 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">$(\max \{t,s+1\}) \log n+O(1)$ </tex-math></inline-formula> bits of redundancy, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$s=s^{+}+s^ - $ </tex-math></inline-formula>. We construct non-systematic codes for correcting <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t_{\mathrm {b}}$ </tex-math></inline-formula> blocks of 0-deletions with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell $ </tex-math></inline-formula>-limited magnitude and s adjacent transpositions with redundancy 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">$(2(t_{\mathrm {b}}+2s)+1)\log (n+1)+O(1)$ </tex-math></inline-formula> bits and systematic codes 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">$((2(t_{\mathrm {b}}+2s)+1)(1+1/(\log (t_{\mathrm {b}}\ell +4)))\log (N+1)+O(\log \log N)$ </tex-math></inline-formula> redundant bits in an N-length codeword.