Codes correcting a burst of deletions or insertions

Clayton Schoeny, Antonia Wachter-Zeh, Ryan Gabrys, Eitan Yaakobi

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

6 Zitate (Scopus)

Abstract

This paper studies codes that correct bursts of deletions. Namely, a code will be called a b-burst-correcting code if it can correct a deletion of any b consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically log(n) + b - 1, the redundancy of the best code construction by Cheng et al. is b(log(n/b + 1)). In this paper we close on this gap and provide codes with redundancy at most log(n) + (b - 1) log(log(n)) + b - log(b). We also extend the burst deletion model to two more cases: 1. a deletion burst of at most b consecutive bits and 2. a deletion burst of size at most b (not necessarily consecutive). We extend our code construction for the first case and study the second case for b = 3, 4. The equivalent models for insertions are also studied and are shown to be equivalent to correcting the corresponding burst of deletions.

OriginalspracheEnglisch
TitelProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
Herausgeber (Verlag)Institute of Electrical and Electronics Engineers Inc.
Seiten630-634
Seitenumfang5
ISBN (elektronisch)9781509018062
DOIs
PublikationsstatusVeröffentlicht - 10 Aug. 2016
Extern publiziertJa
Veranstaltung2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spanien
Dauer: 10 Juli 201615 Juli 2016

Publikationsreihe

NameIEEE International Symposium on Information Theory - Proceedings
Band2016-August
ISSN (Print)2157-8095

Konferenz

Konferenz2016 IEEE International Symposium on Information Theory, ISIT 2016
Land/GebietSpanien
OrtBarcelona
Zeitraum10/07/1615/07/16

Fingerprint

Untersuchen Sie die Forschungsthemen von „Codes correcting a burst of deletions or insertions“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren