🔢 mathematics

Channels with Input-Correlated Synchronization Errors

This paper establishes conditions under which the information capacity of channels with input-correlated synchronization errors is achieved by stationary ergodic sources and demonstrates how these results enable the construction of explicit capacity-achieving codes for multi-trace channels with runlength-dependent deletions, a model relevant to DNA-based data storage.

Original authors: Roni Con, João Ribeiro

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Roni Con, João Ribeiro

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message written on a long strip of paper to a friend. In a perfect world, your friend receives the strip exactly as you wrote it. But in the real world, things go wrong. Sometimes, the paper gets torn (deletions), sometimes extra pieces of paper get stuck in the middle (insertions), or the paper stretches and shrinks. This is what information theorists call "synchronization errors."

For a long time, scientists assumed these errors happened randomly and independently, like raindrops hitting a roof. However, the authors of this paper, Roni Con and João Ribeiro, point out that real-world systems—specifically DNA data storage—don't work that way. In DNA storage, the "paper" is a strand of DNA. They found that errors don't happen randomly; they depend on the pattern of the message itself. For example, if you have a long run of the same letter (like "AAAAA"), it's much more likely to get deleted than a mixed-up string.

Here is a breakdown of their work using simple analogies:

1. The Problem: The "Pattern-Dependent" Storm

Imagine you are walking through a forest where the ground is muddy.

The Old View: Scientists used to think the mud was distributed randomly. You might slip on any step, regardless of where you are.
The New Reality: The authors show that the mud is actually correlated with your path. If you walk on a long, straight path of smooth stones (a long run of the same DNA letter), the mud is deep and you are likely to slip (delete). If you walk on a rocky, uneven path (mixed letters), you stay dry.

The paper studies "channels" (the path) where the chance of a mistake depends on the entire message you are sending, not just the specific letter you are currently sending.

2. The Big Discovery: Finding the "Speed Limit"

In information theory, every channel has a "capacity"—a maximum speed limit for how much data you can send reliably.

The Challenge: When errors depend on the message pattern, calculating this speed limit is incredibly hard. It's like trying to calculate the speed limit of a road where the traffic jams depend on the color of the cars driving on it.
The Breakthrough: The authors prove that for a wide class of these "pattern-dependent" channels, the speed limit does exist and can be calculated. They show that you can reach this limit using a specific type of "smart" message generator (called a stationary ergodic source) that keeps the message patterns balanced.
The Result: They prove that the theoretical speed limit is the same as the practical speed limit you can achieve with real codes. This is a huge deal because it tells engineers, "Yes, there is a way to send data at this maximum speed, even with these tricky errors."

3. The Solution: Building the "Smart Mail"

Knowing the speed limit is one thing; actually building a system to reach it is another. The authors provide a recipe for building efficient codes (the "mail trucks" that carry the data).

They use a clever construction technique involving buffers:

The Analogy: Imagine you are sending a series of important letters (data blocks) through a chaotic wind tunnel. To keep them from getting mixed up, you place a giant, distinct "STOP" sign (a long run of zeros) between every letter.
The Trick: Because the authors proved that their "smart" data blocks are never too boring (they always have a good mix of 0s and 1s), the wind tunnel is unlikely to accidentally create a fake "STOP" sign inside a letter.
The Process:
1. Outer Code: A high-level code that corrects mistakes.
2. Inner Code: The "smart" data blocks that fit the channel's rules.
3. Buffers: The giant "STOP" signs that help the receiver know where one letter ends and the next begins, even if the wind (errors) tries to scramble them.

They show that for single-trace channels (sending the message once), this system is very fast to decode. For multi-trace channels (sending the same message multiple times, like taking multiple photos of the same DNA strand to get a clearer picture), they use a slightly different, more complex method to align the photos, but it still works efficiently.

4. The "DNA" Connection

The paper is heavily motivated by DNA-based data storage.

In DNA storage, scientists write data using the four DNA letters (A, C, G, T).
They observed that long stretches of the same letter (e.g., "GGGGGG") get deleted more often during the reading process.
The authors' "runlength-dependent" model captures this perfectly. They even provide specific lower bounds (guaranteed minimum speeds) for channels that mimic these DNA errors, showing that we can store data much more efficiently than previously thought possible if we use their methods.

Summary

In short, this paper says:

Real-world errors are patterned, not random.
We can calculate the maximum speed for sending data through these patterned errors.
We can build practical, fast systems to reach that maximum speed by using "smart" data patterns and "giant stop signs" (buffers) to keep everything in sync.

This work bridges the gap between abstract math and the messy reality of storing data in DNA, offering a roadmap to make DNA storage faster and more reliable.

Technical Summary: Channels with Input-Correlated Synchronization Errors

Problem Statement

The paper addresses the fundamental challenge of characterizing the capacity and designing efficient codes for communication channels subject to synchronization errors (deletions, insertions, and replications). While prior work has extensively studied channels with independent and identically distributed (i.i.d.) errors, the authors argue that this assumption fails to capture the behavior of real-world systems, particularly DNA-based data storage. Empirical evidence suggests that synchronization error rates in DNA sequencing are correlated with the input sequence structure; for instance, runs of identical symbols or specific nucleotide concentrations (e.g., high G/C content) exhibit higher deletion rates.

