A1 Refereed original research article in a scientific journal
On Unique Error Patterns in the Levenshtein’s Sequence Reconstruction Model
Authors: Junnila, Ville; Laihonen, Tero; Lehtilä, Tuomo
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Publication year: 2025
Journal: IEEE Transactions on Information Theory
Journal name in source: IEEE Transactions on Information Theory
ISSN: 0018-9448
eISSN: 1557-9654
DOI: https://doi.org/10.1109/TIT.2025.3568068
Web address : https://doi.org/10.1109/tit.2025.3568068
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/498433789
In the Levenshtein’s sequence reconstruction problem a codeword is transmitted through N channels and in each channel a set of errors is introduced to the transmitted word. In previous works, the restriction that each channel provides a unique output word has been essential. In this work, we assume only that each channel introduces a unique set of errors to the transmitted word and hence, some output words can also be identical. As we will discuss, this interpretation is both natural and useful for deletion and insertion errors. We give properties, techniques and (optimal) results for this situation. Quaternary alphabets are relevant due to applications related to DNA-memories. Hence, we introduce an efficient Las Vegas style decoding algorithm for simultaneous insertion, deletion and substitution errors in q-ary Hamming spaces for q ≥ 4.
Downloadable publication This is an electronic reprint of the original article. |  |
Funding information in the publication:
The authors were funded in part by the Research Council of Finland grants 338797 and 358718.
