The Capacity of a Family of Sticky Channels

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.