Codes for Correcting $t$ Limited-Magnitude Sticky Deletions

Abstract

Codes for correcting sticky insertions/deletions and limited-magnitude errors have attracted significant attention due to their applications of flash memories, racetrack memories, and DNA data storage systems. In this paper, we first consider the error type of $t$-sticky deletions with $\ell$-limited-magnitude and propose a non-systematic code for correcting this type of error with redundancy $2t(1-1/p)\cdot \log (n+1)+O(1)$, where $p$ is the smallest prime larger than $\ell +1$. Next, we present a systematic code construction with an efficient encoding and decoding algorithm with redundancy $\frac{\lceil 2t(1-1/p)\rceil \cdot \lceil \log p\rceil }{\log p}\log (n+1)+O(\log \log n)$, where $p$ is the smallest prime larger than $\ell +1$.

arXiv admin note: substantial text overlap with arXiv:2301.11680