Name
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 t(r) row and t(c) column deletions such that t(r) + t(c) = t for a given t. We refer to these type of deletions as t criss cross deletions. We show that the asymptotic redundancy of a code correcting t-criss-cross deletions is 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 + 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/ISIT45174.2021.9517743 | 2021 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lorenz Welter | 1 | 1 | 2.04 |
| Rawad Bitar | 2 | 0 | 0.34 |
| Antonia Wachter-Zeh | 3 | 129 | 33.65 |
| Eitan Yaakobi | 4 | 604 | 70.41 |