EUVIMEDEUVIMED entdecken
Crossref

Improved Constructions of Linear Codes for Insertions and Deletions

Roee Gross, Roni Con, Eitan Yaakobi

IEEE Transactions on Information Theory · 2026-06 · 72 (6) · 3830-3839

DOI: 10.1109/tit.2026.3678200 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-06. Verfasst von Roee Gross und 2 weiteren Autor:innen. Die Arbeit nennt 41 Literaturangaben. Gefördert von: Israel Science Foundation, European Union.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 - \delta - \varepsilon $ that can efficiently correct a $\delta $ -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 {\delta } - \varepsilon $ that can also efficiently correct $\delta $ -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 $\delta $ -fraction of indels, the rate is bounded by $(1-\delta)/2$ .

Förderung

  • Israel Science Foundation
  • European Union

Zitieren

APA

Gross, R., Con, R., & Yaakobi, E. (2026). Improved Constructions of Linear Codes for Insertions and Deletions. IEEE Transactions on Information Theory, 72(6), 3830-3839. https://doi.org/10.1109/tit.2026.3678200

Vancouver

Gross R, Con R, Yaakobi E. Improved Constructions of Linear Codes for Insertions and Deletions. IEEE Transactions on Information Theory. 2026;72(6):3830-3839. doi:10.1109/tit.2026.3678200

BibTeX
@article{Gross2026,
  author = {Gross, Roee and Con, Roni and Yaakobi, Eitan},
  title = {Improved Constructions of Linear Codes for Insertions and Deletions},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {6},
  pages = {3830--3839},
  doi = {10.1109/tit.2026.3678200}
}
Kostenlos starten →