Construction and redundancy of codes for correcting deletable errors

2018/04/29 by Ghurumuruhan Ganesan, Ganesan, Ghurumuruhan
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.1805.00776

openalex publication_date 2018/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider a binary word being transmitted through a communication channel that introduces deletable errors where each bit of the word is either retained, flipped, erased or deleted. The simplest code for correcting all possible deletable error patterns of a fixed size is the repetition code whose redundancy grows linearly with the code length. In this paper, we relax this condition and construct codes capable of correcting nearly all deletable error patterns of a fixed size, with redundancy growing as a logarithm of the word length.

Related

• Real-time error correction codes for deletable errors
• Codes Correcting Two Deletions
• Codes Correcting a Burst of Deletions or Insertions
• Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
• Optimal Codes Correcting a Burst of Deletions of Variable Length