| Paper ID | D6-S5-T4.2 |
| Paper Title |
Multiple Criss-Cross Deletion-Correcting Codes |
| Authors |
Lorenz Welter, Rawad Bitar, Antonia Wachter-Zeh, Technical University of Munich, Germany; Eitan Yaakobi, Technion - Israel Institute of Technology, Germany |
| Session |
D6-S5-T4: Array & Burst Deletion-Correcting Codes |
| Chaired Session: |
Monday, 19 July, 23:20 - 23:40 |
| Engagement Session: |
Monday, 19 July, 23:40 - 00:00 |
| Abstract |
This paper investigates the problem of correcting multiple criss-cross deletions in arrays. More precisely, we study the unique recovery of n x n arrays affected by any combination of tr row and tc column deletions such that tr + tc = 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 + (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.
|