The core problem is to establish capacity theorems and construct efficient, capacity-achieving codes for a general class of channels where the distribution of synchronization errors applied to the $i$ -th input symbol $x_i$ may depend on the entire input string $x$ , rather than just a local window or being i.i.d.

Methodology

1. Theoretical Framework: Admissible Channels

The authors introduce a class of channels termed "admissible channels." A channel $Z$ is admissible if there exists a "well-behaved" auxiliary channel $Z^*$ such that the mutual information $I(X; Z(X))$ equals $I(X; Z^*(X))$ for any input process $X$ .

A "well-behaved" channel $Z^*$ must satisfy four specific properties:

Bounded Output Entropy: The entropy of the output grows linearly with the input length.
Concatenation: The channel's behavior on a concatenated input can be reconstructed from its behavior on the parts, given the parts' outputs.
Partition: The channel's output on a long string can be approximated by the outputs on its blocks, with the "boundary" information (prefix/suffix effects) having entropy that is sublinear ( $o(n)$ ).
Amortized Preimage Size: The number of input strings mapping to a specific output sequence, given the block outputs, is bounded in a way that allows for information density convergence.

2. Capacity Theorems

Using these definitions, the paper proves that for any admissible channel:

The information capacity (supremum of mutual information rates over all input processes) equals the coding capacity (supremum of achievable rates).
The capacity is achieved by stationary ergodic input sources.
The capacity is also the limit of capacities achieved by $m$ -th order Markov processes as $m \to \infty$ .

These results generalize previous work by Dobrushin (i.i.d. errors) and Mao, Diggavi, and Kannan (bounded intersymbol interference).

3. Code Construction Strategy

To move from existence theorems to explicit, efficient codes, the authors combine their capacity results with techniques from Pernice, Li, and Wootters (PLW22) and Brakensiek, Li, and Spang (BLS20).

Dense Codes: The capacity theorems imply the existence of "dense" capacity-achieving codes (where short substrings have significant Hamming weight).
Single-Trace Construction: For single-trace channels, the authors use a concatenated coding scheme. An outer code corrects adversarial insertion/deletion (insdel) errors, while an inner code (derived from the capacity-achieving dense codes) handles the specific channel errors. Synchronization is maintained using "buffers" (long runs of zeros) between inner codewords.
Multi-Trace Construction: For multi-trace channels (relevant to DNA storage where multiple reads of the same data are available), the authors adapt the BLS20 approach. They utilize a dual-inner-code strategy: one code for data and a second for synchronization symbols. This allows the decoder to align traces before performing trace reconstruction on the data symbols.

Key Contributions and Results

1. General Capacity Theorems

The paper establishes that for a wide class of input-correlated synchronization channels, the information capacity is achievable by stationary ergodic sources and coincides with the coding capacity. This generalizes the Mao-Diggavi-Kannan (MDK18) model and applies to multi-trace settings.

2. Efficient Capacity-Achieving Codes

The authors provide explicit constructions for two specific scenarios:

Bounded Runlength-Dependent Deletion Channels: Channels where the deletion probability $d(\ell)$ $d (ℓ)$ for a run of length $\ell$ $ℓ$ is non-decreasing and becomes constant ( $d(M) < 1$ $d (M) < 1$ ) for $\ell \ge M$ $ℓ \geq M$ .
- Single-Trace: Codes are encodable in linear time and decodable in quasi-linear time.
- Multi-Trace: Codes are encodable in linear time and decodable in quadratic time.
- These codes achieve rates arbitrarily close to the channel capacity.

3. Capacity Lower Bounds

The paper derives new lower bounds on the capacity of threshold deletion channels (a specific type of runlength-dependent channel where bits in runs of length $\ge \tau$ are deleted with probability $d$ , while shorter runs are preserved).

First Bound: Based on the observation that typical random strings have a specific fraction of bits in long runs, improving upon standard i.i.d. deletion bounds.
Second Bound: Based on a greedy construction of codes with restricted run lengths, tailored to the channel's specific deletion mechanics.
These lower bounds are shown to be achievable by the efficient codes described above via Theorem 11.

Significance and Claims

The paper claims that its primary significance lies in bridging the gap between theoretical capacity results for correlated synchronization errors and practical, efficient coding schemes.

Generalization: It moves beyond the restrictive i.i.d. error assumption, providing a framework that captures realistic error patterns observed in DNA storage systems (e.g., runlength-dependent deletions).
Constructive Existence: Unlike many capacity theorems that only prove existence, this work demonstrates how to construct codes that achieve these capacities with polynomial-time encoding and decoding.
Multi-Trace Utility: The results are specifically tailored to the multi-trace setting, which is critical for DNA-based data storage where multiple sequencing reads (traces) of the same molecule are generated.
Modesty: The authors note that while their framework covers a broad class of channels, the specific efficient constructions presented focus on "bounded" runlength-dependent deletions. They acknowledge that the decoding complexity for the multi-trace case (quadratic time) is higher than the single-trace case (quasi-linear) due to the use of a simpler matching algorithm compared to more advanced indexing schemes.

The work does not propose new experimental setups but rather provides the theoretical and algorithmic tools necessary to design codes for existing technologies exhibiting these correlated error patterns.