Search

The Levenshtein’s channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most t errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code $C \subseteq \mathbb{F}_2^n$ has error-correcting capability e, we write t = e + l, (l ≥ 1). In this paper, we provide new bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound l + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound l + 1 is the best possible.

In this paper, we introduce t-revealing codes in the binary Hamming space Fn. Let C ⊆ Fn be a code and denote by I t {C; x) the set of codewords 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 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, namely, the length of the output list L of the decoder and the maximal number of input clues m needed for information retrieval.