Coding Schemes for the Noisy Torn Paper Channel * These authors contributed equally. Funded by the European Union (DiDAX, 101115134). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Execu

Frederik Walter * , Maria Abu-Sini * , Nils Weinhardt , Antonia Wachter-Zeh · 2026

Read Coding Schemes for the Noisy Torn Paper Channel * These authors contributed equally. Funded by the European Union (DiDAX, 101115134). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Execu by Frederik Walter * , Maria Abu-Sini * , Nils Weinhardt , Antonia Wachter-Zeh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11501.txt.

Introduction

Frederik Walter, Maria Abu-Sini, Nils Weinhardt, and Antonia Wachter-Zeh code data for torn DNA. Their 2026 preprint treats DNA decay as a torn paper channel. DNA can store data for the long term in archives. Strands decay over time, and codes must survive that decay.

The channel model has two stages of damage in sequence. First, noise flips bits by substitution at random. Then the strand breaks into unordered, noisy substrings. Coders get a bag of torn scraps, like a ripped page. Schemes must rebuild the message from those scraps alone. The team designs coding schemes for that double damage. Sound codes are a must for DNA archives to work.

Catalog record

CREATORFrederik Walter * , Maria Abu-Sini * , Nils Weinhardt , Antonia Wachter-Zeh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-11501

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Coding Schemes for the Noisy Torn Paper Channel * These authors contributed equally. Funded by the European Union (DiDAX, 101115134). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Frederik Walter * , Maria Abu-Sini * , Nils Weinhardt , Antonia Wachter-Zeh Abstract To make DNA a suitable medium for archival data storage, it is essential to consider the decay process of the strands observed in DNA storage systems. This paper studies the decay process as a probabilistic noisy torn paper channel (TPC), which first corrupts the bits of the transmitted sequence in a probabilistic manner by substitutions, then breaks the sequence into a set of noisy unordered substrings. The present work devises coding schemes for the noisy TPC by embedding markers in the transmitted sequence. We investigate the use of static markers and markers connected to the data in the form of hash functions. These two tools have also been recently exploited to tackle the noiseless TPC. Simulations show that static markers excel at higher substitution probabilities, while data-dependent markers are superior at lower noise levels. Both approaches achieve reconstruction rates exceeding 99 % 99\% with no false decodings observed, primarily limited by computational resources. I Introduction DNA strands used for data storage tend to decay over time, causing strands to break into short fragments [ 8 ] . Moreover, DNA synthesis and sequencing processes are error-prone, introducing insertions, deletions, and substitutions. Consequently, enabling long-term storage in such systems necessitates algorithms capable of recovering data from a set of disordered, noisy substrings. The probabilistic binary noisy torn paper channel (TPC) models this decay and noise accumulation. This channel takes a binary sequence, corrupts its bits uniformly at random with a substitution probability p_{s} , and subsequently breaks the noisy sequence at any position with probability p_{b}=\frac{\alpha}{\log_{2}n} , where n denotes the length of the transmitted sequence. The capacity of this channel has been investigated in [ 22 ] . This paper devises coding schemes for the noisy TPC that enable the reconstruction of the transmitted sequence from the received set of unordered noisy fragments. These schemes provide valuable insights and potential solutions for addressing the decay challenges inherent in DNA storage systems. This paper presents two coding schemes for the noisy TPC. As a first step, we focus on the case of breakage and substitutions solely, and hence leave the investigation of insertions and deletions for future work. The two devised schemes build upon existing work [ 11 , 27 ] . A standard approach to reconstructing a sequence from unordered fragments involves interleaving a codeword of an erasure code with a marker followed by an index. The marker facilitates index detection, which subsequently identifies the fragment’s location. This technique is inspired by the interleaving pilot scheme proposed in [ 27 ] . However, a significant drawback of this scheme, as illustrated in Fig. 3 , is that the interleaved indices are independent of the data. Breakages occurring between indices yield fragments devoid of position information, leading to ambiguity in their placement. This results in multiple fragment permutations that appear equally valid. To mitigate this ambiguity, [ 11 , 18 ] proposed interleaving the codeword with sequence-dependent information rather than fixed markers. Specifically, [ 11 ] suggested interleaving the sequence with hash values derived from data blocks. Thus, the literature primarily employs two tools: (1) interleaving with markers and indices, and (2) interleaving with data-dependent hash values. I-A Our Contribution In this work, we propose two coding schemes that leverage these tools to address the noisy TPC. The first scheme, detailed in Section II , relies primarily on explicit indexing. It interleaves the sequence with markers (specifically 001 ), followed by bits from a de Bruijn sequence acting as indices, and parity bits derived from the preceding data block. These parity bits serve to link the data with the structural redundancy. The second scheme (Section III ) adopts a hash-based approach without explicit indices. It interleaves the sequence with hash values designed to be robust against substitutions. While the hash functions, as used in [ 11 ] , are effective for the noiseless TPC, they are unsuitable here; a single substitution can drastically alter the hash value (the avalanche effect), making it impossible to verify the adjacency of two fragments. To overcome this, we employ locality-sensitive hashing (LSH). LSH ensures that small changes in the data, such as those caused by substitutions, result in minimal changes to the hash value, thereby facilitating the correct identification of consecutive fragments even in the presence of noise. To correct the substitutions after reconstructing the sequence, both schemes utilize an outer low-density parity-check (LDPC) code. The overall processing pipeline can be seen in Fig. 1 . Fig. 1 : Concatenated coding scheme for the noisy TPC. Fig. 2 : The structure of the coding scheme presented in Section II is illustrated in the upper word. Markers, followed by indices and parity bits are interleaved into an LDPC codeword. The colors and the values inside the word and the fragments are referred to in Section II . Moreover, affixing the fragments {\boldsymbol{f}}_{1} and {\boldsymbol{f}}_{2} at indices 4 and 15 , respectively, constitutes assembly \mathbf{a} , which is a partial assembly. Affixing fragments {\boldsymbol{f}}_{3} and {\boldsymbol{f}}_{4} in the gaps results in the complete assembly \mathbf{b} . Finally, Section IV presents simulations evaluating these schemes. We compare the robustness of static markers against data-dependent hashing to maintain reconstruction integrity and identify the optimal operating regimes for each approach. I-B Further Related Work Beyond the discussed approaches, we highlight that [ 18 ] and [ 19 ] introduced a coding scheme for the noiseless TPC utilizing Varshamov-Tenengolts (VT) codes as hash functions. Furthermore, Ravi et al. studied in [ 20 ] and [ 22 ] the capacity of the torn paper channel when fragments might be lost with certain probability that depends on their lengths. In parallel, adversarial settings of the TPC have been extensively studied [ 1 , 3 , 28 , 29 , 30 , 31 , 32 , 33 , 12 , 13 ] . These works typically impose constraints such as minimum fragment lengths or upper bounds on the number of breakages and errors. Finally, related models including shotgun sequencing and chop-and-shuffle channels have received significant attention in the recent literature [ 24 , 2 , 6 , 4 , 14 , 15 , 7 , 25 , 26 , 9 , 21 , 16 , 17 ] . I-C Notations Throughout this paper, we use 1 -based indexing. For a sequence \mathbf{x} , the notation \mathbf{x}_{[i,j]} represents the substring starting at index i and ending at index j and |\mathbf{x}| denotes the length. We denote by \text{x}_{j}^{i} i repetitions of the j -th bit of sequence \mathbf{x} . The operator \mathbf{x}_{1}||\mathbf{x}_{2} denotes the concatenation of sequences \mathbf{x}_{1},\mathbf{x}_{2} . Finally, an assembly refers to the method of affixing fragments, at specific positions, as illustrated in Fig. 2 . We denote an assembly by small bold letters, and we call an

Read the complete text