1. Communicating over the Torn-Paper Channel
- Author
-
Alireza Vahid and Ilan Shomorony
- Subjects
FOS: Computer and information sciences ,0301 basic medicine ,Computer science ,Computer Science - Information Theory ,Information Theory (cs.IT) ,Block (permutation group theory) ,020206 networking & telecommunications ,02 engineering and technology ,Combinatorics ,03 medical and health sciences ,030104 developmental biology ,Channel (programming) ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science::Information Theory ,Communication channel - 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^{-\alpha}$, where $\alpha = \lim_{n\to\infty} 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.
- Published
- 2020