1. Capacity of the Torn Paper Channel with Lost Pieces
- Author
-
Aditya Narayan Ravi, Alireza Vahid, and Ilan Shomorony
- Subjects
Combinatorics ,Capacity planning ,Fragment (logic) ,Channel (programming) ,Binary number ,Length distribution ,Nuclear Experiment ,Information theory ,Computer Science::Information Theory ,Block (data storage) ,Mathematics - Abstract
We study the problem of transmitting a message over a channel that randomly breaks the message block into small fragments, deletes a subset of them, and shuffles the remaining fragments. We characterize the capacity of the binary torn-paper channel under arbitrary fragment length distribution and fragment deletion probabilities. We show that, for a message with block length $n$ , discarding fragments shorter than $\log(n)$ does not affect the achievable rates, and that the capacity is given by a simple closed-form expression that can be understood as “coverage minus reordering-cost”.
- Published
- 2021