Binary t₁-Deletion-t₂-Insertion-Burst Correcting Codes and Codes Correcting a Burst of Deletions

2022/11/21 by Zuo Ye, Ye, Zuo, Ohad Elishco +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.2211.11658

openalex publication_date 2022/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We first give a construction of binary t₁-deletion-t₂-insertion-burst correcting codes with redundancy at most log(n)+(t₁-t₂-1)loglog(n)+O(1), where t₁≥ 2t₂. Then we give an improved construction of binary codes capable of correcting a burst of 4 non-consecutive deletions, whose redundancy is reduced from 7log(n)+2loglog(n)+O(1) to 4log(n)+6loglog(n)+O(1). Lastly, by connecting non-binary b-burst-deletion correcting codes with binary 2b-deletion-b-insertion-burst correcting codes, we give a new construction of non-binary b-burst-deletion correcting codes with redundancy at most log(n)+(b-1)loglog(n)+O(1). This construction is different from previous results.

Related

• Codes Correcting a Burst of Deletions or Insertions
• Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes
• t-Deletion-s-Insertion-Burst Correcting Codes
• Codes Correcting Two Bursts of Exactly b Deletions
• An Improvement of Non-binary Code Correcting Single b-Burst of Insertions or Deletions