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

DOI10.1109/TIT.2021.3111455zbMATH Open1489.94172arXiv1802.08396OpenAlexW3199899104MaRDI QIDQ5030282FDOQ5030282

Authors: Siddharth Bhandari, Jaikumar Radhakrishnan 

Publication date: 17 February 2022

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

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.

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)

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)