| Paper ID | D4-S7-T2.1 |
| Paper Title |
Capacity of the Torn Paper Channel with Lost Pieces |
| Authors |
Aditya Narayan Ravi, University of Illinois Urbana-Champaign, United States; Alireza Vahid, University of Colorado, Denver, United States; Ilan Shomorony, University of Illinois Urbana-Champaign, United States |
| Session |
D4-S7-T2: Information Theory for Biology |
| Chaired Session: |
Friday, 16 July, 00:00 - 00:20 |
| Engagement Session: |
Friday, 16 July, 00:20 - 00:40 |
| 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”.
|
