💻 computer science

New Capacity Upper Bounds For Binary Deletion Channel

This paper derives two new closed-form upper bounds on the capacity of the binary deletion channel by utilizing a first-order Markov input process, one based on an auxiliary two-bit fixed-length channel and the other on a direct mutual information approximation parameterized by a Markov correlation coefficient.

Original authors: Hassan Tavakoli

Published 2026-07-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hassan Tavakoli

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 to a friend across a noisy, chaotic room. In the world of digital communication, this is usually like playing a game of "telephone" where words get garbled or flipped upside down. But there is a trickier version of this game called the Binary Deletion Channel. Here, the noise doesn't just flip your bits (changing a 0 to a 1); it simply swallows them whole. You send a long string of 0s and 1s, but some vanish into thin air before they reach your friend. The receiver gets a shorter, scrambled version of your message and has to guess what was lost.

This isn't just a party game; it's a massive puzzle for scientists. While we have perfect formulas for how much information we can send through channels that flip bits or erase them (like a "Binary Erasure Channel" where the receiver knows exactly where the holes are), the "Deletion Channel" is a notorious mystery. We don't know the exact limit of how much data we can squeeze through it. We only have a fence of "upper bounds" (the absolute maximum possible) and "lower bounds" (what we know we can definitely do). Finding the true limit is like trying to find the exact speed limit of a car that keeps changing its engine while you're driving it.

This paper steps into that messy room to build a better fence. The authors, Hassan Tavakoli and colleagues, aren't solving the whole mystery yet, but they have constructed two new, sharper "upper bounds." Think of these as tighter ceilings on how high the data can fly. They did this by creating two clever, simplified versions of the problem—like testing a new car engine in a wind tunnel before putting it on the highway.

First, they looked at a simplified scenario where the sender only sends tiny, two-bit chunks of data (like "00", "01", "10", or "11") and calculated the absolute best performance possible for that tiny chunk. They proved that if you can't do better than this in the tiny world, you certainly can't do better in the big, complex world. By doing the math on this "two-bit" model, they derived a neat, closed-form formula (a single equation you can solve without a computer) that acts as a strict ceiling for the channel's capacity. They double-checked their work from scratch, proving that their math is solid and that there is only one perfect way to arrange the bits to hit this ceiling.

Second, they took a different approach by looking at the relationship between the bits that survive and the bits that were deleted. They assumed the bits follow a pattern where the next bit depends slightly on the one before it (like a chain reaction). Using this pattern, they created a second formula. Interestingly, they found that this second formula doesn't have a "sweet spot" to maximize; instead, it gets tighter the more predictable the bits are. They showed that as the deletion rate gets higher, the best strategy is to make the bits more repetitive and correlated, essentially "hugging" each other so they are less likely to get lost.

The paper doesn't claim to have found the exact answer to the Deletion Channel mystery. Instead, it offers two new, mathematically proven limits that are tighter than some older estimates. It confirms that as the channel gets noisier (more deletions), the smartest way to send data is to make the bits more dependent on one another, trading some randomness for a better chance of survival. It's a step forward in understanding the limits of communication in a world where things can simply disappear.

Technical Summary: New Capacity Upper Bounds for the Binary Deletion Channel

Problem Definition
The paper addresses the Binary Deletion Channel (BDC), a communication model where input bits are independently deleted with probability $d$ , and the receiver observes the remaining subsequence without knowledge of the deletion positions. While the channel capacity $C(d)$ is well-defined, no closed-form expression exists. Current literature relies on upper and lower bounds, with notable existing bounds including $1-h(d)$ for $d < 0.5$ and $0.4143(1-d)$ for $d \ge 0.65$ . The primary challenge in computing exact capacity is the combinatorial ambiguity in mapping input sequences to output subsequences.

Methodology
The authors propose two new closed-form upper bounds on $C(d)$ , both utilizing a first-order Markov process for the channel input. The methodology relies on two core intuitions: (1) auxiliary channels that approximate the BDC can yield useful bounds, and (2) input correlation aids the decoder in estimating deleted bits.

