Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels
Abstract
In DNA data storage, racetrack memories, and packet networks, data are written as many short strands of fixed length. The receiver knows where each strand begins and ends, and deletions occur only inside a strand. The relevant limit for such systems is the block capacity CN(d), the largest mutual information between a length-N input and the output of a binary deletion channel with deletion probability d. Because the boundaries are known, CN(d)/N is never smaller than the classical capacity C(d). Computing CN(d) is hard because the input takes 2N values. For 0≤ d<1, we show that the optimal input is unique, gives positive probability to every string, and is unchanged by complementing or reversing the strings. We then introduce the optimized run distribution (ORD), which assigns one probability to each number of runs; it is optimal for N≤3 and is solved with a numerical optimality certificate up to N=16. For longer strands, an exact recursion for the output distribution gives unbiased rate estimates, and an empirical Bernstein inequality turns them into confidence intervals. Within the statistical precision, a one-parameter Markov input performs as well as the best inputs found. For strands of 100-200 bits, known boundaries increase the rate by up to 0.026 bits per symbol beyond the best certified upper bound on the capacity of the unsegmented channel. Via Fano's inequality, the block capacity also bounds the rate of any code that uses a single strand; in the tabulated case, this bound is tighter than the best known finite-length bound for strands longer than about 90 bits. Conversely, block rates yield lower bounds on C(d); at d=0.1, the bound is within 1.1×10−4 bits/use of the best certified lower bound. Finally, InfoNCE estimates, even with the optimal critic, empirically lose most of their ability to rank inputs as the strand length grows.
Related
- Marker-Delimited Codes for Short-Blocklength, High-Rate Coding over Multi-Read Edit Channels
- Non-asymptotic Sphere-Packing Bounds for Finite-Blocklength Scalar Gaussian Multiple-Access and Broadcast Channels
- Maximal input entropy for binary two-deletion and two-insertion channels
- On Sequence Reconstruction Problem for q-ary Deletion Channels
- Selective boundary condition reduction via learned error gating
BibTeX
@misc{khodaiemehr2026orbit,
title = {{Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels}},
author = {Hassan Khodaiemehr and Chen Feng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24889},
eprint = {2609.24889},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24889},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels
AU - Hassan Khodaiemehr
AU - Chen Feng
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.24889
UR - https://arxiv.org/abs/2609.24889
AB - In DNA data storage, racetrack memories, and packet networks, data are written as many short strands of fixed length. The receiver knows where each strand begins and ends, and deletions occur only inside a strand. The relevant limit for such systems is the block capacity C_N(d), the largest mutual information between a length-N input and the output of a binary deletion channel with deletion probability d. Because the boundaries are known, C_N(d)/N is never smaller than the classical capacity C(d). Computing C_N(d) is hard because the input takes 2^N values. For 0≤ d<1, we show that the optimal input is unique, gives positive probability to every string, and is unchanged by complementing or reversing the strings. We then introduce the optimized run distribution (ORD), which assigns one probability to each number of runs; it is optimal for N≤3 and is solved with a numerical optimality certificate up to N=16. For longer strands, an exact recursion for the output distribution gives unbiased rate estimates, and an empirical Bernstein inequality turns them into confidence intervals. Within the statistical precision, a one-parameter Markov input performs as well as the best inputs found. For strands of 100-200 bits, known boundaries increase the rate by up to 0.026 bits per symbol beyond the best certified upper bound on the capacity of the unsegmented channel. Via Fano's inequality, the block capacity also bounds the rate of any code that uses a single strand; in the tabulated case, this bound is tighter than the best known finite-length bound for strands longer than about 90 bits. Conversely, block rates yield lower bounds on C(d); at d=0.1, the bound is within 1.1×10^−4 bits/use of the best certified lower bound. Finally, InfoNCE estimates, even with the optimal critic, empirically lose most of their ability to rank inputs as the strand length grows.
ER -