Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels

Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels. Cheraghchi, M. & Ribeiro, J. IEEE Transactions on Information Theory, 65(11):6950–6974, 2019. Preliminary version in Proceedings of Allerton 2018.

Link

Paper doi abstract bibtex

We study natural examples of binary channels with synchronization errors. These include the duplication channel, which independently outputs a given bit once or twice, and geometric channels that repeat a given bit according to a geometric rule, with or without the possibility of bit deletion. We apply the general framework of Cheraghchi (STOC 2018) to obtain sharp analytical upper bounds on the capacity of these channels. Previously, upper bounds were known via numerical computations involving the computation of finite approximations of the channels by a computer and then using the obtained numerical results to upper bound the actual capacity. While leading to sharp numerical results, further progress on the full understanding of the channel capacity inherently remains elusive using such methods. Our results can be regarded as a major step towards a complete understanding of the capacity curves. Quantitatively, our upper bounds sharply approach, and in some cases surpass, the bounds that were previously only known by purely numerical methods. Among our results, we notably give a completely analytical proof that, when the number of repetitions per bit is geometric (supported on $\{0,1,2,ṡ\}$) with mean growing to infinity, the channel capacity remains substantially bounded away from $1$.

@ARTICLE{ref:CR19:sticky,
  author =	 {Mahdi Cheraghchi and Jo\~{a}o Ribeiro},
  title =	 {Sharp Analytical Capacity Upper Bounds for Sticky
                  and Related Channels},
  year =	 2019,
  journal =	 {IEEE Transactions on Information Theory},
  volume =	 65,
  number =	 11,
  pages =	 {6950--6974},
  note =	 {Preliminary version in {Proceedings of Allerton
                  2018}.},
  doi =		 {10.1109/TIT.2019.2920375},
  url_Link =	 {https://ieeexplore.ieee.org/document/8727914},
  url_Paper =	 {https://arxiv.org/abs/1806.06218},
  abstract =	 {We study natural examples of binary channels with
                  synchronization errors.  These include the
                  duplication channel, which independently outputs a
                  given bit once or twice, and geometric channels that
                  repeat a given bit according to a geometric rule,
                  with or without the possibility of bit deletion. We
                  apply the general framework of Cheraghchi (STOC
                  2018) to obtain sharp analytical upper bounds on the
                  capacity of these channels.  Previously, upper
                  bounds were known via numerical computations
                  involving the computation of finite approximations
                  of the channels by a computer and then using the
                  obtained numerical results to upper bound the actual
                  capacity.  While leading to sharp numerical results,
                  further progress on the full understanding of the
                  channel capacity inherently remains elusive using
                  such methods. Our results can be regarded as a major
                  step towards a complete understanding of the
                  capacity curves.  Quantitatively, our upper bounds
                  sharply approach, and in some cases surpass, the
                  bounds that were previously only known by purely
                  numerical methods. Among our results, we notably
                  give a completely analytical proof that, when the
                  number of repetitions per bit is geometric
                  (supported on $\{0,1,2,\dots\}$) with mean growing
                  to infinity, the channel capacity remains
                  substantially bounded away from $1$.  }
}

Downloads: 0