Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes

Abstract

In this paper, we construct systematic $q$-ary two-deletion correcting codes and burst-deletion correcting codes, where $q\ge 2$ is an even integer. For two-deletion codes, our construction has redundancy $5\log n+O(\log q\log \log n)$ and has encoding complexity near-linear in $n$, where $n$ is the length of the message sequences. For burst-deletion codes, we first present a construction of binary codes with redundancy $\log n+9\log \log n+{\gamma }_t+o(\log \log n)$ bits $({\gamma }_t$ is a constant that depends only on $t)$ and capable of correcting a burst of at most $t$ deletions, which improves the Lenz-Polyanskii Construction (ISIT 2020). Then we give a construction of $q$-ary codes with redundancy $\log n+(8\log q+9)\log \log n+o(\log q\log \log n)+{\gamma }_t$ bits and capable of correcting a burst of at most $t$ deletions.