IEEE Transactions on Information Theory
On the Insdel Error-Correcting Capacities of Binary Reed–Muller Codes and Simplex Codes
Runqing Qiu, Shixin Zhu, Yang Li, Zhonghua Sun
Abstract
Insertion-deletion (insdel for short) codes have received extensive attention due to their ability to correct synchronization errors. It is usually a very challenging problem to determine the insdel distances of linear codes. In this paper, a good lower bound on the insdel distance of a linear code with a certain algebraic structure is provided and it indeed gives an affirmative answer to an open problem proposed by Hao Chen (IEEE Transactions on Information Theory, 68(8): 5126–5132, 2022). Applying this lower bound to binary first-order Reed-Muller codes and binary simplex codes, we obtain that they possess linear subcodes that can correct arbitrary insdel errors while maintaining Hamming distances robustness. The application of this bound on Reed-Muller codes completely solves an open problem left by Lara Dolecek and Venkat Anantharam (IEEE Transactions on Information Theory, 53(4): 1430–1443, 2007). In order to enhance the code rate, we further perform puncturing on these subcodes and determine the Hamming distances of the punctured subcodes while ensuring that their insdel distances remain unchanged.