Improved Torn Paper Coding via Local Alignment

Technical Summary: Improved Torn Paper Coding via Local Alignment

Problem Definition
The paper addresses the "torn paper channel," a communication model where a transmitted codeword is fragmented at random locations into pieces that arrive at the decoder in an unordered manner. The primary challenge is global alignment: determining the original position of each fragment to reconstruct the codeword. This model is motivated by physical data storage and transmission systems prone to fragmentation, such as DNA storage (where molecules suffer random strand breaks) and forensic 3D fingerprinting (where data embedded in physical structures may be shattered).

A critical limitation in prior work, specifically the interleaved-pilot scheme by Shomorony and Vahid [12], is the reliance on global statistical uniqueness to identify fragment positions. In that scheme, a De Bruijn sequence serves as a pilot, but to distinguish pilot bits from data bits with high probability, fragments must be sufficiently long (specifically, exceeding a threshold of roughly $(2+\delta)m \log n$). Fragments shorter than this threshold are discarded and treated as erasures, significantly reducing the achievable transmission rate below the channel capacity.

Methodology: Local Alignment
The authors propose a novel coding scheme that shifts the alignment paradigm from global statistics to local structural patterns. The core innovation is the use of Run-Length Limited (RLL) constraints to create a "local alignment" mechanism that allows the decoder to identify fragment positions using much shorter fragments.

The encoding process involves three main components:

1. RLL Constraints: The information is encoded using an erasure code ($C_{er}$) that is further constrained by an RLL$(0, k-1)$ block code. This ensures that no sequence of $k$ consecutive zeros appears in the data portion of the codeword.
2. Modified Pilot Sequence: A De Bruijn sequence is modified to include specific "markers"—deterministic runs of $\beta$ consecutive zeros. These markers are embedded at fixed intervals within the pilot sequence. Crucially, the RLL constraint on the data ensures that such long runs of zeros cannot occur in the information bits, making the markers unique and locally identifiable.
3. Interleaving: The modified pilot sequence is interleaved with codewords from the RLL-constrained erasure code.

Decoding Algorithm
The decoding process proceeds in three stages:

• Local Alignment: The decoder examines fragments of length at least $(1+\delta)m \log n$. By de-interleaving the fragment, it identifies the subsequence containing the unique $\beta$-length zero runs (the markers). This allows the decoder to distinguish pilot bits from data bits within the fragment, even if the fragment is too short to contain a globally unique window of the De Bruijn sequence.
• Global Alignment: Once the pilot bits are isolated, the decoder extracts the De Bruijn subsequence. Since the De Bruijn sequence has the property that every subsequence of a certain length is unique, the decoder can determine the absolute global position of the fragment.
• Erasure Decoding: After aligning the fragments, the missing positions (from discarded short fragments or those that failed alignment) are treated as erasures. A standard erasure decoder (using Gaussian elimination on a random binary linear code) recovers the original message.

Key Contributions and Results

1. Provable Rate Increase: The proposed local alignment strategy effectively halves the minimum required fragment length compared to the global alignment approach in [12]. By utilizing fragments that were previously discarded, the scheme achieves a strictly higher achievable rate.
2. Theoretical Rate: The authors derive an achievable rate of approximately $(1 - 1/m)(m\alpha + 1)e^{-m\alpha}$, where $\alpha$ is the channel parameter ($\lim_{n\to\infty} p_n \log n$) and $m$ is an optimization parameter. Numerical optimization shows this rate significantly outperforms the rates of [12] and [8] across various values of $\alpha$, approaching the channel capacity $e^{-\alpha}$ more closely.
3. Extension to Lost Pieces (TPC-LP): The framework is extended to the Torn Paper Channel with Lost Pieces (TPC-LP), where fragments are independently deleted with a length-dependent probability. The authors show that for a "hard-threshold" deletion regime (where all fragments below a logarithmic length are deleted), the proposed scheme achieves an arbitrarily small additive gap to the TPC-LP capacity as the threshold parameter increases.
4. Vanishing Error Probability: The paper provides rigorous proofs demonstrating that the decoding error probability vanishes as the codeword length $n$ approaches infinity, addressing a gap in previous heuristic designs that lacked such guarantees.

Significance
The paper claims that its significance lies in bridging the gap between theoretical channel capacity and practical achievable rates in fragmented channels. By replacing the requirement for long, globally unique fragments with a local structural marker, the scheme extracts information from a much larger fraction of the channel output. This results in a provable improvement in transmission rates for DNA storage and similar physical fragmentation scenarios, while maintaining the rigorous guarantee of vanishing error probability. The work also establishes that local alignment strategies are robust to length-dependent fragment deletions, making them suitable for generalized models of physical data loss.