Technical Program

Paper Detail

Paper IDM.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

Visit Website!