Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

Abstract

We construct systematic $q$-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length $n\ge 2$, our first construction has length $n+3$ over an alphabet of size $q=2^s<2^{32}{n}^7$ for some integer $s$, with polynomial-time encoding and decoding. A cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size $O(n^4)$, leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size $q<(n+2{)}^4$. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for $n\ge 2$.

arXiv comment52 pages