Capacity Achieving Torn Paper Codes
Abstract
In the torn paper channel, a codeword is cut at random locations, and the resulting error-free fragments are delivered to the decoder as an unordered multiset. Although the capacity of this channel can be achieved using random code, decoding such codes generally requires exponential time. The interleaved-pilot construction of Shomorony and Vahid embeds a De Bruijn sequence among the symbols of a shifted erasure code and aligns only fragments that are sufficiently long through global statistical uniqueness. A subsequent local-alignment scheme by Liu and Raviv employs run-length-limited constraints and exclusive all-zero markers to identify pilot positions from local structure, substantially reducing the minimum fragment length that can be aligned. We further improve the method of Liu and Raviv by replacing its fixed pilot sequence with a multilevel successive local alignment and pilot-recycling procedure. In Liu and Raviv, the pilot sequence is chosen once and must simultaneously balance the length of the pilot sequence against the ability to align short fragments. Our construction removes this limitation by reusing pilot sequences across successive decoding levels. A pilot sequence with an independent random linear code is first used to align and decode the longest fragments. The information recovered at this stage is then recycled as a larger pilot sequence for the next stage.This process is repeated over multiple levels, so that progressively shorter fragments are recovered while the length of the pilot sequence remains small. Our construction depends on choosing a series of random linear codes, and we show that for any ε>0, there exists a choice of such codes which attains rate of at least ε below the capacity, with high probability as the block length goes to infinity. Therefore, our construction achieves the capacity of the torn-paper channel.
Related
- The Capacity of the Noisy Torn Paper Channel and the Noisy Shuffling Channel
- Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
- Bounds and Limitations on Codes Achieving List Recovery Capacity
- Efficient capacity-achieving entanglement generation with application to pure-loss Bosonic channels
- On the Evolution of the Capacity-Achieving Input Support for the Amplitude-Constrained AWGN Channel
BibTeX
@misc{liu2026capacity,
title = {{Capacity Achieving Torn Paper Codes}},
author = {Junsheng Liu and Netanel Raviv},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00522},
eprint = {2609.00522},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00522},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Capacity Achieving Torn Paper Codes
AU - Junsheng Liu
AU - Netanel Raviv
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.00522
UR - https://arxiv.org/abs/2609.00522
AB - In the torn paper channel, a codeword is cut at random locations, and the resulting error-free fragments are delivered to the decoder as an unordered multiset. Although the capacity of this channel can be achieved using random code, decoding such codes generally requires exponential time. The interleaved-pilot construction of Shomorony and Vahid embeds a De Bruijn sequence among the symbols of a shifted erasure code and aligns only fragments that are sufficiently long through global statistical uniqueness. A subsequent local-alignment scheme by Liu and Raviv employs run-length-limited constraints and exclusive all-zero markers to identify pilot positions from local structure, substantially reducing the minimum fragment length that can be aligned. We further improve the method of Liu and Raviv by replacing its fixed pilot sequence with a multilevel successive local alignment and pilot-recycling procedure. In Liu and Raviv, the pilot sequence is chosen once and must simultaneously balance the length of the pilot sequence against the ability to align short fragments. Our construction removes this limitation by reusing pilot sequences across successive decoding levels. A pilot sequence with an independent random linear code is first used to align and decode the longest fragments. The information recovered at this stage is then recycled as a larger pilot sequence for the next stage.This process is repeated over multiple levels, so that progressively shorter fragments are recovered while the length of the pilot sequence remains small. Our construction depends on choosing a series of random linear codes, and we show that for any ε>0, there exists a choice of such codes which attains rate of at least ε below the capacity, with high probability as the block length goes to infinity. Therefore, our construction achieves the capacity of the torn-paper channel.
ER -