🔢 mathematics

Deletion-Correcting Codes for the $\ell$ -Symbol Read Channel

This paper investigates adversarial deletion-correcting codes for the $\ell$ -symbol read channel by characterizing the structural impact of $\ell$ -mer deletions and constructing efficient codes with logarithmic redundancy for various parameter regimes, including specific improvements for sporadic cases.

Original authors: Zuo Ye, Gennian Ge

Published 2026-06-26

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Zuo Ye, Gennian Ge

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. However, instead of sending the whole strip at once, you send it through a special machine that reads the message in overlapping chunks.

The Setup: The "Overlapping Window" Machine

Think of your message as a string of beads: A-B-C-D-E-F.
Normally, a reader might look at one bead at a time. But this paper is about a machine that looks at two beads at a time (or $\ell$ beads, depending on the setting).

It reads: AB, then BC, then CD, then DE, then EF.
The machine sends you a list of these pairs: (AB, BC, CD, DE, EF).

This is called the $\ell$ -symbol read channel. It's used in real-world tech like DNA storage (where the machine reads a small group of DNA letters together) or racetrack memory (where a read head scans a group of bits).

The Problem: The "Missing Chunk" Glitch

Now, imagine the transmission gets messy. Some of these overlapping chunks get lost or deleted.

You might receive: (AB, BC, [MISSING], DE, EF).
The computer receiving this sees a gap. It knows BC ends with C, and DE starts with D. But C and D don't match up in the overlapping way they should! The sequence is broken.

The goal of this paper is to design a special code (a way of writing the message) that allows the receiver to figure out exactly what was lost and reconstruct the original message, even if a few chunks go missing.

The Big Discovery: The "Periodic Pattern" Trick

The authors discovered a clever mathematical trick to solve this.

When chunks are deleted, the machine tries to "patch" the gap by inserting the minimum number of missing pieces to make the list look consistent again.

The Insight: They found that when you do this patching, the errors don't look like random holes. Instead, they look like someone snipping out perfectly repeating patterns from the original message.
The Analogy: Imagine your message is a wallpaper with a repeating pattern: Red-Blue-Red-Blue-Red-Blue. If a chunk of the wallpaper is torn out, and you try to tape the edges back together, you'll notice the pattern is broken. But if you know the pattern is Red-Blue, you can easily guess that the missing piece was just another Red-Blue.

The paper calls these repeating sections "Check Patterns." The authors proved that if you lose a few chunks, you are essentially just deleting whole "cycles" of these repeating patterns.

The Solution: The "Mathematical Fingerprint"

To fix the message, the authors built a system that adds a little bit of extra "redundancy" (like a checksum or a receipt) to the message before sending it.

Counting the Patterns: The code counts how many of these "Check Patterns" exist in the message and where they are.
The Power Sum: They use a mathematical tool called "power-sum syndromes." Think of this as taking a photo of the message and calculating a specific number based on the positions of the patterns.
The Fix: When the message arrives with missing chunks:
- The receiver calculates the "fingerprint" of what they received.
- They compare it to the "fingerprint" that was sent.
- The difference tells them exactly which repeating pattern was cut and how many times it was cut.
- Once they know that, they can simply "un-cut" the pattern and restore the original message.

What They Achieved

The paper provides recipes (constructions) for these codes for different scenarios:

Single Deletion: If just one chunk is lost, they have a very efficient code that adds very little extra data (about $\log n$ bits).
Multiple Deletions: If several chunks are lost, they have codes that still work efficiently, provided the "window size" ( $\ell$ ) is large enough compared to the number of lost chunks ( $t$ ).
Special Cases: They also solved some tricky, specific scenarios (like when the window is small and many chunks are lost) that other methods couldn't handle well, improving the efficiency of the storage.

Why It Matters (According to the Paper)

The paper explicitly links this math to:

Nanopore Sequencing: Reading DNA strands where the machine senses groups of letters, not just one.
Racetrack Memory: A type of computer memory where data is read by multiple heads, and sometimes the "track" shifts too far, skipping a read.
DNA Labeling: Identifying parts of a DNA strand using specific labels.

In short, this paper gives us a new, smarter way to write data so that even if a "camera" taking overlapping snapshots of the data drops a few photos, we can still perfectly reconstruct the original scene.

Technical Summary: Deletion-Correcting Codes for the $\ell$ -Symbol Read Channel

1. Problem Statement

This paper investigates the construction of error-correcting codes for the $\ell$ -symbol read channel, a model motivated by overlapping-read mechanisms in sequencing and storage systems. In this channel, a transmitted sequence $x = x_1 \dots x_n$ is observed not as individual symbols, but as a vector of all consecutive $\ell$ -mers (substrings of length $\ell$ ). Formally, the noiseless output is the vector $R_\ell(x) = (x_{[1,\ell]}, x_{[2,\ell+1]}, \dots, x_{[n-\ell+1, n]})$ .

The study focuses on an adversarial deletion model where a fixed number $t$ of $\ell$ -mers are deleted from this read vector. The objective is to design codes capable of uniquely recovering the original sequence $x$ from the corrupted subvector. The paper treats $\ell$ and $t$ as constants and aims to minimize the redundancy (the number of extra bits required) of such codes, specifically targeting asymptotic redundancy of $t \log n + O(1)$ .

2. Methodology and Structural Characterization

