Improved Constructions of Linear Codes for Insertions and Deletions

Read full text Summarise with VIRAT
Authors: Roee Gross, Roni Con, Eitan Yaakobi
Cited by: 0
References: 42

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