Improved error correction for maximum distance separable codes
Insdel Decoding Algorithms for Maximum Distance Separable Codes
Information Theory
Summary
Sometimes when data is sent or stored, bits can get inserted or deleted by mistake, causing errors that are tricky to fix. The authors found new ways to decode special kinds of error-correcting codes called MDS codes that can handle these insertion and deletion errors better than before. Their method works faster than trying every possibility and can correct more errors for certain codes like Reed-Solomon codes. They also created simpler, faster methods for cases with only insertions or only deletions.
What this means in practice
- •For communications engineers: Implement more efficient error correction in channels prone to insertion and deletion errors using MDS codes below half rate to improve data reliability.
- •For data storage developers: Design storage systems that recover from insertion and deletion corruptions more effectively by integrating these improved decoding algorithms for Reed-Solomon codes.
Authors
Bencheng Fan, Margreta Kuijper, Jingge Zhu
Abstract
In this paper, we focus on decoding MDS linear block codes for insdel errors. Building on our recent work for two-dimensional Reed-Solomon codes, we present a decoding algorithm for bounded distance decoding for the general insertion-and-deletion scenario that can be used for any MDS code of rate at most half. Our algorithm employs a sliding window and has a time complexity smaller than brute-force decoding. In particular, for optimal Reed-Solomon codes, it 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.