Capacity limits found for noisy unordered fragment channels
The Capacity of the Noisy Torn Paper Channel and the Noisy Shuffling Channel
Information Theory
Summary
Sending a message broken into scrambled pieces is tricky when each piece may also have errors. The authors studied models where message parts are both shuffled and have bit errors. They found exact limits on how much information can be reliably sent in such noisy, unordered fragment channels. This settles previous open questions about how well communication over these channels works.
What this means in practice
- •For distributed storage engineers: Determine precise storage and retrieval limits when data is stored as unordered, error-prone fragments.
- •For communication system designers: Calculate the maximum reliable data rate when transmitted messages are broken into shuffled pieces with noise.
A theory result. No direct application yet.
Authors
Junsheng Liu, Netanel Raviv
Abstract
The torn paper channel breaks a codeword into fragments and returns all fragments without their original order. The noisy torn paper channel additionally introduces bit substitution errors to each fragment. Recovering the message therefore requires accounting for both bit errors and uncertainty about the fragment order. We establish a capacity upper bound for the noisy torn paper channel that matches the achievable rate of Ravi, Vahid, and Shomorony and resolves their conjecture. Our results also determine the capacity of the noisy shuffling channel of Shomorony and Heckel, in which all fragments have the same length, and resolve their open question.