Codes Correcting Two Bursts of Exactly b Deletions
Zuo Ye, Yubo Sun, Wenjun Yu, Gennian Ge, Ohad Elishco · IEEE Transactions on Information Theory · 2025
In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactlyb, whereb> 1. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most 7 logn+O(logn/ log logn) bits. In contrast, our work introduces a novel approach for constructing q-ary codes that attain a redundancy of at most 5 logn+O(log logn) bits for allb> 1 andq≥ 2. Additionally, for the case whereb= 1, we present a new construction of q-ary two-deletion correcting codes with a redundancy of 5 logn+ O(log logn) bits, for allq> 2.