Criss-Cross Insertion and Deletion Correcting Codes

Rawad Bitar, Lorenz Welter, Ilia Smagloy, Antonia Wachter-Zeh, Eitan Yaakobi

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an n × n array can experience deletions of rows and columns. These deletion errors are referred to as (tr, {tc)-criss-cross deletions if tr rows and tc columns are deleted, while a code correcting these deletion patterns is called a (tr, tc)-criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when tr=tc the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least 2n-3+2 log n bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most 2n+4 log n + 7 +2 log e. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra 5 log n + 5 bits of redundancy to the construction.

Original languageEnglish
Pages (from-to)7999-8015
Number of pages17
JournalIEEE Transactions on Information Theory
Volume67
Issue number12
DOIs
StatePublished - 1 Dec 2021

Keywords

  • Insertion/deletion correcting codes
  • array codes
  • criss-cross deletion errors

Fingerprint

Dive into the research topics of 'Criss-Cross Insertion and Deletion Correcting Codes'. Together they form a unique fingerprint.

Cite this