The core methodological contribution is a structural characterization of how deletions in the read vector translate to deletions in the underlying transmitted sequence.

Structural Analysis

The authors assume the transmitted sequence is prefixed and suffixed with known $\ell$ -mers ( $u$ and $v$ ), denoted as $\tilde{x} = uxv$ . When $t$ $\ell$ -mers are deleted from $R_\ell(\tilde{x})$ , the receiver obtains an inconsistent vector $R'$ .

Consistency Restoration: The decoder inserts the minimum number $s$ of $\ell$ -mers into $R'$ to restore consistency, yielding a vector $R''$ .
Sequence Reconstruction: From $R''$ , a sequence $y$ is reconstructed ( $y = R_\ell^{-1}(R'')$ ).
Key Insight: The paper proves that $y$ $y$ is obtained from $\tilde{x}$ $\tilde{x}$ by deleting symbols from specific periodic substrings.
- If $s < t \le \ell - 2$ , the deletions in $\tilde{x}$ correspond to the removal of complete minimum periods from maximal periodic substrings.
- This implies that the "damage" caused by $\ell$ -mer deletions is localized to these periodic structures and does not arbitrarily scramble the sequence.

Check Patterns

Based on this insight, the authors introduce the concept of $(\ell, t, s)$ -check patterns. These are maximal periodic substrings of $\tilde{x}$ with a minimum period $T \le t-s$ and length at least $\ell - 1 - s$ .

Stability Property: The paper demonstrates that under suitable conditions (specifically $t \le \ell/2$ or specific boundary cases), the number, order, and minimum periods of these check patterns remain invariant (or change in a predictable, reversible way) even after the deletions.
Decoding Reduction: This stability reduces the complex problem of recovering $x$ to a simpler problem: identifying which check patterns suffered deletions and how many complete periods were removed from each.

3. Key Contributions and Results

The paper constructs several families of codes with varying parameters for $\ell$ (read length) and $t$ (number of deletions).

A. General Constructions

Using power-sum syndromes (based on the Varshamov-Tenengolts approach generalized via Lemma III.3), the authors construct codes for general parameter ranges:

Single Deletion ( $t=1$ ): For every $\ell \ge 2$ , they construct codes with redundancy $\log \lfloor (n + 2\ell)/(\ell-1) \rfloor$ .
Multiple Deletions ( $2 \le t \le \ell/2$ ): For $q$ -ary alphabets, they construct $t$ -deletion correcting codes with redundancy $t \log n + O(1)$ . This matches the lower bound order of magnitude.
Boundary Case ( $\ell = 2t - 1, t \ge 3$ ): They construct codes with redundancy $(2t - 1) \log n + O(1)$ .

B. Sporadic Constructions

The authors address specific small parameter pairs where the general conditions ( $\ell \ge 2t$ ) do not hold, deriving improved constructions that challenge the necessity of the general constraints:

$(\ell, t) = (2, 2)$ :
- Binary: Redundancy $2 \log n + O(1)$ (improving upon the previous $4 \log n + o(\log n)$ ).
- Non-binary ( $q > 2$ ): Redundancy $4 \log n + O(1)$ .
$(\ell, t) = (3, 2)$ :
- Binary: Redundancy $2 \log n + O(1)$ .
- Non-binary: Redundancy $3 \log n + O(1)$ .
$(\ell, t) = (3, 3)$ :
- Binary: Redundancy $5 \log n + O(1)$ .
- Non-binary: Redundancy $7 \log n + O(1)$ .

These sporadic results demonstrate that the condition $\ell \ge 2t$ is not strictly necessary to achieve $t \log n + O(1)$ redundancy, nor is the condition $\ell = 2t - 1$ necessary for $(2t-1) \log n + O(1)$ .

C. Explicit Constructions

While the main theorems provide existence proofs based on syndrome values, Section V provides a method to convert these into explicit codes with efficient encoders. This is achieved by appending specific check patterns and repeating them, incurring a slight additional overhead of $O(\log \log n)$ redundancy.

4. Significance and Claims

The paper claims that its primary contribution is the structural characterization linking $\ell$ -mer deletions to periodic substring deletions. This framework unifies the treatment of various parameter settings.

Motivation: The work is motivated by practical applications in nanopore sequencing (where signals depend on $\ell$ -mers), DNA labeling, and racetrack memory (where multiple read heads observe overlapping symbols).
Comparison: The authors compare their results with recent work by Xie and Chen. While Xie and Chen achieved $t \log n + O(\log \log n)$ redundancy under stricter conditions ( $t \le \min\{(\ell-1)/2, (\ell+2)/3\}$ ), this paper achieves $t \log n + O(1)$ under the milder condition $t \le \ell/2$ .
Limitations and Open Problems: The authors acknowledge that their structural arguments rely on the stability of check patterns, which holds when $t \le \ell/2$ . They note that determining the optimal redundancy for pairs where $t > \ell/2$ remains an open question, as the check-pattern stability arguments do not directly apply. They also suggest future work on joint correction of deletions, insertions, and substitutions, and the development of more efficient encoding/decoding algorithms.

In summary, the paper provides a theoretical framework for deletion correction in overlapping read channels, offering a suite of codes with optimal or near-optimal redundancy for a wide range of parameters, while explicitly identifying the structural properties that enable efficient decoding.