Capacity improvements for finite length binary deletion channels
Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels
Information Theory
Summary
Data sent over channels that randomly delete bits can lose information, making it hard to communicate reliably. This paper looks at how to best send fixed-length bit sequences through such channels to maximize the information received. The authors develop a method to simplify the problem by grouping similar input patterns and propose an optimized model called the optimized run distribution (ORD) that performs well for short sequences. They use a combination of exact calculations and machine learning to find the best input patterns for sequences up to length 512, showing improvement over previous approaches.
What this means in practice
- •For network engineers: Optimize coding strategies for communication systems that suffer from bit deletions by using improved input sequence designs.
- •For data transmission system designers: Enhance error-resilience in fixed-length data packets by applying optimized run-length input patterns for channels with random deletions.
Authors
Hassan Khodaiemehr, Chen Feng
Abstract
For a binary deletion channel operating on fixed-length inputs, the relevant figure of merit is the finite-blocklength capacity $C_N(d)=\max_{p(x^N)}\mathrm{I}(X^N;Y)$, not only the infinite-blocklength limit $C(d)$. We show that an optimal input may be chosen constant on complement and permutation-equivalence orbits, reducing the optimization to one weight per orbit, and introduce the optimized run distribution (ORD), an $N$-parameter run-count model that coincides with $C_N(d)$ for $N\le 3$ and is optimal among all run-count-constant inputs. An exact embedding-count dynamic program evaluates $\mathrm{I}$ for these structured laws. A hybrid neural--exact procedure recovers certified ORD weights for $N\le 8$; variational critics (InfoNCE, NWJ, DV/MINE, SMILE) are used only as inner search objectives. Direct score-function learning of ORD weights collapses toward a flat run-length distribution (RLD) for $N\ge 32$. We therefore introduce ORD continuum transfer: a normalized run-count profile learned from exact small-$N$ ORD solutions is resampled at target lengths up to $N=512$. Transferred ORD consistently outperforms RLD at moderate deletion probabilities; at $d=0.1$ the gain vanishes by roughly $N=128$--$192$. Exact ORD rates converted by Fertonani--Duman's length-entropy inequality are valid lower bounds on $C(d)$; nested-Monte-Carlo evaluations of large-$N$ inputs are reported as diagnostics and are not claimed as capacity lower bounds. A fixed-$N=100$ sample-budget study quantifies nested-MC bias. All primary reported rates are values of $\mathrm{I}(X^N;Y)/N$.