A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

The Levenshtein’s Sequence Reconstruction Problem and the Length of the List




TekijätJunnila Ville, Laihonen Tero, Lehtilä Tuomo

KustantajaInstitute of Electrical and Electronics Engineers Inc.

Julkaisuvuosi2024

JournalIEEE Transactions on Information Theory

Tietokannassa oleva lehden nimiIEEE Transactions on Information Theory

Vuosikerta70

Numero2

Aloitussivu1050

Lopetussivu1066

eISSN1557-9654

DOIhttps://doi.org/10.1109/TIT.2023.3318354

Verkko-osoitehttps://ieeexplore.ieee.org/document/10261297

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/181481576


Tiivistelmä

In the paper, the Levenshtein’s sequence reconstruction problem is considered in the case where the transmitted words are chosen from an e -error-correcting code, at most t substitution errors occur in each of the N channels and the decoder outputs a list of length L . Previously, when t = e + ℓ and the transmitted word is long enough, the numbers of required channels were determined for L = 1, 2 and ℓ+1. Here we determine the exact number of channels in the cases L = 3,4,..., ℓ. This also provides the size of the largest intersection of L balls of radius t (with respect to substitutions) centered at the words with mutual Hamming distances at least 2 e + 1. Furthermore, with the aid of covering codes, we also consider the list sizes in the cases where the length n is rather small (improving previously known results). After that we study how much we can decrease the number of required channels when we use list-decoding codes. Finally, the majority algorithm is discussed for decoding in a probabilistic set-up; in particular, we show that the output word of the decoder can be verified to be the transmitted one with high probability.


Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 21:58