A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On t-revealing codes in binary Hamming spaces
Tekijät: Laihonen Tero
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2019
Lehti: Information and Computation
Lehden akronyymi: INFORM COMPUT
Artikkelin numero: UNSP 104455
Vuosikerta: 268
Sivujen määrä: 11
ISSN: 0890-5401
eISSN: 1090-2651
DOI: https://doi.org/10.1016/j.ic.2019.104455
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/42496316
Tiivistelmä
In this paper, we introduce t-revealing codes in the binary Hamming space F-n. Let C subset of F-n be a code and denote by I-t (C; x) the set of elements of C which are within (Hamming) distance t from a word x is an element of F-n. A code C is t-revealing if the majority voting on the coordinates of the words in I-t (C; x) gives unambiguously x. These codes have applications, for instance, to the list decoding problem of the Levenshtein's channel model, where the decoder provides a list based on several different outputs of the channel with the same input, and to the information retrieval problem of the Yaakobi-Bruck model of associative memories. We give t-revealing codes which improve some of the key parameters for these applications compared to earlier code constructions. (C) 2019 Elsevier Inc. All rights reserved.
In this paper, we introduce t-revealing codes in the binary Hamming space F-n. Let C subset of F-n be a code and denote by I-t (C; x) the set of elements of C which are within (Hamming) distance t from a word x is an element of F-n. A code C is t-revealing if the majority voting on the coordinates of the words in I-t (C; x) gives unambiguously x. These codes have applications, for instance, to the list decoding problem of the Levenshtein's channel model, where the decoder provides a list based on several different outputs of the channel with the same input, and to the information retrieval problem of the Yaakobi-Bruck model of associative memories. We give t-revealing codes which improve some of the key parameters for these applications compared to earlier code constructions. (C) 2019 Elsevier Inc. All rights reserved.
Avainsanat:
Levenshtein's sequence reconstruction problem, List decoding, Majority voting on coordinates
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali