Criss-Cross Burst-Deletion Correcting Codes With Optimal Redundancy and En/Decoding Complexity $\mathcal{O}(n^{2})$
Abstract
Two-dimensional error-correcting codes have attracted significant attention due to their applications in QR codes, DNA-based storage, and racetrack memories. This paper focuses on <inline-formula> <tex-math notation="LaTeX">$(t_{r}, t_{c})$ </tex-math></inline-formula>-criss-cross burst-deletion correcting codes, which are capable of correcting deletions of <inline-formula> <tex-math notation="LaTeX">$t_{r}$ </tex-math></inline-formula> consecutive rows and <inline-formula> <tex-math notation="LaTeX">$t_{c}$ </tex-math></inline-formula> consecutive columns in an <inline-formula> <tex-math notation="LaTeX">$n \times n$ </tex-math></inline-formula> array over an alphabet of size <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>. Existing literature has established a lower bound on the redundancy of <inline-formula> <tex-math notation="LaTeX">$(t_{r} + t_{c})n + 2 \log _{q} n + \mathcal {O}(1)$ </tex-math></inline-formula>. While recent work has demonstrated the existence of optimal codes achieving this bound, the determination of the specific code parameters relies on the pigeonhole principle, resulting in a non-explicit construction that lacks an efficient encoding algorithm. In this work, we present an explicit construction of a <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-ary <inline-formula> <tex-math notation="LaTeX">$(t_{r}, t_{c})$ </tex-math></inline-formula>-criss-cross burst-deletion correcting code for parameters satisfying <inline-formula> <tex-math notation="LaTeX">$t_{r} \mid n$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$t_{c} \mid n$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$q\ge 3$ </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">$n \ge 11 \cdot \max (t_{r}, t_{c})$ </tex-math></inline-formula>. This construction is accompanied by efficient encoding and decoding algorithms with computational complexity <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(n^{2})$ </tex-math></inline-formula>. We further provide a non-asymptotic redundancy analysis showing that, for fixed <inline-formula> <tex-math notation="LaTeX">$t_{r}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$t_{c}$ </tex-math></inline-formula>, the construction achieves the optimal redundancy <inline-formula> <tex-math notation="LaTeX">$(t_{r} + t_{c})n + 2 \log _{q} n + \mathcal {O}(1)$ </tex-math></inline-formula> under an explicit sub-linear alphabet-size condition <inline-formula> <tex-math notation="LaTeX">$q=\Theta (n/\ln n)$ </tex-math></inline-formula>. To the best of our knowledge, this is the first explicit construction that simultaneously attains the asymptotic redundancy lower bound and supports efficient encoding and decoding.