2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.8.2 | ||
| Paper Title | Optimal Codes Correcting a Burst of Deletions of Variable Length | ||
| Authors | Andreas Lenz, Nikita Polyanskii, Technical University of Munich, Germany | ||
| Session | M.8: Insertion Deletion Substitution Codes II | ||
| Presentation | Lecture | ||
| Track | Coding for Storage and Memories | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | In this paper, we present an efficiently encodable and decodable code construction that is capable of correcting a burst of deletions of length at most k. The redundancy of this code is log n + k(k+1)/2 log log n + c_k for some constant c_k that only depends on k and thus is scaling-optimal. The code can be split into two main components. First, we impose a constraint that allows us to locate the burst of deletions up to an interval of size roughly log n. Then, with the knowledge of the approximate location of the burst, we use several shifted Varshamov-Tenengolts codes to correct the burst of deletions, which only requires a small amount of redundancy since the location is already known up to an interval of small size. Finally, we show how to efficiently encode and decode the code. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
