Improved Constructions of Linear Codes for Insertions and Deletions
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
In this work, we study linear error-correcting codes against adversarial insertion-deletion (indel) errors. While most constructions for the indel model are nonlinear, linear codes offer compact representations, efficient encoding, and decoding algorithms, making them highly desirable. A key challenge in this area is achieving rates close to the half-Singleton bound for efficient linear codes over finite fields. We improve upon previous results by constructing explicit codes over Fq2, linear over Fq, with rate 1/2 − δ − ε that can efficiently correct a δ-fraction of indel errors, whereq=O(ε−4). Additionally, we construct fully linear codes over Fqwith rate 1/2 − 2 √ δ − ε that can also efficiently correct δ-fraction of indels. These results significantly advance the study of linear codes for the indel model, bringing them closer to the theoretical half-Singleton bound. We also generalize the half-Singleton bound, for every codeC⊆ Fnlinear over E ⊂ F a subfield of F, such thatChas the ability to correct δ-fraction of indels, the rate is bounded by (1 − δ)/2.
Fields of Study & Subjects
Coding theory and cryptography
Error Correcting Code Techniques
Algorithms and Data Compression
Publication details
- Journal / source
- IEEE Transactions on Information Theory
- Volume
- 72
- Issue
- 6
- Pages
- 3830–3839
- Publication date
- 26 March 2026
- Language
- EN