2022/11/12 by Shu Liu, Liu, Shu, Ivan Tjuawinata +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Coding theory and cryptography #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2211.06606
openalex publication_date 2022/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.