Abstract | ||
---|---|---|
In this paper, we introduce t-revealing codes in the binary Hamming space Fn. Let C⊆Fn be a code and denote by It(C;x) the set of elements of C which are within (Hamming) distance t from a word x∈Fn. A code C is t-revealing if the majority voting on the coordinates of the words in It(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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.ic.2019.104455 | Information and Computation |
Keywords | DocType | Volume |
Levenshtein's sequence reconstruction problem,List decoding,Information retrieval,Associative memory,Majority voting on coordinates,Identifying codes | Journal | 268 |
ISSN | Citations | PageRank |
0890-5401 | 0 | 0.34 |
References | Authors | |
0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tero Laihonen | 1 | 363 | 39.39 |