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

This is the authors' abstract. We don't add key points for this paper.

In this paper, we constructq-ary two-deletion correcting codes and burst-deletion correcting codes, whereq≥ 2is an even integer. For two-deletion codes, our construction has redundancy5log n+O(log qlog log n)and has encoding complexity near-linear inn, wherenis the length of the message sequences. For burst-deletion codes, we first present a construction of binary codes with redundancylog n+9log log n+γ ₜ+o(log log n)bits(γ ₜis a constant that depends only ont) and capable of correcting a burst of at mosttdeletions, which improves the Lenz-Polyanskii Construction (ISIT 2020). Then we give a construction ofq-ary codes with redundancylog n+(8log q+9)log log n+γ ₜ+o(log log n)bits and capable of correcting a burst of at mosttdeletions.