Repository logo
  • Log In
    Log in via Symplectic to deposit your publication(s).
Repository logo
  • About
  • Communities & Collections
  • Advanced Search
  • Statistics
  • Log In
    Log in via Symplectic to deposit your publication(s).
  1. Home
  2. Faculty of Engineering
  3. Faculty of Engineering
  4. Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels
 
  • Details
Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels
File(s)
1806.06218v2.pdf (938.66 KB)
Working paper
Author(s)
Cheraghchi, M
Ribeiro, J
Type
Working Paper
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$.
Date Issued
2018-12-31
URI
http://hdl.handle.net/10044/1/62938
Copyright Statement
© 2018 The Author(s).
Identifier
http://arxiv.org/abs/1806.06218v2
Subjects
cs.IT
math.IT
Notes
37 pages, 12 figures. Fixed some typos and reorganized parts of Section 5
About
Spiral Depositing with Spiral Publishing with Spiral Symplectic
Contact us
Open access team Report an issue
Other Services
Scholarly Communications Library Services
logo

Imperial College London

South Kensington Campus

London SW7 2AZ, UK

tel: +44 (0)20 7589 5111

Accessibility Modern slavery statement Cookie Policy

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback