Multiple Criss-Cross Insertion and Deletion Correcting Codes

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

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

3 Zitate (Scopus)

Abstract

This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of n × n arrays affected by t-criss-cross deletions defined as any combination of tr row and tc column deletions such that tr+ tc= t for a given t. We show an equivalence between correcting t-criss-cross deletions and t-criss-cross insertions and show that a code correcting t-criss-cross insertions/deletions has redundancy at least t n + t log n - log (t). Then, we present an existential construction of a t-criss-cross insertion/deletion correcting code with redundancy bounded from above by t n + O(t2} log2n). The main ingredients of the presented code construction are systematic binary t-deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient.

OriginalspracheEnglisch
Seiten (von - bis)3767-3779
Seitenumfang13
FachzeitschriftIEEE Transactions on Information Theory
Jahrgang68
Ausgabenummer6
DOIs
PublikationsstatusVeröffentlicht - 1 Juni 2022

Fingerprint

Untersuchen Sie die Forschungsthemen von „Multiple Criss-Cross Insertion and Deletion Correcting Codes“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren