🔢 mathematics

Capacity-Achieving Codes for Noisy Insertion Channels

This paper investigates a noisy insertion channel relevant to DNA storage, where it determines the coding capacity and constructs asymptotically optimal error-correcting codes capable of handling multiple identical or complementary insertions alongside a single random insertion.

Original authors: Hengfeng Liu, Chunming Tang, Cuiling Fan

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hengfeng Liu, Chunming Tang, Cuiling Fan

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 in a special language (DNA) across a very chaotic, noisy river.

The Setting: The DNA River

In the world of DNA data storage, we want to store huge amounts of information inside tiny strands of DNA. It's like writing a library on a grain of sand. But, just like a message written on a piece of paper floating down a river, the message can get messed up by the current.

In this specific river, the "current" causes three main types of chaos:

The "Mirror" Glitch (Complement Insertion): Sometimes, the river adds a letter that is the "mirror image" of the one before it. If you have an 'A', the river might add a 'T' (its partner) right next to it.
The "Echo" Glitch (Tandem Duplication): Sometimes, the river gets stuck and repeats a letter. If you have a 'C', it might suddenly become 'CC'.
The "Random Splash" (Random Insertion): Occasionally, a random rock (a random letter) splashes into the stream, adding a completely unexpected letter that doesn't fit the pattern.

The big problem? The river can add infinite "Mirror" and "Echo" glitches, but it only adds one "Random Splash." If you try to read the message at the end, it looks like a jumbled mess of extra letters. How do you figure out what the original message was?

The Solution: The "Signature" Filter

The authors of this paper, Liu, Tang, and Fan, came up with a brilliant way to clean up this mess. They realized that even though the river adds extra letters, the core identity of the message remains hidden underneath.

Think of the message as a string of beads.

If you add a "Mirror" bead or an "Echo" bead, it's like adding a duplicate or a matching pair to the string.
If you "collapse" the string—smushing all the identical or matching beads together—you get back to the original pattern.

They call this collapsed pattern the "Signature."

The Analogy: Imagine your message is a song.

The "Mirror" and "Echo" errors are like someone playing the same note twice or playing a harmony note right after it.
If you listen to the song and ignore the repeats and harmonies, you can still hear the original melody (the Signature).
The "Random Splash" is the only thing that actually changes the melody itself, but since it only happens once, it's a small, fixable mistake.

The Magic Trick: The Code

The researchers built a special "envelope" (a code) for the message before sending it. This envelope has two superpowers:

The Signature Shield: They designed the code so that the "Signature" of the message is unique. Even if the river adds a million extra beads, if you squish them all together, you get a unique fingerprint that tells you exactly what the original message was.
The "One-Splash" Detector: Since they know only one random splash can happen, they added a mathematical "checksum" (like a secret math puzzle) to the message. If the river adds a random letter, the math puzzle breaks in a very specific way. The receiver can look at the broken math, figure out exactly where the random splash happened, and remove it.

The Result: Perfect Recovery

The paper proves two amazing things:

Capacity: They calculated exactly how much information can be sent through this noisy river without losing data. They found that even with all this chaos, you can send almost as much data as you could in a perfect, quiet river. The "noise" doesn't actually slow you down much in the long run.
Speed: They created a recipe (an algorithm) to decode the message. The best part? It's incredibly fast. It takes the same amount of time to decode a message the size of a tweet as it does to decode a message the size of a novel, relative to the length of the received (messy) sequence. It's like having a super-fast scanner that instantly ignores the noise and reads the text.

Why This Matters

This isn't just about math puzzles. This is the key to making DNA storage a reality.

Current Problem: DNA is great for storage, but it's fragile. When we try to read it back, errors happen.
The Breakthrough: This paper gives us the blueprint to build DNA storage systems that are robust enough to handle the messy reality of biology. It tells us we can store data reliably even when the biological "river" is chaotic, and we can do it efficiently.

In a nutshell: The authors figured out how to write a message that survives a chaotic river of duplicates and random splashes. They proved you can send a lot of data through this chaos, and they built a super-fast tool to read it back perfectly.

1. Problem Statement

The paper addresses the challenge of designing error-correcting codes (ECCs) for DNA-based data storage, specifically focusing on noisy insertion channels.

Context: DNA storage is prone to specific error types during synthesis, sequencing, and biological preservation. While traditional insertion/deletion (indel) errors are well-studied, DNA storage introduces unique error mechanisms:
- Complement Insertion: Insertion of a symbol that is the chemical complement of the original (e.g., A $\leftrightarrow$ T, C $\leftrightarrow$ G).
- 1-Tandem Duplication: Insertion of an identical symbol immediately following the original.
- Random Insertion: Due to biological noise, inserted symbols may mutate into random symbols from the alphabet.
The Gap: Previous work (e.g., Yohananov and Schwartz) addressed exact complement insertions but assumed a noise-free environment. Real-world DNA storage involves "noisy" insertions where complement insertions or duplications are accompanied by random substitutions or random insertions.
Objective: The authors aim to:
1. Formalize a Noisy Insertion Channel model allowing arbitrary numbers of complement insertions and 1-tandem duplications, plus at most one random insertion.
2. Determine the coding capacity (asymptotic rate) of this channel.
3. Construct codes that achieve this capacity with linear-time decoding.

2. Methodology

The authors employ a combination of signature-based coding, constrained coding, and algebraic coding theory.

A. Channel Modeling and Definitions

Alphabet: $\mathbb{Z}_q$ (where $q \ge 4$ is even), with a complement operation defined as $\bar{u} = q - 1 - u$ .
Descendant Cones:
- $D^*_{ct}(x)$ : Set of sequences obtained via arbitrary complement insertions and 1-tandem duplications.
- $D^*_{ct}^{(\le 1)}(x)$ : The "Noisy Descendant Cone," including the above plus at most one random insertion.
Signature ( $\sigma(x)$ ): A key concept where a sequence is reduced by collapsing consecutive identical or complementary symbols. For example, in $\mathbb{Z}_4$ $Z_{4}$ with $\bar{0}=3, \bar{1}=2$ $\overset{ˉ}{0} = 3, \overset{ˉ}{1} = 2$ , the sequence $0312130$ reduces to signature $013$.
- Key Property: Complement insertions and 1-tandem duplications do not alter the signature of a sequence. Only random insertions change the signature.

B. Code Construction Strategy

The construction relies on restricting codewords to the set of irreducible sequences ($Irr(n)$), where no two adjacent symbols are complements or identical. This ensures the signature of the codeword is the codeword itself ( $\sigma(x) = x$ ).

The authors construct the final code by intersecting three specific sub-codes to handle different error types in the signature:

Handling Random Substitutions (Point Substitution):
- Uses a modified Varshamov-Tenengolts (VT)-like code ( $C(a,b)(n)$ ).
- Constraints: Sum of symbols $\equiv a \pmod{2q}$ and weighted sum $\equiv b \pmod{qn}$ .
- Function: Corrects a single point substitution in the signature caused by a random insertion of a complementary symbol.
Handling Point Insertions:
- Uses a modified VT code ( $C_T(c,d)(n)$ ) with a modulus of $2q$ instead of $q$ .
- Function: Corrects a single point insertion in the signature.
Handling Burst Insertions (Length 2):
- Random insertions can sometimes cause a "burst" of length 2 in the signature.
- The authors map the codeword into a $2 \times (n/2)$ array.
- Row 1: Encoded with a Run-Length Limited (RLL) constraint to limit the maximum run length, ensuring the deletion location is bounded.
- Row 2: Encoded with a Shifted VT (SVT) code ($SVT(e,f,g)$) which is a $P$ -bounded single-deletion-correcting code.
- Function: Corrects a burst insertion of length 2 in the signature.

Final Construction: The code $C_F$ is the intersection of the irreducible set, the RLL-constrained set, and the three algebraic constraints above.

C. Decoding Algorithm

The decoding process is designed to be linear time $O(N)$ , where $N$ is the length of the received sequence:

Signature Recovery: Collapse the received sequence $y$ to its signature $r = \sigma(y)$ . This compresses the potentially long sequence $y$ (due to arbitrary insertions) into a short sequence $r$ of length $\approx n$ .
Error Classification: Based on the length of $r$ $r$ :
- $|r| = n+1$ : Indicates a point insertion. Use the VT decoder.
- $|r| = n+2$ : Indicates a burst insertion. Use the SVT decoder on the $2 \times \dots$ array.
- $|r| = n$ : Indicates a substitution. Use syndrome calculation to identify and correct the error.
Recovery: The unique recovery of the signature uniquely determines the original codeword.

3. Key Results

A. Coding Capacity

The paper establishes the exact coding capacity for the noisy insertion channel:
$\text{cap}^{\text{noisy}}_q = \log_q(q - 2)$

Significance: This result is identical to the capacity of the exact complement insertion channel (without random noise).
Implication: Correcting the additional random insertion error (and 1-tandem duplications) incurs zero asymptotic rate penalty. The capacity is not reduced by the presence of the "noise" component compared to the noise-free complement channel.

B. Code Size and Optimality

The constructed codes are asymptotically optimal.
The lower bound on the code size $|C_F|$ is approximately:
$|C_F| \ge \frac{q(q-2)^{n-1}}{4 n^3 (3 \log_q n + 4) q^3}$
The redundancy is $O(\log_q n)$ , meaning the rate approaches $\log_q(q-2)$ as $n \to \infty$ .

C. Complexity

The decoding algorithm runs in strictly linear time $O(N)$ with respect to the received sequence length. This is crucial for practical DNA storage applications where read lengths can be large.

4. Significance and Contributions

Realistic Channel Modeling: The paper moves beyond idealized models by incorporating biochemical noise (random insertions) into the complement insertion channel, making the results more applicable to real-world DNA storage systems.
Capacity Characterization: It proves a counter-intuitive result: adding a random insertion error to a channel already suffering from arbitrary complement insertions does not lower the theoretical information transmission rate.
Practical Construction: Unlike many capacity-achieving proofs that are non-constructive, this paper provides an explicit code construction and a linear-time decoding algorithm.
Generalization: The work generalizes previous results on exact complement insertion channels and tandem duplication channels, unifying them under a noisy framework.

5. Future Directions

The authors propose two open problems:

Extending the model to allow $p$ random insertions (conjecturing the capacity remains $\log_q(q-2)$ ).
Handling tandem duplications of length $>1$ (specifically length up to 3) alongside complement insertions and random noise.

In summary, this paper provides a rigorous theoretical foundation and a practical engineering solution for reliable data storage in DNA systems subject to complex, noisy insertion errors.