Insdel Decoding Algorithms for Maximum Distance Separable Codes
Bencheng Fan, Margreta Kuijper, Jingge Zhu
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.
尚无 AI 解读，展示原文摘要