Multiple Criss-Cross Deletion-Correcting Codes

This paper investigates the problem of correcting multiple criss-cross deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by any combination of $t_\mathrm{r}$ row and $t_\mathrm{c}$ column deletions such that $t_\mathrm{r} + t_\mathrm{c} = t$ for a given $t$. We refer to these type of deletions as $t$-criss-cross deletions. We show that a code capable of correcting $t$-criss-cross deletions has redundancy at least $tn + t \log n - \log(t!)$. Then, we present an existential construction of a code capable of correcting $t$-criss-cross deletions where its redundancy is bounded from above by $tn + \mathcal{O}(t^2 \log^2 n)$. The main ingredients of the presented code are systematic binary $t$-deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the deleted rows and columns, thus transforming the deletion-correction problem into an erasure-correction problem which is then solved using the second ingredient.