Insdel codes from subspace and rank-metric codes

Insertion and deletion (insdel in short) codes are designed to deal with synchronization errors in communication channels caused by insertions and deletions of message symbols. These codes have received a lot of attention due to their applications in diverse areas such as computational biology, DNA data storage, race-track memory error corrections, language processing, and synchronous digital communication networks. In the present work, we study constructions and limitations of insdel codes from rank metric and subspace codes. This paper studies and improves the idea of the work [4] by Hao Chen on the connection between insdel codes and subspace codes. We discuss why subspace code is a natural choice for constructing insdel codes and show that the interleaved Gabidulin codes can be used to construct nonlinear insdel codes approaching the Singleton bound. Then we show that the indexing scheme of transforming efficient Hamming metric codes to efficient insdel codes can be adapted for the class of rank metric codes. And that improves the base field size of the construction of insdel codes from lifted rank-metric codes. It is also shown that the size of the insdel code from a subspace code can be improved significantly than in the previously proposed construction. We give an algebraic condition for a linear Gabidulin rank metric code to be optimal insdel code adapting the condition proved for Reed-Solomon codes. Moreover, we give constructions of linear and nonlinear insdel codes from Sidon spaces. (c) 2023 Elsevier B.V. All rights reserved.

Automated summary

This paper investigates the constructions and limitations of insertion and deletion (insdel) codes, and connects them with rank metric and subspace codes. The research reveals that subspace codes are a suitable choice for constructing insdel codes, and shows that interleaved Gabidulin codes can be used to construct nonlinear insdel codes. Additionally, the indexing scheme for transforming efficient Hamming metric codes is adapted for rank metric codes, improving the base field size of insdel code constructions. It is also demonstrated that the size of insdel codes from subspace codes can be significantly improved compared to previous constructions. The paper provides an algebraic condition for a linear Gabidulin rank metric code to be an optimal insdel code, adapting the condition proved for Reed-Solomon codes. Moreover, constructions of both linear and nonlinear insdel codes from Sidon spaces are presented.