Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 46 min ago
PreprintarXiv licencearXiv

Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound

  • Bencheng Fan
  • Margreta Kuijper
  • Jingge Zhu
Open at sourcePDFDOICite

Abstract

In this paper, we focus on decoding optimal Reed-Solomon codes of dimension two for insdel errors up to the half-Singleton bound. We present a decoding algorithm for the general insertion-and-deletion scenario with a time complexity smaller than brute-force decoding. Our algorithm corrects insdel errors up to the half-Singleton bound, which exceeds the scope of existing methods. Additionally, for the special cases of insertion-only and deletion-only insdel error patterns, we present two different algorithms with a time complexity smaller than our general algorithm.

Related

  1. Insdel Decoding Algorithms for Maximum Distance Separable Codes
    Bencheng Fan, Margreta Kuijper, Jingge Zhu
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
    Neehar Verma, Camilla Hollanti, Razane Tajeddine
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
    Joshua Brakensiek, Yeyuan Chen, Aaron Putterman +2
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  4. Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
    Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  5. Combinatorial limitations of list-decoding Reed-Solomon codes
    Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{fan2026insdel,
  title = {{Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound}},
  author = {Bencheng Fan and Margreta Kuijper and Jingge Zhu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15413},
  eprint = {2610.15413},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15413},
}
RIS
TY  - UNPB
TI  - Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound
AU  - Bencheng Fan
AU  - Margreta Kuijper
AU  - Jingge Zhu
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2610.15413
UR  - https://arxiv.org/abs/2610.15413
AB  - In this paper, we focus on decoding optimal Reed-Solomon codes of dimension two for insdel errors up to the half-Singleton bound. We present a decoding algorithm for the general insertion-and-deletion scenario with a time complexity smaller than brute-force decoding. Our algorithm corrects insdel errors up to the half-Singleton bound, which exceeds the scope of existing methods. Additionally, for the special cases of insertion-only and deletion-only insdel error patterns, we present two different algorithms with a time complexity smaller than our general algorithm.
ER  -