Correcting Multiple Bursts of Exactly t Deletions

Stored or transmitted data is often subject to errors arising from noise, interference, or physical defects. Error-correcting codes play a crucial role in detecting and recovering from such errors to ensure reliable communication and data storage. In this thesis, we focus on burst deletion errors, where multiple consecutive symbols may be removed from a sequence. We propose novel code constructions that efficiently correct multiple bursts of exactly t deletions. Our primary contribution is a generalizable framework that extends existing deletion-correcting methods to handle multiple bursts in both binary and q-ary sequences.

Specifically, we construct a code capable of correcting two bursts of exactly t deletions in binary sequences with redundancy at most 6.4 log n + 10 log log n+O(1). We further extend our construction to q-ary sequences, achieving redundancy 7.4 log n+10 log log n+3 log q+O(1). Additionally, we introduce a code for three bursts of exactly t deletions with redundancy at most 15 log n+o(log n), and an encoding and decoding complexity of O(n^7).

Our approach combines deletion-correcting codes, such as Guruswami and Håstad’s explicit two-deletion code, with efficient erasure-correcting codes, including Dumer’s linear codes with designed distance 5. For a code correcting three bursts of exactly t deletions, we employ syndrome compression to identify error locations and leverage structured redundancy to improve efficiency. We analyze the time complexity of our encoding and decoding process and show that our three bursts of t deletion correcting code has an encoding and decoding complexity of O(n^7), which is asymptotically more efficient than a direct application of syndrome compression for large t.

This work contributes to the broader study of deletion-correcting codes by providing explicit constructions that balance redundancy, efficiency, and scalability. The proposed techniques offer promising directions for improving deletion error resilience in DNA storage, document synchronization protocols, and digital communications. We conclude with potential extensions, including the correction of multiple bursts of 2 erasures and further optimization of redundancy in multi-burst scenarios.