Optimal Codes Correcting a Burst of Deletions of Variable Length
share
In this paper, we present an efficiently encodable and decodable code construction that is capable of correction a burst of deletions of length at most k. The redundancy of this code is log n + k(k+1)/2loglog 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 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.
READ FULL TEXT