Please use this identifier to cite or link to this item:
Title: A lower bound on the list-decodability of insdel codes
Authors: Liu, Shu
Tjuawinata, Ivan
Xing, Chaoping
Keywords: Science::Mathematics::Applied mathematics::Information theory
Engineering::Computer science and engineering::Data::Coding and information theory
Issue Date: 2023
Source: Liu, S., Tjuawinata, I. & Xing, C. (2023). A lower bound on the list-decodability of insdel codes. IEEE Transactions On Information Theory.
Project: 2021YFE109900 
Journal: IEEE Transactions on Information Theory 
Abstract: 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 and the alphabet size. 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 is not list-decodable with a given list size, then the list decoding radius is lower bounded by a bound involving the list size and Levenshtein distance. In other words, if the list decoding radius is less than this lower bound, the code must be list-decodable with the given list size. 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.
ISSN: 0018-9448
DOI: 10.1109/TIT.2023.3302862
Schools: School of Computer Science and Engineering 
Research Centres: Strategic Centre for Research in Privacy-Preserving Technologies & Systems (SCRIPTS)
Rights: © 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at:
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Final - A Lower Bound on the List-Decodability of Insdel Codes - R1.pdf636.19 kBAdobe PDFThumbnail

Page view(s)

Updated on Jun 23, 2024


Updated on Jun 23, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.