UNI-MB - logo
UMNIK - logo
 
E-viri
Recenzirano Odprti dostop
  • Bounds on the Zero-Error Li...
    Bhandari, Siddharth; Radhakrishnan, Jaikumar

    IEEE transactions on information theory, 2022-Jan., 2022-1-00, Letnik: 68, Številka: 1
    Journal Article

    Let <inline-formula> <tex-math notation="LaTeX">\mathcal {X}= \{x_{1},x_{2},\ldots, x_{q}\} </tex-math></inline-formula> and let <inline-formula> <tex-math notation="LaTeX">n(m,q,\ell) </tex-math></inline-formula> be the smallest <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> for which there is a code <inline-formula> <tex-math notation="LaTeX">C \subseteq \mathcal {X} ^{n} </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">m </tex-math></inline-formula> elements such that for every list <inline-formula> <tex-math notation="LaTeX">w_{1}, w_{2}, \ldots, w_{\ell +1} </tex-math></inline-formula> of distinct codewords from <inline-formula> <tex-math notation="LaTeX">C </tex-math></inline-formula>, there is a coordinate <inline-formula> <tex-math notation="LaTeX">j \in n </tex-math></inline-formula> such that <inline-formula> <tex-math notation="LaTeX">\{w_{1}j, w_{2}j, \ldots, w_{\ell +1}j\} = \mathcal {X} </tex-math></inline-formula>. We show that there is a constant <inline-formula> <tex-math notation="LaTeX">A>0 </tex-math></inline-formula> such that for <inline-formula> <tex-math notation="LaTeX">\epsilon < 1/5 </tex-math></inline-formula>, for all large <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula> and large enough <inline-formula> <tex-math notation="LaTeX">m </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">m>q^{5} </tex-math></inline-formula>), we have <inline-formula> <tex-math notation="LaTeX">n(m,q, \lceil \epsilon q\ln {q}\rceil) \geq \exp {(Aq^{1-5\epsilon })}\log _{2}{m} </tex-math></inline-formula>. This bound has consequences for the zero-error list-decoding capacity of the <inline-formula> <tex-math notation="LaTeX">q/(q-1) </tex-math></inline-formula> channel studied by Elias (1988). Our result implies that for <inline-formula> <tex-math notation="LaTeX">A </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">\epsilon </tex-math></inline-formula> as above, the zero-error list-decoding capacity of the <inline-formula> <tex-math notation="LaTeX">q/(q-1) </tex-math></inline-formula> channel with list-size <inline-formula> <tex-math notation="LaTeX">\epsilon q\ln {q} </tex-math></inline-formula> is at most <inline-formula> <tex-math notation="LaTeX">\exp (-Aq^{1-5\epsilon }) </tex-math></inline-formula>, that is, it falls exponentially as <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula> increases. This confirms a conjecture of Chakraborty et al. (2006).