Communicating over the Torn-Paper Channel

2020/05/26 by Shomorony, Ilan, Vahid, Alireza
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2005.12895

Abstract

We consider the problem of communicating over a channel that randomly "tears" the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length n and pieces of length \rm Geometric(p_n), we characterize the capacity as C = e^-α, where α= lim_n→∞ p_n log n. Our results show that the case of \rm Geometric(p_n)-length fragments and the case of deterministic length-(1/p_n) fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.

Related

• Recovering a Message from an Incomplete Set of Noisy Fragments
• On the Capacity of the Carbon Copy onto Dirty Paper Channel
• Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels
• An Upper Bound on the Capacity of Vector Dirty Paper with Unknown Spin and Stretch
• On the Capacity of the Slotted Strongly Asynchronous Channel with a Bursty User