All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-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.