PaperlayerView exact revision on arXiv

Source-linked AI summary

Capacity Achieving Torn Paper Codes

Junsheng Liu, Netanel Raviv

arXiv:2609.00522v1cs.IT

TL;DR

The torn-paper channel delivers intact fragments without their original order, creating a reconstruction problem that combines error correction with fragment alignment. This paper introduces multilevel successive local alignment with pilot recycling, recovering progressively shorter fragments and achieving the channel capacity with high probability.

  • Problem

    The torn-paper channel requires decoding an unordered multiset of error-free fragments while recovering their original positions, and motivates coding methods for physically fragmented storage and identification systems.

  • Method

    A multilevel pilot-recycling scheme successively aligns and decodes fragments, reusing recovered information as additional pilot symbols for later levels.

  • Results

    The construction has vanishing total decoding error probability with high probability and achieves the torn-paper-channel capacity.

  • Takeaways & Limitations

    Pilot recycling enables recovery of progressively shorter fragments while retaining a small initial pilot sequence, supporting capacity-achieving decoding for the torn-paper channel.

Abstract

from arXiv · show

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~$\varepsilon>0$, there exists a choice of such codes which attains rate of at least~$\varepsilon$ below the capacity, with high probability as the block length goes to infinity. Therefore, our construction achieves the capacity of the torn-paper channel.

I. INTRODUCTION

The torn paper channel preserves fragment symbols but destroys their original order, requiring the decoder to reconstruct both positions and content. This work introduces successive local alignment with pilot recycling to overcome efficiency limitations of prior structured schemes and achieve capacity.

  • I. INTRODUCTION: Random breaks produce an unordered multiset of error-free fragments, so decoding must recover both fragment locations and the original message.The channel does not alter or delete bits, but positional context is lost.
  • I. INTRODUCTION: DNA storage and 3D-printing identification motivate the channel model because physical fragmentation can remove positional context without corrupting embedded symbols.
  • I. INTRODUCTION: The channel capacity is e^−α, and random coding attains it, but decoding random codes generally has exponential complexity.
  • I. INTRODUCTION: Prior structured constructions improve decoding practicality but remain strictly below capacity, motivating further improvements in fragment alignment.
  • I. INTRODUCTION: Successive local alignment recycles decoded symbols as new pilots, allowing progressively shorter fragments to be aligned without inserting many fixed pilots.

B. The interleaved-pilot method of Shomorony and Vahid

The interleaved-pilot method embeds a De Bruijn sequence among shifted erasure-code symbols and globally aligns only sufficiently long fragments. Shorter fragments are discarded and treated as erasures, creating an effective-rate penalty.

  • B. The interleaved-pilot method of Shomorony and Vahid: Every length-log(n/m) substring of the De Bruijn sequence appears exactly once, enabling absolute fragment positioning when such a window is identified.
  • B. The interleaved-pilot method of Shomorony and Vahid: The construction interleaves a De Bruijn pilot sequence with codewords from a randomly shifted erasure code.The shift is formed by XORing erasure-code codewords with an independent Bernoulli(1/2) vector.
  • B. The interleaved-pilot method of Shomorony and Vahid: For k=(2+δ)log n, pilot windows are asymptotically unlikely to coincide with shifted erasure-code windows.
  • B. The interleaved-pilot method of Shomorony and Vahid: Fragments longer than approximately (2+δ)m log n can be globally aligned, after which the outer shifted-erasure code corrects missing positions.
  • B. The interleaved-pilot method of Shomorony and Vahid: The method discards shorter fragments because pilot windows long enough for statistical uniqueness exceed the length needed for unique De Bruijn identification.

C. The local-alignment method by Liu and Raviv

Liu and Raviv use local structure rather than long global comparisons to identify pilot positions in shorter fragments. The present work improves this approach by recycling recovered information as pilots across successive decoding levels.

  • C. The local-alignment method by Liu and Raviv: Run-length-limited encoding prevents shifted erasure-codewords from containing the exclusive all-zero marker used for local pilot identification.
  • C. The local-alignment method by Liu and Raviv: A fragment of length at least approximately (1+δ)m log n can be locally aligned by locating the marker in its de-interleaved subsequences.
  • C. The local-alignment method by Liu and Raviv: Local alignment lowers the fragment-length threshold from approximately (2+δ)m log n, allowing more previously discarded fragments to contribute to decoding.
  • C. The local-alignment method by Liu and Raviv: Pilot length still creates a tradeoff: more pilots align shorter fragments but leave fewer information positions, while fewer pilots discard more short fragments.
  • C. The local-alignment method by Liu and Raviv: Successive pilot recycling reuses recovered information as additional pilots, enabling progressively shorter-fragment alignment without adding more fixed pilots.

