Summary
2020
Session Number:B06
Session:
Number:B06-7
Criss-Cross Deletion Correcting Codes
Rawad Bitar, Ilia Smagloy, Lorenz Welter, Antonia Wachter-Zeh, Eitan Yaakobi,
pp.304-308
Publication Date:2020/10/18
Online ISSN:2188-5079
PDF download
Summary:
This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an \(n\times n\) array can experience deletions of rows and columns. These deletion errors are referred to as \((t_r,t_c)\)-criss-cross deletions if \(t_r\) rows and \(t_c\) columns are deleted, while a code correcting these deletion patterns is called a \((t_r,t_c)\)-criss-cross deletion correcting code. The definitions for criss-cross insertions are similar. Similar to the one-dimensional case, it is first shown that the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. Then, we mostly investigate the case of \((1,1)\)-criss-cross deletions. An asymptotic upper bound on the cardinality of \((1,1)\)-criss-cross deletion correcting codes is shown which assures that the asymptotic redundancy is at least \(2n-2+2\log n\) bits. Finally, a code construction with an explicit decoding algorithm is presented. The redundancy of the construction is away from the lower bound by at most \(2 \log n+9+2\log e\) bits.