Reed solomon decoding methods correct more insertion and deletion errors
Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound
Information Theory
Summary
Communication and storage systems sometimes lose or add extra pieces in transmitted messages, causing errors. Decoding these messages correctly is important to recover the original information. The authors focus on a special type of error called insertion and deletion errors for certain Reed-Solomon codes. They designed new algorithms that can correct more of these errors efficiently than previous methods. Their work offers faster ways to fix messages even when errors involve insertions only or deletions only.
What this means in practice
- •For distributed storage engineers: Design fault-tolerant storage systems that can correct combined insertion and deletion errors beyond previous limits for Reed-Solomon codes of dimension two.
- •For digital communication developers: Build communication protocols resilient to insertion-only or deletion-only errors with faster decoding algorithms specialized for these cases.
Authors
Bencheng Fan, Margreta Kuijper, Jingge Zhu
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.