Codes Correcting Two Bursts of Exactly b Deletions

2024/08/06 by Ye, Zuo, Sun, Yubo, Yu, Wenjun +2 · 4 citations
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2408.03113

Abstract

In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactly b, where b>1. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most 7log n+O(log n/loglog n) bits. In contrast, our work introduces a novel approach for constructing q-ary codes that attain a redundancy of at most 5log n+O(loglog n) bits for all b>1 and q≥2. Additionally, for the case where b=1, we present a new construction of q-ary two-deletion correcting codes with a redundancy of 5log n+O(loglog n) bits, for all q>2.

Cited by

• On the Maximum Size of Codes Under the Damerau-Levenshtein Metric
• Correcting Bursty/Localized Deletions: A New Error-Position-Estimation Code
• Correcting Errors Through Partitioning and Burst-Deletion Correction
• Criss-Cross Deletion Correcting Codes: Optimal Constructions with Efficient Decoders

Related

• Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes
• Codes Correcting a Burst of Deletions or Insertions
• Binary t₁-Deletion-t₂-Insertion-Burst Correcting Codes and Codes Correcting a Burst of Deletions
• New Construction of q-ary Codes Correcting a Burst of at most t Deletions
• Codes Correcting Two Deletions