On t-revealing codes in binary Hamming spaces

: Laihonen Tero

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2019

Information and Computation

: INFORM COMPUT

: UNSP 104455

: 268

: 11

: 0890-5401

: 1090-2651

DOI: https://doi.org/10.1016/j.ic.2019.104455

: https://research.utu.fi/converis/portal/detail/Publication/42496316

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.

Levenshtein's sequence reconstruction problem, List decoding, Majority voting on coordinates

CoordinatewiseIRFin.pdf