The Capacity of a Family of Sticky Channels

Abstract

We determine the capacity of a family of $q$-ary sticky-insertion channels. Fix $q\ge 2$ and $d\ge 1$, and let $\lambda$ be the unique positive solution of ${\lambda }^d=(q-1)({\lambda }^{d-1}+\cdots +\lambda +1)$. We prove that, for every repetition law supported on $1+d{\mathbb{Z}}_{\ge 0}$ and satisfying a coefficientwise-domination criterion with domination constant $\gamma \ge {\lambda }^{-d}$, the Shannon capacity equals the zero-error capacity, both being ${\log }_2\lambda$ bits per symbol. We also exhibit explicit repetition laws satisfying these conditions, one of which is given by the weighted Fuss--Catalan numbers. To the best of our knowledge, these are the first known cases of nontrivial repeat channels whose Shannon capacity has been determined exactly.