Correcting bursty and localized deletions using guess & check codes

We consider the problem of constructing binary codes for correcting deletions that are localized within a certain part of the codeword that is unknown a priori. The model that we study is when δ ≤ w deletions occur in a window of size at most w bits. These δ deletions are not necessarily consecutive, but are restricted to a window of size w. The localized deletions model is a generalization of the bursty model, where all the deleted bits are consecutive. In this work we propose new explicit codes, based on the family of Guess & Check codes [1,2], that can correct, with high probability, δ ≤ w deletions that are localized within a window of size at most w = O (log k), where k is the length of the information message. These codes have deterministic polynomial time encoding and decoding schemes. The redundancy of these codes is c log k + w + 1, where c is a constant representing a code parameter.