III. SUCCESSIVE LOCAL ALIGNMENT WITH PILOT RECYCLING

The construction partitions codeword positions into nested residue classes and uses successive decoding levels to recycle recovered information as pilot bits. This enables alignment of progressively shorter fragments while retaining a small fixed pilot sequence.

  • Pilot recycling: The decoder starts with a fixed pilot sequence, then recursively reuses recovered bits as additional pilot symbols.Fragments with multiple consistent global placements are discarded, and the normalized length of these ambiguous fragments vanishes.
  • Decoding levels: The level parameter t_i determines the alignment scale, with level i targeting fragments of length at least (1 + δ)t_i log n.The process begins at t_J = T and proceeds to lower alignment scales.
  • Residue-class construction: Nested residue classes assign fixed pilot positions and level-specific information codewords across the codeword.The pilot occupies R_J, while level i uses B_i = R_{i-1} \ R_i and corresponding positions A_i.
  • Pilot recycling: At each level, decoded information enlarges the known position set and becomes available for aligning shorter fragments.After decoding level i, known bits expand from S_i to S_{i-1} = A_i ˙∪ S_i.
  • Decoding levels: In the illustrative four-level assignment, the minimum alignable fragment length decreases from 3(1 + δ) log n to 1.5(1 + δ) log n.The successive thresholds are 3, 2.5, 2, and 1.5 times (1 + δ) log n.

IV. ENCODING

Encoding combines locally identifiable pilot markers with independently coded, shifted, RLL-constrained information levels placed across modular residue classes. The resulting codeword assigns pilot or information bits to every position.

  • Pilot construction: The fixed pilot contains deliberately inserted all-zero markers, while information codewords prohibit runs of β consecutive zeros.This separates pilot structure from information-bearing sequences during local alignment.
  • Level codewords: Each information level uses an independent random binary linear code followed by an RLL(0, β−1) encoder.Once fragments are aligned, uncovered level bits are treated as erasures and recovered by erasure decoding.
  • Level codewords: Public random shifts make encoded level bits uniformly random, allowing recovered bits to be reused for recursive alignment.The shift is bijective, and the RLL encoder is injective.
  • Residue-class placement: Each level codeword is self-interleaved across its assigned residue classes and placed repeatedly across length-Q blocks.The level-i codeword is divided into |B_i| blocks, with one block assigned to each residue in B_i.
  • Residue-class placement: The pilot occupies positions 0, T, 2T, ..., n − T, while the level assignments complete a disjoint partition of the codeword positions.Thus every codeword position receives exactly one pilot or information bit.

V. LEVELIZED DECODING

The levelized decoder converts the torn-paper output into recursive erasure-decoding problems, beginning with long fragments and incorporating shorter ones as known bits accumulate.

  • Initial decoding: At the initial level, sufficiently long fragments are locally aligned using the fixed pilot marker and then globally placed.The decoder identifies the pilot subsequence, extracts aligned information, and forms an incomplete level codeword.
  • Erasure recovery: Uncovered coordinates of each aligned level codeword are treated as erasures and corrected using that level’s erasure-correcting code.This transforms reconstruction after alignment into erasure decoding.
  • Pilot recycling: After level J is decoded, its positions become known and expand the known set from S_J to S_{J−1}.The expansion is S_{J−1} = A_J ˙∪ S_J.
  • Pilot recycling: At each subsequent level, all previously recovered bits are reused to test candidate global positions for shorter fragments.Fragments with multiple consistent placements are discarded, while remaining uncovered bits are again erasure-decoded.
  • Relation to prior work: The procedure follows local marker-based alignment from earlier work while adding recursive recycling of recovered bits.The earlier local method identifies pilot bits inside a fragment rather than relying exclusively on global statistics.

A. First level of decoding

The first decoding level identifies the pilot subsequence in sufficiently long fragments, extracts a De Bruijn subsequence, and uses its unique occurrence to determine each fragment’s global position.

  • Initial local alignment: The first level processes fragments with length at least (1 + δ)T log n, using only their prefixes to determine global location.Once a prefix is located, the entire fragment can be placed globally.
  • Initial local alignment: De-interleaving creates T candidate subsequences, and the unique subsequence containing the all-zero marker is selected as the pilot subsequence.Algorithm 1 groups fragment bits by index modulo T.
  • De Bruijn extraction: Algorithm 2 removes inserted markers and RLL-added boundary bits from the pilot subsequence to recover a subsequence of the original De Bruijn sequence.The recovered sequence is denoted q_f.
  • Global alignment: |q_f| ≥ log2 N_{q,n} for sufficiently large n, so q_f occurs uniquely in the De Bruijn sequence and reveals the fragment’s global position.The uniqueness follows from the defining property of a De Bruijn sequence.
  • Global alignment: Every fragment meeting the first-level threshold can therefore be uniquely aligned before the decoder transitions to shorter fragments and erasure decoding.This establishes the first step of the recursive procedure.

