TY - GEN
T1 - Capacity of the Torn Paper Channel with Lost Pieces
AU - Ravi, Aditya Narayan
AU - Vahid, Alireza
AU - Shomorony, Ilan
N1 - Funding Information:
ACKNOWLEDGEMENTS The research of A. N. Ravi and I. Shomorony was supported in part by NSF grant CCF-2007597. The research of A. Vahid was supported in part by NSF grant ECCS-2030285.
Publisher Copyright:
© 2021 IEEE.
PY - 2021/7/12
Y1 - 2021/7/12
N2 - 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'.
AB - 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'.
UR - http://www.scopus.com/inward/record.url?scp=85115049239&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115049239&partnerID=8YFLogxK
U2 - 10.1109/ISIT45174.2021.9518272
DO - 10.1109/ISIT45174.2021.9518272
M3 - Conference contribution
AN - SCOPUS:85115049239
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1937
EP - 1942
BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021
Y2 - 12 July 2021 through 20 July 2021
ER -