Improved lower bounds on binary deletion channel capacity using learned run-length codes
Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
Information Theory
Summary
When digital messages lose some bits randomly during transmission, it’s hard to know exactly how much information can still get through. The authors worked on a channel model where bits are independently deleted and improved the best known lower estimates of its capacity. They used computer learning to optimize how message runs of zeros and ones are encoded, leading to better guarantees on data rates than previous methods. Their approach tries many different run-length patterns and finds those that make the channel most efficient, providing more accurate bounds at all tested deletion rates.
What this means in practice
- •For network engineers: Design error-correcting codes that better tolerate random bit deletions using optimized run-length patterns from learned distributions.
- •For data compression developers: Create compression algorithms that more accurately estimate throughput loss over deletion-prone channels by employing improved lower bound techniques.
Authors
Hassan Khodaiemehr, Chen Feng, Tolga M. Duman
Abstract
The capacity $C(d)$ of the i.i.d. binary deletion channel exists by Dobrushin's information-stability theorem, but no closed form is known. Classical constructive lower bounds from i.i.d. run-length coding have been evaluated only for one- or two-parameter families (geometric, Markov, or Morse-type). We show that the same infinite-blocklength functionals become strictly stronger when the run-length law $P$ is treated as a free distribution and optimized by learning. We reduce the Drinea--Mitzenmacher functional to a bilinear form in $P$ and prove that finite-support truncation is one-sided, so computed values remain valid lower bounds. We extend the Venkataramanan et al. reductions from geometric runs to arbitrary finite-support laws, including a residual-run HMM for output-bit entropy. Softmax gradient ascent searches $P$; every reported number is a fresh one-sided evaluation of the formula, with no Monte Carlo and no finite length-entropy penalty. The envelope of the two optimized bounds exceeds Gallager's $1-h(d)$ (for $d<1/2$) and the tabulated bounds of Drinea--Mitzenmacher, Venkataramanan et al., and Rubinstein--Con at every tested $d$. Representative values: $C(d)\ge 0.92212$, $0.72939$, $0.56486$, $0.35127$, $0.22616$, $0.10414$, $0.02891$, $0.01322$ at $d=0.01$, $0.05$, $0.10$, $0.20$, $0.30$, $0.50$, $0.80$, $0.90$. The largest absolute gain over that record is $3.7\times 10^{-3}$ bits (at $d=0.30$); the largest relative gain is $6.8\%$ (at $d=0.90$). For $d\le 0.45$ the envelope is the free-$P$ Venkataramanan functional; from $d=0.50$ it is the learned Drinea--Mitzenmacher law. At large $d$ the optimizer finds sparse run-length combs that parametric families cannot represent. A concurrent enclosure of Papailiopoulos is stronger on much of $[0,1]$, but our envelope remains larger at high $d$ (e.g. $0.02891$ vs $0.02884$ at $d=0.80$; $0.01322$ vs $0.01293$ at $d=0.90$).