B. Level-wise inverse-RLL and erasure decoding

At each decoding level, the construction extracts the self-interleaved RLL codeword, reverses the RLL encoding, removes the shift, and uses a random linear code to recover erasures. Correctly recovered level bits then support the next alignment stage.

  • B. Level-wise inverse-RLL and erasure decoding: Algorithm 3 extracts residue-class subsequences, concatenates them in order, removes RLL padding, and reverses the shift to produce a partially observed level-i codeword.The procedure preserves unknown coordinates as erasures during extraction and inverse-RLL decoding.
  • B. Level-wise inverse-RLL and erasure decoding: The level-i random binary linear code recovers unknown coordinates in the partially observed codeword.Lemma 8 states that the algorithm outputs a partially observed version of u_i in C_i.
  • B. Level-wise inverse-RLL and erasure decoding: The decoder removes one RLL-inserted 1 after every β−1 bits, leaving the shifted codeword with its erasures preserved.These padding positions occur at indices β−1, 2β−1, and so on.
  • B. Level-wise inverse-RLL and erasure decoding: Successful erasure correction is required with high probability before recovered level bits can recursively assist alignment at shorter-fragment levels.The probabilistic verification of the erasure pattern is deferred to Section VI-B.

C. Alignment with recycled pilot bits

The decoder recursively recycles recovered codeword bits as pilot information, enabling local alignment of progressively shorter fragments. After all levels are decoded, the recovered level codewords reconstruct the original message.

  • C. Alignment with recycled pilot bits: Recovered bits from levels i+1 through J enlarge the known set from S_i+1 to S_i and serve as recycled pilot bits for level i.The fixed pilot bits remain known alongside the previously decoded codeword bits.
  • C. Alignment with recycled pilot bits: At level i, fragments of length at least (1 + δ)t_i log n are tested against known bits to identify a unique global starting position.A candidate is consistent when every fragment bit mapped to a known coordinate agrees with the corresponding codeword bit.
  • C. Alignment with recycled pilot bits: After uniquely aligned fragments are placed, level-i extraction and decoding reveal the bits on A_i, expanding the known set for the next level.The procedure repeats at level i−1 with a shorter threshold determined by t_i−1.
  • C. Alignment with recycled pilot bits: At the final level, every fragment of length at least (1 + δ)t_1 log n with a unique position is processed, and all level codewords are combined into the original message.The final known set covers every codeword coordinate.

VI. RATE CALCULATION AND DECODING RELIABILITY

The analysis section proves reliability properties for pilot recycling, establishes random-code requirements, and calculates the resulting construction rate.

  • VI. RATE CALCULATION AND DECODING RELIABILITY: Section VI analyzes pilot recycling, the required properties of random binary linear codes, and the resulting rate.These topics are organized in Sections VI-A, VI-B, and VI-C.
  • VI. RATE CALCULATION AND DECODING RELIABILITY: The reliability analysis covers the pilot-recycling technique and the erasure-correction properties needed by the level codes.The supplied passage identifies these as the principal proof components of the section.
  • VI. RATE CALCULATION AND DECODING RELIABILITY: The section computes the rate of the proposed code construction after establishing the needed decoding conditions.The passage explicitly states that the resulting rate is calculated in Section VI-C.

A. Pilot recycling ambiguity

Pilot recycling makes successive alignment possible by combining fixed De Bruijn bits with previously decoded level-codeword bits. The analysis shows that ambiguous fragments contribute negligible total length and that their ambiguity probability vanishes for each level.

  • A. Pilot recycling ambiguity: The ambiguity test compares candidate placements against the known set S_i, while the true placement is always consistent because the channel introduces no bit errors.A fragment is ambiguous when at least one false placement also passes the consistency test.
  • A. Pilot recycling ambiguity: Every level-i fragment of length at least (1 + δ)t_i log n contains known bits from both the fixed De Bruijn sequence and previously decoded level codewords.Lemma 9 lower-bounds these contributions by (1 + δ/2)(t_i/T) log n and (1 + δ/2)(1−t_i/T) log n, respectively.
  • A. Pilot recycling ambiguity: The ambiguity proof proceeds inductively from level J down to level 1, beginning with the fixed De Bruijn pilot at the base level.At level J, sufficiently long fragments contain at least (1 + δ/2) log n original De Bruijn bits after removing marker and RLL bits.
  • A. Pilot recycling ambiguity: For every fixed level i, the probability that a fragment has at least two i-consistent placements is at most n^-ρ_i+o(1) for some ρ_i > 0.This bound controls the probability of discarding a fragment because of ambiguous placement.
  • A. Pilot recycling ambiguity: The normalized total length of fragments declared ambiguous converges to zero in probability, so ambiguous fragments cause only a negligible number of additional erasures.The recursion’s discarded ambiguous length is therefore o(n).