Auxiliary Channel Approach (Theorem 1):
The authors introduce the Fixed-length Input BDC (FI-BDC), where the input length is fixed at $n$ , but the output length varies. They focus specifically on a two-bit FI-BDC (FI-BDC with $n=2$ ).
- They construct the transition matrix for this two-bit channel (Table II).
- They derive the mutual information $I(X; Y)$ for this auxiliary channel under a symmetric first-order Markov input distribution parameterized by $\gamma$ (or equivalently, $p_0$ , the probability of repeated symbols).
- The optimization problem is solved to find the unique closed-form maximizer $p_0^*(d)$ .
- The final bound is derived by leveraging the super-additivity of mutual information across independent two-bit sub-blocks, scaling the two-bit capacity by $1/2$ .
Direct Mutual Information Approximation (Theorem 2):
The second bound is derived by directly approximating the mutual information between sent and received bits.
- This approach utilizes an auxiliary side-information variable to mark the position of the last undeleted predecessor.
- The resulting expression is parameterized by the Markov correlation parameter $\gamma$ .
- Unlike Theorem 1, this bound is not the result of maximizing over $\gamma$ ; rather, $\gamma$ is treated as a design parameter or a source-determined value.

Key Contributions and Results

Theorem 1 (Closed-Form Bound 1):
The paper derives a closed-form upper bound:
$C \le \frac{1}{2}(1 - d)^2 \log_2 \left(1 + 2^{-\frac{2d}{1-d}}\right) + \frac{1 - d^2}{2}$
- Optimization Verification: The authors rigorously verify that the objective function for the two-bit auxiliary channel is strictly concave with a unique interior maximizer. They confirm the closed-form solution for the optimal input distribution $p_0^*(d)$ using computer-algebra systems and numerical checks.
- Monotonicity: The optimal correlation parameter $\gamma^*(d)$ is shown to be strictly increasing with $d$ , moving from $0.5$ (independent bits) as $d \to 0$ to $1$ (perfect correlation) as $d \to 1$ . This reflects the intuition that higher deletion probabilities necessitate stronger temporal correlation in the input to aid decoding.
- Complexity: Evaluating this bound requires $O(1)$ arithmetic operations, contrasting with previous bounds (e.g., Fertonani–Duman) that require iterative optimization over exponentially large state spaces.
Theorem 2 (Closed-Form Bound 2):
The paper presents a second bound:
$C_{BDC} \le (1 - d) \left(1 - H\left(\frac{d(1 - \gamma)}{1 + d(1 - 2\gamma)}\right)\right)$
- Nature of $\gamma$ : The authors clarify that this bound is monotonic in $\gamma$ with no interior maximum. Therefore, $\gamma$ is not an optimized variable but a parameter determined by the source or chosen for design purposes.
- Endpoint Behavior: The bound correctly reduces to $C \le 1$ when $d=0$ (with $\gamma=0.5$ ) and $C=0$ when $d=1$ (with $\gamma=1$ ). The paper proposes a linear interpolation $\gamma = 0.5 + d/2$ to bridge these endpoints, noting this is a design choice rather than an analytical optimum.
Comparison with Prior Work:
The paper notes that the bound from Theorem 1 is at least as tight as the bound derived from the Fixed-length Input Fixed-length Output (FIFO-BDC) auxiliary channel (Lemma 1). The second bound is evaluated against Fertonani–Duman and Dalai bounds in Figure 4 of the original text (though the figure is not reproduced here).

Significance and Claims
The paper claims significance primarily in providing two new closed-form upper bounds that are computationally efficient ( $O(1)$ ) and analytically verified.

Theoretical Rigor: The authors emphasize the rigorous verification of Theorem 1's optimization, correcting a minor algebraic error found in an intermediate draft and confirming the strict concavity of the objective function.
Clarification of Parameters: A key contribution is the clarification regarding the parameter $\gamma$ in Theorem 2. The authors explicitly state that $\gamma$ should not be viewed as an approximated optimizer but as a source-determined parameter, correcting a potential misinterpretation of the formula's behavior.
Scope Limitations: The paper modestly defines its scope. It does not claim to solve the general BDC capacity problem, nor does it claim to find the optimal input memory for all admissible processes (e.g., higher-order Markov or run-length coded sources). The results are strictly limited to the specific first-order symmetric Markov family used in the derivations.
Exclusions: The authors explicitly note that they have intentionally excluded certain "unifying" claims, asymptotic forms not derived in the text, and broader convergence theorems to maintain analytical precision.

In summary, the paper advances the state of the art by offering computationally tractable, closed-form upper bounds for the BDC, grounded in auxiliary channel analysis and direct mutual information approximation, with a strong emphasis on the mathematical verification of the optimization steps involved.

Technical Summary: New Capacity Upper Bounds for the Binary Deletion Channel

More like this