Codes for Correcting Asymmetric Adjacent Transpositions and Deletions
share
Owing to the vast applications in DNA-based data storage, Gabrys, Yaakobi, and Milenkovic recently proposed to study codes in the Damerau–Levenshtein metric, where both deletion and adjacent transposition errors occur. In particular, they designed a code correcting a single deletion and s adjacent transpositions with at most (1+2s)log n bits of redundancy. In this work, we consider a new setting where both asymmetric adjacent transpositions (also known as right-shifts or left-shifts) and deletions occur. We present several constructions of the codes correcting these errors in various cases. In particular, we design a code correcting a single deletion, s^+ right-shift, and s^- left-shift errors with at most (1+s)log (n+s+1)+1 bits of redundancy where s=s^++s^-. In addition, we investigate codes correcting t 0-deletions and s adjacent transpositions with both unique decoding and list-decoding algorithms. Our main contribution here is a construction of a list-decodable code with list-size O(n^min{s+1,t}) and has at most (max{t,s+1}) log n+O(1) bits of redundancy. Finally, we provide both non-systematic and systematic codes for correcting t blocks of 0-deletions with ℓ-limited-magnitude and s adjacent transpositions.
READ FULL TEXT