B. Induced erasure patterns and random linear decoding

The decoder models retained fragments as structured erasure patterns rather than independent BEC erasures, then uses random binary linear codes to recover missing level bits. Good erasure patterns and independent parity-check matrices yield vanishing decoding error with high probability.

  • Random linear decoding: At each level, erased bits are recoverable exactly when the corresponding parity-check submatrix has full column rank.Decoding reduces to solving a linear system over F2 for the erased coordinates.
  • Erasure structure: The torn-paper channel induces bursts of consecutive erasures, so memoryless BEC concentration tools cannot be applied directly.The analysis instead treats erasures through the channel cuts and the multilevel alignment procedure.
  • Reliability bound: For every fixed level, the random-code failure contribution tends to zero exponentially because the level block length grows linearly with n.The good-pattern failure bound is at most exponentially small in the level block length.
  • Failure decomposition: Level-i failure occurs either because the erasure pattern is not good or because the parity-check columns for a good pattern are linearly dependent.The proof separates these two cases and bounds them separately.
  • Overall reliability: A randomly chosen collection of parity-check matrices and public shifts achieves vanishing total decoding error with probability tending to one.This follows by combining the good-erasure-pattern analysis with random linear-code decoding bounds and Markov’s inequality.

C. Rate calculation

The construction’s rate is obtained from the information carried by the multilevel codewords, while the fixed pilot contributes no message bits. By successively reducing threshold, finite-level, spacing, and coding-margin losses, the rate approaches and achieves the torn-paper capacity.

  • Rate calculation: The fixed pilot carries no message bits; all information is contained in the level codewords occupying the disjoint information sets A_i.Independent choices of level codewords produce distinct length-n codewords.
  • Rate calculation: The resulting rate is computed from the dimensions of the level codes and their allocation across the information levels.The construction partitions codeword positions into the pilot set and level-specific sets A_1,...,A_J.
  • Rate losses: The rate bound accounts for the fragment-length threshold, finite T, spacing between levels, and the 3η random-code margin.These are identified as the four losses relative to e−α.
  • Capacity approach: For every ε > 0, the authors choose construction parameters so the rate is within ε of e−α while maintaining positive level-code rates.The choices proceed through δ, T, m, and η, followed by the reliability result.
  • Capacity result: The proposed construction achieves the torn-paper-channel capacity e−α.The capacity conclusion combines the rate theorem with vanishing decoding error for a deterministic code sequence.

APPENDIX A OMITTED PROOFS

The appendix supplies proofs for run-length-limited coding, local pilot identification, coverage, and the counting bounds used to control ambiguous alignments. These results support successive recovery of progressively shorter fragments.

  • RLL coding: RLL(0, k−1) encoding appends one 1 to each block of k−1 information bits, giving rate (k−1)/k and bounding zero runs by k−1.Decoding splits the encoded word into length-k blocks and removes the final bit of each block.
  • RLL coding: RLL(0, k−2) encoding surrounds each block of k−2 information bits with 1s, giving rate (k−2)/k and bounding zero runs by k−2.The decoder removes the first and last bit of each length-k block.
  • Local pilot identification: For every sufficiently long fragment, Algorithm 1 uniquely identifies the de-interleaved subsequence containing the pilot and returns the corresponding modulo-T subsequences.The pilot subsequence contains the marker, while information-only subsequences cannot contain the required zero pattern.
  • Coverage: The coverage V_γ measures the fraction of output bits lying in fragments of length at least γ log n.Its long-fragment behavior is used in the rate and discarded-fragment analysis.
  • Ambiguous alignment: The number of candidate De Bruijn subsequences for a level-i fragment is bounded by T b_n (1 + δ)t_i log n = n^o(1).The count considers T residue classes, b_n possible offsets within a pilot block, and possible starting locations.
Loading 2609.00522v1…