Bounds on the Zero-Error List-Decoding Capacity of the q/(q – 1) Channel

DOI10.1109/TIT.2021.3111455MaRDI QIDQ5030282zbMATH OpenOpenAlexFDO

Authors Siddharth Bhandari, Jaikumar Radhakrishnan

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.08396

zbMATH Keywords

boundsconjecture of Chakrabortyzero-error list-decoding capacity

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Channel models (including quantum) in information and communication theory (94A40) Decoding (94B35)

Abstract: We consider the problem of determining the zero-error list-decoding capacity of the $q/(q-1)$ channel studied by Elias (1988). The $q/(q-1)$ channel has input and output alphabet consisting of $q$ symbols, say, $Q=x_1,x_2,ldots,x_q$; when the channel receives an input $xinQ$, it outputs a symbol other than $x$ itself. Let $n(m,q,ell)$ be the smallest $n$ for which there is a code $Csubseteq{Q}^n$ of $m$ elements such that for every list $w_1,w_2,ldots,w_{ell+1}$ of distinct code-words from $C$, there is a coordinate $jin[n]$ that satisfies $w_1[j],w_2[j],ldots,w_{ell+1}[j]=Q$. We show that for $epsilon<1/6$, for all large $q$ and large enough $m$, $n(m,q,epsilonqlnq)geqOmega(exp(q^{1-6epsilon}/8)lo{g}_{2}m)$. The lower bound obtained by Fredman and Koml'{o}s (1984) for perfect hashing implies that $n(m,q,q-1)=exp(Omega(q))lo{g}_{2}m$; similarly, the lower bound obtained by K"{o}rner (1986) for nearly-perfect hashing implies that $n(m,q,q)=exp(Omega(q))lo{g}_{2}m$. These results show that the zero-error list-decoding capacity of the $q/(q-1)$ channel with lists of size at most $q$ is exponentially small. Extending these bounds, Chakraborty et al. (2006) showed that the capacity remains exponentially small even if the list size is allowed to be as large as $1.58q$. Our result implies that the zero-error list-decoding capacity of the $q/(q-1)$ channel with list size $epsilonq$ for $epsilon<1/6$ is $exp(Omega(q^{1-6epsilon}))$. This resolves the conjecture raised by Chakraborty et al. (2006) about the zero-error list-decoding capcity of the $q/(q-1)$ channel at larger list sizes.

Cited in

(2)

• Erasure, list, and detection zero-error capacities for low noise and a relation to identification
• An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel

This page was built for publication: Bounds on the Zero-Error List-Decoding Capacity of the q/(q – 1) Channel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030282)