Insdel Decoding Algorithms for Maximum Distance Separable Codes
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.
Related
- Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound
- Nonisomorphic separable Banach spaces at Lipschitz distance one
- Maximum purity of absolutely separable and absolutely PPT states in qutrit--qudit systems
- Minimum Distance Spectral Radius of Tree with Given Maximum Degree
- Approximation Algorithms for Maximum-Weight Degree-Bounded Forests
BibTeX
@misc{fan2026insdel,
title = {{Insdel Decoding Algorithms for Maximum Distance Separable Codes}},
author = {Bencheng Fan and Margreta Kuijper and Jingge Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34511},
eprint = {2610.34511},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34511},
}
RIS
TY - UNPB
TI - Insdel Decoding Algorithms for Maximum Distance Separable Codes
AU - Bencheng Fan
AU - Margreta Kuijper
AU - Jingge Zhu
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34511
UR - https://arxiv.org/abs/2610.34511
AB - 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.
ER -