2025/07/07 by Ye, Zuo, Sun, Yubo, Ge, Gennian
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2507.04797
Codes correcting bursts of deletions and localized deletions have garnered significant research interest in recent years. One of the primary objectives is to construct codes with minimal redundancy. Currently, the best known constructions of q-ary codes correcting a burst of at most t deletions ((≤ t)-burst-deletion correcting codes) achieve redundancy log n+8loglog n+o(loglog n) (for any q and t) or log n+tloglog n+O(1) (for even q). For codes correcting single t-localized-deletion (t-localized-deletion correcting codes), state-of-the-art constructions attain redundancy log n+O\parenvt(loglog n)2 (for any q and t) or log n+2tloglog n+O(1) (for even q). Here, n denotes the code-length, and q and t are fixed. These codes employ a position-estimation component to approximate error positions, augmented by additional constraints that enable error-correction given the information about error positions. In this work, we select codewords from the set of sequences whose differential sequences are strong-(ℓ,ε)-locally-balanced. By imposing a VT-type constraint and an L1-weight constraint on the differential sequences of codewords, we construct novel position-estimation codes. When q≥ 2 and t