Improved Constructions of Linear Codes for Insertions and Deletions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909816632377344 |
|---|---|
| author | Gross, Roee Con, Roni Yaakobi, Eitan |
| author_facet | Gross, Roee Con, Roni Yaakobi, Eitan |
| contents | 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 \(\mathbb{F}_{q^2}\), linear over \(\mathbb{F}_q\), with rate \(1/2 - δ- \varepsilon\) that can efficiently correct a \(δ\)-fraction of indel errors, where \(q = O(\varepsilon^{-4})\). Additionally, we construct fully linear codes over \(\mathbb{F}_q\) with rate \(1/2 - 2\sqrtδ - \varepsilon\) 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 code \(C \subseteq \mathbb{F}^n\) linear over \(\mathbb{E} \subset \mathbb{F}\) a subfield of $\mathbb{F}$, such that \(C\) has the ability to correct \(δ\)-fraction of indels, the rate is bounded by $(1-δ)/2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26077 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Constructions of Linear Codes for Insertions and Deletions Gross, Roee Con, Roni Yaakobi, Eitan Information Theory 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 \(\mathbb{F}_{q^2}\), linear over \(\mathbb{F}_q\), with rate \(1/2 - δ- \varepsilon\) that can efficiently correct a \(δ\)-fraction of indel errors, where \(q = O(\varepsilon^{-4})\). Additionally, we construct fully linear codes over \(\mathbb{F}_q\) with rate \(1/2 - 2\sqrtδ - \varepsilon\) 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 code \(C \subseteq \mathbb{F}^n\) linear over \(\mathbb{E} \subset \mathbb{F}\) a subfield of $\mathbb{F}$, such that \(C\) has the ability to correct \(δ\)-fraction of indels, the rate is bounded by $(1-δ)/2$. |
| title | Improved Constructions of Linear Codes for Insertions and Deletions |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.26077 |