Efficiently list-decodable insertion and deletion codes via concatenation

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deleti...

Full description

Saved in:

Bibliographic Details
Main Authors:	Liu, Shu, Tjuawinata, Ivan, Xing, Chaoping
Other Authors:	Nanyang Technopreneurship Center
Format:	Article
Language:	English
Published:	2022
Subjects:	Engineering::Computer science and engineering Codes Error Correction
Online Access:	https://hdl.handle.net/10356/157154
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Nanyang Technological University
Language:	English

id	sg-ntu-dr.10356-157154
record_format	dspace
spelling	sg-ntu-dr.10356-1571542022-05-14T20:11:48Z Efficiently list-decodable insertion and deletion codes via concatenation Liu, Shu Tjuawinata, Ivan Xing, Chaoping Nanyang Technopreneurship Center Strategic Centre for Research in Privacy-Preserving Technologies & Systems (SCRIPTS) Engineering::Computer science and engineering Codes Error Correction In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes. Info-communications Media Development Authority (IMDA) National Research Foundation (NRF) Submitted/Accepted version The work of Shu Liu was supported in part by the National Natural Science Foundation of China under Grant 11901077, Grant 2019YFB1803102, and Grant 2020YFB1806805; in part by the National Key Research and Development Program of China under Contract IFN2020203; and in part by the Fundamental Research Funds for the Central Universities of China under Grant ZYGX2018KYQD216. The work of Ivan Tjuawinata was supported by the National Research Foundation, Singapore, under its Strategic Capability Research Centres Funding Initiative. The work of Chaoping Xing was supported in part by the National Natural Science Foundation of China under Grant 12031011 and in part by the National Key Research and Development Project under Grant 2020YFA0712300. 2022-05-09T05:56:49Z 2022-05-09T05:56:49Z 2021 Journal Article Liu, S., Tjuawinata, I. & Xing, C. (2021). Efficiently list-decodable insertion and deletion codes via concatenation. IEEE Transactions On Information Theory, 67(9), 5778-5790. https://dx.doi.org/10.1109/TIT.2021.3096154 0018-9448 https://hdl.handle.net/10356/157154 10.1109/TIT.2021.3096154 2-s2.0-85113964964 9 67 5778 5790 en IEEE Transactions on Information Theory © 2021 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: https://doi.org/10.1109/TIT.2021.3096154. application/pdf
institution	Nanyang Technological University
building	NTU Library
continent	Asia
country	Singapore Singapore
content_provider	NTU Library
collection	DR-NTU
language	English
topic	Engineering::Computer science and engineering Codes Error Correction
spellingShingle	Engineering::Computer science and engineering Codes Error Correction Liu, Shu Tjuawinata, Ivan Xing, Chaoping Efficiently list-decodable insertion and deletion codes via concatenation
description	In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes.
author2	Nanyang Technopreneurship Center
author_facet	Nanyang Technopreneurship Center Liu, Shu Tjuawinata, Ivan Xing, Chaoping
format	Article
author	Liu, Shu Tjuawinata, Ivan Xing, Chaoping
author_sort	Liu, Shu
title	Efficiently list-decodable insertion and deletion codes via concatenation
title_short	Efficiently list-decodable insertion and deletion codes via concatenation
title_full	Efficiently list-decodable insertion and deletion codes via concatenation
title_fullStr	Efficiently list-decodable insertion and deletion codes via concatenation
title_full_unstemmed	Efficiently list-decodable insertion and deletion codes via concatenation
title_sort	efficiently list-decodable insertion and deletion codes via concatenation
publishDate	2022
url	https://hdl.handle.net/10356/157154
_version_	1734310107360002048

Efficiently list-decodable insertion and deletion codes via concatenation

Similar Items