Strict Half-Singleton Bound, Strict Direct Upper Bound for Linear Insertion-Deletion Codes and Optimal Codes
Qinqin Ji, Dabin Zheng, Hao Chen, Xiaoqiang Wang · IEEE Transactions on Information Theory · 2023
Let${\mathcal C}$be an$[n, k]$linear code over the finite field${\mathbb F}_{q}$. Let$d_{I}({\mathcal C})$denote its insertion-deletion (insdel for short) distance, which characterizes the insdel error-correcting capability of${\mathcal C}$. To determine the insdel distances of linear codes is a very challenging problem. In this paper we propose a strict half-Singleton upper bound$d_{I}({\mathcal C}) \leq 2(n-2k+1)$if${\mathcal C}$does not contain the codeword with all 1s, which generalizes the half-Singleton bound on the insdel distances of linear codes due to Cheng-Guruswami-Haeupler-Li, and a stronger direct upper bound$d_{I}({\mathcal C}) \leq 2(d_{H}({\mathcal C})-t)$under a weak condition, where$t\geq 1$is a positive integer determined by the generator matrix and$d_{H}({\mathcal C})$denotes the Hamming distance of${\mathcal C}$. A sufficient condition for a linear code attaining the strict half-Singleton bound is given. We prove that the code length of an optimal binary linear insdel code with respect to the (strict) half-Singleton bound is about twice its dimension and conjecture that optimal binary linear insdel codes have exact parameters$[{2k, k, 4}]$or$[{2k+1, k, 4}]$with respect to the half-Singleton bound or the strict half-Singleton bound, respectively. Moreover, interestingly explicit optimal linear insdel codes attaining the (strict) half-Singleton bound, with the code length being independent of the finite field size, are given.