학술논문
Correcting bursty and localized deletions using guess & check codes
Document Type
Conference
Author
Source
2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) Communication, Control, and Computing (Allerton), 2017 55th Annual Allerton Conference on. :9-16 Oct, 2017
Subject
Language
Abstract
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.