🔢 mathematics

Simple Finite-Length Achievability and Converse Bounds for the Deletion Channel and the Insertion Channel

This paper establishes tighter finite-length converse bounds on code size for deletion and insertion channels by deriving an efficient reference output distribution, while also providing a simple algorithm for computing achievability bounds to facilitate performance comparison.

Original authors: Ruslan Morozov, Tolga Mete Duman

Published 2026-04-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ruslan Morozov, Tolga Mete Duman

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 string of beads to a friend. But there's a problem: the messenger is a bit clumsy. Sometimes, they accidentally drop a bead (a deletion), and sometimes, they accidentally add an extra, random bead from their pocket (an insertion). By the time your friend receives the string, it might be shorter or longer than you sent, and the order of the remaining beads might be confusing.

This is the problem of Deletion and Insertion Channels. It's a huge deal in modern technology, especially for DNA data storage, where we try to store computer files inside strands of DNA. If the DNA gets "dropped" or "stuck" during reading, the file gets corrupted.

This paper by Ruslan Morozov and Tolga Duman is like a team of detectives trying to figure out the absolute limits of how much information you can reliably send through this clumsy messenger. They aren't just guessing; they are calculating the hard mathematical "speed limits" for these channels.

Here is a breakdown of their work using simple analogies:

1. The Two Sides of the Coin: "Can We Do It?" vs. "Can We Do Better?"

In the world of coding, there are two main questions:

The Achievability Bound (The "Can We Do It?" Test): This asks, "Is there any clever way to pack our beads so that even if the messenger drops a few, we can still read the message?" If the answer is yes, we have a "lower bound" on how good we can get.
The Converse Bound (The "Can We Do Better?" Test): This asks, "No matter how clever we are, is there a hard limit where it becomes impossible to send more information without errors?" This is an "upper bound." If you try to send more than this, you will fail.

The Paper's Goal: The authors wanted to find a much tighter (more accurate) "upper bound" for these messy channels. Before this, the best they had was a very loose estimate, like saying, "You can't drive faster than 1,000 mph," when the real limit is actually 150 mph. They wanted to find that 150 mph number.

2. The Old Way: The "BEC" Benchmark

Previously, to get an upper limit, researchers used a trick. They compared the messy "Deletion Channel" to a simpler, cleaner channel called the Binary Erasure Channel (BEC).

