Skip to content
Preprint

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

Oct 2026 · 1 citation · ⚡ 1 influential · 17 references
Computer Science Mathematics

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.