Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes
Abstract
DNA storage systems retrieve information by randomly sampling synthesized DNA strands, making the number of reads required for successful recovery a fundamental performance measure. This motivates the coverage depth problem: for given code parameters, determine a linear code that minimizes the expected number of randomly sampled columns required to span the entire information space. While MDS codes are known to be optimal whenever they exist, identifying optimal codes in parameter regimes where MDS codes do not exist remains largely open. In this work, we derive a general formula for the expectation in the coverage depth setting, and apply this result to establish the optimality of the q-ary simplex code for the parameters that allow its existence. Moreover, we show the optimality of the q-ary Hamming code by relating coverage depth to independent sets in the dual code and exploiting log-concavity properties of matroid basis-generating polynomials. We further analyze random linear codes, derive an exact expression for their expected coverage depth, and show that, in the constant-rate regime, their additive gap from the MDS benchmark remains bounded independently of the code length.
Related
- Optimal Average Success Probabilities of Binary (n,n−1) and (n,n−2) Quantum Random Access Codes
- Entropy-Regularized Optimal Transport for Time-Varying Multi-Agent Coverage Control
- Last-Coverage Probabilities of Random Walks on Cycle Graphs for Symmetric, Biased, and Time-Dependent Walks
- The Coverage Depth Problem in Distributed DNA Data Storage
- Optimal Quantum ( r , δ )-Locally Repairable Codes From Matrix-Product Codes
BibTeX
@misc{gross2026optimal,
title = {{Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes}},
author = {Roee Gross and Yitzchak Grunbaum and Matteo Bertuzzo and Eitan Yaakobi and Alberto Ravagnani},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07370},
eprint = {2610.07370},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07370},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes
AU - Roee Gross
AU - Yitzchak Grunbaum
AU - Matteo Bertuzzo
AU - Eitan Yaakobi
AU - Alberto Ravagnani
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.07370
UR - https://arxiv.org/abs/2610.07370
AB - DNA storage systems retrieve information by randomly sampling synthesized DNA strands, making the number of reads required for successful recovery a fundamental performance measure. This motivates the coverage depth problem: for given code parameters, determine a linear code that minimizes the expected number of randomly sampled columns required to span the entire information space. While MDS codes are known to be optimal whenever they exist, identifying optimal codes in parameter regimes where MDS codes do not exist remains largely open. In this work, we derive a general formula for the expectation in the coverage depth setting, and apply this result to establish the optimality of the q-ary simplex code for the parameters that allow its existence. Moreover, we show the optimality of the q-ary Hamming code by relating coverage depth to independent sets in the dual code and exploiting log-concavity properties of matroid basis-generating polynomials. We further analyze random linear codes, derive an exact expression for their expected coverage depth, and show that, in the constant-rate regime, their additive gap from the MDS benchmark remains bounded independently of the code length.
ER -