Codes for Correcting Localized Deletions

DOI10.1109/TIT.2021.3051532MaRDI QIDQ5001622zbMATH OpenOpenAlexFDO

Authors Serge Kas Hanna, Salim El Rouayheb

Publication date 22 July 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.01941

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: We consider the problem of constructing binary codes for correcting deletions that are localized within certain parts of the codeword that are unknown a priori. The model that we study is when $deltaleqw$ deletions are localized in a window of size $w$ bits. These $delta$ deletions do not necessarily occur in consecutive positions, but are restricted to the window of size $w$. The localized deletions model is a generalization of the bursty model, in which all the deleted bits are consecutive. In this paper, we construct new explicit codes for the localized model, based on the family of Guess & Check codes which was previously introduced by the authors. The codes that we construct can correct, with high probability, $deltaleqw$ deletions that are localized in a single window of size $w$, where $w$ grows with the block length. Moreover, these codes are systematic; have low redundancy; and have efficient deterministic encoding and decoding algorithms. We also generalize these codes to deletions that are localized within multiple windows in the codeword.

Cited in

(2)

• scientific article; zbMATH DE number 5302391 (Why is no real title available?)
• scientific article; zbMATH DE number 605666 (Why is no real title available?)

This page was built for publication: Codes for Correcting Localized Deletions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5001622)