List Decoding of Insertions and Deletions

被引:20
作者
Wachter-Zeh, Antonia [1 ]
机构
[1] Tech Univ Munich, Inst Commun Engn, D-80333 Munich, Germany
关键词
Insertions; deletions; Levenshtein metric; list decoding; Varshamov-Tenengolts (VT) codes; CODES; BOUNDS; RECONSTRUCTION;
D O I
10.1109/TIT.2017.2777471
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov-Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions.
引用
收藏
页码:6297 / 6304
页数:8
相关论文
共 50 条
[31]   Optimal Interactive Coding for Insertions, Deletions, and Substitutions [J].
Sherstov, Alexander A. ;
Wu, Pei .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (10) :5971-6000
[32]   IPRO plus /-: Computational Protein Design Tool Allowing for Insertions and Deletions [J].
Chowdhury, Ratul ;
Grisewood, Matthew J. ;
Boorla, Veda Sheersh ;
Yan, Qiang ;
Pfleger, Brian F. ;
Maranas, Costas D. .
STRUCTURE, 2020, 28 (12) :1344-+
[33]   Improved bounds for codes correcting insertions and deletions [J].
Yasunaga, Kenji .
DESIGNS CODES AND CRYPTOGRAPHY, 2024, 92 (05) :1267-1278
[34]   Improved bounds for codes correcting insertions and deletions [J].
Kenji Yasunaga .
Designs, Codes and Cryptography, 2024, 92 :1267-1278
[35]   On Mismatched List Decoding [J].
Somekh-Baruch, Anelia .
2015 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2015, :526-530
[36]   Generalized List Decoding [J].
Zhang, Yihan ;
Budkuley, Amitalok J. ;
Jaggi, Sidharth .
2020 INFORMATION THEORY AND APPLICATIONS WORKSHOP (ITA), 2020,
[37]   Secure list decoding [J].
Hayashi, Masahito .
2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2019, :2149-2153
[38]   A Lower Bound on List Size for List Decoding [J].
Guruswami, Venkatesan ;
Vadhan, Salil .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (11) :5681-5688
[39]   Clustering in the Boolean Hypercube in a List Decoding Regime [J].
Dinur, Irit ;
Goldenberg, Elazar .
AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2013, 7965 :413-424
[40]   List Decoding of Arikan's PAC Codes [J].
Yao, Hanwen ;
Fazeli, Arman ;
Vardy, Alexander .
ENTROPY, 2021, 23 (07)