论文标题
INSDEL代码的列表可调节性的下限
A Lower Bound on the List-Decodability of Insdel Codes
论文作者
论文摘要
对于配备有指标，符号对度量或覆盖度量标准等指标的代码，约翰逊的限制保证了此类代码的列表可调节性。也就是说，约翰逊的界限提供了代码列表编码半径的下限，其相对最小距离$δ$，列表尺寸$ l $和字母大小$ q。$ q。$ $ q。$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ q。插入和删除错误的代码可调节性可确定性（我们称之为insdel代码），这是自然而然的问题。 Wachter-Zeh首先研究了这个问题，结果由Hayashi和Yasunaga修改了，该结果对Insdel代码的列表可调节性的下限进行了修改。 本文的主要目的是向更进一步解决上述开放问题。在这项工作中，我们为INSDEL代码的列表可调节性提供了新的下限。结果，我们表明，与约翰逊在其他紧密的指标下绑定的代码不同，Hayashi和Yasunaga给出的Insdel代码的列表可调节性的限制并不紧张。我们的主要想法是表明，如果具有给定Levenshtein距离$ D $的INSDEL代码不可用列表尺寸$ L $定为列表，则列表解码半径被涉及$ l $和$ d $的界限所限制。换句话说，如果列表解码半径小于此下限，则该代码必须列表用列表大小$ l $来定义。在论文的末尾，我们使用这种约束来为各种知名代码提供INSDEL列表可定义性，这尚未进行过广泛的研究。
For codes equipped with metrics such as Hamming metric, symbol pair metric or cover metric, the Johnson bound guarantees list-decodability of such codes. That is, the Johnson bound provides a lower bound on the list-decoding radius of a code in terms of its relative minimum distance $δ$, list size $L$ and the alphabet size $q.$ For study of list-decodability of codes with insertion and deletion errors (we call such codes insdel codes), it is natural to ask the open problem whether there is also a Johnson-type bound. The problem was first investigated by Wachter-Zeh and the result was amended by Hayashi and Yasunaga where a lower bound on the list-decodability for insdel codes was derived. The main purpose of this paper is to move a step further towards solving the above open problem. In this work, we provide a new lower bound for the list-decodability of an insdel code. As a consequence, we show that unlike the Johnson bound for codes under other metrics that is tight, the bound on list-decodability of insdel codes given by Hayashi and Yasunaga is not tight. Our main idea is to show that if an insdel code with a given Levenshtein distance $d$ is not list-decodable with list size $L$, then the list decoding radius is lower bounded by a bound involving $L$ and $d$. In other words, if the list decoding radius is less than this lower bound, the code must be list-decodable with list size $L$. At the end of the paper we use such bound to provide an insdel-list-decodability bound for various well-known codes, which has not been extensively studied before.
