The Capacity of the Noisy Torn Paper Channel and the Noisy Shuffling Channel

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.