Strict Half-Singleton Bound, Strict Direct Upper Bound for Linear Insertion-Deletion Codes and Optimal Codes
Strict Half-Singleton Bound, Strict Direct Upper Bound for Linear Insertion-Deletion Codes and Optimal Codes
复制标题
线性插入删除码和最优码的严格半单例界、严格直接上界
DOI：
10.1109/tit.2023.3234967
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Xiaoqiang Wang
中科院分区：
文献类型：
--
作者：
Qi;Dabin Zheng;Haoyuan Chen;Xiaoqiang Wang
设<inline-formula> < text -math notation="LaTeX"> ${\mathcal C}$ </ text -math></inline-formula>为<inline-formula> < text -math notation="LaTeX"> $[n, k]$ </ text -math></inline-formula> <inline-formula> < text -math notation="LaTeX"> ${\mathbb F}_{q}$ </ text -math></inline-formula>。令<inline-formula> < text -math notation="LaTeX"> $d_{I}({\mathcal C})$ </ text -math></inline-formula>表示其插入-删除（简称indel）距离，表征了<inline-formula> < text -math notation="LaTeX"> ${\mathcal C}$ </ text -math></inline-formula>的indel纠错能力。确定线性码的内嵌距离是一个非常具有挑战性的问题。本文提出了一个严格的半单例上界<inline-formula> < text -math表记法="LaTeX"> $d_{I}({\mathcal C}) \leq 2(n-2k+1)$ </ text -math></inline-formula>，如果<inline-formula> < text -math表记法="LaTeX"> ${\mathcal C}$ </ text -math></inline-formula>不包含全为1的码字，它推广了由chengu - guruswami - haeupler - li导出的线性码的内模距离的半单例界。在弱条件下，有一个更强的直接上界<inline-formula> < text -math notation="LaTeX"> $d_{I}({\mathcal C}) \leq 2(d_{H}({\mathcal C})-t)$ </ text -math></inline-formula>，其中<inline-formula> < text -math notation="LaTeX"> $t\geq 1$ </ text -math></inline-formula>是由生成器矩阵确定的正整数，<inline-formula> < text -math notation="LaTeX"> $d_{H}({\mathcal C})$ </ text -math></inline-formula>表示<inline-formula> < text -math notation="LaTeX"> ${\mathcal C}$ </ text -math></inline-formula>的汉明距离。给出了线性码达到严格半单胞界的一个充分条件。证明了最优二进制线性嵌套码相对于（严格）半单胞界的码长约为其维数的两倍，并推测最优二进制线性嵌套码具有精确参数<inline-formula> < text -math notation="LaTeX"> $[{2k, k, 4}]$ </ text -math></inline-formula>或<inline-formula> < text -math notation="LaTeX"> $[{2k+1, k, 4}]$ </ text -math></inline-formula>相对于半单胞界或严格半单胞界。分别。此外，有趣的是，给出了当码长与有限域大小无关时，达到（严格）半单态界的显式最优线性内码。
Let <inline-formula> <tex-math notation="LaTeX">${\mathcal C}$ </tex-math></inline-formula> be an <inline-formula> <tex-math notation="LaTeX">$[n, k]$ </tex-math></inline-formula> linear code over the finite field <inline-formula> <tex-math notation="LaTeX">${\mathbb F}_{q}$ </tex-math></inline-formula>. Let <inline-formula> <tex-math notation="LaTeX">$d_{I}({\mathcal C})$ </tex-math></inline-formula> denote its insertion-deletion (insdel for short) distance, which characterizes the insdel error-correcting capability of <inline-formula> <tex-math notation="LaTeX">${\mathcal C}$ </tex-math></inline-formula>. To determine the insdel distances of linear codes is a very challenging problem. In this paper we propose a strict half-Singleton upper bound <inline-formula> <tex-math notation="LaTeX">$d_{I}({\mathcal C}) \leq 2(n-2k+1)$ </tex-math></inline-formula> if <inline-formula> <tex-math notation="LaTeX">${\mathcal C}$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$d_{I}({\mathcal C}) \leq 2(d_{H}({\mathcal C})-t)$ </tex-math></inline-formula> under a weak condition, where <inline-formula> <tex-math notation="LaTeX">$t\geq 1$ </tex-math></inline-formula> is a positive integer determined by the generator matrix and <inline-formula> <tex-math notation="LaTeX">$d_{H}({\mathcal C})$ </tex-math></inline-formula> denotes the Hamming distance of <inline-formula> <tex-math notation="LaTeX">${\mathcal C}$ </tex-math></inline-formula>. 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 <inline-formula> <tex-math notation="LaTeX">$[{2k, k, 4}]$ </tex-math></inline-formula> or <inline-formula> <tex-math notation="LaTeX">$[{2k+1, k, 4}]$ </tex-math></inline-formula> 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.
DOI：
10.4230/lipics.icalp.2018.76
发表时间：
2018-02
期刊：
ArXiv
影响因子：
--
作者：
Bernhard Haeupler;Amirbehshad Shahrasbi;M. Sudan
通讯作者：
Bernhard Haeupler;Amirbehshad Shahrasbi;M. Sudan
DOI：
10.1109/itw.2017.8278045
发表时间：
2017-11
期刊：
2017 IEEE Information Theory Workshop (ITW)
影响因子：
--
作者：
Yeow Meng Chee;Han Mao Kiah;A. Vardy;Van Khu Vu;Eitan Yaakobi
通讯作者：
Yeow Meng Chee;Han Mao Kiah;A. Vardy;Van Khu Vu;Eitan Yaakobi
最佳文档交换以及插入和删除的新代码
DOI：
10.1109/focs.2019.00029
发表时间：
2019
期刊：
IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Haeupler, Bernhard
通讯作者：
Haeupler, Bernhard