The Analogy: Imagine the BEC is a messenger who doesn't drop beads but instead puts a "MISSING" tag on the empty spots. It's easier to solve because you know where the holes are.
The Problem: Since the real Deletion Channel is worse than the BEC (because you don't know where the holes are), the limit calculated for the BEC is too high. It's like using the speed limit of a highway to set the speed limit for a muddy dirt road. It's a safe guess, but it's not very precise.

3. The New Idea: "Layering" the Problem

The authors developed a new method called the Layer-Oriented Converse Bound.

The Analogy: Imagine you are trying to guess a secret code. Instead of looking at the whole code at once, you organize the possibilities into "layers" based on how many beads were dropped.
- Layer 1: All messages where exactly 1 bead was dropped.
- Layer 2: All messages where exactly 2 beads were dropped.
- And so on.

The authors realized that within each specific "layer" (e.g., exactly 2 beads dropped), the math becomes much simpler and more predictable. They created a special "reference map" (a mathematical distribution) for each layer. By analyzing these layers individually and then combining them, they could draw a much tighter line around the maximum possible code size.

Think of it like this:

Old Method: Trying to guess the weight of a bag of mixed fruit by weighing the whole bag and guessing the average weight of a fruit.
New Method: Sorting the fruit into piles (apples, oranges, bananas), weighing each pile separately, and then adding them up. You get a much more accurate total weight.

4. The "Side Information" Trick

To make the math workable, the authors used a clever trick. They imagined giving the receiver a little bit of "cheat sheet" information (side information) about where the blocks of beads started and ended.

The Analogy: Imagine the messenger drops the beads, but also leaves a tiny note saying, "I dropped 3 beads here, then 5 beads there."
The Result: This makes the channel easier to analyze. The authors proved that even with this "cheat sheet," the limit they calculated is still a valid limit for the real channel (where the receiver gets no cheat sheet). Because the "cheat sheet" version is easier, the limit is easier to calculate, but it still holds true for the harder, real-world version.

5. The Results: Tighter, But Not Perfect

When they ran the numbers:

The Good News: Their new "Layer-Oriented" bound is much tighter than the old "BEC" bound. It tells us much more precisely how much data we can store in DNA before it becomes too risky.
The Bad News: There is still a gap between their "upper limit" (what is theoretically impossible) and the "lower limit" (what we can actually achieve with current algorithms).
- The Analogy: They found out the speed limit is 150 mph (not 1,000). But the fastest car they can build right now only goes 100 mph. They know the limit is 150, but they haven't figured out how to build a car that hits 145 yet.

6. Why Does This Matter?

This research is crucial for DNA Data Storage. As we try to store the world's data in tiny strands of DNA, we need to know exactly how much we can pack in before the "clumsy messenger" (the DNA sequencing process) causes too many errors.

If the limit is too loose, we might try to store too much data and fail.
If the limit is too tight, we might be too conservative and waste the amazing potential of DNA storage.

By providing a sharper, more accurate "speed limit," this paper helps engineers design better codes to store our digital memories in biology, ensuring that even if a few beads drop, the story remains intact.

Summary

The authors took a messy, hard-to-solve problem (sending data through a channel that deletes and inserts bits) and broke it down into neat, manageable "layers." By analyzing these layers with a new mathematical tool, they drew a much tighter boundary around what is possible, giving us a clearer picture of the future of DNA data storage.

1. Problem Statement

The paper addresses the fundamental problem of determining the maximum achievable code size ( $M$ ) for synchronization error channels (specifically Binary Deletion Channels - BDC, and Binary Insertion Channels - BIC) under finite block lengths.

Context: While asymptotic capacity results for deletion/insertion channels are well-studied, practical applications like DNA data storage often operate with finite block lengths (hundreds of nucleotides) rather than the asymptotic limit.
Challenge: Existing finite-length bounds for these channels are either loose (e.g., the Binary Erasure Channel bound) or computationally intractable. Standard achievability bounds (like the Dependency Testing bound) require knowledge of the mutual information density distribution, which is extremely difficult to compute for synchronization channels.
Goal: To derive tight, computable converse bounds (upper limits on code size) and a simple achievability bound (lower limit) for finite-length deletion and insertion channels.

2. Methodology

The authors employ a combination of hypothesis testing-based converse bounds and combinatorial optimization.

A. The Converse Bound Framework

The paper utilizes the Symbol-Wise Converse Bound (from Polyanskiy et al.), which bounds the code size based on the divergence between the channel's conditional output distribution and a reference output distribution ( $Q$ ).
$M(W, \varepsilon) \leq \inf_{Q} \sup_{x} D_{\varepsilon+\eta}(W(\cdot|x) \parallel Q) + \log_2 \frac{1}{\eta}$
The core difficulty lies in choosing an optimal reference distribution $Q$ that makes the bound tight and computable.

B. Max-Oriented and Layer-Oriented Bounds

To solve the $Q$ selection problem, the authors introduce two specific distributions:

Max-Oriented Distribution ( $\tilde{Q}_W$ ): A distribution proportional to the maximum probability of any output $y$ given any input $x$ (i.e., $Q(y) \propto \max_x W(y|x)$ ). This yields a simple bound but is often loose.
Layer-Oriented Distribution (LO-CVB): The authors generalize the max-oriented approach by partitioning the output alphabet into "layers" (subsets of outputs that have a constant total probability for any input).
- For the Deletion Channel, layers are defined by the output length ( $w$ ). Since the output length distribution is independent of the input sequence, the set of all strings of length $w$ forms a layer.
- For Insertion Channels, layers are similarly defined by output length.
- The bound is computed by optimizing over subsets of these layers ( $\Lambda$ ). This effectively provides the receiver with "side information" regarding which layer (output length) the received signal belongs to, simplifying the channel to a memoryless one with side information.

C. Combinatorial Computation (Embedding Numbers)

The tightness of the bound depends on calculating embedding numbers:

$d$ -embedding number: The number of ways a specific output string $y$ can be formed by deleting bits from an input string $x$ .
$i$ -embedding number: The number of ways $y$ can be formed by inserting bits into $x$ .
$g$ -embedding number: For Gallager's insertion channel.
The authors define $E_d(m, w)$ as the sum of the maximum embedding numbers over all possible output strings of length $w$ . They provide algorithms to compute these values for small to moderate block lengths ( $m$ ), which are the primary computational bottleneck.

D. Achievability Bound (Greedy Algorithm)

For comparison, the authors propose a Greedy Achievability Bound (GAVB). This algorithm constructs a code iteratively:

Start with an empty code.
Add the codeword that maximizes the increase in the probability of correct decoding (minimizing the error probability) given the current code.
Repeat until the desired code size is reached.
While this has exponential complexity, it provides a tight lower bound for small block lengths to benchmark the converse bounds.

3. Key Contributions

Layer-Oriented Converse Bound (LO-CVB): A novel, computable upper bound for finite-length deletion and insertion channels. It is derived by splitting the output space into layers (based on output length) and optimizing the reference distribution over these layers.
Tighter than BEC Bound: The LO-CVB is proven to be strictly tighter (lower) than the standard Binary Erasure Channel (BEC) converse bound for finite lengths, which is currently the only alternative for these channels.
Combinatorial Tables: The paper provides extensive pre-computed tables of embedding numbers ( $E_d, E_i, E_g$ ) for block lengths up to $m=32$ (deletion) and $m=25$ (insertion), enabling the direct calculation of the bounds without re-running complex combinatorial searches.
Greedy Achievability Algorithm: A practical algorithm to compute tight lower bounds for small block lengths, facilitating the analysis of the gap between achievability and converse bounds.
Analysis of Side Information: The paper clarifies that the LO-CVB is valid for the original channel because the channel with side information (layer boundaries) is a degraded version of the original channel.

4. Results

Comparison with BEC: For deletion channels with probabilities $\delta \in \{0.05, 0.2, 0.5, 0.8\}$ , the LO-CVB consistently outperforms the BEC bound. The gap widens as the block length increases, whereas the BEC bound tends to converge to the erasure capacity ( $1-\delta$ ).
Gap to Optimality:
- For very small block lengths ( $m=5$ ), the LO-CVB is close to the performance of optimal codes found via brute force.
- For larger lengths ( $m=17$ ), a significant gap remains between the LO-CVB and the Greedy Achievability Bound (GAVB). The authors attribute this to the "looseness" introduced by the side information (layer boundaries) required to make the bound computable.
Insertion Channels: Similar improvements over the BEC bound were observed for both standard and Gallager's insertion channels.
Normal Approximation: The LO-CVB generally provides a tighter bound than the normal approximation (which is an asymptotic result) for the finite lengths considered, although the normal approximation sometimes yields lower rates for very low error probabilities.

5. Significance

Practical Relevance: The results are directly applicable to emerging technologies like DNA data storage, where block lengths are finite (hundreds of bits) and synchronization errors (deletions/insertions) are dominant.
Theoretical Advancement: It moves beyond asymptotic capacity limits to provide rigorous finite-length performance guarantees, a critical step for designing practical coding schemes.
Benchmarking: By providing both a tight lower bound (GAVB) and a tighter upper bound (LO-CVB) than previously available, the paper establishes a new benchmark for evaluating coding schemes for synchronization channels.
Future Directions: The paper highlights that the remaining gap between the converse and achievability bounds suggests room for improvement, potentially through better upper bounds on embedding numbers or reduced side information strategies.

In summary, this paper bridges the gap between theoretical information limits and practical finite-length coding for synchronization channels by introducing a computationally feasible, layer-based converse bound that significantly improves upon existing benchmarks.